Computing Bayes-Nash equilibria in Combinatorial auctions with continuous value and action spaces

Vitor Bosshard, Benedikt Bünz, Benjamin Lubin, Sven Seuken

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication26th International Joint Conference on Artificial Intelligence, IJCAI 2017
EditorsCarles Sierra
PublisherInternational Joint Conferences on Artificial Intelligence
Pages119-127
Number of pages9
ISBN (Electronic)9780999241103
DOIs
StatePublished - 2017
Event26th International Joint Conference on Artificial Intelligence, IJCAI 2017 - Melbourne, Australia
Duration: Aug 19 2017Aug 25 2017

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
Volume0
ISSN (Print)1045-0823

Conference

Conference26th International Joint Conference on Artificial Intelligence, IJCAI 2017
Country/TerritoryAustralia
CityMelbourne
Period8/19/178/25/17

ASJC Scopus subject areas

  • Artificial Intelligence

Cite this