Pacing Equilibria in Second-Price Auctions with Few Goods
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915998535254016 |
|---|---|
| author | Huang, Yiyang Yan, Yonglei Wang, Zihe Liu, Zhengyang |
| author_facet | Huang, Yiyang Yan, Yonglei Wang, Zihe Liu, Zhengyang |
| contents | In this paper, we investigate the computation of second-price pacing equilibria (SPPEs), a foundational model in online advertising auctions. We present a polynomial-time algorithm for computing exact SPPEs in instances with a constant number of goods. Our core technique maps buyers' pacing multipliers to the highest bids on each good, effectively partitioning the parameter space into a set of distinct geometric cells. By enumerating these cells, we fix the relative ordering of the bids and reduce the problem of equilibrium computation to a linear feasibility program. Finally, we demonstrate that this tractability extends to large-scale markets with an arbitrary number of goods, provided the goods can be aggregated into a constant number of valuation types. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_09332 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Pacing Equilibria in Second-Price Auctions with Few Goods Huang, Yiyang Yan, Yonglei Wang, Zihe Liu, Zhengyang Computer Science and Game Theory In this paper, we investigate the computation of second-price pacing equilibria (SPPEs), a foundational model in online advertising auctions. We present a polynomial-time algorithm for computing exact SPPEs in instances with a constant number of goods. Our core technique maps buyers' pacing multipliers to the highest bids on each good, effectively partitioning the parameter space into a set of distinct geometric cells. By enumerating these cells, we fix the relative ordering of the bids and reduce the problem of equilibrium computation to a linear feasibility program. Finally, we demonstrate that this tractability extends to large-scale markets with an arbitrary number of goods, provided the goods can be aggregated into a constant number of valuation types. |
| title | Pacing Equilibria in Second-Price Auctions with Few Goods |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2605.09332 |