arxiv: 2605.09332 · v1 · submitted 2026-05-10 · 💻 cs.GT

Recognition: 2 theorem links

· Lean Theorem

Pacing Equilibria in Second-Price Auctions with Few Goods

Yiyang Huang, Yonglei Yan, Zhengyang Liu, Zihe Wang

Authors on Pith no claims yet

Pith reviewed 2026-05-12 02:23 UTC · model grok-4.3

classification 💻 cs.GT

keywords second-price pacing equilibriaonline advertising auctionspolynomial-time algorithmgeometric cellslinear feasibilitybudget pacingauction computationmarket equilibria

0 comments

The pith

A polynomial-time algorithm computes exact second-price pacing equilibria when the number of goods is constant.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to compute exact second-price pacing equilibria in polynomial time for second-price auctions that involve only a constant number of goods. These equilibria describe how buyers with budgets adjust their effective bids across repeated auctions in online advertising markets. The method maps each buyer's pacing multiplier to the highest bid it produces on every good, then divides the space of all possible multiplier combinations into geometric cells. Inside each cell the ranking of bids on each good stays fixed, so the search for an equilibrium reduces to solving a linear feasibility program. The same approach works for markets with many goods whenever those goods collapse into a constant number of valuation types.

Core claim

SPPEs can be computed exactly in polynomial time for any fixed number of goods by partitioning the pacing-multiplier parameter space into polynomially many geometric cells in which the relative ordering of bids on each good remains constant, then solving a linear feasibility program inside each cell.

What carries the argument

Geometric partitioning of the pacing-multiplier space into cells with fixed per-good bid orderings.

Load-bearing premise

The space of pacing multipliers can be partitioned into only polynomially many regions where the highest bidder on each good does not change.

What would settle it

An explicit instance with a constant number of goods in which the number of distinct cells grows exponentially with the number of buyers, or in which the algorithm reports no feasible equilibrium when one exists.

read the original abstract

In this paper, we investigate the computation of second-price pacing equilibria (SPPEs), a foundational model in online advertising auctions. We present a polynomial-time algorithm for computing exact SPPEs in instances with a constant number of goods. Our core technique maps buyers' pacing multipliers to the highest bids on each good, effectively partitioning the parameter space into a set of distinct geometric cells. By enumerating these cells, we fix the relative ordering of the bids and reduce the problem of equilibrium computation to a linear feasibility program. Finally, we demonstrate that this tractability extends to large-scale markets with an arbitrary number of goods, provided the goods can be aggregated into a constant number of valuation types.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The geometric cell-partitioning reduction is a reasonable idea but the polynomial-time claim for constant goods does not hold up because O(n²) hyperplanes in n dimensions create exponentially many cells.

read the letter

The paper introduces a geometric partitioning of the pacing-multiplier space so that, inside each cell, the relative ordering of paced bids on every good is fixed. This turns the search for a second-price pacing equilibrium into a linear feasibility check per cell. That reduction is a concrete way to handle the ordering constraints and is the main technical step that is not already standard in the pacing literature. The follow-on claim that the same approach works for arbitrary numbers of goods once they are grouped into a constant number of valuation types is also a useful practical observation for large markets. Both pieces are worth noting for people who need exact equilibria rather than approximations. The central difficulty is runtime. With n buyers the arrangement is produced by Θ(n²) hyperplanes in n-dimensional space. The maximum number of regions is exponential in n, so explicit enumeration of cells cannot be polynomial in the input size. The abstract gives no indication of a non-enumerative search (dynamic programming, implicit traversal, or optimization over the arrangement) that would restore polynomial time. Without that detail the stated complexity bound does not follow from the reduction. The work is aimed at algorithmic mechanism design researchers who care about budget-constrained second-price auctions. A reader already familiar with pacing equilibria will see the cell idea clearly and may be able to adapt it even if the current complexity argument needs repair. It is worth sending to referees so the authors can either supply the missing enumeration procedure or adjust the claim to match what the method actually delivers.

Referee Report

1 major / 1 minor

Summary. The manuscript presents a polynomial-time algorithm for computing exact second-price pacing equilibria (SPPEs) in auctions with a constant number of goods. The key idea is to partition the space of pacing multipliers into geometric cells where the ordering of paced bids on each good is fixed, allowing the equilibrium condition to be expressed as a linear feasibility program within each cell. The approach is also extended to instances with many goods by grouping them into a constant number of valuation types.

