Strategyproof Tournament Rules for Teams with a Constant Degree of Selfishness

David Pennock, Daniel Schoepflin, Kangning Wang

TL;DR

This paper solves a long-standing open problem in computational social choice by designing the first tournament rule that is strategyproof against colluding teams with a constant degree of selfishness ($\lambda = 11$). By transitioning from counting raw wins to evaluating the "strength" of defeated opponents, the authors prevent teams from intentionally throwing matches to disproportionately benefit a co-conspirator.

What Problem Does This Paper Address?

In sports leagues or voting scenarios modeled as round-robin tournaments, a tournament rule maps match outcomes to a probability distribution over potential winners. A key challenge in mechanism design is making these rules resistant to manipulation and collusion—such as when two teams fix a match outcome so that at least one of them advances (a real-world example being the infamous "disgrace of Gijón" in the 1982 FIFA World Cup).

Prior work modeled team behavior using a parameterized degree of selfishness, $\lambda$. A team with intermediate selfishness $\lambda$ will refuse to intentionally lose a match and sacrifice $x$ amount of its own winning probability unless its accomplice gains at least $(\lambda + 1)x$ in winning probability.

If teams are completely selfless ($\lambda = 0$), preventing collusion while maintaining basic fairness (Condorcet consistency) is mathematically impossible. If they are completely selfish ($\lambda = \infty$), solutions exist. However, for realistic intermediate settings, all previously known tournament rules required $\lambda = \Omega(n)$, meaning their resistance to collusion degraded as the number of teams ($n$) grew. The authors tackle a fundamental question: Can we design a fair tournament rule that remains strategyproof for a constant $\lambda$, completely independent of tournament size?

Methods

The authors introduce a new intermediate property called $\delta$-multiplicative $k$-non-manipulability ($k$-MNM-$\delta$), which bounds the joint multiplicative gain a coalition of $k$ teams can achieve by match-fixing.

Using this framework, they propose two novel randomized tournament rules:

  1. NormalizedGeometricWinCountScore: This rule maps a team's raw win count ($d_i$) to a geometric score: $$s_i = \left(\frac{1}{2}\right)^{(n-2)-d_i}$$ The winner is then chosen proportionally based on these scores.

  2. NormalizedGeometricWinStrengthScore: To fix a vulnerability in the first rule against specific adversarial tournament structures, the authors develop a more sophisticated scoring metric. This rule calculates a "true win score" ($t_i$) that incorporates both a team's own geometric win score and the scores of the teams it managed to defeat: $$t_i = 2s_i + \sum_{j \in D_i} s_j$$ The final winner distribution is a normalized blend of this strength score and a uniform distribution.

Datasets

Not discussed in the paper. This work is purely theoretical and mathematical proof-based.

Key Insights and Ideas

  • The Multiplicative Relaxation: Standard additive non-manipulability metrics fail to capture the risk posed by teams with very low winning probabilities. Shifting the focus to multiplicative bounds ($k$-MNM-$\delta$) provides a tighter grip on strategic behavior for underdogs.
  • Failure of Elimination Brackets: Popular rules like the RandomizedSingleEliminationBracket fail completely under multiplicative criteria. A single match outcome can swing a team's winning probability from zero to positive, creating an infinite multiplicative incentive to collude.
Figure 1: Two {a, b}-adjacent tournaments T and T ′ demonstrating that RandomizedSingleElimina- tionBracket does not guarantee 2-MNM-δ for any finite δ.
  • Strength Over Raw Wins: Simply counting wins leaves a loophole where a weak "kryptonite" team can throw a match to a dominant "superman" team for an outsized probability transfer. By weighting wins by the strength of the defeated opponent, the new rule mathematically ties the beneficiary's gain directly to the loser's sacrifice, neutralizing the incentive to collude.

Key Results

  • Constant Strategyproofness: The authors prove that NormalizedGeometricWinStrengthScore satisfies Condorcet consistency, monotonicity, and 2-non-manipulability for a constant $\lambda = 11$ for any number of teams. This breaks the previous $\Omega(n)$ barrier.
  • Multiplicative Bounds: They demonstrate that NormalizedGeometricWinCountScore achieves 2-MNM-3.5 along with Condorcet consistency and monotonicity.
  • Theoretical Limits: The paper establishes a lower bound showing that no Condorcet-consistent tournament rule can achieve better than 2-MNM-1.5.
  • Refined Fairness: In the appendix, the authors extend their geometric win-count approach to satisfy Top Cycle Consistency (TCC)—ensuring losers outside the top-performing cycle receive zero probability of winning—while maintaining 2-MNM-5.

Limitations and Future Work

  • Tightening the Bound: While $\lambda = 11$ is a constant, a prominent open question is whether a rule exists for the conjectured sharp cutoff of $\lambda = 1$.
  • Minimizing Multiplicative Gain: Finding the absolute minimum $\delta$ for $k$-MNM-$\delta$ rules remains open.
  • Combining Strength and Top Cycle Consistency: The "pruning" method used to achieve Top Cycle Consistency for the win-count rule does not easily translate to the win-strength rule. Designing a mechanism that simultaneously satisfies TCC and a constant $\lambda$-strategyproofness remains a challenging open problem.

Summary updated

Abstract

We revisit the well-studied problem of designing fair and manipulation-resistant tournament rules. In this problem, we seek a mechanism that (probabilistically) identifies the winner of a tournament after observing round-robin play among $n$ teams in a league. Such a mechanism should satisfy the natural properties of monotonicity and Condorcet consistency. Moreover, from the league's perspective, the winner-determination tournament rule should be strategyproof, meaning that no team can do better by losing a game on purpose. Past work considered settings in which each team is fully selfish, caring only about its own probability of winning, and settings in which each team is fully selfless, caring only about the total winning probability of itself and the team to which it deliberately loses. More recently, researchers considered a mixture of these two settings with a parameter $λ$. Intermediate selfishness $λ$ means that a team will not lose on purpose unless its pair gains at least $λs$ winning probability, where $s$ is the individual team's sacrifice from its own winning probability. All of the dozens of previously known tournament rules require $λ= Ω(n)$ to be strategyproof, and it has been an open problem to find such a rule with the smallest $λ$. In this work, we make significant progress by designing a tournament rule that is strategyproof with $λ= 11$. Along the way, we propose a new notion of multiplicative pairwise non-manipulability that ensures that two teams cannot manipulate the outcome of a game to increase the sum of their winning probabilities by more than a multiplicative factor $δ$ and provide a rule which is multiplicatively pairwise non-manipulable for $δ= 3.5$.
BibTeX
@misc{pennock2025strategyproof,
  author = {David Pennock and Daniel Schoepflin and Kangning Wang},
  title = {{Strategyproof Tournament Rules for Teams with a Constant Degree of Selfishness}},
  year = {2025},
  eprint = {2512.05235},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.05235},
}
Figure