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

Applications of combinatorial auctions (CA) as market mechanisms are\nprevalent in practice, yet their Bayesian Nash equilibria (BNE) remain poorly\nunderstood. Analytical solutions are known only for a few cases where the\nproblem can be reformulated as a tractable partial differential equation (PDE).\nIn the general case, finding BNE is known to be computationally hard. Previous\nwork on numerical computation of BNE in auctions has relied either on solving\nsuch PDEs explicitly, calculating pointwise best-responses in strategy space,\nor iteratively solving restricted subgames. In this study, we present a generic\nyet scalable alternative multi-agent equilibrium learning method that\nrepresents strategies as neural networks and applies policy iteration based on\ngradient dynamics in self-play. Most auctions are ex-post nondifferentiable, so\ngradients may be unavailable or misleading, and we rely on suitable\npseudogradient estimates instead. Although it is well-known that gradient\ndynamics cannot guarantee convergence to NE in general, we observe fast and\nrobust convergence to approximate BNE in a wide variety of auctions and present\na sufficient condition for convergence\n