GSP Autobidding Equilibria with Few Advertisers or Slots

1 Introduction

• Undisplayed products can set the prices of several displayed products, coupling allocation and payment through the entire ranking.The paper identifies this global-ranking dependence as the central obstacle to equilibrium computation.Source: §1 · p. 1
• Prior work established equilibrium existence and exact-computation membership in FIXP, while approximate computation is PPAD-hard in general [20].These results motivate the paper's search for tractability under structural restrictions.Source: §1 · p. 2
• With few advertisers, tied bid layers combine their payment polytopes by a Minkowski sum, representing exponentially many rankings with polynomially many outcomes.For ROI, the local representation also includes values so expected surplus can be compressed.Source: §1 · p. 2
• With few slots, budget computation uses threshold recovery and a submodular base polytope for payments at an arbitrarily large threshold tie.For ROI, every group-consecutive equilibrium has a representative with at most K + 2 nonunit multipliers preserving each displayed item's identity and price.Source: §1 · p. 2
• Exact ABE-B and ABE-R computation is polynomial time with a fixed number of advertisers or display slots, returning exact multipliers and distributions over valid group-consecutive rankings.The algorithms also apply when the total number of items is fixed.Source: §1 · p. 2
• The four algorithms reduce computation to polynomially many bounded-variable, degree-at-most-two systems, then use exact polynomial feasibility.Support bounds count complete group-consecutive rankings in the equilibrium distribution.Source: §1 · p. 2, Table 1 · p. 3

2.1 Auction Model

• Each advertiser scales all its product values by one multiplier, and the first K items in a complete ranking occupy the display slots.Slots have nonincreasing click-through rates; undisplayed items have zero click-through rate.Source: §2.1 · p. 4
• A displayed item pays the highest lower-ranked bid from a different advertiser, so undisplayed items remain eligible to set its price.The example shows an undisplayed advertiser product setting both displayed prices.Source: §2.1 · p. 4
• Tie-breaking randomizes over complete rankings valid at the multiplier profile, preserving bid order while reordering tied items.The equilibrium object includes both multipliers and a distribution over these rankings.Source: §2.1 · p. 4, §2.2 · p. 5

2.2 Autobidding Equilibria

• ABE-B requires budget feasibility for expected payments under π and αi = 1 when Pi(π, α) < Bi; ABE-R requires nonnegative expected surplus and Ri(π, α) = 0 when αi < A.Source: §2.2 · p. 5

3.1 Multiplier Properties

• Every exact budget equilibrium has strictly positive multipliers, and ROI multipliers are positive by definition.A zero budget multiplier would imply zero payment despite a positive budget, conflicting with maximal pacing.Source: §3.1 · p. 6

3.2 Group-Consecutive Rankings

• Items with the same owner and value form a group, and a group-consecutive ranking keeps each such group in a contiguous block.The search orders groups rather than enumerating item permutations within each group.Source: §3.2 · p. 6
• Every budget and ROI instance admits an exact equilibrium supported on group-consecutive rankings, with any prescribed internal item orders.Reordering within a group preserves prices and advertisers' values and payments.Source: §3.2 · p. 6

4 A Common Geometric Framework

• A bounded parameter vector captures multipliers and, for fixed-slot budgets, a bid threshold; affine bid comparisons partition its domain into cells fixing orders, ties, and endpoint equalities.Within each cell, the reduction represents rankings or their attainable outcomes.Source: §4 · p. 7
• The central step is a polynomial-size description of attainable outcomes and a bound on their dimension, supplied by Minkowski-sum vertices with few advertisers and threshold capacity or multiplier sparsity with few slots.The structural reductions yield polynomially many equilibrium systems in bounded dimension.Source: §4 · p. 7, Figure 1 · p. 7
• Exact polynomial feasibility solves the resulting degree-at-most-two systems in fixed dimension, and recovered solutions specify multipliers and ranking probabilities.Convex-hull compression gives a distribution on at most d + 1 rankings when the required statistic lies in a d-dimensional convex hull.Source: §4 · p. 7

5 Layerwise Convexification with Few Advertisers

• Although independent tie orders can create exponentially many rankings, layerwise convexification represents them through local convex hulls combined by a Minkowski sum.The payment representation uses each layer's order and combines the resulting local payment matrices.Source: §5 · p. 8, §5.1 · pp. 9–10
• For fixed n, exact budget- and ROI-constrained equilibria can be computed in polynomial time.The algorithms return exact solutions for both constraint types.Source: §5.1 · p. 8, §5.2 · p. 12

5.1 Budget Constraints: Compressing Expected Payments

• Q_F is the convex hull of total payment matrices of valid group-consecutive rankings, and multiplying these matrices by fixed α gives exactly the attainable expected payment vectors.This representation lets the budget algorithm replace ranking distributions while preserving expected advertiser payments.Source: §5.1 · p. 10
• At fixed multipliers, every budget-equilibrium distribution can be replaced by at most n + 1 rankings with the same expected advertiser payments.The preserved payments retain the budget equilibrium at the same multiplier profile.Source: §5.1 · pp. 10–11

