On the Computation of Equilibria in Discrete First-Price Auctions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916467986923520 |
|---|---|
| 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 computational complexity of computing Bayes-Nash equilibria in first-price auctions with discrete value distributions and discrete bidding space, under general subjective beliefs. It is known that such auctions do not always have pure equilibria. In this paper, we prove that the problem of deciding their existence is NP-complete, even for approximate equilibria. On the other hand, it can be shown that mixed equilibria are guaranteed to exist; however, their computational complexity has not been studied before. We establish the PPAD-completeness of computing a mixed equilibrium and we complement this by an efficient algorithm for finding symmetric approximate equilibria in the special case of iid priors. En route to these results, we develop a computational equivalence framework between continuous and discrete first-price auctions, which can be of independent interest, and which allows us to transfer existing positive and negative results from one setting to the other. Finally, we show that correlated equilibria of the auction can be computed in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_12068 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Computation of Equilibria in Discrete First-Price Auctions Filos-Ratsikas, Aris Giannakopoulos, Yiannis Hollender, Alexandros Kokkalis, Charalampos Computer Science and Game Theory Computational Complexity We study the computational complexity of computing Bayes-Nash equilibria in first-price auctions with discrete value distributions and discrete bidding space, under general subjective beliefs. It is known that such auctions do not always have pure equilibria. In this paper, we prove that the problem of deciding their existence is NP-complete, even for approximate equilibria. On the other hand, it can be shown that mixed equilibria are guaranteed to exist; however, their computational complexity has not been studied before. We establish the PPAD-completeness of computing a mixed equilibrium and we complement this by an efficient algorithm for finding symmetric approximate equilibria in the special case of iid priors. En route to these results, we develop a computational equivalence framework between continuous and discrete first-price auctions, which can be of independent interest, and which allows us to transfer existing positive and negative results from one setting to the other. Finally, we show that correlated equilibria of the auction can be computed in polynomial time. |
| title | On the Computation of Equilibria in Discrete First-Price Auctions |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2402.12068 |