• PDF / 2,104,306 Bytes
• 34 Pages / 439.37 x 666.142 pts Page_size
• 42 Downloads / 199 Views

DOWNLOAD

REPORT

---

(2021) 35:5

Irrelevant matches in round‑robin tournaments Marco Faella1 · Luigi Sauro1  Accepted: 5 October 2020 © The Author(s) 2020

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 five 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 each match. Finally, we prove by computational means that there exist tournaments where all matches are relevant to both players, at least up to eight players. Keywords  Tournaments scheduling · Preferences over rankings

1 Introduction Tournaments consist of pairwise matches aimed at establishing a ranking among a set of participants. Sport competitions are often organized in tournaments that attract significant popular interest and financial resources. Depending on the type of tournament and on the ranking rule, there may be matches that are known to have no effect on the ultimate ranking of the two contestants, regardless of their outcome. Clearly, such irrelevant matches are undesirable, as they lack the incentive to win that is the very essence of any contest. For instance, the last round of the preliminary stage of the UEFA Champions League 2014 (Group H) consisted in the matches Porto vs Shakhtar Donetsk and Athletic Bilbao vs BATE Borisov. The scoreboard before the round was: Porto was on top of the group with 13 points, Shakhtar Donetsk was second with 8 points, whereas Athletic Bilbao and BATE Borisov had 3 points each. Since in football tournaments winning a match yields 3 points, Shakhtar Donetsk had no chance of overtaking Porto and, conversely, neither Athletic * Luigi Sauro [email protected] Marco Faella [email protected] 1



Department of Electrical Engineering and Information Technologies, University of Naples Federico II, Naples, Italy

13

Vol.:(0123456789)

5 

Page 2 of 34

Autonomous Agents and Multi-Agent Systems

(2021) 35:5

Bilbao nor BATE Borisov could have overtaken Shakhtar Donetsk. Consequently, any possible outcome of the match Porto vs Shakhtar Donetsk would not have changed the final ranking of both the involved teams. Incidentally, the match ended in an unexciting 1–1 tie. More recently, in Group F of the UEFA Champions League 2018, Manchester City was challenging Shakhtar Donetsk in the last round. The scoreboard before the match was: Manchester City on top with 15 points, Shakhtar Donetsk in second position with 9 points, Napoli 6 points, and finally Feyenoord with 0 points. With respect to the previous example, this case presents an asymmetric situation wh