betaFeedback

WorksComputer Science

FIXP-Completeness in Second-Price Auctions

Abstract

Computing equilibria is a fundamental algorithmic problem in game theory and economics. Although general frameworks are available for proving membership in FIXP, the class capturing exact fixed-point computation, establishing FIXP-completeness often remains challenging. We prove FIXP-completeness of exact equilibrium computation in three second-price auction models: (1). pacing with return-on-investment constraints, with multiplier cap 1+δ1+δ for every fixed rational δ>0δ>0 [Filos-Ratsikas, Hansen, Høgh, and Hollender (2024)]; (2). budget-constrained generalized second-price sponsored shopping [Hansen, Li, and Nie (2026)]; (3). budget-constrained throttling [Liu (2026)]. These results resolve open questions on the exact complexity of automated bidding. Our technical ingredient is a FIXP-complete generalized-circuit problem using only clipped affine gates and the reciprocal x↦1/(1+τx)x\mapsto1/(1+τx), for any fixed positive rational ττ. This gate basis provides a common framework for the three auction reductions: simulating these gates in each model establishes FIXP-hardness without directly implementing multiplication or squaring.

Introduction

How difficult is it to find a solution that is guaranteed to exist? Fixed-point theorems guarantee equilibria and stable outcomes in many models, but do not by themselves provide efficient algorithms for finding them. The class PPAD [37] is central to the complexity of approximate equilibrium computation [7, 26]. Exact computation poses an additional issue: solutions can be irrational even when the input is rational. The class FIXP [22] captures exact fixed-point computation using algebraic circuits. A FIXP-completeness result identifies a problem as having the full computational difficulty of this class. See § 1.4 for further background on fixed-point complexity and equilibrium computation in auctions.

General frameworks establish membership in FIXP and PPAD for broad families of equilibrium problems [25, 26], but proving hardness for these classes can remain difficult. For example, the Hylland–Zeckhauser assignment mechanism has a PPAD-complete approximation problem [39, 6], while exact computation belongs to FIXP and its FIXP-hardness remains open [39]. Neither hardness of approximation nor the existence of irrational solutions supplies the reduction needed to prove FIXP-hardness.

A standard starting point for proving hardness is a generalized-circuit problem [7, 38, 4, 24]. A generalized circuit is a system of gate equations whose input dependencies may contain directed cycles, as illustrated in Figure 1. Each variable is the output of exactly one gate and may be used as an input by multiple gates. Each gate applies an operation to its inputs, usually one or two, and the task is to assign values xi∈[0,1]x_i \in[0,1] satisfying all gate equations simultaneously.1 To use a generalized-circuit problem in a hardness reduction, we construct an equilibrium instance in polynomial time and specify how to recover a circuit solution from every equilibrium. Known FIXP-complete gate sets include quadratic functions such as multiplication (u,v)↦uv(u,v) \mapsto uv, squaring u↦u2u \mapsto u^2 [24 Proposition 5.6], and the shifted product (u,v)↦(u+1)(v+1)/4(u,v) \mapsto(u+1)(v+1)/4 [24 Lemma 5.7]. By contrast, piecewise-linear functions that consist of affine operations and min, max characterize PPAD through Linear-FIXP = PPAD [22].

Two generalized circuits with the same dependency graph

Figure 1. Two generalized circuits with the same dependency graph, using (a) a standard FIXP-complete basis [24 Proposition 5.6] and (b) clipped affine and reciprocal gates from (1). An arrow xj→xix_j \to x_i means that gate ii uses xjx_j as an input; all variables lie in [0,1][0,1].

For approximate problems, a reduction can replace a nonlinear operation by a piecewise-linear approximation if the resulting error stays within the allowed error bound [17, 7]. An exact reduction must enforce the gate equation with zero error. Constructing equilibrium conditions that enforce multiplication or squaring can therefore require a separate argument for each target model [22, 24], making FIXP-hardness difficult to establish. This motivates the following question:

Can we prove FIXP-completeness of equilibrium problems without directly implementing quadratic functions in each target model?

We answer this question affirmatively using generalized circuits with reciprocal gates. Fix a rational τ>0\tau> 0 and write [t]=min⁡{1,max⁡{0,t}}[t] = \min\{1,\max\{0,t\}\}. An instance specifies one equation for each of NN variables x1,…,xN∈[0,1]x_1,\ldots,x_N \in[0,1], of either form

