Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909979374518272 |
|---|---|
| author | Chen, Xi Li, Yuhao |
| author_facet | Chen, Xi Li, Yuhao |
| contents | In this paper, we revisit the problem of approximating a pacing equilibrium in second-price auctions, introduced by Conitzer, Kroer, Sodomka, and Moses [Oper. Res. 2022]. We show that finding a constant-factor approximation of a pacing equilibrium is PPAD-hard, thereby strengthening previous results of Chen, Kroer, and Kumar [Math. Oper. Res. 2024], which established PPAD-hardness only for inverse-polynomial approximations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_15295 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constant Inapproximability of Pacing Equilibria in Second-Price Auctions Chen, Xi Li, Yuhao Computer Science and Game Theory Computational Complexity In this paper, we revisit the problem of approximating a pacing equilibrium in second-price auctions, introduced by Conitzer, Kroer, Sodomka, and Moses [Oper. Res. 2022]. We show that finding a constant-factor approximation of a pacing equilibrium is PPAD-hard, thereby strengthening previous results of Chen, Kroer, and Kumar [Math. Oper. Res. 2024], which established PPAD-hardness only for inverse-polynomial approximations. |
| title | Constant Inapproximability of Pacing Equilibria in Second-Price Auctions |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2501.15295 |