5.2 ROI Constraints: Compressing Expected Surplus

• For ROI, augmenting local payment matrices with value vectors makes expected surplus attainable as a convex hull, so at most n + 1 rankings preserve all ROI conditions at fixed multipliers.The reduction preserves surplus even when expected values and payments change separately.Source: §5.2 · pp. 12–13

6 Boundary Structure with Few Slots

• Few slots do not bound advertisers or eliminate the effect of undisplayed items, so restricting attention to displayed products cannot capture their price-setting role.The method therefore works from the display boundary to identify the coordinates and outcomes needed by the constraints.Source: §6 · pp. 14–15

6.1 Budget Constraints: Threshold Recovery and Capacity

• For fixed K, threshold recovery and bounded payment representations give a polynomial-time algorithm for an exact ABE-B.The Kth-highest bid determines all but at most K −1 multipliers; the resulting equilibrium systems have at most 2K + 1 variables and degree at most two.Source: §6.1 · pp. 15, 17
• For a large threshold tie, attainable expected payments are exactly described by a capacity polytope with submodular subset constraints.The function Φ bounds the click-through rate each advertiser subset can receive; after accounting for budget intervals, only subsets U with q(U) < r need testing.Source: §6.1 · pp. 19–20
• Any feasible threshold-payment vector can be realized constructively by a short distribution over threshold-group orders, using at most |T| orders.This exact capacity description preserves attainable payments without enumerating all possible orders of a large threshold tie.Source: §6.1 · pp. 20–21
• Threshold-payment recovery decomposes a feasible expected payment vector into at most e threshold orders in polynomial time.The decomposition uses the capacity polytope; budget intervals constrain the recovered expectation, not each order.Source: §6.1 · pp. 21–22
• For fixed K, candidate feasibility uses at most 2K variables and degree-two conditions, and an exact solution can be found in polynomial time.Threshold-payment coordinates are eliminated, leaving a system whose dimension depends only on K.Source: §6.1 · p. 22
• For fixed K, the budget algorithm computes an exact equilibrium in polynomial time and returns a distribution supported on at most n + 1 rankings.Its total running time is O(M^O(K^3)).Source: §6.1 · pp. 23–24

6.2 ROI Constraints: Sparse Nonunit Multipliers

• For fixed K, exact ABE-R computation is polynomial-time and returns at most K + 2 nonunit multipliers with support at most min{n + 1, K + 3}.The sparse representative preserves the item, value, and price in every displayed slot of every supported ranking.Source: §6.2 · pp. 24, 26
• Two below-threshold owner witnesses, or a universal threshold witness when e > r, preserve displayed prices while selected multipliers are lowered to one.The transformation rearranges undisplayed groups while preserving displayed items and prices slot by slot.Source: §6.2 · pp. 25–27
• Recovery completes the multiplier profile and expands weighted group orders into at most s + 1 ≤ min{n + 1, K + 3} rankings.The sampled probabilities already determine the distribution, so no separate threshold-payment recovery or decomposition is needed.Source: §6.2 · p. 28
• Every algebraic solution gives an exact ABE-R, and each sparse equilibrium yields a feasible candidate system through canonical prefix completions and surplus compression.The candidate system enforces ROI conditions on the selected advertisers; surplus is zero outside that set.Source: §6.2 · p. 28
• For fixed K, candidate systems have at most 2K+5 variables and degree at most two, enabling polynomial-time exact feasibility.Each system also has O(M^2 + K) conditions; the exact-feasibility bound applies to the total search.Source: §6.2 · p. 28
• The algorithms compute exact algebraic multipliers and explicit distributions over valid rankings, using the structural principles established for few advertisers and few slots.Every advertiser owns at least one item, so n ≤ M.Source: §6.2 · p. 28

• Exact budget and ROI autobidding equilibria are computable in polynomial time when either advertiser count or display-slot count is fixed.Source: §7 · p. 29
• The reductions use layerwise convexification for few advertisers and boundary-based methods for few slots, with explicit distributions over complete valid rankings.Source: §7 · p. 29
• Fixed products per advertiser while both advertiser and slot counts grow remains a natural next question.Resolving this regime would further clarify how catalog size and ownership structure contribute to the complexity of one global ranking.Source: §7 · p. 29

• The authors say the research questions, algorithmic approaches, and main mathematical insights originated from their own work without AI assistance.Source: AI Usage Disclosure · p. 29
• GPT-6.1-SOL assisted with checking derivations, definitions, notation, proof presentation, figures, exposition, and LATEX source.Source: AI Usage Disclosure · p. 29
• The authors report independently reviewing and verifying the model’s suggestions and take responsibility for the final manuscript’s accuracy and integrity.Source: AI Usage Disclosure · p. 29