Best-Response Dynamics in Tullock Contests with Convex Costs

Abstract

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. We consider the model proposed by Ghosh and Goldberg (2023), where the agent making the move is randomly selected at each time step. We show convergence to an $\epsilon$-approximate equilibrium in $O(\beta \log (n/(\epsilon \delta )))$ steps with probability $1-\delta$, where $\beta$ is a parameter of the agent selection process, e.g., $\beta =n^2\log (n)$ if agents are selected uniformly at random at each time step. We complement this result with a lower bound of $\Omega (n+\log (1/\epsilon )/\log (n))$ applicable for any agent selection process.

43 pages. WINE '23 version