  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.
