d4-conf-atal-2018-0169

The paper’s theorem statements concern rebate-rule properties and are attributed to prior work; neither asserts an algorithm, complexity bound, or hardness result. The paper’s own redistribution improvements are experimental findings without a named numbered computational guarantee, so the otherwise plausible continuous-population optimization question has no qualifying result to anchor it.

The objection that survived

The opponent argues that in the atomless limit an individual has zero mass, so rebates can approach VCG revenue per capita and the optimal redistribution approaches full redistribution; this makes the proposed problem potentially trivial.

What the mirror covers

The proposed mirror covers optimal-in-expectation redistribution for homogeneous and heterogeneous resources. It leaves aside worst-case redistribution and the paper’s neural-network training experiments.

Open questions for a prover

The case FOR (proponent)

The strongest positive case is a high-multiplicity version of the paper’s redistribution problem. Consider a large public allocation programme with many agents who each want at most one resource. A type is a complete valuation vector for the available resource classes. If \(N\) is the population size, type \(t\) has mass \(\mu_t=n_t/N\), and resource class \(j\) has supply \(q_jN\). This supply scaling keeps the allocation problem meaningful as the population grows. It is plausible when many agents fall into a modest number of valuation classes; the paper’s experiments with \(n\leq 10\) do not themselves establish that regime.

One candidate question is Continuous Optimal-in-Expectation Redistribution. Its input is a finite type set \(T\) with rational valuation vectors, per-capita supplies \(q\), and a finite rational prior over societies \(\mu\). An allocation assigns mass \(x_{tj}\) of type \(t\) to resource \(j\), with \(\sum_j x_{tj}\leq\mu_t\) and \(\sum_t x_{tj}\leq q_j\), and must maximize reported welfare. The mechanism also chooses an anonymous Groves rebate rule: each agent’s rebate depends on the distribution of reports excluding that agent. The objective is to maximize expected aggregate rebate, subject to feasibility, individual rationality, and truthfulness. To preserve the paper’s finite-agent incentive question, admissible rules should be limits of exact finite-\(N\) mechanisms as \(n_t/N\to\mu_t\) and supplies approach \(q_jN\). A solution is an optimal allocation and rebate rule, not neural-network weights.

For finite-support priors and finite type sets, I would expect a tractable LP formulation if the limiting incentive and feasibility constraints admit polynomial-size separation. The central open questions would be whether that limit preserves the exact DSIC conditions, whether the LP has efficient separation, and how its optimum compares with the finite-\(N\) optimum. The main modeling risk is real: taking a nonatomic limit can erase the effect of one agent’s report on VCG payments and rebates. The leave-one-out limit has to retain that effect.

There is a serious anchor problem. The supplied paper has no numbered Theorem, Lemma, Corollary, or Proposition asserting a computational complexity result. Its two theorem environments are attributed to Gujar and Narahari: one characterizes DSIC rebate functions; the other rules out a linear rebate function with nonzero redistribution index in the heterogeneous setting under the stated conditions. Neither is a complexity result, and neither is printed with a number in the supplied text. The nonlinear heterogeneous OE finding and the reported improvement for homogeneous OE are experimental results, not numbered formal results. I therefore cannot honestly present the candidate question as mirroring a qualifying named anchor. The paper’s experiments motivate it, but the weakness of that evidence—and the difficulty of carrying DSIC through the continuum limit—keeps this from being a strong anchor-based case.

The case AGAINST (opponent, writing after the proponent)

There is no paper-owned computational result to anchor a mirror to. The theorem statements are attributed prior results about DSIC and linear rebates; the paper’s own claims are experimental outcomes from neural-network training. Its strongest proposed question, optimal-in-expectation redistribution for a continuous population, is therefore a new problem suggested by the experiments, not a continuous version of a named complexity result.

That proposed model has a deeper problem in the ordinary atomless limit. Let \(R(\mu)\) be the VCG revenue per unit mass at society \(\mu\). When one agent has zero mass, the distribution of everyone else is still \(\mu\). Each agent can receive rebate \(R(\mu)\), computed from that distribution. The rebate does not depend on the agent’s report, so adding it to VCG preserves DSIC; in the continuum, the aggregate rebate equals the aggregate VCG revenue. Feasibility is tight and the redistribution index is \(1\). The finite-agent obstruction the paper studies has disappeared, making the limiting OE optimization trivial.

Requiring a sequence of exact finite-agent mechanisms does not rescue the ordinary limit. For a finite type set, one can rebate each agent the minimum VCG revenue per capita over the possible reports that agent could make, holding everyone else’s reports fixed. Each rebate is report-independent and no greater than the actual revenue per capita, so the mechanism remains DSIC and feasible. Away from mass thresholds where the marginal allocation changes, a single report changes the per-capita revenue by a vanishing amount as the population grows. The rebate ratio then tends to \(1\). The interesting remainder lies in finite-size corrections or boundary societies, where exact counts and rounding can control the result; that may motivate a high-multiplicity project, but it is not a nontrivial answer in the continuous society model.

This is a strong objection to the proposed OE anchor, not an airtight case against every imaginable scenario. The public-allocation setting can plausibly have many agents per valuation type, and a project on the finite-size gap might be worthwhile. I cannot honestly claim that no such project deserves attention; the firmer conclusion is that the paper supplies no computational result to mirror, and its most natural continuous version loses the redistribution problem at the limit.

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.