xi=[aixj+bixk+ci]orxi=11+τxji,(1)x_i = [a_i x_j + b_i x_k + c_i] \quad\text{or} \quad x_i = \frac{1}{1+\tau x_{j_i}}, \tag*{(1)}

where the coefficients are binary-encoded rationals and the input indices belong to [N]={1,…,N}[N] = \{1,\ldots,N\}. The right-hand sides define a continuous self-map of [0,1]N[0,1]^N, so a solution exists by Brouwer’s fixed-point theorem. Figure 1 compares a four-gate instance over a standard FIXP-complete gate set with a four-gate instance over our gate set.

Theorem 1.1 (see also Theorem 4.2). For every fixed rational τ>0\tau> 0, finding an exact solution of a generalized circuit using only the gates in (1) is FIXP-complete.2

We apply Theorem 1.1 to automated bidding, where software chooses bids or participation probabilities while satisfying advertisers’ financial constraints. Computing equilibria in these markets is central to predicting bidding behavior and evaluating revenue and welfare. The complexity of this task also helps assess whether automated bidding procedures can reach stable outcomes efficiently.

In a second-price auction for a single item, the highest bidder wins and pays the highest competing bid, or zero if there is no competing bidder. When a bidder seeks to maximize its value for the item minus its payment and faces no financial constraint, bidding its value is optimal regardless of the other bids [40]. This removes the need to predict competitors’ bids, unlike a first-price auction, where the winner pays its own bid.

The models involve multiple items and financial constraints that apply across items. Spending on one item can therefore affect how much a bidder can spend on others. Thus bidding one’s value for each item is not necessarily optimal under these constraints. This makes equilibrium computation more challenging.

We study three second-price auction models: pacing in separate second-price auctions with return-on-investment (ROI) constraints [34, 26], budget-constrained autobidding in generalized second-price (GSP) sponsored shopping [28], and budget-constrained throttling in second-price auctions [8, 35]. Prior work explicitly poses exact FIXP-completeness as an open question for each model [26, 28, 35]. Using our reciprocal-gate framework based on Theorem 1.1, we resolve these questions by proving FIXP-completeness for all three problems.

Pacing Equilibria in ROI-constrained Auctions

In this model [34, 26], each bidder assigns a value to each advertising opportunity (item) and seeks to maximize the total value it acquires. Its ROI constraint requires this total value to be at least a specified positive multiple of its total payment. We consider the case in which total payment is at most total acquired value.

Pacing controls all of a bidder’s bids through one scalar, its multiplier, so it can adjust its bidding across items to meet its financial constraint. Here each bidder chooses its own multiplier between one and the cap 1+δ1+\delta, for a fixed rational δ>0\delta> 0, and multiplies its value for every item by that same factor to obtain its bids. Each item is allocated among its highest bidders at the second-highest bid, with tied bidders allowed to share the item and pay in proportion to their shares. At a second-price ROI pacing equilibrium, each bidder’s total payment is at most the value of its allocation, and any bidder whose payment is less than that value uses multiplier 1+δ1+\delta. The task is to find the multipliers and allocation from the bidders’ values.

Li and Tang [34] prove PPAD-hardness of approximate equilibrium computation even for constant approximation parameters. For exact computation, Filos-Ratsikas, Hansen, Høgh, and Hollender [26], § 7 prove FIXP-membership and give rational instances in which every equilibrium has an irrational multiplier. They explicitly ask whether exact equilibrium computation is FIXP-complete. The following theorem answers this question for cap 1+δ1+\delta with any fixed rational δ>0\delta> 0.

Theorem 1.2 (Informal). For every fixed rational δ>0\delta> 0, computing an exact second-price ROI pacing equilibrium with cap 1+δ1+\delta from the bidders’ values is FIXP-complete.

The formal model and proof appear in § 5 (Definition 5.1 and Theorem 5.2).

Autobidding Equilibria in Sponsored Shopping

In sponsored shopping [20, 28], sellers bid to have their products displayed in advertising positions (slots), for example alongside shopping search results. Each bidder is a seller and may own several products, called items, so it can occupy several slots. An item’s value is its seller’s value for a click on its advertisement. The seller’s budget limits its expected total payment. An autobidder chooses bids for a seller using a multiplier between zero and one: it multiplies the values of all the seller’s items by that same factor.

