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.
2018
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)).
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/728105
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact