What Is the Computational Complexity of Autobidding Equilibria in GSP Sponsored Shopping?

The answer splits into exact and approximate cases

The paper asks how hard it is to compute an autobidding equilibrium in a GSP sponsored shopping auction, a setting where one bidder may own many items competing for the same slots. The answer depends on whether the target is an exact equilibrium or an approximate one. Computing an exact equilibrium is shown to lie in FIXP, the class for exact fixed points of functions given by algebraic circuits. Computing a γ-approximate equilibrium is shown to be in PPAD, and PPAD-hard when γ is inverse-polynomial in the input size, which makes the approximate problem PPAD-complete at that precision.

Both results are proved separately for the two constraint models the paper studies: budget constraints (ABE-B) and return-on-investment constraints (ABE-R). The earlier work that introduced this auction model treated only the ROI-constrained setting, so the budget-constrained case is new ground here. The paper also shows that equilibria always exist in both models and that some equilibrium always has polynomial-size support over the allocation space, meaning it can be written as a distribution over polynomially many deterministic allocations rather than the exponentially large set of all valid orderings.

Hardness arises inside a single auction

Earlier hardness results for pacing and autobidding equilibria in second-price auctions relied on markets with many parallel auctions, where the difficulty came from interaction across auctions. The paper points out that exact pacing equilibria for second-price auctions are tractable when the number of auctions is constant. That contrast sets up the question this paper answers: can intractability appear within a single GSP sponsored shopping auction?

The paper's reductions show that it can. Because all items enter one global ranking, items from unrelated parts of a reduction can influence the prices a gadget's items pay, and separating nominal value scales does not stop this interference since bidders' multipliers are endogenous. The reductions handle this by ensuring local pricing holds in every approximate equilibrium and by replicating output items so that local price differences dominate both other gadgets' contributions and the permitted approximation error. Both hardness reductions work even when all items are displayed and all click-through rates are equal.

Multiple items per bidder change the payment rule

In classical sponsored search an advertiser typically bids for a single link, so an allocation is a matching of bidders to positions. In sponsored shopping a retailer may promote several products for the same query, so a single bidder can win multiple slots and the allocation assigns bidder-item pairs to positions, with values depending on both the bidder and the item. The paper models this with n bidders, K slots with decreasing click-through rates, and m_i items per bidder whose values are sorted in decreasing order.

The payment rule is GSP without self-pricing: an item pays the next-highest bid in the ranking that belongs to a different bidder, so a bidder's own items cannot set one another's prices. The paper notes this matches the design described by major advertising platforms such as Google Ads, where eligible keywords from the same account do not compete. Autobidding enters through uniform bidding: each bidder picks a single multiplier α_i and bids α_i times the value of each item, rather than choosing a separate bid per item. An autobidding equilibrium is a profile of these multipliers together with a valid randomized tie-breaking rule over allocations.

Some equilibria cannot be written as rational numbers

The paper exhibits instances of GSP sponsored shopping auctions, under budget constraints and under ROI constraints respectively, in which autobidding equilibria must be irrational. That matters for how the exact result should be read: an exact equilibrium may not be representable with rational numbers, so an algorithm that outputs exact rational data cannot cover every instance.

This is why the paper treats approximation as the natural relaxation and why the approximate problem gets its own membership and hardness results. The paper also notes in its discussion that its irrational examples produce equilibrium multipliers involving square roots, but that these examples alone do not give a reduction establishing Square-Root-Sum-hardness for an exact equilibrium comparison problem.

Quantile coupling keeps the support polynomial

The existence proof inherited from the earlier work was nonconstructive: it did not imply that an exact equilibrium can be supported on only polynomially many pure allocations, and it did not even place the approximate problem in TFNP. The paper closes that gap with a construction that represents an allocation as a sequence of group insertions, builds a legal marginal distribution for each insertion, and then uses a common quantile to couple these marginals into a joint distribution over polynomially many permutations and their probabilities.

At every fixed point, each permutation receiving positive probability is bid-consistent. The construction avoids explicitly representing the exponentially large allocation space, which is what makes the polynomial-support guarantee possible in both constraint models. The authors describe this as, to their knowledge, the first use of quantile coupling to establish complexity upper bounds for equilibrium computation, and they expect the technique to apply to other problems where local choice distributions must be coupled into globally feasible outcomes.

Discretizing payments turns exact circuits into PPAD membership

The PPAD membership result for approximate equilibria is obtained by adapting the optimization-gate framework of Filos-Ratsikas et al. Starting from the algebraic circuit used for exact equilibria, the authors replace the nonlinear payment computations with controlled discretizations that admit piecewise-linear implementations. The construction preserves bid consistency and budget or ROI feasibility exactly, while allowing approximation only in the maximal-pacing condition.

The paper describes this as, to its knowledge, the first application of the linear-OPT framework to establish PPAD membership for approximate versions of equilibrium problems that may have only irrational exact solutions. The membership holds when γ is inverse-exponential in the input size, while hardness holds when γ is inverse-polynomial; the gap between those two regimes is where the paper's open questions sit.

Fixed parameters and constant precision remain open

The hardness reductions use growing numbers of bidders, items, and positions with positive click-through rates. That leaves room for polynomial-time algorithms when, for example, the number of bidders, the number of items per bidder, or the number of positive-CTR positions is fixed; the authors conjecture that restrictions of this kind restore tractability, and they point to recent polynomial-time results for exact pacing equilibria in second-price auction markets with a constant number of buyers or goods as promising directions. Any such algorithm would have to accommodate algebraic outputs, since rational equilibria need not exist.

The approximation threshold is also unresolved. The reductions place gates in separate bid intervals whose multiplicative widths are c = 1 + Θ(1/n), which keeps the overall value range bounded but leaves local gaps of only Θ(1/n). Widening the intervals to a constant would create an exponential range of values and, under the current amplification argument, require exponentially many items. So hardness for a constant γ remains open, and the inverse-polynomial hardness rules out an FPTAS unless all PPAD problems admit polynomial-time algorithms; whether either setting admits a PTAS is left open. The exact lower bound is open too: strengthening it to FIXP-hardness would combine with the membership result to give FIXP-completeness.

The practical reading is about precision, not solvability

The most decision-relevant distinction in this paper is between exact and approximate computation, not between the two constraint models. ABE-B and ABE-R receive the same treatment and land in the same places: FIXP membership for exact equilibria, PPAD membership for inverse-exponential precision, and PPAD-hardness for inverse-polynomial precision. A reader comparing the two settings should not expect one to be easier than the other on the basis of these results.

The second distinction is between hardness and infeasibility. PPAD-hardness at inverse-polynomial precision rules out an FPTAS unless all PPAD problems are polynomial-time solvable, but it does not rule out a PTAS, and the paper explicitly leaves that question open. Combined with the polynomial-support guarantee, the picture is that equilibria are plentiful and compactly representable, while computing them to tight precision is as hard as the PPAD-complete problems the reductions start from. The open frontier the authors identify is structural restriction, such as fixing the number of bidders, items per bidder, or positive-CTR positions, rather than a difference between budget and ROI constraints.

Sources used in this answer