# Computing Perfect Bayesian Equilibria in Sequential Auctions with Verification

arXiv: https://arxiv.org/abs/2312.04516 · HTML: https://mlsanity.com/paper/2312.04516/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2023.

## Built on by (most cited first, 2 of 2)

- [Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2402.19420/) (2024)
- [Belief-Driven Multi-Agent Collaboration via Approximate Perfect Bayesian Equilibrium for Social Simulation](https://mlsanity.com/paper/2603.24973/) (2026)

## Abstract (arXiv)

We present an algorithm for computing pure-strategy epsilon-perfect Bayesian equilibria in sequential auctions with continuous action and value spaces. Importantly, our algorithm includes a verification phase that computes an upper bound on the utility loss of the found strategies. Prior work on equilibrium computation in auctions with verification has focussed on the single-round case, but the methods do not work for sequential auctions because of two main challenges: (1) there are infinitely many subgames, and (2) the setting has no optimal substructure as bidders' beliefs and best response strategies depend on the strategies of previous rounds. We make two contributions. First, we introduce a tailor-made game abstraction that discretizes the auction and augments the state space with the public beliefs, such that an approximate equilibrium can be computed via dynamic programming. Second, we prove a decomposition theorem to upper bound the utility loss of the computed equilibrium. This is essential because it is neither guaranteed that the auction has an equilibrium nor that any algorithm converges to it. We validate our algorithm on multiple settings with known equilibria and apply it to a new multi-round combinatorial auction.