- Toward a fair and strategyproof tournament rule for selfish agents
- Project Year:
2021
- REU Student (s):
Eric Xue | Yale University CT
- Student 1 Institution:
Yale University
- Project Mentor:
Ariel Schvartzman
- Project Mentor Area:
DIMACS
- Project Abstract:
A tournament on n agents is a binary relation that describes the outcomes of the $\binom{n}{2}$ matches played between two distinct agents. Tournaments play an important role not only in sporting events but in any setting where any two agents are comparable and some "most qualified" agent should be selected, such as elections. The winner of a tournament is determined by a tournament rule that maps tournaments to probability distributions over the agents. We want these rules to be fair (i.e., choose a high quality agent) and robust to strategic manipulation. Prior work has shown that under minimally fair rules, manipulations between two agents can be prevented when utility is nontransferable but not when utility is completely transferable. Motivated by the fact that neither utility model reflects reality, we consider pairwise manipulations under partially transferable utility. These situations arise, for example, when agents care about winning themselves but are still willing to collude if joint gains offset perceived individual losses. We show that previously studied tournament rules require high levels of selfishness in order to prevent pairwise manipulations and that for fixed levels of selfishness, there are always two agents who stand to gain a constant positive amount of probability under these rules by manipulating in large enough tournaments. We also show that for stronger notions of fairness, non-manipulable tournament rules are closely related to tournament rules that witness decreasing gains from manipulation as the number of agents increases. A major open question that remains is whether there is a tournament rule that is fair and non-manipulable for a fixed level of selfishness that meets the lower bound we prove. We conjecture that indeed such a rule exists.
