Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Conference or Workshop Paper |
| Scope | Discipline-based scholarship |
| Published in Proceedings | Yes |
| Title | Computing Bayes-Nash Equilibria in Combinatorial Auctions with Continuous Value and Action Spaces |
| Organization Unit | |
| Authors |
|
| Editors |
|
| Presentation Type | paper |
| Item Subtype | Original Work |
| Refereed | Yes |
| Status | Published in final form |
| Language |
|
| ISBN | 9780999241103 |
| Page Range | 119 - 127 |
| Event Title | Twenty-Sixth International Joint Conference on Artificial Intelligence |
| Event Type | conference |
| Event Location | Melbourne, Australia |
| Event Start Date | September 19 - 2017 |
| Event End Date | September 26 - 2017 |
| Place of Publication | California |
| Publisher | International Joint Conferences on Artificial Intelligence Organization |
| Abstract Text | Combinatorial auctions (CAs) are widely used in practice, which is why understanding their incentive properties is an important problem. However, finding Bayes-Nash equilibria (BNEs) of CAs analytically is tedious, and prior algorithmic work has only considered limited solution concepts (e.g. restricted action spaces). In this paper, we present a fast, general algorithm for computing symmetric pure ε-BNEs in CAs with continuous values and actions. In contrast to prior work, we separate the search phase (for finding the BNE) from the verification step (for estimating the ε), and always consider the full (continuous) action space in the best response computation. We evaluate our method in the well-studied LLG domain, against a benchmark of 16 CAs for which analytical BNEs are known. In all cases, our algorithm converges quickly, matching the known results with high precision. Furthermore, for CAs with quasi-linear utility functions and independently distributed valuations, we derive a theoretical bound on ε. Finally, we introduce the new Multi-Minded LLLLGG domain with eight goods and six bidders, and apply our algorithm to finding an equilibrium in this domain. Our algorithm is the first to find an accurate BNE in a CA of this size. |
| Digital Object Identifier | 10.24963/ijcai.2017/18 |
| Export |
BibTeX
EP3 XML (ZORA)
|