acceptodds
Under review as a conference paper at ICLR 2027

High-Precision First-Price Throttling Equilibria via Positive-Tree Continuation

Abstract

First-price throttling lets budget-constrained advertisers randomize participation without changing bids, but ill-conditioned payment Jacobians complicate high-precision equilibrium computation. To overcome this obstacle, we represent a normalized continuation direction by positive tree polynomials. This yields a deterministic algorithm that computes a rational -approximate equilibrium in time for every finite rational first-price market of encoding length . We then characterize extensions through payment evaluation and derive computable revenue and coordinate-error certificates. Finally, learning results distinguish residual accuracy from participation accuracy, with matching sample bounds for a cyclic boundary family.

Primary area:
optimization
Keywords:
First-price auctions, throttling equilibria, equilibrium learning.

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_T7ceOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

It's about throttling equilibria, which is quite a big topic in e-commerce. I didn't get much out of this paper due to poor writing.

Critical strengths

I do not discern any strengths.

Critical weaknesses

I cannot support this paper, since it's impossible to read by anyone who is not heavily into the minutiae of its line of research. Too much jargon in the abstract ("payment Jacobian", "continuation direction") and Introduction. There are some more detailed failures of exposition, a few of which I mention below.

Paragraph 1 hints at quite an interesting situation: a total search problem (probably in NP but I can't be sure) with a unique solution. Sort-of like integer factorization, or simple stochastic games etc, therefore.

Paragraph 2 use the symbols n and m, but they're not introduced until start of Section 2. The poor reader is left wondering whether n is meant to be the same as N. Paragraph 3 is full of optimisation jargon, I didn't understand it.

Bottom of page 1 "Our algorithm is centralized". That's a concern for a ML conference, since one would prefer decentralised learning-style dynamics to be the main theme.

Top of p.2: "Two entry conditions extend its positive-tree..." -- what does "it" refer to? Further jargon like "pointed reliability" used but not explained.

First 3 lines of Section 2: what is the role of j? I assume the budgets B_i are exogenous; are the bids b_{ij} also exogenous, or are they to be computed? Likewise theta.

Algorithm 1: consider incorporating the description of the subroutine Step_h into the pseudocode.

"participation coin" -- I looked it up, seems to be something to do with blockchain. I don't see the connection with pacing/throttling auctions.

Questions for authors

I have no questions, although some are implicit in the weaknesses noted above.

2 comments
AuthorsOpenReview ↗

Response to Reviewer T7ce

We agree that the submission made the problem and proof difficult to assess. The task is to compute independent entry probabilities from fixed bids and budgets, with feasible expected spending and approximate equilibrium. At tolerance 2−p2^{-p}, Theorem 1.1 takes time polynomial in the input length and pp. The answers below explain the exposition changes; page numbers refer to the revision.

  1. Jargon in the abstract and introduction

The revised opening first explains the auction task: given bids, budgets, priorities, and precision, compute independent entry probabilities respecting expected budgets and the approximate equilibrium conditions. The Main Idea describes increasing participation, keeping payments proportional to budgets, and freezing near-full participants. The abstract removes "payment Jacobian" and "continuation direction".

The verification route is: input/output definitions (pp. 2-3), the two-bidder calculation (p. 5), Algorithm 1 (p. 6), Lemma 3.1 and Section 3.4 (pp. 4-7), with detailed proofs in Appendices A.3-A.4 (pp. 16-21).

  1. The unique solution and the search problem

The exact equilibrium is unique but may be irrational. The input is a rational market and unary precision pp; the output is a rational vector meeting the 2−p2^{-p}-approximate conditions. Theorem 1.1 gives polynomial-time computation; rational candidates are also directly verifiable.

For example, take two unit-bid goods with opposite priority orders and budget 1/21/2 per bidder. At common participation xx, each bidder pays x(2−x)x(2-x); the exact equilibrium is x=1−1/2x=1-1/\sqrt2. The rational candidate vector x=0.29x=0.29 pays 0.49590.4959 per bidder, respects both budgets, and has residual 0.0082<0.010.0082 < 0.01. This illustrates how to check a rational candidate without representing the irrational exact solution.

  1. The meanings of nn, mm, and NN

Here nn counts bidders, mm counts goods, and NN is the total binary encoding length. The introduction defines all three before using them.

  1. Centralized computation and feedback-based learning

Theorem 1.1 studies worst-case computation from known bids and budgets. To address your learning concern, added Theorem C.10 (p. 35) adapts CKK's updates to observing only winners and payments. The controller actively adjusts participation between batches of fresh i.i.d. auctions. With a known payment-to-budget bound RR, it learns a population δ\delta-approximate equilibrium with probability 1−α1-\alpha using O~(nRδ−3)\widetilde O(nR\delta^{-3}) auctions, with logarithmic factors specified in the theorem. Each batch's hard budgets are enforced on every sequence; training and deployment budgets are separate.

This complements the full-observation learner in Theorem 5.4 and the hard-budget revenue guarantee in Corollary 5.5. A decentralized solver with the same worst-case high-precision guarantee remains open.

  1. "Its" and "pointed reliability"

"Its" referred to the continuation algorithm. Section 4 now states the payment extension directly: entry cannot increase others' payments, and the entrant covers their total payment decrease.

In a matroid auction, a feasibility rule specifies which bidders can be served together. Bidders are processed in bid-priority order and accepted whenever that rule permits. For an entering bidder, pointed reliability is the probability that she can be accepted after higher-priority participants have been processed. Section 4.1 explains this event before the equivalence theorem.

  1. Roles of jj, BiB_i, bijb_{ij}, and θi\theta_i

Index jj identifies goods and ii identifies bidders. Bids bijb_{ij} and budgets BiB_i are given inputs. The algorithm computes only the participation probabilities θi\theta_i. Section 2 states these roles.

  1. Step subroutine in Algorithm 1

Algorithm 1 now includes the full Step subroutine in lines 9--19 (p. 6): coefficient computation, the rational linear solve, state-series updates, and odds rounding.

  1. "Participation coin"

This meant an independent random entry decision: bidder ii participates with probability θi\theta_i. We removed the phrase and state the rule directly in Sections 2 and 5.2.

  1. AI use and verifiability

The revision retains the AI use disclosure on p. 11: assistance with literature, auxiliary mathematical arguments and proof development, writing, and supporting code. We take responsibility for the final claims, proofs, citations, and artifacts.

To address verifiability, Equations (1) and (3) give checkable output conditions; Algorithm 1 contains the rational Taylor step; Sections 3.2–3.4 connect the analytic bound, accumulated error, and bit complexity. These are the specific exposition changes intended to make the result assessable.

These are improvements but I don't think the paper is ready to be published. On page 2: "reading δ" -- I guess that means something like, taking as input the encoding of δ. I suggest to say that δ is represented as a rational number (numerator and denominator in binary), which is a standard assumption.

Reviewer_r2ShOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper obtains a computationally efficient algorithm for calculating an approximate throttling equilibrium in first-price auctions. Specifically, for an auction of encoding length, the algorithm runs in time poly(N,log⁡(1/δ))poly(N, \log(1/\delta)) and calculates a δ\delta-approximate equilibrium. The problem is as follows. We have nn bidders and mm items. Bidder ii submits bid bi,jb_{i, j} for item jj. Each bidder is "active" with probability θi\theta_i. Each item is allocated to the first active bidder. Each agent also has a budget. A throttling equilibrium is a vector θ\theta such that for each bidder, either the agent is always active or, in expectation, their budget is exhausted. While a throttling equilibrium exists and is unique, calculating the equilibrium is difficult because of the high computation number of the Jacobain matrix.

Critical strengths

The paper resolves an open problem in the literature, providing a computationally efficient algorithm for finding throttling equilibrium.

Critical weaknesses
  • While the problem of throttling equilibrium has been considered before, it is not a very commonly considered concept in the literature. As such, I think criticisms of the concept (e.g. the budget feasibility holds only in expectation) apply here as well. Additionally, given the advances in LLMs, I think the fact that the problem is solved is less important than it used to be.
  • I think presentation can be improved.
Questions for authors
  • line 029: What do you mean by error bound? Error on what? (if you mean error on algorithm then the sentence is a bit weird since "lack of algorithm" is the main problem)
  • Is the equilibrium unique or not? Line 028 claims so but line 034 says "even for unique" so I'm a bit confused.
  • line 037: what is Root-finder convergence?
2 comments
AuthorsOpenReview ↗

Response to Reviewer r2Sh

Thank you for the review. We address the importance, budget model, presentation, and your three questions below. Page numbers refer to the revision; line numbers refer to the initial submission.

  1. Importance of the problem

The computational question is whether requesting more accuracy bits makes equilibrium computation exponentially harder. Theorem 1.1 answers Chen and Li's explicit precision question: at tolerance 2−p2^{-p}, our cost is poly⁡(N,p)\operatorname{poly}(N,p) bit operations, whereas CKK's particular multiplicative update can require Ω(2p)\Omega(2^p) rounds. The guarantee covers every finite rational first-price market, including ties and full participation, without a condition-number assumption. Lemma 3.1 supplies the analytic bound independently of coefficient magnitudes.

This matters within the fixed-bid model because throttling controls spending without changing advertisers' bids CKK, Introduction. Corollary 5.2 further shows that residual accuracy has a direct economic consequence: every δ\delta-approximate equilibrium earns at least (1−δ)OPT⁡(B)(1-\delta)\operatorname{OPT}(B) over budget-feasible static independent participation, even when participation probabilities are hard to estimate accurately.

Your realized-budget objection also motivates an added result rather than only a clarification. Corollary 5.5 enforces hard deployment budgets on every sequence and quantifies the revenue loss; the conditions and benchmark are stated below. The advance is therefore a certified precision guarantee together with explicit revenue consequences.

  1. Budgets hold only in expectation

Within the theoretical model, Corollary 5.5 proves budget feasibility on every sequence and a revenue bound under the stated small-payment assumption.

Corollary 5.5 (p. 10) skips unaffordable bids in HH fresh i.i.d. single-slot auctions, independent of training, with total budgets Ci=HBiC_i=HB_i. Let κ=R/H\kappa=R/H, where RR bounds one payment relative to BiB_i. For δ≤1/4\delta\le1/4 and κ≤5δ2/4\kappa\le5\delta^2/4, E[RevHF]/H≥(1−α)(1−δ)2OPT⁡(B)\mathbb E[\mathrm{Rev}^F_H]/H\ge(1-\alpha)(1-\delta)^2\operatorname{OPT}(B). Here α\alpha is the training failure probability; expectation includes training and future randomness.

If filtering removes a static winner, her remaining budget is below her bid. Lemma C.7 turns this fact into a pathwise revenue-loss bound, and Corollary C.8 controls its expectation using budget slack. Outcomes may change. Appendix C.3 also gives an additive bound for every horizon and a high-probability realized-revenue bound.

The comparator is static independent participation with fixed bids. The condition concerns individual payments relative to total budgets; extending the horizon at fixed budgets alone does not ensure it. The controlled-feedback learner also enforces separate training budgets. Dynamic-game equilibrium analysis remains open.

  1. Presentation

We rewrote the opening around the auction task and define the inputs before using them. Section 2 separates exact uniqueness, residual accuracy, and coordinate error.

Section 3 gives the proof roadmap, the two-bidder calculation (p. 5), and the full Step subroutine (p. 6). Table 1 compares the statistical guarantees. Corollaries 5.2 and 5.5 explain the revenue and finite-budget consequences. The core analytic lemma and complete algorithm remain in the 10-page main text.

  1. Line 029: what does "error bound" mean?

It means coordinate error ∣θ−θ⋆∣∞\\|\theta-\theta^\star\\|_\infty, the largest absolute error in a bidder's participation probability. The equilibrium residual instead measures budget exhaustion or near-full participation.

Section 2 gives a numerical example: with one unit-bid good and budget 1/21/2, participation 0.490.49 has coordinate error 0.010.01 and residual 0.020.02. Theorem 5.1 gives a computable coordinate-error certificate; Proposition 5.3 shows why residual accuracy alone cannot imply comparably small coordinate error.

  1. Lines 028 and 034: is the equilibrium unique?

Yes. With positive budgets and fixed tie-breaking, the exact equilibrium is unique, as established by CKK. Its probabilities may be irrational; multiple rational vectors can meet the approximate conditions. Sections 1-2 now distinguish these facts. We removed "even for a unique equilibrium" to resolve the ambiguity.

  1. Line 037: what is "root-finder convergence"?

This meant convergence of a numerical method for the equilibrium equations. Establishing our computational claim requires bounds on the number of steps, work per step, and intermediate encoding lengths.

We replaced the ambiguous paragraph with the algorithm's Main Idea. Sections 3.3-3.4 and Appendices A.3-A.4 connect the Taylor recurrence, rounding, step count, and bit lengths to prove the stated bit-complexity bound.

Thank you for your response. I have no more questions.

Reviewer_7dJwOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the problem of computing first-price throttling equilibria to high precision when payment Jacobians can be ill-conditioned. The paper proposes positive-tree continuation, which normalizes the continuation direction and uses positive polynomial representations to obtain certified numerical steps. It establishes polynomial dependence on input length and logarithmic precision, then develops payment-rule extensions, error certificates, and statistical learning bounds

Critical strengths
  1. The main result improves the precision dependence while covering finite rational markets without a condition-number assumption. This is a substantial theoretical contribution rather than only a convergence result for favorable instances

  2. The positive-tree representation provides a clear explanation for why the normalized direction remains analytically manageable. The rational implementation also addresses rounding and coefficient bit lengths, which are essential to the claimed computational guarantee

  3. The paper carefully distinguishes equilibrium residuals from errors in participation probabilities. Its computable certificates and boundary examples make this distinction concrete and connect it to statistical sample requirements

Critical weaknesses
  1. The paper establishes polynomial-time tractability but does not evaluate practical running time. The repeated rational linear solves and high-order expansions could still be costly compared with simpler updates at useful precision levels

  2. Coordinate-error guarantees remain dependent on revenue sensitivity, which can vanish near the boundary. The sharp statistical characterization applies to a specific cyclic family, leaving broader coordinate-identification rates unresolved

  3. The learning results assume access to all bids and priorities for each sampled context. They therefore do not directly address the censored feedback or realized budget constraints encountered in online throttling

Questions for authors

NA

1 comment
AuthorsOpenReview ↗

Response to Reviewer 7dJw

Thank you for recognizing the precision improvement, the numerical analysis, and the distinction between residual and participation error. We address your three concerns below. Page numbers refer to the revision.

  1. Practical running time

Our contribution is theoretical: a uniform worst-case bit-complexity guarantee for high-precision equilibrium computation. We study how cost scales with binary input length NN and requested accuracy bits pp across all finite rational first-price markets.

Theorem 1.1 gives poly⁡(N,p)\operatorname{poly}(N,p) bit operations for tolerance 2−p2^{-p}, including tied bids and full participation, without a condition-number assumption. CKK's algorithm is also provably convergent; the distinction is its worst-case precision dependence. Appendix A.5 shows that CKK's particular multiplicative update can require Ω(2p)\Omega(2^p) rounds. Sections 3.3-3.4 and Appendices A.3-A.4 give the step-count, arithmetic, rounding, and bit-length proofs supporting our guarantee.

  1. Revenue sensitivity and statistical scope

The sensitivity dependence is intrinsic. Proposition 5.3 gives residual rnr^n, coordinate error rr, and the exact certificate E(θ)/gk(θ)=r\mathcal E(\theta)/g_k(\theta)=r. A uniform O(δ)O(\delta) coordinate-error guarantee therefore needs additional assumptions.

Corollary 5.2 (p. 8) explains why residual accuracy is nevertheless economically useful: every δ\delta-approximate equilibrium earns at least (1−δ)OPT⁡(B)(1-\delta)\operatorname{OPT}(B) over budget-feasible static independent participation vectors, without a positive marginal-revenue assumption.

Table 1 distinguishes this guarantee, coordinate learning with a known positive marginal-revenue bound (Corollary C.5), and matching cyclic coordinate bounds of order (2η)−2nlog⁡(1/α)(2\eta)^{-2n}\log(1/\alpha) (Theorem 5.6). The cyclic upper estimator need not be feasible; the lower bound covers every estimator, including feasible ones, excluding a uniform O(η−2)O(\eta^{-2}) rate for the general class. Matching arbitrary-market coordinate bounds remain open.

  1. Winner/payment feedback and realized budgets

We added a controlled-feedback variant of CKK's updates in Theorem C.10 (p. 35). The learner observes only winners and payments and actively selects participation probabilities between batches of fresh i.i.d. auctions. With known payment-to-budget bound RR, it returns a population δ\delta-approximate equilibrium with probability 1−α1-\alpha using O~(nRδ−3)\widetilde O(nR\delta^{-3}) auctions; the theorem gives the logarithmic factors. Each batch's hard budgets are enforced on every sequence. Total training budgets KτBiK\tau B_i are separate from deployment budgets.

Corollary 5.5 (p. 10) deploys either learner's output in HH fresh i.i.d. auctions independent of training, under hard budgets HBiHB_i. For κ=R/H\kappa=R/H, δ≤1/4\delta\le1/4, and κ≤5δ2/4\kappa\le5\delta^2/4, E[RevHF]/H≥(1−α)(1−δ)2OPT⁡(B)\mathbb E[\mathrm{Rev}^F_H]/H\ge(1-\alpha)(1-\delta)^2\operatorname{OPT}(B). This expectation guarantee allows outcomes to change. Lemma C.7 bounds pathwise revenue loss, and Corollary C.8 controls that loss using budget slack. An additive bound covers every horizon; Corollary C.9 also controls realized revenue with high probability.

The comparator remains static independent participation. A longer horizon at fixed total budgets need not improve κ\kappa. Arbitrary passive censored logs and dynamic-game equilibria remain open.

Comments on the paper

1 comment
AuthorsOpenReview ↗

High-precision computation: contribution and targeted revisions

We thank the reviewers. The central contribution is a theoretical, uniform worst-case bit-complexity guarantee for high-precision equilibrium computation in finite rational first-price markets. We clarified its proof and added targeted consequences addressing the feedback and realized-budget concerns. The main text is 10 pages; page numbers below refer to the revision.

  1. Computational contribution and importance

Throttling manages budgets while preserving bids, accommodating fixed-bid requirements and representative participation over eligible auctions CKK, Introduction. Theorem 1.1 answers Chen and Li's precision question: for binary input length NN and tolerance 2−p2^{-p}, it computes a rational approximate equilibrium in poly⁡(N,p)\operatorname{poly}(N,p) bit operations. Expected budgets are respected; each bidder nearly always participates or nearly exhausts her budget. The exact equilibrium is unique but may be irrational.

The guarantee covers tied bids and full participation without a condition-number assumption. CKK's particular multiplicative update can require Ω(2p)\Omega(2^p) rounds (Appendix A.5). The normalized positive-polynomial bound in Lemma 3.1 is independent of coefficient magnitudes. Algorithm 1 uses rational linear solves and reuses one factorization per step. Section 3 and Appendices A.3-A.4 establish the analytic, rounding, and bit-length bounds.

  1. Response to the full-observation concern

Added Theorem C.10 (p. 35) adapts CKK's updates to controlled winner/payment feedback: the learner observes winners and payments, while actively selecting entry probabilities in batches of fresh i.i.d. auctions. For nn bidders and a known payment-to-budget bound RR, it returns a δ\delta-approximate equilibrium with probability 1−α1-\alpha using O(nRδ−3log⁡(2R)log⁡(nlog⁡(2R)/(αδ)))O(nR\delta^{-3}\log(2R)\log(n\log(2R)/(\alpha\delta))) auctions.

Each batch of τ\tau auctions enforces hard budgets τBi\tau B_i on every sequence; at most KK batches require training budgets KτBiK\tau B_i. Deployment budgets are separate. This feedback corollary complements the full-observation learner in Theorem 5.4. Its precision dependence is inverse polynomial; the high-precision advance of Theorem 1.1 concerns the known-market and empirical-market solves.

  1. Response to the realized-budget concern

Corollary 5.5 (p. 10) implements either learned vector by skipping unaffordable bids. In HH fresh i.i.d. single-slot auctions independent of training, every realized budget HBiHB_i is respected.

Small individual payments relative to total budgets also preserve near-optimal expected revenue. Let κ=R/H\kappa=R/H. For δ≤1/4\delta\le1/4 and κ≤5δ2/4\kappa\le5\delta^2/4, Appendix C.3 gives E[RevHF]/H≥(1−α)(1−δ)2OPT⁡(B)\mathbb E[\mathrm{Rev}^F_H]/H\ge(1-\alpha)(1-\delta)^2\operatorname{OPT}(B). The benchmark is fixed-bid static independent participation. Budget feasibility holds on every sequence; this revenue guarantee averages training and future randomness.

Lemma C.7 uses a simple fact: a filtered static winner has less remaining budget than her bid. Corollary C.8 bounds the resulting expected revenue loss using budget slack. Filtering may change outcomes. Corollary 5.5 also gives an additive bound at every horizon; Corollary C.9 gives a high-probability realized-revenue bound. The small-payment condition concerns payment size relative to total budget; a longer horizon alone need not satisfy it.

  1. Statistical scope and verification

Corollary 5.2 identifies equilibrium revenue with the static optimum and gives a (1−δ)(1-\delta) revenue guarantee without a positive marginal-revenue assumption. Proposition 5.3 explains why this remains useful despite residual rnr^n coexisting with coordinate error rr. Table 1 separates the statistical guarantees; matching general coordinate rates remain open. The controlled-feedback extension requires active sampling; passive censored logs and dynamic-game equilibria remain open.

The revised opening defines the inputs and accuracy notions. The two-bidder calculation (p. 5), full Step subroutine (p. 6), and proof roadmap make the argument easier to check.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.