On the Complexity of Exact Autobidding Equilibria
cs.GT, cs.CC
Submitted: 2026-11-03
Updated: 2026-11-03
Comments: Full version with appendices
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Terminology
Sources
- Auto-bidding and Auctions in Online Advertising: A Survey
- No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints
- Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria
- Beyond the PPAD hardness of Auto-bidding Auctions
- Throttling Equilibria in Auction Markets
- Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
- Pure-Circuit: Tight Inapproximability for PPAD
- No-Regret Online Autobidding Algorithms in First-price Auctions
- Efficiency of the Generalized Second-Price Auction for Value Maximizers
- Towards Efficient Auctions in an Auto-bidding World
- Autobidding Equilibria in Sponsored Shopping
- On the Complexity of Equilibrium Computation in First-Price Auctions
- PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
- Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence
- GSP Autobidding Equilibria with Few Advertisers or Slots
- Vulnerabilities of Single-Round Incentive Compatibility in Auto-bidding: Theory and Evidence from ROI-Constrained Online Advertising Markets
- Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments