Header

UZH-Logo

Maintenance Infos

Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification


Bosshard, Vitor; Bünz, Benedikt; Lubin, Benjamin; Seuken, Sven (2020). Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification. Journal of Artificial Intelligence Research, 69:531-570.

Abstract

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.

Abstract

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.

Statistics

Citations

Dimensions.ai Metrics
6 citations in Web of Science®
9 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

22 downloads since deposited on 15 Oct 2021
5 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Scopus Subject Areas:Physical Sciences > Artificial Intelligence
Uncontrolled Keywords:Artificial Intelligence
Scope:Discipline-based scholarship (basic research)
Language:English
Date:23 October 2020
Deposited On:15 Oct 2021 13:30
Last Modified:25 Apr 2024 01:40
Publisher:AI Access Foundation
ISSN:1076-9757
OA Status:Gold
Free access at:Publisher DOI. An embargo period may apply.
Publisher DOI:https://doi.org/10.1613/jair.1.11525
Other Identification Number:merlin-id:21579
  • Content: Published Version