Research map / Learning theory and algorithms / Submodular and game algorithms

Computing Perfect Bayesian Equilibria in Sequential Auctions with Verification

AAAI 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Correlated equilibria in sequential games · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Computes pure-strategy epsilon-PBE in sequential auctions via a belief-augmented finite abstraction, backward induction over stage-auction BNEs, and a verification procedure bounding the utility loss.

Problem

Computing perfect Bayesian equilibria in sequential auctions with continuous type and action spaces is hard: infinitely many subgames, and no optimal substructure because beliefs depend on previous-round strategies.

Approach

Augment the state with public beliefs (PBS) and discretize types/beliefs with piecewise-constant strategies so a PBE can be found by backward induction over finitely many stage auctions (each solved as a BNE via iterated best response), and then bound the utility loss by a decomposition theorem evaluated at hyperrectangle vertices.

Key results

• Across sequential sales, reserve-price, and split-award settings, the algorithm recovers known analytical PBEs with average L2 distances between about 0.003 and 0.014.
• In the sequential LLG auction, the verification procedure certifies an epsilon of 1.47e-4, indicating near-perfect convergence.
• In the sequential LLG auction, the global bidder shades bids for types below about 1.1 in round one and bids truthfully above it, while both bidders bid truthfully in round two.

Surprising findings

• In the sequential LLG auction, the first-round global bidder's strategy is non-continuous, shading below a type threshold of about 1.1 and bidding truthfully above it.

Limitations

• Assumes independent types and public beliefs; interdependent types from mechanisms and information from payments are not handled.
• Restricted to pure strategies and deterministic mechanisms; mixed strategies and random tie-breaking are left to future work.
• No convergence guarantee for best-response dynamics; the verification bound is what certifies quality.

Experimental setup

Benchmarks: sequential sales (first- and second-price) sequential sales with reserve prices two-round split-award auction two-round local-local-global auction

Metrics: L2 distance to known equilibrium strategies epsilon from verification procedure core hours runtime

Baselines: analytical equilibria of sequential sales analytical PBE of split-award auction analytical equilibria of sequential sales with reserve prices

Builds on: iterated best response for BNE in single-round auctions (Bosshard et al.) piecewise-constant PBE dynamic program (Fudenberg-Tirole style PBE) Bosshard et al. verification procedure

Closest papers by meaning

• Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response (ICML 2025 · similarity 0.90)
• A Bayesian Clearing Mechanism for Combinatorial Auctions (AAAI 2018 · similarity 0.90)
• Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games (AAAI 2025 · similarity 0.90)
• On the Power of Randomization for Obviously Strategy-Proof Mechanisms (AAAI 2025 · similarity 0.86)
• Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions (ICML 2025 · similarity 0.86)
• Protocols for Verifying Smooth Strategies in Bandits and Games (NeurIPS 2025 · similarity 0.86)