Metraipolis › archive › dc_95a63ae6db55
Nash Equilibria in Auctions with Pacing Strategies: Complexity and Inefficiency — arXiv:2609.34515
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.34515
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T22:14:03.343Z
- SHA-256 of the archived text
d828e30cad6dac407f329c8898e04b51855880ea035a1f62073292bab658b622- Stable URL of this page
https://metraipolis.com/documento/dc_95a63ae6db55
How to cite
Nash Equilibria in Auctions with Pacing Strategies: Complexity and Inefficiency — arXiv:2609.34515 — arXiv (en), https://arxiv.org/abs/2609.34515 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_95a63ae6db55 (Metraipolis archive dc_95a63ae6db55, sha256 d828e30cad6dac407f329c8898e04b51855880ea035a1f62073292bab658b622)
BibTeX
@misc{dc95a63ae6db55,
title = {Nash Equilibria in Auctions with Pacing Strategies: Complexity and Inefficiency — arXiv:2609.34515},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.34515},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_95a63ae6db55; sha256 d828e30cad6dac407f329c8898e04b51855880ea035a1f62073292bab658b622},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34515. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We introduce and study Auctions with Pacing Strategies (APS) games, a full-information model in which utility-maximizing bidders compete across many simultaneous first-price auctions, each choosing a single pacing multiplier that uniformly scales their values into bids. We settle three central questions. First, we show that there are instances that admit no approximate pure Nash equilibria. Then, we prove that the problem of deciding whether an APS game admits an (approximate) equilibrium is NP-complete in general, but can be solved in polynomial time if either the number of bidders or the number of items is fixed. Finally, when an equilibrium does exist, we characterize its inefficiency exactly, showing that both the Price of Anarchy and the Price of Stability equal $\frac{e}{e-1}$.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-29 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.34515 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T21:55:21.833Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).