Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.06444 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Despite the extensive literature on Tullock contests, computational results for the general model with heterogeneous contestants remain scarce. This paper studies the algorithmic complexity of computing a pure Nash Equilibrium (PNE) in such general Tullock contests. We find that the elasticity parameters {r_i}, which govern the returns to scale of contestants' production functions, play a decisive role in the problem's complexity. Our core conceptual insight is that the computational hardness is determined specifically by the number of contestants with medium elasticity (r_i \in (1, 2]). This is illustrated by a complete set of algorithmic results under two parameter regimes: -Efficient Regime: When the number of contestants with medium elasticity is logarithmically bounded by the total number of contestants (O(log n)), we provide an algorithm that determines the existence of a PNE and computes an epsilon-PNE in polynomial time in both n and log(1/epsilon) (i.e., Poly(n,log(1/epsilon))) whenever it exists. This result generalizes classical findings for concave (r_i <= 1) and convex (r_i > 2) cases, establishing computational tractability for a broader class of mixed-elasticity contests. -Hard Regime: In contrast, we show when the number of medium elasticity contestants exceed Omega(log n), determining the existence of PNEs is NP-complete and it is impossible for any algorithm to compute an epsilon-PNE within running time Poly(n,log(1/epsilon)). We then design a Fully Polynomial-Time Approximation Scheme (FPTAS) that computes an epsilon-PNE in Poly(n,1/epsilon), guaranteeing efficient approximations for hard instances.