Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification
share
Combinatorial auctions (CAs) are mechanisms that are widely used in practice, and understanding their properties in equilibrium is an important open problem when agents act under uncertainty. Finding such Bayes-Nash equilibria (BNEs) is difficult, both analytically and algorithmically, and prior algorithmic work has been limited to solving simplified versions of the auction games being studied. In this paper, we present a fast, precise, and general algorithm for computing pure ϵ-BNEs in CAs with continuous values and actions. Our algorithm separates the search phase (for finding the BNE) from the verification step (for estimating ϵ), and computes best responses using the full (continuous) action space. We thoroughly validate our method in the well-studied LLG domain, against a benchmark of 16 CAs for which analytical BNEs are known. We further apply our algorithm to higher-dimensional auctions, which would have previously been considered intractable, by first introducing the new Multi-Minded LLLLGG domain with eight goods and six bidders, and then finding accurate and expressive equilibria in this domain. We release our code under an open source license, making it available to the broader research community.
READ FULL TEXT