2018/03/02 by Peter Hegarty, Hegarty, Peter, Anders Martinsson +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #05C20 #05C90 #60C05 #91F99 #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Game Theory and Voting Systems #Optimization and Search Problems #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1803.00823
openalex publication_date 2018/03/02 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
In 2000 Allen Schwenk, using a well-known mathematical model of matchplay\ntournaments in which the probability of one player beating another in a single\nmatch is fixed for each pair of players, showed that the classical\nsingle-elimination, seeded format can be "unfair" in the sense that situations\ncan arise where an indisputibly better (and thus higher seeded) player may have\na smaller probability of winning the tournament than a worse one. This in turn\nimplies that, if the players are able to influence their seeding in some\npreliminary competition, situations can arise where it is in a player's\ninterest to behave "dishonestly", by deliberately trying to lose a match. This\nmotivated us to ask whether it is possible for a tournament to be both honest,\nmeaning that it is impossible for a situation to arise where a rational player\nthrows a match, and "symmetric" - meaning basically that the rules treat\neveryone the same - yet unfair, in the sense that an objectively better player\nhas a smaller probability of winning than a worse one. After rigorously\ndefining our terms, our main result is that such tournaments exist and we\nconstruct explicit examples for any number n >= 3 of players. For n=3, we show\n(Theorem 3.6) that the collection of win-probability vectors for such\ntournaments form a 5-vertex convex polygon in R3, minus some boundary points.\nWe conjecture a similar result for any n >= 4 and prove some partial results\ntowards it.\n