Our work proposes a different rule that slightly, but still not optimally, reduces the potential gains from manipulation. The theoretical rule we propose identifies a small set of teams as “significant”, which we define as teams that could form coalitions that lead to a team in the coalition being the clear winner.
We classify each possible tournament outcome into one of five buckets depending on how close it is to having a team win all their games. If the tournament has a team that wins all their games, we declare that team the winner. If the tournament is far from having a team that wins all their games, we choose a winner uniformly at random. For tournaments that are “close” to having a team that wins all their games, we identify those teams that could substantially gain from manipulating the tournament. We prove that there are not many such teams, and for each “close” tournament, we assign specific probabilities to each team so that the gains from manipulation for groups of size three are 50% at most (and still the optimal 33% for groups of size two).
One common concern about our model is that we assume all outcomes of the ground truth are deterministic, e.g., A always beats B, and this may not align with real tournaments. After all, underdogs always have a chance! Do our results hold if we allow for randomized outcomes, e.g., A beats B 80% of the time? It turns out that, thanks to prior work, the answer to this question is “yes” because the worst case instances are those with deterministic outcomes. Related work shows that if we restrict the win probability of all games to, say, the 60–40% interval, then we can expect to decrease the gains from manipulation as the tournament becomes more competitive.
In another attempt to overcome the impossibility result we presented before, we introduce a new model for determining which manipulations are beneficial. In the model outlined thus far, teams in the manipulation coalitions treat their joint probability of winning as a uniform mass. That is, a team in the coalition does not care which other team’s chances of winning go up or down, even if it is their own — an assumption that is unlikely since teams naturally care about their own chance of winning, or are at least a little selfish. To model the assumption that teams in manipulating coalitions are still a little selfish, we introduce weights to the manipulation calculations to reflect this.
We observed that if each team weights their own chances of winning twice as much as that of the other teams in the manipulating coalition, there exist rules that satisfy properties 1 and 3 for tournaments with at most six teams. We conjecture that, under this model, there may indeed exist rules that satisfy properties 1 and 3 exactly. We also show that for several popular rules, a large weight is needed for the rule to satisfy properties 1 and 3.