Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification
| Autor: | Benedikt Bünz, Vitor Bosshard, Sven Seuken, Benjamin Lubin |
|---|---|
| Přispěvatelé: | University of Zurich |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Theoretical computer science Computer science 10009 Department of Informatics Value (computer science) 1702 Artificial Intelligence Space (commercial competition) 000 Computer science knowledge & systems Upper and lower bounds Combinatorial auction symbols.namesake Bayes' theorem Computer Science - Computer Science and Game Theory Nash equilibrium Artificial Intelligence Code (cryptography) symbols Common value auction Computer Science and Game Theory (cs.GT) |
| Popis: | We present a new algorithm for computing pure-strategy $\varepsilon$-Bayes-Nash equilibria ($\varepsilon$-BNEs) in combinatorial auctions with continuous value and action spaces. An essential innovation of our algorithm is to separate the algorithm's search phase (for finding the $\varepsilon$-BNE) from the verification phase (for computing the $\varepsilon$). Using this approach, we obtain an algorithm that is both very fast and provides theoretical guarantees on the $\varepsilon$ it finds. Our main technical contribution is a verification method which allows us to upper bound the $\varepsilon$ across the whole continuous value space without making assumptions about the mechanism. Using our algorithm, we can now compute $\varepsilon$-BNEs in multi-minded domains that are significantly more complex than what was previously possible to solve. We release our code under an open-source license to enable researchers to perform algorithmic analyses of auctions, to enable bidders to analyze different strategies, and to facilitate many other applications. Comment: 40 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|