Items are ranked in nonincreasing order of bids, and the highest-ranked items fill the available slots. The generalized second-price (GSP) rule extends second-price pricing to ranked advertising positions [21]. In the sponsored-shopping model, an item’s price is the first lower-ranked bid belonging to a different seller, or zero if no such item exists; other items of the same seller are skipped. We consider one slot per item, with all items displayed and each item’s payment equal to its price.3

A budget-constrained autobidding equilibrium consists of multipliers and a possibly randomized ordering of items with equal bids. Each bidder’s expected total payment, averaging over this ordering, must be at most its budget, and any bidder with unused budget must use multiplier one. The task is to find multipliers for which ties can be resolved to satisfy these conditions, given item ownership, values, and bidder budgets.

Hansen, Li, and Nie [28] prove FIXP-membership for exact equilibrium computation and PPAD-completeness for inverse-polynomial approximation, under both budget and ROI constraints. They also give rational instances in which every exact equilibrium has an irrational multiplier. They explicitly ask whether exact equilibrium computation is FIXP-hard [28 Section 7]. The following theorem answers this question for the budget-constrained model.

Theorem 1.3 (Informal). With one slot per item and all click-through rates equal to one, computing a multiplier vector of an exact budget-constrained autobidding equilibrium in GSP sponsored shopping from item ownership, values, and bidder budgets is FIXP-complete.

The formal model and proof appear in § 6 (Definition 6.1 and Theorem 6.2).

Throttling in Second-Price Auctions

In throttling [8], each bidder has fixed bids for the items and a positive budget. Each bidder, or an algorithm acting on its behalf, chooses a participation probability between zero and one to control its expected spending. With this probability, the bidder participates in the auctions for all items; otherwise, it participates in none. Participation decisions are independent across bidders. Each item is sold by the second-price rule among participating bidders. At an exact second-price throttling equilibrium, each bidder’s expected total payment is at most its budget, and any bidder with unused budget participates with probability one. The task is to find these participation probabilities from the bids and budgets.

Chen, Kroer, and Kumar [8] prove FIXP-membership for exact equilibrium computation and PPAD-completeness for approximation with a sufficiently small constant error parameter. They also give rational instances in which every exact equilibrium has an irrational participation probability. Liu [35] extends the approximation-hardness result to every fixed error parameter in (0,1)(0, 1) and explicitly asks whether exact equilibrium computation is FIXP-complete [35 Section 6]. The following theorem answers this question.

Theorem 1.4 (Informal). Computing an exact budget-constrained throttling equilibrium in second-price auctions is FIXP-complete, even when each item has at most three positive bids and these bids are pairwise distinct.

The formal model and proof appear in § 7 (Definition 7.1 and Theorem 7.2).

Background and Related Work

PPAD, FIXP, and Equilibrium Computation Nash’s theorem guarantees that every finite game has a mixed Nash equilibrium, but does not provide an efficient algorithm for finding one. This motivates the study of total search problems, in which every valid input has a solution: the challenge is finding a solution, rather than deciding whether one exists. Papadimitriou [37] introduced PPAD to study a class of discrete total search problems arising from constructive fixed-point arguments.

Chen, Deng, and Teng [7] prove PPAD-completeness of exact Nash equilibrium computation in rational two-player games. Approximation hardness has also been studied extensively, from exponentially small and inverse-polynomial additive error [17, 7] to constant error under several game models and approximation notions [16, 38, 18].

Beyond Nash equilibria, PPAD-completeness results span competitive markets [12], one-sided matching [6], fair division and cake cutting [32], and first- and second-price auctions [24, 9]. These results concern exact or approximate solutions, depending on the model.

Exact computation presents an additional issue: rational games with three or more players may have only irrational equilibria. To study the complexity of computing such solutions exactly, Etessami and Yannakakis [22] introduced FIXP. Its defining task is to find x=F(x)x = F(x) for a continuous self-map of a compact rational polytope, represented by a circuit using rational constants and arithmetic operations; see Definitions 3.1 and 3.2 for the formal definition and reductions. Their central result is that computing an exact mixed Nash equilibrium of a three-player finite game is FIXP-complete. They also prove that the piecewise-linear restriction of FIXP equals PPAD, connecting exact nonlinear fixed-point computation to its piecewise-linear counterpart. For more details on the fixed-point foundations of PPAD and FIXP, see the survey by Yannakakis [42].

