OpenAlex ·
Complexity of Autobidding Equilibria in GSP Sponsored Shopping
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.13716
- Original
- Read it at the publisher
- Topics
Abstract
We revisit autobidding equilibria in GSP sponsored shopping auctions, recently proposed and studied in Dütting et al. On the existence side, we show that autobidding equilibria under both budget constraints (ABE-B) and return-on-investment constraints (ABE-R) always exist and, moreover, always admit equilibria with polynomial-size support over the allocation space. On the computational side, we show that computing an exact equilibrium is in FIXP, and that computing an approximate equilibrium is in PPAD. We also prove that computing an approximate equilibrium is PPAD-hard for both ABE-B and ABE-R. Together, these results provide a fairly comprehensive picture of the computational complexity of autobidding equilibria in GSP sponsored shopping auctions.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Econometrics
The Financing of Debt Relief: Intermediary Liquidity and the Value of Borrower Information
Displacement Is Endogenous: AI Workers in a Search-and-Matching Labor Market
AI-Mediation in Retail Markets: Revenue Effects and Assortment Optimization
Too Late to Prune: Generative AI, the Screen, and Team Creative Decisions
The Buffett Effect
Get the few papers worth your time in Econometrics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.