Source-linked AI summary
Complexity of Autobidding Equilibria in GSP Sponsored Shopping
Kristoffer Arnsfelt Hansen, Yuhao Li, Xinhao Nie
TL;DR
Earlier work established equilibrium existence for GSP sponsored shopping auctions, but left open the computational complexity of finding equilibria and whether the difficulty could arise within one auction. This paper develops constructions and reductions for budget and ROI constraints, establishing complexity bounds for exact and approximate computation and polynomial-size support. It also identifies constant-precision hardness as an open direction.
Problem
Prior existence results left open whether equilibria in GSP sponsored shopping auctions could be computed with meaningful complexity bounds, including when the setting is a single auction.
Source: §1 · pp. 2–3Method
The paper uses quantile coupling for polynomial-support equilibria, piecewise-linear discretizations for approximate-equilibrium membership, and price-amplifying reductions for hardness.
Source: §1.1 · pp. 3–4Results
For both ABE-B and ABE-R, exact equilibrium computation is in FIXP, approximate computation is PPAD-complete at inverse-polynomial precision, and equilibria admit polynomial-size support.
Source: §1.1 · p. 3, §7 · p. 36Takeaways & Limitations
The authors expect quantile coupling to be useful in other equilibrium and allocation problems where local choice distributions can be coupled into globally feasible outcomes.
Source: §7 · p. 36The reductions establish hardness only at inverse-polynomial precision; whether approximate-equilibrium computation is PPAD-hard for any constant precision remains open.
Source: §7 · p. 36
Abstract
from arXiv · showhide
We revisit autobidding equilibria in GSP sponsored shopping auctions, recently proposed and studied in D\"utting 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.
1 Introduction
Sponsored shopping auctions allocate multiple bidder–item pairs across slots, creating a combinatorial GSP setting for autobidding. This paper asks how hard it is to compute equilibria in that setting and gives complexity results for both budget and ROI constraints.
1 Introduction
- Sponsored shopping assigns bidder-item pairs to slots, and GSP without self-pricing prices an item using the next relevant bid from another bidder.A retailer may win multiple slots with different products for the same query.Source: §1 · p. 2
- Prior work introduced the model and showed equilibrium existence and a half-optimal-welfare guarantee, but its existence proof did not provide a computational upper bound.The earlier study focused on ROI constraints, while this paper addresses both ROI and budget constraints.Source: §1 · p. 2, §1.1 · p. 3
- A single GSP sponsored shopping auction has computational hardness from its within-auction combinatorial structure, not interactions across multiple auctions.All items share one ranking, so items from unrelated gadgets can affect prices.Source: §1 · p. 3
1.1 Our results
- Exact autobidding equilibrium computation is in FIXP for both budget-constrained and ROI-constrained settings.The paper also proves approximate-equilibrium computation is in PPAD at inverse-exponential precision and PPAD-hard at inverse-polynomial precision.Source: §1.1 · p. 3
- The paper exhibits instances with only irrational equilibria under both constraint models, motivating the study of approximate equilibria.The authors frame this as a central question about computational complexity.Source: §1 · p. 2, §1.1 · p. 3
- The paper's methods use quantile coupling to construct polynomial-support equilibria and controlled piecewise-linear discretizations for approximate-equilibrium membership.The hardness reductions also amplify local price differences to handle global price interactions.Source: §1.1 · pp. 3–4
2 Preliminaries
The preliminaries define the multi-item position-auction setting, its GSP allocation and no-self-pricing payment rules, and the autobidding equilibrium concepts used for budget and ROI constraints.
2 Preliminaries
- Each bidder has multiple value-sorted items, and slot click-through rates scale item values, with zero click-through rates assigned to positions beyond the available slots.The model assumes positive values and decreasing click-through rates across the K slots.Source: §2 · p. 4
2.1 GSP without self-pricing
- GSP ranks items by bids and assigns them to slots in that order, while each item’s price is based on the next-highest bid from another bidder.Randomized tie-breaking is allowed; total bidder payments aggregate payments across their items.Source: §2.1 · pp. 4–5
2.2 Autobidding and equilibria
- Uniform bidding scales each item’s true value by one bidder-specific multiplier; under budget constraints, an autobidding equilibrium uses multipliers in [0,1], bid-consistent allocations, and expected payments no greater than budgets.Source: §2.2 · pp. 5–6
- In both equilibrium models, a bidder whose constraint is sufficiently slack must use the maximal multiplier under the corresponding exact or approximate pacing condition.Approximate ABE-B and ABE-R relax maximal pacing using a γ-margin while retaining bid consistency and feasibility.Source: §2.2 · p. 6
3 Technical overview
The technical overview constructs polynomial-support allocation distributions and fixed-point circuits for equilibrium computation, then reduces Pure-Circuit to establish PPAD-hardness for both constraint models.
3 Technical overview
- Grouping equal-valued items and inserting groups at legal bid-order positions yields fixed-point allocation constructions with polynomial-size support.Quantile coupling combines insertion marginals into a joint distribution using O(T^2) cumulative entries for T groups.Source: §3 · p. 7
- The circuit tracks item positions to compute supported allocations’ GSP payments and expected payments and valuations, then adjusts multipliers according to constraint slack or violation.The position and payment calculations feed the multiplier updates in the fixed-point construction.Source: §3 · p. 7
- For PPAD membership, discretizing probability-weighted variable payments preserves feasibility and approximate maximal pacing, with polynomial encoding precision even for inverse-exponential γ.Budget-case error is bounded by γB_i; ROI-case error is bounded by γV_i.Source: §3 · p. 7
- The hardness reduction encodes Pure-Circuit gates as multiplier constraints, separates gate price scales with guard bidders, and replicates output items to amplify payment differences.The budget and ROI constructions use their respective feasibility and pacing conditions to implement gate behavior.Source: §3 · pp. 7–8
- Any γ-approximate autobidding equilibrium can be transformed in polynomial time into a feasible solution of the corresponding Pure-Circuit instance.The reduction establishes local correctness for every gate type under both budget and ROI constraints.Source: §3 · pp. 7–8
4 FIXP-membership
The section develops fixed-point arguments for FIXP membership in autobidding equilibria, constructing bid-valid randomized allocations and expected GSP payments. It verifies equilibrium conditions in the budget and ROI settings and establishes a structural property of exact equilibria in both.
4 FIXP-membership
- The construction groups each bidder’s items by distinct value, with each group having a common value and multiplicity.Each group is treated as a block in the randomized allocation.Source: §4 · p. 8, §4.1 · p. 9
4.1 Group Allocations
- The quantile coupling preserves the insertion marginals and yields a randomized allocation supported on at most Q = O(T^2) deterministic group allocations.When the insertion marginals are supported on legal positions, the resulting allocation is bid-valid.Source: §4.1 · pp. 11–12
4.2 GSP Payments
- For each allocation in the mixture, the circuit identifies the next bid from another bidder, retrieves item CTRs, and computes exact expected GSP payments.Groups are contiguous blocks, so all items in a group share its per-click price; aggregating payments gives each bidder’s expected payment under the randomized allocation.Source: §4.2 · p. 14
4.3 Fixed Point in Budget Case
- At a fixed point of the full circuit, the multiplier profile and randomized allocation form an ABE-B equilibrium.The construction ensures the allocation is bid-valid, computes each bidder’s expected GSP payment, and keeps each multiplier in [0, 1].Source: §4.3 · pp. 14–15
- In the budget case, a fixed point satisfies each bidder’s budget constraint and maximal-pacing condition, yielding an ABE-B.The argument shows that payments cannot exceed budgets and that a bidder with payment below budget must have multiplier 1.Source: §4.3 · p. 15
4.4 Fixed Point in ROI case
- In the ROI case, the fixed-point argument verifies ROI feasibility and maximal pacing when a bidder’s valuation exceeds payment.If expected payment exceeded valuation, the multiplier update would contradict the fixed-point identity; if valuation exceeds payment, the multiplier must equal A.Source: §4.4 · p. 15
- In both budget- and ROI-constrained settings, an exact equilibrium exists with each bidder’s equal-value items consecutive in every supported deterministic allocation.The construction orders groups and expands each group into its items in a fixed internal order.Source: §4.4 · p. 15
5 PPAD-membership
Rational instances in both constraint models can have only equilibria with irrational pacing multipliers, obstructing PPAD membership for exact equilibrium computation under standard rational representation. The section establishes PPAD membership for approximate equilibria in both the budget and ROI settings.
5.1 Instances with Only Irrational Equilibria
- Rational instances exist in both ABE-B and ABE-R where every equilibrium has an irrational pacing multiplier, so exact equilibrium computation is not in PPAD under standard rational representation.These examples motivate considering approximate equilibria instead.Source: §5.1 · pp. 16–17
5.2 Approximate Equilibria in Budget case
- For every rational 0 < γ < 1 with polynomial encoding length, a polynomial-time circuit construction has fixed points inducing γ-approximate ABE-B.The construction works for constant, inverse-polynomial, and inverse-exponential approximation parameters.Source: §5.2 · p. 20
5.3 Approximate Equilibria in ROI case
- For every rational 0 < γ < 1 with polynomial encoding length, a polynomial-time circuit construction has fixed points inducing γ-approximate ABE-R.Source: §5.3 · p. 21
6 PPAD-hardness
This section establishes PPAD-hardness for approximate ABE-B and ABE-R by reducing from Pure-Circuit and showing how equilibria encode circuit solutions. The reductions use multiplier bounds and gate gadgets, with the ABE-R analysis ensuring boolean outputs and satisfaction of the specified gate constraints.
6.1 The Pure-Circuit problem
- Pure-Circuit with gates {NOT, NOR, NPURIFY} is PPAD-complete even when each node is the input of exactly one gate, NPURIFY gates are nonconsecutive, and each gate has distinct input and output nodes.Source: §6.1 · p. 23
6.2 PPAD-hardness for ABE-B
- In any γ-approximate ABE-B, each real agent’s multiplier lies in [c^−1, 1].Source: §6.2 · p. 25
- For γ ≤ 32/(1000n + 42), every feasible γ-approximate autobidding equilibrium in the constructed auction decodes, via Equation (4), to a feasible solution of the given Pure-Circuit instance.The decoding maps αv ≤ c^−1/3 to 0, αv = 1 to 1, and other values to ⊥; decoded values satisfy the NPURIFY constraint.Source: §6.2 · pp. 24, 26, 27
6.3 PPAD-Hardness of Computing ABE-R
- If K ≥ nm and two agents have identical valuations with v_i,m = 2v_i,m−1 > 0, both multipliers are at most 2 in every γ-approximate ABE-R.The bound uses ROI feasibility alone and holds for any γ > 0.Source: §6.3 · pp. 27–28
- With at least nm slots, any q ≥ 2 identical-valuation agents whose final value is q/(q−1) times the preceding value have multipliers at most q/(q−1) in every approximate ABE-R.The bound uses ROI feasibility alone, so it holds for every approximation parameter γ > 0, without requiring maximal pacing.Source: §6.3 · pp. 28–29
- The reduction makes each circuit vertex a real agent, adds items according to its gate roles, and uses 128n + 129 identical auxiliary agents to create guard bids between levels.All click rates are 1, there are more slots than items, and the constructed item values have polynomial encoding length.Source: §6.3 · pp. 30–31
- For an output block of k items valued c^(i+1/2), every feasible ABE-R satisfies α_u v_out ≤ λc^(i+1), implying 1 ≤ α_u ≤ λc^(1/2) ≤ c^(1/2+1/128).This bound controls real bidders’ multipliers and supports separation of bids across levels.Source: §6.3 · p. 31
- Guard bids keep bids from different levels separated, so output-item prices depend only on corresponding gate inputs and support the gate-by-gate correctness proof.The proof treats NOT, NOR, and NPURIFY gates; no two NPURIFY gates are consecutive.Source: §6.3 · pp. 32–35
- For γ ≤ 1/(256n), the reduction is correct, and every feasible approximate ABE-R encodes a feasible Pure-Circuit solution.The assignment is extracted by classifying each real agent’s scaled multiplier using thresholds c^(3/16) and c^(1/2), with an intermediate value decoded as ⊥.Source: §6.3 · pp. 30, 31, 33
- Thus at least one output is boolean, satisfying all NOT, NOR, and NPURIFY constraints and establishing the reduction’s correctness.Source: §6.3 · p. 35
7 Conclusion
The paper establishes computational-complexity results for budget- and ROI-constrained autobidding equilibria, while leaving questions about exact hardness, tractable restrictions, and constant-approximation hardness open. It also describes how AI tools contributed during revisions.
7 Conclusion
- Both constraint settings admit FIXP membership for exact computation, PPAD-completeness for approximate computation at inverse-polynomial precision, and equilibria supported on polynomially many deterministic allocations.The support guarantee uses quantile coupling to combine legal insertion marginals within PL pseudo-circuits.Source: §7 · p. 36
- The authors leave open whether exact-equilibrium hardness can be strengthened to FIXP-hardness, noting that their constructions do not yet encode a sum-of-square-roots comparison in every equilibrium.They identify Square-Root-Sum-hardness for an associated exact equilibrium comparison problem as a possible first step.Source: §7 · p. 36
- The reductions use growing numbers of bidders, items, and positive-CTR positions, leaving open whether fixing any of these quantities permits efficient computation.The authors conjecture that suitable structural restrictions restore polynomial-time tractability.Source: §7 · p. 36
- Whether approximate-equilibrium computation remains PPAD-hard for any constant γ > 0 remains open.Current reductions use local gaps of Θ(1/n); constant-width intervals would create an exponential range and, under the current amplification argument, require exponentially many items.Source: §7 · p. 36
AI Usage Disclosure
- An earlier version was developed without AI assistance; during revisions, ChatGPT-6 Astra helped identify quantile coupling and assisted with exposition and LATEX, while the authors retained responsibility for the mathematical claims.The revised allocation construction avoids the earlier requirement that each bidder’s items have pairwise distinct values.Source: AI Usage Disclosure · pp. 36–37
A Remarks on Multiplier Cap
The multiplier cap is a bounded representation of equilibria rather than an additional economic parameter. The computational task formalizes a sufficiently large cap and seeks an equilibrium representation that remains valid as the cap increases.
A Remarks on Multiplier Cap
- The cap bounds the equilibrium representation; specifying only an unspecified “sufficiently large” value leaves unclear which capped-equilibrium output the computational task requires.The paper frames A as a representation device, not an additional auction parameter.Source: A Remarks on Multiplier Cap · p. 39
- The intended output at a suitable A0 represents equilibria for every A ≥ A0, with the same allocation distribution and non-endpoint multipliers while endpoint multipliers track the cap.Lemma A.1 states that the equilibria retain the same approximation parameters.Source: A Remarks on Multiplier Cap · p. 39
- Hardness reductions cannot use a prescribed cap to calibrate auction parameters or separate gadget bids, so the necessary multiplier bounds must follow from the constructed auction’s equilibrium conditions.The authors state that this makes the hardness proof more technically demanding.Source: A Remarks on Multiplier Cap · p. 40