Beyond finite games, FIXP-completeness results span competitive markets [27], Bayesian first-price auctions [24], and envy-free cake cutting with general valuations and computational versions of topological existence theorems [25]. Further connections between fair division and topology include FIXP-hardness for exact consensus halving and the Borsuk–Ulam problem [19].

Important open FIXP-completeness questions span matching, markets, and fair division. Examples include exact equilibrium computation for the Hylland–Zeckhauser mechanism for one-sided matching [31, 39], exact equilibrium computation in Arrow–Debreu exchange markets with constant-elasticity-of-substitution (CES) utilities [12], and contiguous envy-free cake cutting with additive valuations represented by algebraic circuits [25].4 In each case, FIXP-membership is known, while the cited works leave FIXP-hardness open. Our reciprocal-gate framework does not resolve these questions.

The membership side has a more general methodology. Filos-Ratsikas, Hansen, Høgh, and Hollender [25, 26] show how to incorporate suitably represented convex optimization problems into fixed-point constructions, obtaining FIXP-membership and, under additional conditions ensuring suitable rational solutions, PPAD-membership. Our contribution concerns the complementary hardness direction: a restricted nonlinear gate basis that can be implemented through auction equilibrium conditions.

First-Price Auctions In a first-price auction, bidders trade off the probability of winning against the payment upon winning. With private information, a pure Bayes–Nash equilibrium specifies a bid as a function of each bidder’s private value, maximizing expected utility given its beliefs and the other bidding functions. For further background on auction theory and equilibrium bidding, see Klemperer’s survey [33]. Filos-Ratsikas, Giannakopoulos, Hollender, Lazos, and Poças [24] prove PPAD-completeness for approximate and FIXP-completeness for exact equilibrium computation in a Bayesian first-price auction model. Further PPAD-completeness results concern approximation with common priors and an input-specified tie-breaking rule [13], and approximate mixed equilibria with discrete values and bids under subjective priors [23] or a correlated common prior [5].

Under budget constraints, first-price pacing has unique equilibrium multipliers, computable in polynomial time through an Eisenberg–Gale convex program [14]. First-price throttling has a unique equilibrium and admits polynomial-time approximation, although the exact equilibrium may be irrational [8].

Second-Price Auctions and Autobidding For budget-constrained second-price pacing, Conitzer, Kroer, Sodomka, and Stier-Moses [15] establish existence and show that selecting a welfare- or revenue-maximizing equilibrium is NP-hard. Chen, Kroer, and Kumar [9] prove that finding any equilibrium is PPAD-complete, for both exact computation and inverse-polynomial approximation. An exact equilibrium with rational coordinates of polynomial bit length always exists. Chen and Li [10] strengthen the hardness result to constant approximation, and Liu [35] gives tight bounds. Polynomial-time algorithms are known when either the number of bidders [41] or the number of goods [30] is constant.

For ROI-constrained autobidding in sponsored shopping, Dütting, Li, Paes Leme, Spendlove, and Teng [20] establish existence and welfare guarantees. Our result in Theorem 1.3 concerns budget constraints; the FIXP-hardness of computing an exact ROI-constrained equilibrium remains open [28].

The use of multipliers is also supported by results on optimal bidding. In second-price auctions, an ROI-constrained bidder facing fixed competing bids can maximize its total acquired value using a multiplier, provided it may choose its share of each item on which it ties for the highest bid [34 Proposition 1]. Related work studies optimal bidding and welfare under more general financial constraints [2], and algorithms that jointly handle budget and ROI constraints [3]. For models with continuously distributed values, convergence guarantees for pacing and throttling have been obtained under smoothness and tail conditions [11]. For a broader survey of autobidding algorithms, equilibria, and auction design, see [1].

Proof Overview

The Challenge of Exact Gate Simulation

Approximate gate constraints can already capture PPAD-hardness using only piecewise-linear functions, meaning functions that are affine on each of finitely many regions. For example, for some fixed δ>0\delta> 0, finding values in [0,1][0, 1] that satisfy every gate equation within additive error δ\delta is PPAD-complete even with only u↦1−uu \mapsto1-u and (u,v)↦min⁡{1,u+v}(u,v) \mapsto\min\{1,u+v\} [24 Proposition 5.5]. Adding u↦u2u \mapsto u^2 makes the exact version FIXP-complete [24 Proposition 5.6]. This distinction also appears in the characterization Linear-FIXP = PPAD of Etessami and Yannakakis [22 Section 5]: restricting FIXP circuits to rational affine operations and min⁡,max⁡\min,\max gives precisely PPAD. Thus requiring zero error in a piecewise-linear circuit problem does not by itself establish FIXP-hardness.

