We consider tournaments played by a set of players in order to establish a ranking among them. We introduce the notion of irrelevant match, as a match that does not influence the ultimate ranking of the involved parties. After discussing the basic properties of this notion, we seek out tournaments that have no irrelevant matches, focusing on the class of tournaments where each player challenges each other exactly once. We prove that tournaments with a static schedule and at least 5 players always include irrelevant matches. Conversely, dynamic schedules for an arbitrary number of players can be devised that avoid irrelevant matches, at least for one of the players involved in any given match. Finally, we prove by computational means that there exist tournaments where all matches are relevant to both players, at least up to 8 players.
Do All Tournaments Admit Irrelevant Matches? / Faella, Marco; Sauro, Luigi. - (2018), pp. 982-989. (Intervento presentato al convegno 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)).
Do All Tournaments Admit Irrelevant Matches?
marco faella
;luigi sauro
2018
Abstract
We consider tournaments played by a set of players in order to establish a ranking among them. We introduce the notion of irrelevant match, as a match that does not influence the ultimate ranking of the involved parties. After discussing the basic properties of this notion, we seek out tournaments that have no irrelevant matches, focusing on the class of tournaments where each player challenges each other exactly once. We prove that tournaments with a static schedule and at least 5 players always include irrelevant matches. Conversely, dynamic schedules for an arbitrary number of players can be devised that avoid irrelevant matches, at least for one of the players involved in any given match. Finally, we prove by computational means that there exist tournaments where all matches are relevant to both players, at least up to 8 players.File | Dimensione | Formato | |
---|---|---|---|
tournaments.pdf
solo utenti autorizzati
Descrizione: Articolo principale
Tipologia:
Documento in Pre-print
Licenza:
Accesso privato/ristretto
Dimensione
588.61 kB
Formato
Adobe PDF
|
588.61 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.