← Paper page The Complexity of Tullock Contests Ask this paper arXiv ↗

The Complexity of
Tullock Contests

When many different contestants spend effort to win one prize, when can a computer work out where the competition settles?

Yu He, Fan Yao, Yang Yu, Xiaoyun Qiu, Minming Li, Haifeng Xu · EC 2026

Press → or click to step through

A Tullock contest: effort buys a chance to win

contestants effort output 2 1 1 depends on effort, efficiency and elasticity (next slide) win chance 50% 25% 25% = share of total output one prize a draw paid, win or lose

Each contestant weighs a better chance of winning against the cost of effort.

Illustration with outputs 2, 1, 1. The paper’s examples include R&D races, election campaigns, proof-of-work mining and crowdsourcing contests.

The key knob: elasticity, or how output grows with effort

effort → output 0.5 1 1.5 3
double the effort, and output is elasticity 0.5× 1.4 elasticity 1× 2 elasticity 1.5× 2.8 elasticity 3× 8 illustration; each contestant can have their own value
small (up to 1) medium (1 to 2) large (above 2) 012 lottery contest, e.g. Bitcoin mining → winner-take-all as it grows

Classic analyses assume a few contestants who are alike. Here every contestant can differ in both efficiency and elasticity.

Where does competition settle? Hard to say by hand

a few identical contestants classic formulas ✓ just two different ones their equilibrium efforts are irrational numbers: no neat formula mining: many, all different does a stable outcome even exist? example from the paper’s appendix: elasticities 0.5 and 1

So ask an algorithm: decide whether a stable outcome exists, and compute one to any precision.

“Stable” means a pure Nash equilibrium: no contestant can gain by changing their own effort.

Try it: above elasticity 1, contestants go all-or-nothing

your expected net gain 0 your effort (share of the prize) → 0 1
your best effort rivals’ total output → 0 1
your elasticity

Illustration: one contestant (efficiency 1, prize 1) facing rivals whose combined output is fixed. The paper’s Figure 1 shows the same shapes.

What makes it hard: only the medium contestants

small elasticity ininin take part whenever it pays, adjusting effort smoothly nothing to guess large elasticity inoutout anyone in holds over half the winning chance at most one is in (if all are large: no equilibrium at all) medium elasticity in/out?in/out?in/out? both can be stable, depending on the others must try combinations 3 medium contestants → 8 in/out patterns: each pattern: one simple search over the total output

Result: with few medium contestants (at most logarithmically many), an algorithm quickly decides whether an equilibrium exists and computes one to high precision.

Patterns double with each medium contestant, so “few” keeps the work polynomial; each extra digit of precision costs little time (Theorem 1). This covers the classic all-small and all-large cases and their mixtures.

Many medium contestants: a hidden puzzle

Illustration based on the paper’s hardness proof: at the critical total output, each medium contestant who joins takes a fixed slice of the winning chance. Click to choose who is in.

100% 0 winning chances must add up to exactly 100%

Hint: exactly one group works.

An equilibrium exists only if some group adds to exactly 100%: the Subset Sum puzzle, a classic NP-complete problem.

So deciding whether an equilibrium exists is NP-complete once medium contestants are more than logarithmically many.

Even high-precision approximation cannot be fast (time growing only with the number of digits) unless P = NP: a “no” instance always misses 100% by a tiny but definite gap.

Yet near-equilibria are always within reach

relax one rule: the winning chances need only land near 100% tolerance candidate total outputs (a fine grid) → schematic 100% closest total the algorithm can reach at each point near 100%: an approximate equilibrium ✓

An FPTAS: the time grows polynomially with the number of contestants and with one over the precision, the best kind of guarantee left given the hardness.

Everyone still best-responds to the total; at each grid point a fast approximate Subset Sum picks who is in. Needs medium elasticities to stay a fixed distance above 1 (otherwise pseudo-polynomial). In experiments, run times followed the predicted growth, and one 10-contestant contest had many different near-equilibria: near total output 39.8 the active pair switches from {1, 8} to {4, 7}.

What this means

  1. 1Elasticity decides how hard equilibria are to computeSpecifically, the number of contestants with medium elasticity (between 1 and 2).
  2. 2Few medium contestants: fast and preciseDecide existence exactly and compute high-precision equilibria in polynomial time.
  3. 3Many: NP-complete, but approximation worksHigh precision is out of reach unless P = NP; an FPTAS still finds approximate equilibria efficiently.

Paper page · arXiv · Ask this paper