The second-price rule does not directly supply the missing nonlinear arithmetic. For n≥2n \ge2, the second-highest bid, counting tied bids separately, satisfies

2ndmax⁡(b1,…,bn)=max⁡1≤i<j≤nmin⁡{bi,bj}.\operatorname{2ndmax}(b_1,\ldots,b_n)=\max_{1\le i<j\le n}\min\{b_i,b_j\}.

This is piecewise-linear, and any finite composition of this operation with affine operations remains piecewise-linear. It therefore cannot compute u2u^2 or uvuv exactly on the whole input domain. A reduction must use the full equilibrium conditions to enforce such relations, rather than only compose the operations that determine prices.

A related obstacle is explicit in the first-price auction reduction of [24 Section 5.2]: it is “unclear how to simulate a G+G_+-gate or a G×G_\times-gate,” referring to clipped addition and multiplication. That reduction instead implements ϕ(u,v)=(u+1)(v+1)/4\phi(u,v)=(u+1)(v+1)/4 together with clipped doubling and u↦1−uu \mapsto1-u, obtaining a FIXP-complete exact circuit problem.

Reciprocal Gate

We start from the generalized-circuit problem with gates

u↦1−u,(u,v)↦⌊u+v⌋,andu↦u2,u \mapsto1-u,\qquad(u,v) \mapsto\lfloor u+v\rfloor,\qquad\text{and}\qquad u \mapsto u^2,

which is known to be FIXP-complete [24 Proposition 5.6]. We call the first type of gate in (1) a clipped affine gate and the second a reciprocal gate. Our goal is to implement the three gates above using only these two gate types. The gates u↦1−uu \mapsto1-u and (u,v)↦⌊u+v⌋(u,v) \mapsto\left\lfloor u+v\right\rfloor are already clipped affine gates, so it suffices to implement squaring.

A key observation is that, for 0<t<10<t<1, it holds that

t2=t−(1t+11−t)−1.(2)t^2=t-\left(\frac{1}{t}+\frac{1}{1-t}\right)^{-1}. \tag*{(2)}

This is a special case of Hua’s identity [29, 36]. In our context, (2) expresses a square using affine operations and reciprocals, but is undefined at the endpoints and can produce intermediate values exceeding one. To stay in [0,1][0,1], we use the gates from (1), writing Rτ(u)=1/(1+τu)R_\tau(u)=1/(1+\tau u) for the reciprocal gate with rational τ>0\tau>0.

For example, to compute x↦x2x\mapsto x^2 for x∈[0,1]x\in[0,1] while keeping all intermediate values in [0,1][0,1], first form

r+=R1(1+x2),r−=R1(1−x2),ands=34(r++r−)−1.r_+=R_1\left(\frac{1+x}{2}\right), \qquad r_-=R_1\left(\frac{1-x}{2}\right), \qquad\text{and}\qquad s=\frac{3}{4}(r_++r_-)-1.

These values lie in [0,1][0,1] and satisfy

s=x29−x2∈[0,18]andx2=9(1−R1(s)).s=\frac{x^2}{9-x^2}\in\left[0,\frac{1}{8}\right]\qquad\text{and}\qquad x^2=9(1-R_1(s)).

Lemma 4.1 extends this construction to every τ>0\tau>0. Replacing each squaring gate preserves the source solutions and proves Theorem 1.1.

Inverse Pseudogate

We now explain how to obtain the reciprocal from a suitable nonlinear response.

The key idea is to first use an auction construction to enforce a gate x=G(u)x=G(u) whose inverse has the form

G−1(x)=a+bx+cRτ(x),(3)G^{-1}(x)=a+bx+cR_\tau(x), \tag*{(3)}

where a,b,c,τa,b,c,\tau are fixed rationals with c≠0c\ne0 and τ>0\tau>0. The first step is to implement G−1G^{-1} using the following inverse-gate construction.

Lemma 2.1 (Informal). Let G:[0,1]→[0,1]G:[0,1]\to[0,1] be any continuous strictly decreasing bijection. Using auxiliary variables and directed cycles, gates for GG and clipped affine operations can implement the inverse gate x↦G−1(x)x\mapsto G^{-1}(x) exactly.

