Equilibrium Learning in Combinatorial Auctions: Computing Approximate Bayesian Nash Equilibria via Pseudogradient Dynamics

While the complexity of computing Bayes-Nash equilibria Applications of combinatorial auctions (CA) as market mechanisms (BNE) is not well understood, Cai and Papadimitriou [14] show that are prevalent in practice, yet their Bayesian Nash equilibria (BNE) BNE computation for a specific combinatorial auction is already (at remain poorly understood. Analytical solutions are known only for least) PP-hard. Furthermore, finding an -approximation to a BNE is a few cases where the problem can be reformulated as a tractable still NP-hard. Explicit solutions exist for very few specific environments, partial differential equation (PDE). In the general case, finding BNE but in general, we neither know whether a BNE exists nor is known to be computationally hard. Previous work on numerical do we have a solution theory. Combinatorial auctions have become computation of BNE in auctions has relied either on solving such a pivotal research problem in algorithmic game theory [29] and PDEs explicitly, calculating pointwise best-responses in strategy they are widely used in the field [8, 15]. Thus, understanding their space, or iteratively solving restricted subgames. In this study, we equilibria is paramount, and access to scalable numerical methods present a generic yet scalable alternative multi-agent equilibrium for computing or approximating BNE can have a significant impact.