Computing exact bidding equilibria in sponsored shopping auctions
GSP Autobidding Equilibria with Few Advertisers or Slots
Computer Science and Game Theory
Summary
Sponsored shopping auctions decide which products appear in limited display spots and what prices advertisers pay. The authors show that when either the number of advertisers or the number of slots is small and bidders have budget or ROI constraints, it is possible to compute exact stable bidding strategies efficiently. They develop new mathematical ways to represent possible outcomes and prove that these methods work with systems of polynomial equations. Their work helps understand how complex bidding scenarios can be solved exactly in practical settings.
What this means in practice
- •For advertising platform engineers: Calculate exact bidding equilibria for auctions with few advertisers or slots under budget and ROI constraints to optimize auction design and pricing.
- •For online marketplace operators: Improve auction mechanisms for sponsored product listings where advertisers face financial constraints, enhancing pricing transparency and efficiency.
A theory result. No direct application yet.
Authors
Yiyang Huang, Zhengyang Liu, Yonglei Yan, Zihe Wang
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\}$.