Efficient Equilibrium Computation in Symmetric First-Price Auctions
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_ | 1866908913291493376 |
|---|---|
| author | Filos-Ratsikas, Aris Giannakopoulos, Yiannis Hollender, Alexandros Kokkalis, Charalampos |
| author_facet | Filos-Ratsikas, Aris Giannakopoulos, Yiannis Hollender, Alexandros Kokkalis, Charalampos |
| contents | We study the complexity of computing Bayes-Nash equilibria in single-item first-price auctions. We present the first efficient algorithms for the problem, when the bidders' values for the item are independently drawn from the same continuous distribution, under both established variants of continuous and finite bidding sets. More precisely, we design polynomial-time algorithms for the white-box model, where the distribution is provided directly as part of the input, and query-efficient algorithms for the black-box model, where the distribution is accessed via oracle calls. Our results settle the computational complexity of the problem for bidders with i.i.d. values. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_24317 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Efficient Equilibrium Computation in Symmetric First-Price Auctions Filos-Ratsikas, Aris Giannakopoulos, Yiannis Hollender, Alexandros Kokkalis, Charalampos Computer Science and Game Theory Computational Complexity 91A68 We study the complexity of computing Bayes-Nash equilibria in single-item first-price auctions. We present the first efficient algorithms for the problem, when the bidders' values for the item are independently drawn from the same continuous distribution, under both established variants of continuous and finite bidding sets. More precisely, we design polynomial-time algorithms for the white-box model, where the distribution is provided directly as part of the input, and query-efficient algorithms for the black-box model, where the distribution is accessed via oracle calls. Our results settle the computational complexity of the problem for bidders with i.i.d. values. |
| title | Efficient Equilibrium Computation in Symmetric First-Price Auctions |
| topic | Computer Science and Game Theory Computational Complexity 91A68 |
| url | https://arxiv.org/abs/2603.24317 |