Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Journal Article |
| Scope | Discipline-based scholarship |
| Title | Computing bayes-nash equilibria in combinatorial auctions with verification |
| Organization Unit | |
| Authors |
|
| Item Subtype | Original Work |
| Refereed | Yes |
| Status | Published in final form |
| Language |
|
| Journal Title | Journal of Artificial Intelligence Research |
| Publisher | AI Access Foundation |
| Geographical Reach | international |
| ISSN | 1076-9757 |
| Volume | 69 |
| Page Range | 531 - 570 |
| Date | 2020 |
| Abstract Text | We present a new algorithm for computing pure-strategy ε-Bayes-Nash equilibria (ε-BNEs) in combinatorial auctions. The main innovation of our algorithm is to separate the algorithm’s search phase (for finding the ε-BNE) from the verification phase (for computing the ε). Using this approach, we obtain an algorithm that is both very fast and provides theoretical guarantees on the ε it finds. Our main contribution is a verification method which, surprisingly, allows us to upper bound the ε across the whole continuous value space without making assumptions about the mechanism. Using our algorithm, we can now compute ε-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 many other applications. |
| Free access at | DOI |
| Digital Object Identifier | 10.1613/jair.1.11525 |
| Other Identification Number | merlin-id:20196 |
| PDF File |
Download from ZORA
|
| Export |
BibTeX
EP3 XML (ZORA)
|