OpenAlex ·
GSP Autobidding Equilibria with Few Advertisers or Slots
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.29310
- Original
- Read it at the publisher
- Topics
Abstract
In sponsored-shopping auctions, one advertiser may win several positions, and a product that is never displayed may determine the prices of several winners. Under generalized second-price (GSP) pricing without self-pricing, these interactions couple allocation and payment through a single global ranking. We prove that exact autobidding equilibria under budget and return-on-investment (ROI) constraints can be computed in polynomial time whenever either the number $n$ of advertisers or the number $K$ of display slots is fixed. Our algorithms rely on two structural reductions. With few advertisers, the payment polytopes of tied bid layers combine by a Minkowski sum, giving a fixed-dimensional representation of exponentially many rankings. With few slots, budget equilibria admit threshold recovery and an exact submodular description of attainable payments at the display boundary. For ROI, we prove that every group-consecutive equilibrium has a representative with at most $K+2$ nonunit multipliers, preserving the item and price in every displayed slot. In each case, the reduction leads to polynomially many systems of polynomial equations and inequalities in bounded dimension. The algorithms compute exact multipliers and explicit distributions over valid group-consecutive rankings, with support at most $n+1$; for ROI with few slots, this improves to $\min\{n+1,K+3\}$.
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 Computational Complexity
Motivation and Contribution in Open Source Software: A Meta-Analytic Investigation
The Delegation Divide: An Open Index of AI-Agent Delegability across Occupations and Countries
The Customer Is the Builder: How AI Coding Agents Are Rewriting the Economics of Software
Joules-to-GDP: How Much Economic Value Do AI Systems Produce per Unit of Energy?
The Capability Transfer: Cohort Reversal, Codified Expertise, and the Adaptability Tax of AI Transformation
Get the few papers worth your time in Computational Complexity 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.