Abstract
This paper investigates the algorithmic complexity of computing Pure Nash Equilibria (PNE) in Tullock Contests, a foundational model for competitive resource allocation. We demonstrate that the complexity of finding an equilibrium is dictated by the elasticity parameter $r_i$ of the contestants. While the game is efficiently solvable when $r_i$ values fall outside the interval $(1, 2]$, we prove that the problem becomes computationally intractable within this "magic interval." To address these hard cases, we develop a Fully Polynomial-Time Approximation Scheme (FPTAS) and validate our theoretical findings through large-scale computational experiments.
Introduction
The Tullock Contest serves as a cornerstone in economic theory, modeling scenarios where participants invest effort or resources to increase their probability of winning a prize. From rent-seeking behavior in political lobbying to the competitive landscape of blockchain mining, the model captures the essence of "pay-to-play" competition. Despite its longevity, the computational aspects of the Tullock Contest—specifically when participants are heterogeneous—have remained under-explored.
The central challenge in these contests is identifying the Pure Nash Equilibrium (PNE): a state where no contestant can improve their expected payoff by unilaterally changing their effort level. This paper maps the computational landscape of these equilibria, identifying exactly when the problem is easy to solve and when it becomes a combinatorial nightmare.
The Role of Elasticity
The dynamics of a Tullock Contest are governed by the elasticity parameter $r_i$. This parameter determines whether a contestant's production function exhibits diminishing returns ($r_i \le 1$), increasing returns, or more complex non-linear behavior.
When contestants have different $r_i$ values, the game becomes non-monotonic and non-linear. The authors categorize the complexity of finding a PNE into three distinct regimes based on these values:
- The Tractable Regime ($r_i \le 1$): When elasticity is low, the contest behaves as a socially-concave game. In this regime, the equilibrium is unique and can be found efficiently using bisection methods or Multi-agent Mirror Descent (MMD).
- The Hardness Zone ($r_i \in (1, 2]$): This "magic interval" represents the transition from concave to convex dynamics. The authors prove that if multiple players fall into this range, determining the existence of a PNE is NP-hard, assuming the Exponential Time Hypothesis (ETH).
- The Winner-Takes-All Regime ($r_i > 2$): For high elasticity, the game simplifies significantly. The authors prove a "winner-takes-all" property: if a PNE exists, at most one player will exert non-zero effort, which drastically reduces the search space.
Complexity and the Subset Sum Connection
The most significant theoretical contribution of this work is the formal proof of hardness for the $(1, 2]$ interval. By reducing a variant of the Subset Sum problem to the PNE existence problem, the authors demonstrate that finding an equilibrium in this range is as difficult as solving classic combinatorial problems.
This connection reveals that the difficulty lies in the discrete choice of participation: deciding which subset of players will actively compete and which will drop out. This bridge between continuous game theory and discrete theoretical computer science explains why standard gradient-based solvers often fail in these specific scenarios.
Algorithmic Solutions: FPTAS
To navigate the "Hardness Zone," the authors propose a Fully Polynomial-Time Approximation Scheme (FPTAS). Since finding an exact PNE is intractable in the medium-elasticity range, the FPTAS seeks an $\epsilon$-PNE—a state where no player can gain more than an $\epsilon$ advantage by deviating.
The algorithm works by discretizing the space of possible total aggregate effort and using a pruned subset-selection approach to manage the combinatorial explosion of player combinations. It achieves a runtime of $O(n^2/\epsilon^2)$, ensuring that an approximate equilibrium can be found in polynomial time whenever an exact one exists.
Experimental Validation
The theoretical results are complemented by a robust Python implementation. The authors tested their hybrid algorithms—combining bisection, MMD, and the FPTAS—on synthetic large-scale instances. These experiments confirmed that the algorithms scale predictably and can handle complex, heterogeneous scenarios that were previously computationally out of reach. The authors have released their code as an open-source module to facilitate further research.
Conclusion and Future Work
This research provides a complete taxonomy of the Tullock Contest's complexity. By identifying the $(1, 2]$ elasticity range as the source of computational hardness, the authors have provided a roadmap for both theorists and practitioners.
While this work settles many questions, several avenues remain for future study. The authors identify a "constant player" gap, questioning if the game remains hard if only a very small number of players fall into the $(1, 2]$ range. Additionally, while this study focuses on Pure Nash Equilibria, exploring the complexity of Mixed Nash Equilibria in these heterogeneous settings remains a fertile ground for future research.
Summary updated