| paper | d4-journals-geb-2020-0031 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: All allocation and payment functions converge uniformly. For \(m=1\), their limits are exactly computable in polynomial time as continuous piecewise affine functions with rational coefficients. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem D.2
Given a rational distribution μ over advertiser types \(t=(v_t,B_t)\), a maximum per-advertiser supply \(S\), and ε>0, take each replication factor \(q\) for which \(qμ_t\) is integral. Run ACA on \(qμ_t\) bidders of each type with total supply \(qs\), using one uniformly random priority order to break equal-value ties and reusing it across \(s\in[0,S]\). For each type, let \(X_{t,q}(s)\) and \(P_{t,q}(s)\) be its expected average per-bidder allocation and payment. Do these curves converge uniformly as \(q\to\infty\), and can an algorithm compute ε-approximations to the limiting curves uniformly over \(s\in[0,S]\) in time polynomial in support size τ, input bit length \(L\), and \(\log(1/\epsilon)\), independent of \(q\)?
A type-level mass model with types \(t=(v_t,B_t)\) and masses μ_t; supply \(s\) is measured per advertiser, and the outputs are the limiting per-advertiser allocation and payment curves \(X_t(s)\) and \(P_t(s)\), with aggregate type outcomes μ_tX_t(s) and μ_tP_t(s).
The finite ~O(n) event algorithm gives no evidence that replicated outcomes converge or admit ~O(1)-independent support-size compression; establishing that is the central open leap in the proposed mirror.
fatal: False
Covers type-aggregate outcome computation from Theorem D.2 and supply monotonicity from Theorem 4.1. It does not transfer individual truthfulness, individual rationality, budget feasibility, or Pareto optimality to the continuum, and leaves the paper's broader online-supply model and heuristic discussion aside.
The strongest positive case is a narrow one: the high-multiplicity limit of the Adaptive Clinching Auction (ACA). This paper has no named NP-hardness result, so it cannot anchor a claim that population continuization removes discrete hardness. Its useful anchors are positive results about computing ACA outcomes and how they change with supply.
The lead computational anchor is Theorem D.2, proved here: given \(n\) agents, their values, public budgets, and supply, the ACA allocation and payments can be computed in \(\tilde O(n)\) time. The paper’s main structural anchor is Theorem 4.1, also proved here: for budget-constrained agents with single-dimensional values, ACA is in the strong online supply model for multi-unit supply. Thus, if supply rises from \(s\) to \(s'\), each agent’s allocation and payment weakly increase. Theorem 4.3’s incentive compatibility, individual rationality, budget feasibility, and Pareto optimality are cited from Bhattacharya et al. [4], rather than proved as a new result here.
A plausible regime is a large advertising exchange with many campaign accounts drawn from a small menu of value and budget profiles. A type is a reported value and public budget, \((v_t,B_t)\); \(\mu_t\) is that type’s share of advertisers. Total inventory scales with the market, so supply \(s\) means \(s\) units per advertiser on average. This keeps the ACA’s values, budgets, allocation, and payments in the model. The continuous object is the advertiser population; the paper’s already-divisible ad inventory is not the continuization.
I would hand a prover this problem, High-Multiplicity ACA Limit. The input is a finite rational distribution \(\mu\) over types \((v_t,B_t)\), a maximum per-advertiser supply \(S\), and an accuracy \(\epsilon>0\). For each replication factor \(q\) such that every \(q\mu_t\) is integral, create \(q\mu_t\) advertisers of type \(t\), and run ACA with total supply \(qs\), for each \(s\in[0,S]\). To make identical advertisers genuinely indistinguishable, break ties by a uniformly random priority order, reused across supply levels, and take each type’s average expected allocation and payment per advertiser:
\[
X_{t,q}(s)=\frac{1}{q\mu_t}\mathbb{E}\!\left[\sum_{i\text{ of type }t}x_i(qs)\right],\qquad
P_{t,q}(s)=\frac{1}{q\mu_t}\mathbb{E}\!\left[\sum_{i\text{ of type }t}\pi_i(qs)\right].
\]
The question is whether these curves converge as \(q\to\infty\), and, if so, to give a compact description or an algorithm that approximates the limiting allocation and payment curves uniformly on \([0,S]\) in time polynomial in support size \(\tau\), input bit length \(L\), and \(\log(1/\epsilon)\), independent of \(q\). A proof of nonconvergence for some valid input would refute the universal version. The solution describes per-type outcomes; the corresponding mass allocation and payment are \(\mu_tX_t(s)\) and \(\mu_tP_t(s)\).
Theorem 4.1 supplies a useful predicted property of this limit: for \(s\le s'\), \(X_t(s)\le X_t(s')\) and \(P_t(s)\le P_t(s')\). At every finite \(q\), the same priority order couples the ACA runs and gives those inequalities agent by agent; averaging preserves them, and convergence would carry them to the limit. So this question retains the paper’s online allocation-and-payment behavior alongside its outcome computation.
I would expect Class A, provisionally. With only \(\tau\) distinct value-budget types, the limiting dynamics may be describable through a small number of value exits and changes in the highest remaining budget tier. But Theorem D.2’s \(\tilde O(n)\) bound does not establish support-size compression or convergence. Further questions include the convergence rate, whether the limit has a finite piecewise description, and whether the finite ACA’s truthfulness has any meaningful counterpart in the limit.
The weakest point is the regime and its strategic interpretation. Large cohorts of advertisers sharing exact values and budgets are plausible as standardized campaign profiles, but less compelling than a large, diverse advertiser market. And a limit of aggregate truthful outcomes is not automatically a truthful mechanism for atomless individuals: one person’s report has zero mass. This proposal therefore mirrors ACA outcome computation and supply monotonicity, not a claim that all of the paper’s strategic guarantees survive unchanged. That is a real limitation, but it leaves a concrete high-multiplicity question about the same auction rather than substituting continuity of outcomes or supply for continuity of the population.
The strongest case against is a question of fit with ChoCo’s computational agenda, not a claim that a population limit cannot be defined. A direct continuum version of the ACA could be written down, and the discrete advertising scenario is not the only possible one.
Theorem 4.1 concerns how outcomes change as supply increases. Its coordinatewise claim is about named bidders. In an atomless population, an individual has zero mass, so that claim needs a new type-level formulation. If the proposed average curves converge, their monotonicity follows from the finite auctions; it is a useful property of the mirror, but by itself it does not supply a population-complexity question.
Theorem D.2 is the paper’s real computational anchor. Its \(\tilde O(n)\) running time computes the outcome of a specified auction and emits \(n\) allocations and payments. The proof advances through at most linearly many value and budget events. With finitely many exact \((v,B)\) types, copies of a type behave symmetrically between value exits; the paper’s remaining-budget structure suggests that the substantive events can be grouped by types and budget tiers. The many-copy limit may require careful analysis, especially around ties, but it appears to be an asymptotic study of a low-dimensional event process rather than a new optimization problem with a pricing bottleneck or a complexity landscape. That makes it a narrower fit for a programme aimed at computational questions such as bribery, control, and robustness.
The best version of the proposed mirror would define a type-level ACA directly for a rational mass distribution over \((v,B)\), with supply measured per capita, and ask for an efficient algorithm to compute its allocation and payment curves. That avoids making the limit depend on a tie-breaking convention. It also makes the scope concern clearer: the object is the aggregate execution of an existing mechanism. That could be worthwhile mechanism-design mathematics, but its connection to ChoCo’s central computational gap is less direct than the proponent’s framing suggests.
The suggested advertising regime is plausible if many accounts share exact values and public budgets. That exact homogeneity is a demanding assumption: coarser value or budget groups would change the model’s types. Still, a standardized market could meet it, so this is not a decisive objection. Nor do the paper’s divisible goods count as a collision: outcome continuity alone does not continuize the population. Theorem 4.3 is cited prior work, and the paper does not already analyze the high-multiplicity population limit.
So the negative case is weak as a universal claim. The type-level limit is coherent, and the fact that its answer might be simple would not make the question invalid. The strongest objection is that it may be a small asymptotic extension of one auction algorithm rather than a worthwhile addition to ChoCo’s computational programme; that is a judgment about priority, not a fundamental failure of the mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.