d4-conf-aaai-2024-2255

Theorem 1 proves existence of a near-optimal continuous rebate function, but gives no algorithm, running-time bound, hardness result, or computational formulation used to find one. The fractional-histogram problem is a plausible extension, but it lacks a named computational result from this paper to mirror, so bit (a) fails.

The objection that survived

The finite leave-one-out deletion preserves an atomic pivotal effect, so \(q_n\) is a fractional-count relaxation rather than the atomless VCG limit; the proponent flags this issue but does not resolve it.

What the mirror covers

The proposed extension would cover worst-case allocative-efficiency optimization for public-project VCG rebates over fractional valuation-class counts. It leaves the neural-network ticket-drawing method, empirical ablations, and reported mechanisms for \(4\) to \(20\) agents without a computational anchor.

Open questions for a prover

The case FOR (proponent)

The strongest plausible mirror is high multiplicity in a public project: a very large population of residents whose valuations fall into a small number \(\tau\) of exact classes. A class is a valuation \(\theta_t\), since that is the paper’s only agent characteristic. For example, a citywide project model might use a few standardized benefit levels, each shared by many residents. The population is represented by class shares \(\mu_t\), with \(\sum_t\mu_t=1\).

For fixed \(n\ge2\), let \(e_t\) be one unit of class \(t\), and consider shares where \(n\mu_t\ge1\) for each represented class. The distribution of the other \(n-1\) residents when the removed resident is of class \(t\) is \(\nu_{\mu,t}=(n\mu-e_t)/(n-1)\). The continuous problem is to choose a Groves rebate function \(q_n\) on these distributions and maximize \(\alpha\), subject, for every such \(\mu\), to
\[ (n-1)s_n(\mu)\le n\sum_t\mu_tq_n(\nu_{\mu,t})\le(n-\alpha)s_n(\mu), \qquad s_n(\mu)=\max\left\{n\sum_t\mu_t\theta_t,1\right\}. \]
A solution is \(q_n\) and the largest feasible worst-case ratio \(\alpha\). This keeps the paper’s efficient build rule, leave-one-agent-out Groves term, non-deficit constraint, and worst-case objective; it relaxes integer class counts to fractional shares. It is a recognizable high-multiplicity version of the authors’ underlying mechanism-design problem.

The closest numbered result is Theorem 1, proved in this paper: for any fixed number of agents \(n\), if \(\alpha^*\) is the optimal worst-case efficiency ratio, then for every \(\epsilon>0\) there is a VCG redistribution mechanism with continuous \(h\) whose ratio is at least \(\alpha^*-\epsilon\). That is a result about continuity of the payment function over profiles of a *finite* set of agents. It is not a computational complexity result, nor a result about a continuous population. The paper has no numbered theorem, lemma, corollary, or proposition classifying a computational problem as tractable or hard; its algorithm and tables report empirical methods and results. So there is no eligible named computational anchor here, and the proposed histogram problem cannot be presented as an anchor-compliant mirror.

For that unanchored candidate, I would leave the complexity direction open: fractional shares might enable a continuous-optimization approach, but the paper supplies no finite representation or separation result for \(q_n\). The weak point is that a large public-project population with only a few exact valuation classes is a specific regime, and the individual’s \(1/n\) contribution to the project decision remains central to the VCG rebate. As \(n\) grows, that pivotal effect may make the limit degenerate.

The case AGAINST (opponent, writing after the proponent)

The cleanest case against starts with the anchor: this paper has no named result classifying the complexity of a computational problem. Theorem 1 proves that, for fixed finite \(n\), continuous rebate functions can approach the optimal efficiency ratio. It says nothing about a continuous population or computational complexity. The paper’s mechanism discoveries, algorithms, and tables are important computational contributions, but they are not the kind of complexity result the proposed mirror was meant to anchor. So the proponent’s public-project problem is a plausible new question, not a mirror of an eligible named result.

The strongest challenge to that candidate is the role of an individual agent in VCG. In the literal atomless limit, removing one agent does not change the population distribution. With the project cost fixed at \(1\), any population with positive average valuation eventually satisfies the build threshold; scaling the cost with population can preserve a nontrivial threshold, but an individual report still has no effect on the allocation. The leave-one-out externality that gives the paper its VCG rebates then disappears. That weakens the case that the paper’s mechanism-design problem has a natural atomless version.

The proposed \(q_n\) model addresses this by retaining a finite deletion of size \(1/n\), while allowing fractional class counts. That is mathematically coherent and probably the best version of the mirror. But it preserves a finite pivotal agent inside a fractional histogram: it is a relaxation of finite-\(n\) profiles, not the atomless VCG limit. It also extends the rebate function to fractional leave-one-out histograms that no finite profile need realize. Those changes may be exactly what the authors would accept as a useful high-multiplicity problem, so they do not defeat the mirror outright.

Accordingly, the negative case is strongest on the absence of an eligible computational anchor and the loss of individual pivotality in a genuine continuum. It is weak as a universal claim: the fractional-histogram relaxation remains a sensible, potentially worthwhile problem, and the paper’s lack of a complexity theorem does not make that question uninteresting. I would argue against treating this paper as a strong anchor for the programme, but I cannot honestly conclude that no worthwhile continuous mirror exists.

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.