Best-Response Dynamics in Tullock Contests with Convex Costs

Understand

We study the convergence of best-response dynamics in Tullock contests with convex cost functions (these games always have a unique pure-strategy Nash equilibrium).

• We show that best-response dynamics rapidly converges to the equilibrium for homogeneous agents.
• For two homogeneous agents, we show convergence to an $\epsilon$-approximate equilibrium in $\Theta(\log\log(1/\epsilon))$ steps.
• For $n \ge 3$ agents, the dynamics is not unique because at each step $n-1 \ge 2$ agents can make non-trivial moves.