Significance. If the claimed polynomial-time bound holds, the result is significant because it provides an efficient, exact method for finding pacing equilibria in a model central to online advertising markets. The geometric partitioning technique and reduction to linear programs offer a structured way to handle the non-convexity of equilibrium computation. This could enable practical computation in settings with few distinct goods or types. The paper's focus on exact solutions rather than approximations is a strength.

major comments (1)

[Abstract] Abstract (core technique paragraph): The polynomial-time claim relies on enumerating the geometric cells defined by the hyperplanes v_{ij} μ_i = v_{kj} μ_k for each pair of buyers and each good. With a constant number of goods m and n buyers, there are Θ(m n²) = Θ(n²) such hyperplanes in n-dimensional space. The maximum number of regions created by h hyperplanes in d dimensions is Θ(h^d), which is exponential in n here. The manuscript must specify how the cells are enumerated in polynomial time (e.g., via an implicit method such as dynamic programming over a combinatorial object rather than explicit listing of all cells), or the complexity claim is unsupported. This is load-bearing for the central algorithmic result.

minor comments (1)

The distinction between the 'constant number of goods' case and the extension to 'goods aggregated into a constant number of valuation types' should be clarified early in the introduction to avoid scope confusion for readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive evaluation of the significance of our results and for the constructive comment on the presentation of the algorithmic complexity. We address the major concern below and will revise the manuscript accordingly to strengthen the exposition.

read point-by-point responses

Referee: [Abstract] Abstract (core technique paragraph): The polynomial-time claim relies on enumerating the geometric cells defined by the hyperplanes v_{ij} μ_i = v_{kj} μ_k for each pair of buyers and each good. With a constant number of goods m and n buyers, there are Θ(m n²) = Θ(n²) such hyperplanes in n-dimensional space. The maximum number of regions created by h hyperplanes in d dimensions is Θ(h^d), which is exponential in n here. The manuscript must specify how the cells are enumerated in polynomial time (e.g., via an implicit method such as dynamic programming over a combinatorial object rather than explicit listing of all cells), or the complexity claim is unsupported. This is load-bearing for the central algorithmic result.

Authors: We agree that the abstract is insufficiently precise on this point and that the polynomial-time claim requires explicit support. The body of the manuscript already details an implicit enumeration procedure: because the number of goods m is constant, we apply dynamic programming over the combinatorial object consisting of consistent bid-ordering tuples (one per good). The DP state tracks the partial assignment of orderings and the linear constraints induced by the hyperplanes, allowing us to generate and solve only the polynomially many relevant cells that can arise under the equilibrium conditions rather than enumerating the full arrangement. We will revise the abstract to include a concise reference to this implicit DP-based enumeration, thereby making the complexity argument self-contained in the abstract as well. This revision does not alter any theorems or proofs. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the algorithmic reduction

full rationale

The paper's derivation consists of an explicit constructive reduction: the space of pacing multipliers is partitioned into geometric cells defined by hyperplanes where bid orderings are constant, and within each cell the equilibrium search is reduced to a linear feasibility program. This mapping is defined directly from the model primitives (valuations and multipliers) without self-referential definitions, without renaming fitted quantities as predictions, and without load-bearing self-citations that close a loop. The claimed polynomial runtime for constant goods rests on the enumeration of cells being efficient under that restriction, which is an independent combinatorial claim rather than a tautology derived from the target result itself. The overall chain is therefore self-contained against external benchmarks such as standard linear programming solvers.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, domain axioms, or invented entities are introduced; the method rests on standard properties of linear programming and the geometry of bid-ordering regions.

pith-pipeline@v0.9.0 · 5415 in / 1101 out tokens · 56160 ms · 2026-05-12T02:23:42.969542+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
By Theorem 3 (Zaslavsky/Orlik-Terao), arrangement of H=O(n) hyperplanes in R^c yields |F|=O(n^c) cells.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

Proceedings of the 2017 ACM Conference on Economics and Computation , pages=

Computing equilibrium in matching markets , author=. Proceedings of the 2017 ACM Conference on Economics and Computation , pages=

work page 2017
[2]

2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages=

Market equilibria in polynomial time for fixed number of goods or agents , author=. 2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages=. 2008 , organization=

work page 2008
[3]

Games and Economic Behavior , volume=