See Lemma 4.4 for the formal statement. On input x∈[0,1]x\in[0,1], the construction uses auxiliary variables y,z∈[0,1]y,z\in[0,1] satisfying

y=G(z)andz=⌊z+y−x⌋.y=G(z)\qquad\text{and}\qquad z=\left\lfloor z+y-x\right\rfloor.

Together, the two equations force y=xy=x. For 0<z<10<z<1, the clipping equation gives z=z+y−xz=z+y-x; at z=0z=0 or z=1z=1, the equation y=G(z)y=G(z) and the endpoint values G(0)=1G(0)=1, G(1)=0G(1)=0 give the same conclusion. Hence each input xx has the unique extension y=xy=x, z=G−1(x)z=G^{-1}(x). This is the pseudogate principle of [25 Section 3.2]: the auxiliary fixed-point equations enforce the required function at every solution.

Once z=G−1(x)z = G^{-1}(x) is available, a clipped affine gate implements the reciprocal gate by outputting ⌊(z−a−bx)/c⌋=Rτ(x)\left\lfloor(z-a-bx)/c\right\rfloor= R_{\tau}(x). Clipping does not change the value because Rτ(x)∈[0,1]R_{\tau}(x) \in[0,1].

This construction replaces each reciprocal gate in the circuits of Theorem 1.1 by gates for GG and clipped affine gates: every original solution extends to the new circuit, and every new solution projects to an original solution. Finding an exact solution to a generalized circuit using only clipped affine gates and GG is FIXP-complete, as formalized in Corollary 4.5.

