- 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
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.
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−p, Theorem 1.1 takes time polynomial in the input length and p. The answers below explain the exposition changes; page numbers refer to the revision.
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).
The exact equilibrium is unique but may be irrational. The input is a rational market and unary precision p; the output is a rational vector meeting the 2−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/2 per bidder. At common participation x, each bidder pays x(2−x); the exact equilibrium is x=1−1/2. The rational candidate vector x=0.29 pays 0.4959 per bidder, respects both budgets, and has residual 0.0082<0.01. This illustrates how to check a rational candidate without representing the irrational exact solution.
Here n counts bidders, m counts goods, and N is the total binary encoding length. The introduction defines all three before using them.
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 R, it learns a population δ-approximate equilibrium with probability 1−α using O(nRδ−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.
"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.
Index j identifies goods and i identifies bidders. Bids bij and budgets Bi are given inputs. The algorithm computes only the participation probabilities θi. Section 2 states these roles.
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.
This meant an independent random entry decision: bidder i participates with probability θi. We removed the phrase and state the rule directly in Sections 2 and 5.2.
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.