Best-Response Dynamics in Lottery Contests

Abheek Ghosh and Paul W. Goldberg

Papers from arXiv.org

Abstract: We study the convergence of best-response dynamics in lottery contests. We show that best-response dynamics rapidly converges to the (unique) equilibrium for homogeneous agents but may not converge for non-homogeneous agents, even for two non-homogeneous agents. For $2$ 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 a model 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$ if agents are selected uniformly at random at each time step. Our simulations indicate that this bound is tight.

Date: 2023-05
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2305.10881 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2305.10881

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().