| paper | d4-conf-atal-2008-0015 |
| 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: \(\mathrm P\): feasible exactly when \(B\le q\,\mathbb E_{\mu\sim\Pi}[Q_q(\mu)]\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
THEOREM 1
Given a finite value set \(T\subseteq[L,U]\), a rational supply share \(q\in(0,1)\), and a finite rational prior \(\Pi\) over societies \(\mu\in\Delta(T)\), allocate mass \(q\) efficiently to the highest reported values, splitting mass at the cutoff as needed. Find coefficients for a common per-capita rebate \(\rho(\mu)\), a finite linear combination of quantile values of \(\mu\), that maximizes \(\mathbb{E}_{\mu\sim\Pi}[\rho(\mu)]\), subject to dominant-strategy truthfulness for each infinitesimal bidder and the pointwise non-deficit constraint \(\rho(\mu)\le q\theta_q(\mu)\), where \(\theta_q(\mu)\) is the allocation cutoff.
An atomless unit-demand auction with bidder values drawn from finite types \(T\), population distribution \(\mu\), and supply \(q\) per unit of population. Efficient allocation and VCG cutoff payments are paired with a common per-capita rebate that is a linear combination of quantile values; choose the rebate to maximize expected redistribution under a prior over societies while maintaining individual truthfulness and non-deficit.
The rebate truthfulness constraint becomes automatic when an individual has zero mass, so the mirror loses the finite theorem’s coupled leave-one-out design tradeoff; the proponent acknowledges this change but does not establish convergence of the finite optimum to the proposed continuum optimum.
fatal: False
The mirror covers THEOREM 1’s optimization of anonymous linear rebates under efficient allocation, truthfulness, and non-deficit. It leaves aside the discretization-mechanism results, other properties of the linear mechanism, and the experiments.
The strongest mirror I see is the paper’s optimal expected redistribution result in a nonatomic, high multiplicity auction. The natural regime is a large market in which many bidders share each of a relatively small number \(\tau\) of values. A type is a bidder’s complete value for one unit, with unit demand and identical auction rights; \(\mu_t\) is the fraction of the population with value \(t\). The supply scales with the market: a fraction \(q\) of the population receives a unit. Each allocated bidder still gets an indivisible unit; at a tied cutoff, allocation can be randomized so the allocated mass is exactly \(q\).
My sole anchor, and the lead, is Theorem 1, proved in this paper. There is no comparable numbered hardness result to anchor instead. The theorem considers \(m<n\) bidders with sorted values \(v_1\ge\cdots\ge v_n\) in \([L,U]\), under a prior over their values. It proves that an anonymous linear rebate rule
\[
r_i(v_{-i})=c_0+\sum_{j=1}^{n-1}c_jv_{-i,j}
\]
can be chosen to maximize expected total redistribution while preserving efficient allocation, dominant-strategy incentive compatibility, and the ex-post non-deficit constraint. Here \(v_{-i,j}\) is the \(j\)-th highest value other than bidder \(i\)’s.
For the theorem’s coefficients, define \(o_0=U-\mathbb E v_1\), \(o_i=\mathbb E v_i-\mathbb E v_{i+1}\) for \(1\le i<n\), and \(o_n=\mathbb E v_n-L\). Choose
\[
k\in\arg\min_{i:\,i-m\text{ odd}} o_i\,m\binom{n-1}{m}/\binom{n}{i}.
\]
With
\[
G(n,m,i)=\frac{\binom{n-i-1}{n-m-1}}{\binom{m-1}{i-1}},
\qquad
H(n,m,i)=\frac{\binom{i-1}{m-1}}{\binom{n-m-1}{n-i-1}},
\]
the theorem sets coefficients as follows. If \(0<k\le m\), set \(c_i=(-1)^{m-i}G(n,m,i)\) for \(k<i\le m\), \(c_k=m/n-\sum_{i=k+1}^m(-1)^{m-i}G(n,m,i)\), and all other coefficients to zero. If \(k=0\), use \(c_i=(-1)^{m-i}G(n,m,i)\) for \(1\le i\le m\), \(c_0=Um/n-U\sum_{i=1}^m(-1)^{m-i}G(n,m,i)\), and zero otherwise. If \(m+1\le k<n\), use \(c_i=(-1)^{m-i-1}H(n,m,i)\) for \(m+1\le i<k\), \(c_k=m/n-\sum_{i=m+1}^{k-1}(-1)^{m-i-1}H(n,m,i)\), and zero otherwise. If \(k=n\), use \(c_i=(-1)^{m-i-1}H(n,m,i)\) for \(m+1\le i<n\), \(c_0=Lm/n-L\sum_{i=m+1}^{n-1}(-1)^{m-i-1}H(n,m,i)\), and zero otherwise. The expected amount left unredistributed is \(o_km\binom{n-1}{m}/\binom{n}{k}\); the optimum is unique exactly when the minimizing \(k\) is unique and there are no even \(i\), odd \(j\) with \(o_i=o_j=0\). The paper also notes that \(k=m+1\) gives the Bailey–Cavallo rule \(r_i=(m/n)v_{-i,m+1}\).
Here is the continuous problem I would hand to a prover. Optimal Expected Redistribution\(_\infty\) takes a finite set of values \(T\subseteq[L,U]\), a rational supply share \(q\in(0,1)\), and a finite rational prior \(\Pi\) over rational societies \(\mu\in\Delta(T)\). For each reported society, allocate mass \(q\) to the highest reported values, splitting mass at the cutoff as needed; let \(\theta_q(\mu)\) be the cutoff value, with a fixed one-sided convention for boundary ties. The mechanism adds the same rebate \(\rho(\mu)\) to every infinitesimal bidder, where \(\rho\) is a finite linear combination of quantile values of \(\mu\). Find a feasible such rule maximizing \(\mathbb E_{\mu\sim\Pi}[\rho(\mu)]\), subject to dominant-strategy truthfulness, efficiency, and the pointwise non-deficit constraint \(\rho(\mu)\le q\theta_q(\mu)\) for every society.
This is a population mirror: \(\mu\) is the society, and \(\Pi\) expresses uncertainty about its composition. The co-modification is that supply is \(q\) per unit mass. With an atomless population, one person’s report does not change \(\mu\), so a common rebate based on \(\mu\) does not change that person’s incentives. The rule \(\rho^*(\mu)=q\theta_q(\mu)\) is itself a linear quantile rule. It returns the full VCG revenue per unit mass, satisfies the non-deficit bound with equality, and is optimal for every prior. This is my inference for the mirror, not a result proved by the paper. It is the limit suggested by the paper’s Bailey–Cavallo special case: as \(m/n\) tends to \(q\), its rank statistic tends to the population cutoff.
I expect this mirror to be tractable: given a society with \(\tau\) supported values, the cutoff and rebate can be computed by sorting the support and accumulating masses. It covers Theorem 1’s optimization of redistribution under efficient allocation, incentive compatibility, and non-deficit, rather than the paper’s separate discretization of valuation-dependent rebate functions. It also suggests useful follow-up questions: how quickly does the finite-\(n\) optimum approach full redistribution when \(m/n\to q\); how does a positive lower bound on individual influence change the answer; and what happens under coalition-proofness or additional fairness constraints?
The soft spot is substantial: atomlessness removes the individual pivotal effects that make Theorem 1’s finite-bidder coefficient choice interesting. The continuous optimum is much simpler, and the authors might regard it as a limiting market-design variant rather than a direct restatement of their theorem. I think the case still holds because it preserves their auction, the efficient allocation, VCG payments, anonymous rank-based rebates, and expected redistribution objective; high multiplicity explains exactly why the finite strategic constraint changes in the limit.
Theorem 1 is a genuine anchor, so the case against cannot rest on the paper lacking a named result. The stronger objection is that the proposed continuation removes the constraint that makes the theorem’s optimization distinctive.
In the finite auction, bidder \(i\)’s rebate \(r_i(v_{-i})\) must exclude their own bid to preserve dominant-strategy truthfulness. In the proposed atomless model, a bidder’s report changes no mass in \(\mu\), so a common rebate \(\rho(\mu)\) is already unaffected by that bidder’s report. The allocation still has a meaningful threshold incentive, but that comes from the fixed VCG allocation rule. The rebate-design constraint has disappeared. The remaining budget condition, \(\rho(\mu)\le q\theta_q(\mu)\), is a condition on each society separately; it no longer couples the bidders’ leave-one-out rebates as in Theorem 1. That is a structural change to the feasible set, not just a simpler answer. The fact that the resulting answer may be straightforward is not itself an objection.
A closer limit could keep rebates based on each bidder’s leave-one-out empirical measure. But at any fixed finite population size, that retains the individual grid and rank data; as the mass of an individual tends to zero, the distinction that enforced rebate truthfulness vanishes. Alternatively, give each strategic actor positive mass so their report can change the society. That restores influence by making the actor a cohort or group, and asks for group incentive compatibility rather than the paper’s individual dominant-strategy property. A first-order limit of finite-agent incentive constraints might also be worth studying, but it needs an additional scaling and tie convention; it is a new local-incentive model, not a continuation determined by Theorem 1.
Additional constraints such as individual rationality or coalition-proofness could produce a richer continuous optimization problem. They are plausible extensions, but they supply new design requirements rather than preserve this theorem’s central one.
So the negative case is strongest against this paper as a ChoCo complexity mirror: its sole theorem-level anchor loses the rebate incentive constraint when the population becomes truly atomless, while restoring that constraint keeps finite granularity or changes who the strategic actors are. I cannot honestly establish the universal claim that no continuous auction model inspired by this paper would be worthwhile. The weak point is that a carefully specified first-order or cohort model might be valuable in its own right; it would simply answer a different question.
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.