- Non-manipulable tournament rules
- Project Year:
2022
- REU Student (s):
David Miksanik | Charles University (Prague, Czech Republic)
| Jan Soukup | Charles University (Prague, Czech Republic)
- Student 1 Institution:
Charles University (Prague, Czech Republic)
- Student 2 Institution:
Charles University (Prague, Czech Republic)
- Project Mentor:
Ariel Schvartzman
- Project Mentor Area:
DIMACS
- Project Abstract:
We consider a manipulability of tournament rules on $n$ teams, where the rules select (possibly randomly) a single winner based on the result of all $\binom{n}{2}$ matches. A tournament rule is said to be $k$-SNM-$\alpha$, if no $k$ teams can increase their joint probability of winning by fixing the $\binom{k}{2}$ matches between them; hence, $k$-SNM-$\alpha$ is a measure of manipulability of a tournament rule. Previous works show that among all Condorcet-consistent (i.e., undefeated teams always win with probability 1) monotonous (i.e., no team can increase its probability to win by throwing matches) rules the best we can hope for are $k$-SNM-$\frac{k-1}{2k-1}$ rules and show several examples of rules achieving this bound for $k=2$. In the case of $k=3$, there exists only one rule achieving non-trivial non-manipulability, specifically $3$-SNM-$\frac{31}{60}$. Our main result is an existence of a new rule that is Condorcet-consistent, monotonous, $2$-SNM-$\frac{1}{3}$, and $3$-SNM-$\frac{1}{2}$. Additionally, the analysis of this rule is tight and uses a new technique with the possibility of finding similar rules achieving even stronger non-manipulability. Our second result shows that rules for tournaments on $n$ teams satisfying a stronger version of Condorcet-consistency can be extended to rules for any number of teams with only slightly worse manipulability. Finally, for every $d \geq 3$, we generalize a~random single binary elimination bracket rule to a~random single $d$-ary elimination bracket (RS$d$EB) rule (the complete binary tree is replaced by the complete $d$-ary tree). We show that, for every $k \geq 3$, the rule RS$k$EB is Condorcet-consistent, monotone, and $k$-SNM-$\alpha$ for $\alpha < 1$ depending on $k$.
