Strategyproof Tournament Rules for Teams with a Constant Degree of Selfishness

David M. Pennock, Daniel Schoepflin, Kangning Wang

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 $\lambda$. Intermediate selfishness $\lambda$ means that a team will not lose on purpose unless its pair gains at least $\lambda 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 $\lambda = \Omega(n)$ to be strategyproof, and it has been an open problem to find such a rule with the smallest $\lambda$. In this work, we make significant progress by designing a tournament rule that is strategyproof with $\lambda = 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 $\delta$ and provide a rule which is multiplicatively pairwise non-manipulable for $\delta = 3.5$.

Introduction

In competitive sports leagues and various social choice scenarios, the design of tournament rules is a critical task. A tournament rule is a mechanism that maps the results of a round-robin tournament—represented as a complete directed graph where an edge from $i$ to $j$ indicates $i$ beat $j$—to a probability distribution over the participants. The goal is to select a winner in a way that is both "fair" and resistant to strategic manipulation.

Two fundamental fairness criteria are Condorcet Consistency (a team that beats every other team must win with 100% probability) and Monotonicity (winning a game should never decrease a team's probability of winning the tournament). However, achieving these while ensuring strategyproofness—preventing teams from intentionally losing to manipulate the outcome—has proven notoriously difficult.

The Challenge of Strategyproofness

The core issue in tournament design is collusion. Teams may have incentives to "throw" a game if doing so significantly increases the winning probability of a favored partner, even at a small cost to themselves. To quantify this, researchers use a selfishness parameter $\lambda$. A team is considered $\lambda$-selfish if it will only sacrifice $s$ of its own winning probability if its partner gains at least $(\lambda + 1)s$.

Comparison of two tournaments $T$ and $T'$, where the outcome of the game between teams $a$ and $b$ is reversed. Such transitions are central to analyzing the strategyproofness of tournament rules.

Historically, all known fair tournament rules required $\lambda$ to scale linearly with the number of teams $n$ (i.e., $\lambda = \Omega(n)$). This implies that in large leagues, even a tiny incentive could lead to manipulation. This paper breaks this barrier by introducing rules that are strategyproof for a constant $\lambda$, independent of $n$.

Geometric Scoring Rules

The authors propose three randomized rules based on geometric scoring sequences. These sequences are designed to dampen the impact of any single game outcome on the overall distribution.

  1. NormalizedGeometricWinCountScore: This rule assigns scores based on a team's total wins ($d_i$) using the sequence $s_i = (1/2)^{(n-2)-d_i}$. The winner is chosen with probability proportional to these scores.
  2. NormalizedGeometricWinStrengthScore: This refined rule incorporates "strength of schedule." A team's score $t_i$ is the sum of its own win-count score and the win-count scores of all teams it defeated. This ensures that defeating a strong opponent is rewarded more than defeating a weak one.
  3. TopCycleGeometricWinCountScore: This version targets Top Cycle Consistency, a stronger fairness notion. It restricts the potential winners to the "top cycle"—the smallest set of teams such that every team in the set has beaten every team outside it.

Overcoming the "Superman-Kryptonite" Barrier

A major hurdle in previous research was the "Superman-Kryptonite" scenario. In this case, a dominant team ("Superman") might lose to a very weak team ("Kryptonite"). If Kryptonite throws the game to Superman, Superman's already high probability might jump significantly, while Kryptonite's near-zero probability changes negligibly.

The authors' "Strength" rule addresses this by making a team's probability dependent on the quality of its victims. If a weak team throws a game to a strong team, the gain for the strong team is mathematically capped because the weak team's contribution to the strong team's "strength score" is minimal.

Key Results and Multiplicative Non-manipulability

The paper introduces a new theoretical framework: $\delta$-multiplicative pairwise non-manipulability. This ensures that no two teams can manipulate a game to increase their joint winning probability by more than a factor of $\delta$.

Key findings include:

  • Constant Strategyproofness: The NormalizedGeometricWinStrengthScore rule is strategyproof for $\lambda = 11$, the first such rule where $\lambda$ is $o(n)$.
  • Multiplicative Bounds: The NormalizedGeometricWinCountScore achieves a 3.5-multiplicative bound, while the Top Cycle version achieves a factor of 5.
  • Computational Efficiency: All proposed rules can be computed in $O(n^2)$ time, making them practical for real-world leagues.

Conclusion and Future Work

This work represents a significant leap in computational social choice, proving that constant-degree strategyproofness is achievable for fair tournament rules. While the paper achieves $\lambda = 11$, the long-standing conjecture that $\lambda = 1$ is the ultimate limit remains open. Future research may focus on combining the "Strength" and "Top Cycle" approaches or finding the absolute minimum achievable $\delta$.

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 M. 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