References

  1. [1]Gagan Aggarwal, Ashwinkumar Badanidiyuru, Santiago R. Balseiro, Kshipra Bhawalkar, Yuan Deng, Zhe Feng, Gagan Goel, Christopher Liaw, Haihao Lu, Mohammad Mahdian, Jieming Mao, Aranyak Mehta, Vahab Mirrokni, Renat Paes Leme, Andrés Perlot, Georgios Piliouras, Jon Schneider, Ariel Schwartzman, Balasubramanian Sivan, Kelly Spendlove, Yifeng Teng, Di Wang, Hanrui Zhang, Mingfei Zhao, Wennan Zhu, and Song Zuo. Auto-bidding and auctions in online advertising: A survey. ACM SIGecom Exchanges, 22(1):159–183, 2024. https://doi.org/10.1145/3699824.3699838. (Cited on page 6.)
  2. [2]Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. Autobidding with constraints. In Web and Internet Economics (WINE 2019), volume 11920 of Lecture Notes in Computer Science, pages 17–30. Springer, 2019. https://doi.org/10.1007/978-3-030-35389-6_2. (Cited on page 6.)
  3. [3]Santiago R. Balseiro, Kshipra Bhawalkar, Zhe Feng, Haihao Lu, Vahab Mirrokni, Balasubramanian Sivan, and Di Wang. A field guide for pacing budget and ROS constraints. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 2607–2638, 2024. (Cited on page 6.)arxiv.org/abs/2302.08530
  4. [4]Eleni Batziou, Kristoffer Arnsfelt Hansen, and Kasper Høgh. Strong approximate consensus halving and the Borsuk–Ulam theorem. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics, pages 24:1–24:20, 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.24. (Cited on page 1.)
  5. [5]Mark Chen, Xi Chen, Hao Cui, William Pires, and Jonah Stockwell. On the complexity of mixed equilibria in first-price auctions with correlated priors. arXiv preprint arXiv:2610.07858, 2026. https://doi.org/10.48550/arXiv.2610.07858. (Cited on page 5.)
  6. [6]Thomas Chen, Xi Chen, Binghui Peng, and Mihalis Yannakakis. Computational hardness of the Hylland–Zeckhauser scheme. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2253–2268, 2022. https://doi.org/10.1137/1.9781611977073.90. (Cited on pages 1 and 4.)
  7. [7]Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3):14:1–14:57, 2009. https://doi.org/10.1145/1516512.1516516. (Cited on pages 1 and 4.)
  8. [8]Xi Chen, Christian Kroer, and Rachitesh Kumar. Throttling equilibria in auction markets. Operations Research, forthcoming. Numbered references are to the author manuscript revised September 2026. (Cited on pages 2, 4, 5, 8, 28, 29, and 34.)
  9. [9]Xi Chen, Christian Kroer, and Rachitesh Kumar. The complexity of pacing for second-price auctions. Mathematics of Operations Research, 49(4):2109–2135, 2024. https://doi.org/10.1287/moor.2022.0009. (Cited on pages 4 and 5.)
  10. [10]Xi Chen and Yuhao Li. Constant inapproximability of pacing equilibria in second-price auctions. In Web and Internet Economics (WINE 2025), volume 16266 of Lecture Notes in Computer Science, pages 294–306. Springer, 2026. https://doi.org/10.1007/978–3–032–18660–7_15. (Cited on page 5.)
  11. [11]Li Chen, Jamie Morgenstern, and Yuanyuan Yang. Beyond the PPAD hardness of auto-bidding auctions. arXiv preprint arXiv:2608.01889, 2026. https://doi.org/10.48550/arXiv.2608.01889. (Cited on page 6.)
  12. [12]Xi Chen, Dimitris Paparas, and Mihalis Yannakakis. The complexity of non-monotone markets. Journal of the ACM, 64(3):20:1–20:56, 2017. https://doi.org/10.1145/3064810. (Cited on pages 4 and 5.)
  13. [13]Xi Chen and Binghui Peng. Complexity of equilibria in first-price auctions under general tie-breaking rules. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pages 698–709, 2023. https://doi.org/10.1145/3564246.3585195. (Cited on page 5.)
  14. [14]Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolas E. Stier-Moses, Eric Sodomka, and Christopher A. Wilkens. Pacing equilibrium in first price auction markets. Management Science, 68(12):8515–8535, 2022. https://doi.org/10.1287/mnsc.2022.4310. (Cited on page 5.)
  15. [15]Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E. Stier-Moses. Multiplicative pacing equilibria in auction markets. Operations Research, 70(2):963–989, 2022. https://doi.org/10.1287/opre.2021.2167. (Cited on page 5.)
  16. [16]Constantinos Daskalakis. On the complexity of approximating a Nash equilibrium. ACM Transactions on Algorithms, 9(3):23:1–23:35, 2013. https://doi.org/10.1145/2483699.2483703. (Cited on page 4.)
  17. [17]Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195–259, 2009. https://doi.org/10.1137/070699652. (Cited on pages 1 and 4.)
  18. [18]Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. Pure-Circuit: Tight inapproximability for PPAD. Journal of the ACM, 71(5):31:1–31:48, 2024. https://doi.org/10.1145/3678166. (Cited on page 4.)
  19. [19]Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. Computing exact solutions of consensus halving and the Borsuk–Ulam theorem. Journal of Computer and System Sciences, 117:75–98, 2021. https://doi.org/10.1016/j.jcss.2020.10.006. (Cited on page 5.)
  20. [20]Paul Dütting, Yuhao Li, Renato Paes Leme, Kelly Spendlove, and Yifeng Teng. Autobidding equilibria in sponsored shopping. In Proceedings of the 27th ACM Conference on Economics and Computation (EC 2026). ACM, 2026. (Cited on pages 3, 6, and 20.)arxiv.org/abs/2602.21966
  21. [21]Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242–259, 2007. https://doi.org/10.1257/aer.97.1.242. (Cited on pages 3 and 20.)
  22. [22]Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria, and other fixed points. SIAM Journal on Computing, 39(6):2531–2597, 2010. https://doi.org/10.1137/080720826. (Cited on pages 1, 5, 6, 9, 10, and 12.)
  23. [23]Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, and Charalampos Kokkalis. On the computation of equilibria in discrete first-price auctions. SIAM Journal on Computing, 55(5):851–902, 2026. https://doi.org/10.1137/24M1780861. (Cited on page 5.)
  24. [24]Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos, and Diogo Poças. On the complexity of equilibrium computation in first-price auctions. SIAM Journal on Computing, 52(1):80–131, 2023. https://doi.org/10.1137/21M1435823. (Cited on pages 1, 2, 4, 5, 6, 7, 9, 10, and 14.)
  25. [25]Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høğh, and Alexandros Hollender. FIXP-membership via convex optimization: Games, cakes, and markets. SIAM Journal on Computing, Special Section FOCS 2021, pages FOCS21-30–FOCS21-84, 2023. https://doi.org/10.1137/22M1472656. (Cited on pages 1, 5, 7, and 12.)
  26. [26]Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høğh, and Alexandros Hollender. PPAD-membership for problems with exact rational solutions: A general approach via convex optimization. SIAM Journal on Computing, Special Section STOC 2024, pages STOC24-297–STOC24-421, 2026. https://doi.org/10.1137/24M1689089. (Cited on pages 1, 2, 3, 5, 16, and 20.)
  27. [27]Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 890–901, 2017. https://doi.org/10.1145/3055399.3055474. (Cited on page 5.)
  28. [28]Kristoffer Arnsfelt Hansen, Yuhao Li, and Xinhao Nie. Complexity of autobidding equilibria in GSP sponsored shopping. arXiv preprint arXiv:2610.13716, 2026. https://doi.org/10.48550/arXiv.2610.13716. (Cited on pages 2, 3, 4, 6, 20, 21, and 27.)
  29. [29]Loo-Keng Hua. Some properties of a sfield. Proceedings of the National Academy of Sciences, 35(9):533–537, 1949. https://doi.org/10.1073/pnas.35.9.533. (Cited on page 7.)
  30. [30]Yiyang Huang, Yonglei Yan, Zihe Wang, and Zhengyang Liu. Pacing equilibria in second-price auctions with few goods. arXiv preprint arXiv:2605.09332, 2026. https://doi.org/10.48550/arXiv.2605.09332. (Cited on page 6.)
  31. [31]Aanund Hylland and Richard Zeckhauser. The efficient allocation of individuals to positions. Journal of Political Economy, 87(2):293–314, 1979. https://doi.org/10.1086/260757. (Cited on page 5.)
  32. [32]Yasushi Kawase, Bodhayan Roy, and Mohammad Azharuddin Sanpui. PPAD-completeness of contiguous envy-free cake cutting with additive valuations. arXiv preprint arXiv:2610.19690, 2026. https://doi.org/10.48550/arXiv.2610.19690. (Cited on pages 4 and 5.)
  33. [33]Paul Klemperer. Auction theory: A guide to the literature. Journal of Economic Surveys, 13(3):227–286, 1999. https://doi.org/10.1111/1467-6419.00083. (Cited on page 5.)
  34. [34]Juncheng Li and Pingzhong Tang. Vulnerabilities of single-round incentive compatibility in auto-bidding: Theory and evidence from ROI-constrained online advertising markets. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI 2024), pages 2886–2894, 2024. https://doi.org/10.24963/ijcai.2024/320. (Cited on pages 2, 3, 6, and 16.)
  35. [35]Zhengyang Liu. Tight inapproximability of pacing and throttling equilibria in second-price auctions. arXiv preprint arXiv:2608.16682, 2026. https://doi.org/10.48550/arXiv.2608.16682. (Cited on pages 2, 4, and 5.)
  36. [36]Sandro Mattarei. Inverse-closed additive subgroups of fields. Israel Journal of Mathematics, 159(1):343–347, 2007. https://doi.org/10.1007/s11856-007-0050-6. (Cited on page 7.)
  37. [37]Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994. https://doi.org/10.1016/S0022–0000(05)80063–7. (Cited on pages 1 and 4.)
  38. [38]Aviad Rubinstein. Inapproximability of Nash equilibrium. SIAM Journal on Computing, 47(3):917–959, 2018. https://doi.org/10.1137/15M1039274. (Cited on pages 1, 4, and 10.)
  39. [39]Vijay V. Vazirani and Mihalis Yannakakis. Computational complexity of the Hylland–Zeckhauser mechanism for one-sided matching markets. SIAM Journal on Computing, 54(2):193–232, 2025. https://doi.org/10.1137/23M157586X. (Cited on pages 1 and 5.)
  40. [40]William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8–37, 1961. https://doi.org/10.1111/j.1540–6261.1961.tb02789.x. (Cited on page 2.)
  41. [41]Yonglei Yan, Zihe Wang, and Zhengyang Liu. Pacing equilibria in second-price auctions with few buyers. Proceedings of the AAAI Conference on Artificial Intelligence, 40(20):17302–17309, 2026. https://doi.org/10.1609/aaai.v40i20.38782. (Cited on page 6.)
  42. [42]Mihalis Yannakakis. Equilibria, fixed points, and complexity classes. Computer Science Review, 3(2):71–85, 2009. https://doi.org/10.1016/j.cosrev.2009.03.004. (Cited on page 5.)

Paper details

vlnc:W_zsckh367
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6

View statement
Looking for related papers…
Contents