Toward Fair and Strategyproof Tournament Rules for Tournaments with Partially Transferable Utilities
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.
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 significantly offset individual losses.
We show that several previously studied tournament rules require a high degree of non-transferability 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 is whether there is a tournament rule that is fair and non-manipulable for a low degree of transferability that meets the lower bound we prove.
We conjecture that indeed such a rule exists.
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 significantly offset individual losses.
We show that several previously studied tournament rules require a high degree of non-transferability 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 is whether there is a tournament rule that is fair and non-manipulable for a low degree of transferability that meets the lower bound we prove.
We conjecture that indeed such a rule exists.