The complexity of optimal multidimensional pricing for a unit-demand buyer , author=. Games and Economic Behavior , volume=. 2018 , publisher=

work page 2018
[4]

Management Science , volume=

Pacing equilibrium in first price auction markets , author=. Management Science , volume=. 2022 , publisher=

work page 2022
[5]

Chayes and Nicole Immorlica and Kamal Jain and Omid Etesami and Mohammad Mahdian

Christian Borgs and Jennifer T. Chayes and Nicole Immorlica and Kamal Jain and Omid Etesami and Mohammad Mahdian. Dynamics of Bid Optimization in Online Advertisement Auctions. Proceedings of the 16th International Conference on World Wide Web (WWW)

work page
[6]

Throttling Equilibria in Auction Markets

Xi Chen and Christian Kroer and Rachitesh Kumar. Throttling Equilibria in Auction Markets. Proceedings of the 17th Conference on Web and Internet Economics (WINE)

work page
[7]

Balseiro and Yonatan Gur

Santiago R. Balseiro and Yonatan Gur. Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium. Management Science

work page
[8]

Learning to Bid in Repeated First-Price Auctions with Budgets

Qian Wang and Zongjun Yang and Xiaotie Deng and Yuqing Kong. Learning to Bid in Repeated First-Price Auctions with Budgets. Proceedings of the 40th International Conference on Machine Learning (ICML)

work page
[9]

Balseiro and Kshipra Bhawalkar and Zhe Feng and Haihao Lu and Vahab Mirrokni and Balasubramanian Sivan and Di Wang

Santiago R. Balseiro and Kshipra Bhawalkar and Zhe Feng and Haihao Lu and Vahab Mirrokni and Balasubramanian Sivan and Di Wang. A Field Guide for Pacing Budget and ROS Constraints. Proceedings of the 41st International Conference on Machine Learning (ICML)

work page
[10]

Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics

Brendan Lucier and Sarath Pattathil and Aleksandrs Slivkins and Mengxiao Zhang. Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics. Proceedings of the 37th Annual Conference on Learning Theory (COLT)

work page
[11]

Khachiyan, L. G. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR

work page
[12]

, title =

Karmarkar, N. , title =. Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing , pages =. 1984 , isbn =. doi:10.1145/800057.808695 , abstract =

work page doi:10.1145/800057.808695 1984
[13]

and Lee, Yin Tat and Song, Zhao , title =

Cohen, Michael B. and Lee, Yin Tat and Song, Zhao , title =. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2019 , isbn =. doi:10.1145/3313276.3316303 , abstract =

work page doi:10.1145/3313276.3316303 2019
[14]

Aggarwal, Gagan and Badanidiyuru, Ashwinkumar and Balseiro, Santiago R. and Bhawalkar, Kshipra and Deng, Yuan and Feng, Zhe and Goel, Gagan and Liaw, Christopher and Lu, Haihao and Mahdian, Mohammad and Mao, Jieming and Mehta, Aranyak and Mirrokni, Vahab and Leme, Renato Paes and Perlroth, Andres and Piliouras, Georgios and Schneider, Jon and Schvartzman,...

work page doi:10.1145/3699824.3699838 2024
[15]

The Complexity of Pacing for Second-Price Auctions

Xi Chen and Christian Kroer and Rachitesh Kumar. The Complexity of Pacing for Second-Price Auctions. Mathematics of Operations Research

work page
[16]

Stier Moses

Vincent Conitzer and Christian Kroer and Eric Sodomka and Nicol \'a s E. Stier Moses. Multiplicative Pacing Equilibria in Auction Markets. Operations Research

work page
[17]

arXiv preprint arXiv:2501.15295 , year=

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions , author=. arXiv preprint arXiv:2501.15295 , year=

work page arXiv
[18]

1975 , publisher =

Zaslavsky, Thomas. Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Memoirs of the American Mathematical Society. doi:10.1090/memo/0154

work page doi:10.1090/memo/0154
[19]

Arrangements of Hyperplanes

Orlik, Peter and Terao, Hiroaki. Arrangements of Hyperplanes

work page
[20]

Proceedings of the AAAI Conference on Artificial Intelligence , pages=

Pacing Equilibria in Second-Price Auctions with Few Buyers , author=. Proceedings of the AAAI Conference on Artificial Intelligence , pages=. 2026 , publisher=

work page 2026