| paper | Truthful Fair Division |
| authors | Elchanan Mossel, O. Tamuz |
| venue | SAGT 2010 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), even for \(M=2\), \(\alpha_0=1\), and dyadic supplies and masses. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.4
Given a finite set of complete valuation types \(T\) with masses \(\mu_t\), finite indivisible good classes \(G\), per-capita supplies \(s_g\), and additive values \(v_t(g)\in\{1,\ldots,M\}\), let \(\pi_r\) be a lottery over integral bundles \(b\in\mathbb Z_{\ge0}^{G}\) for report \(r\in T\). Maximize \(\alpha\), or decide whether \(\alpha\ge\alpha_0\), subject to \(\sum_{r\in T}\mu_r\sum_b\pi_r(b)b_g=s_g\), \(\sum_b\pi_t(b)v_t(b)\ge\sum_b\pi_r(b)v_t(b)\) for all \(t,r\), and \(v_t(b)\ge\alpha V_t\) whenever \(\pi_r(b)>0\), where \(V_t=\sum_{g\in G}s_gv_t(g)\).
A finite distribution of complete agent types \(\mu\) over a continuum population, indivisible good classes with per-capita supplies \(s\), report-indexed lotteries over integral bundles, aggregate feasibility, truthful menu incentives, and support-wise proportional utility objective \(\alpha\).
The low-risk error need not vanish with population size: small per-capita inventories can bound \(\alpha\) away from \(1\), and truthfulness under positive-mass report deviations needs a more explicit continuum mechanism.
fatal: False
The mirror covers Theorem 3.4 and the low-risk component of Mechanism 3.2 for indivisible goods. It leaves the non-atomic cake results, super-fair mechanisms, and the continuous-extension theorem of Section 3.3 outside the mirror.
The strongest positive case is a high-multiplicity version of the paper’s indivisible-goods mechanism, not the paper’s already-continuous cake model.
My lead anchor is Theorem 3.4, proved in the paper. In its setting there are \(k\) players and \(n\) indivisible goods, each player has additive values in \(\{1,\ldots,M\}\), and \(n\gg M^k\). Mechanism 3.2 groups goods according to their declared \(k\)-dimensional value vectors, partitions every group into \(k\) nearly equal parts, and distributes the leftovers randomly. Theorem 3.4 states that, when player \(i\) reports truthfully, every part \(C_j\) satisfies
\[ \mu_i(C_j)\ge (1-\epsilon)\frac{\mu_i(\mathcal C)}{k}, \]
where \(\epsilon=O(M^k/n)\). Thus truthful players obtain not merely the correct expected value, but a low-risk guarantee: whichever part they receive, its value is close to their proportional share.
The paper contains no named NP-hardness, P, or parameterized-complexity theorem. I am therefore using Theorem 3.4 as a quantitative algorithmic anchor, not pretending that it provides a hardness result.
Here is the continuous-population mirror I would put to the authors.
Let \(T\) be a finite set of complete agent types, with population masses \(\mu_t\ge0\) and \(\sum_t\mu_t=1\). A type includes the entire additive valuation vector, so two agents of type \(t\) are indistinguishable for the mechanism. Let \(G\) be a finite set of good classes, with indivisible per-capita supplies \(s_g\). Equivalently, a finite \(N\)-agent realization has \(N\mu_t\) agents of type \(t\) and \(Ns_g\) copies of good \(g\). Type \(t\) values a bundle \(b\in\mathbb Z_{\ge0}^{G}\) at
\[ v_t(b)=\sum_{g\in G}v_t(g)b_g. \]
The continuous decision variable is a family of lotteries \(\pi_r\) over integral bundles, one lottery for each possible reported type \(r\). Exactly a mass \(\mu_r\pi_r(b)\) of agents reporting \(r\) receives bundle \(b\). Feasibility requires
\[ \sum_{r\in T}\mu_r\sum_b\pi_r(b)b_g=s_g \]
for every good \(g\). Goods remain indivisible for every individual; fractional quantities arise only because a continuum of same-type agents can be divided into masses receiving different integral bundles.
Define the proportional benchmark for type \(t\) by
\[ V_t=\sum_{g\in G}s_gv_t(g). \]
The problem, which I would call Continuous-Population Truthful Low-Risk Fair Division, is:
Given \((T,\mu,G,s,v)\) and a threshold \(\alpha\), find an anonymous randomized direct mechanism satisfying feasibility, truthfulness in expectation,
\[ \sum_b\pi_t(b)v_t(b) \ge \sum_b\pi_r(b)v_t(b) \qquad \text{for every }t,r\in T, \]
and low-risk proportionality,
\[ v_t(b)\ge \alpha V_t \]
for every type \(t\) and every bundle \(b\) that can be assigned by the mechanism. The objective is to maximize \(\alpha\), or decide whether \(\alpha\ge 1-\varepsilon\).
This is recognizably the same underlying problem as Theorem 3.4: truthful assignment of indivisible goods with proportional and low-risk guarantees. What has changed is the population, not the goods. The regime is many agents, \(|T|=\tau\ll N\), with large groups sharing complete valuation vectors. Plausible examples include large institutions allocating repeated positions, services, or resource packages to cohorts of agents with identical preferences. The paper’s own binning idea becomes more natural here: goods need only be classified by their value signatures across the \(\tau\) distinct types, giving at most \(M^\tau\) signatures rather than \(M^k\) signatures across individually named players.
I would expect this mirror to be Class A in the basic bounded-additive setting. The aggregate problem is a configuration LP over integral bundles, and the continuum makes the mass assignment exact: there is no rounding loss when, say, \(0.37\) of a type receives one bundle and \(0.63\) receives another. A finite-\(N\) implementation should then incur only an additive rounding error tending to zero. The main further questions are whether one obtains a polynomial algorithm in \((|G|,\tau,\log s)\), whether \(\alpha=1\) is attainable whenever valuation types differ, and whether the pricing problem for the configuration LP becomes hard when bundle constraints are added.
The mirror is plausible because Theorem 3.4 already studies bounded valuation signatures, large supplies, random assignment, truthfulness, and low risk. The high-multiplicity version is not obtained by declaring the paper’s cake continuous: it keeps each individual allocation integral and makes only the agent population continuous.
The weakest point is that the theorem itself assumes a small number \(k\) of named players, whereas my mirror takes \(N\) large. Replacing the paper’s \(M^k\) dependence by \(M^\tau\) is a natural extrapolation of its proof, not a result proved there. Also, a fixed one-unit cake with infinitely many agents would make proportional utility degenerate; the per-capita supply normalization is essential. Subject to that co-modification, however, this is a genuine population continuization of the paper’s truthful fair-division problem, and the authors should recognize it as such.
The strongest objection is decisive under the programme’s anchor rule: this paper has no named computational-complexity result to continuize. Theorem 3.4 is a quantitative guarantee for a randomized mechanism, not a theorem about the complexity of a computational problem. The paper explicitly says that its non-atomic results are nonconstructive and may be computationally intractable; its “efficient versions” for indivisible goods are described informally, without a numbered polynomial-time, hardness, approximation, or parameterized-complexity statement. Thus the proposed problem would be a new fair-allocation problem inspired by the paper, not a continuous mirror of one of its computational results.
Even granting Theorem 3.4 as an acceptable algorithmic anchor, the proposed model does not carry its central guarantee across the population limit. The proof works by grouping goods into at most \(M^k\) value-signature bins and splitting every bin into \(k\) parts. In a population of \(N\) agents, reproducing the theorem’s low-risk conclusion requires splitting each bin into \(N\) parts, not \(\tau\) parts: every individual must be able to receive any assigned part while retaining nearly her proportional value. If there are at most \(M^\tau\) bins, the rounding loss for one bundle is on the order of
\[ \frac{1}{N}\sum_S v_t(S)r_S =O(M^{\tau+1}), \qquad r_S<N. \]
The proportional value of one agent is the per-capita quantity \(V_t\), so the resulting relative error is \(O(M^{\tau+1}/V_t)\), independent of \(N\). Population multiplicity therefore does not make the theorem’s low-risk error vanish. To recover the guarantee, one must also make the per-capita supply enormous. That is preservation of the paper’s large-goods regime, not a benefit supplied by continuizing the population.
The obstruction is visible in the simplest type space. Take one valuation type, one good class, value \(1\) per good, and per-capita supply \(s=1/2\). A continuum of agents does not allow fractional individual bundles: half the population receives one good and half receives none. Hence every positive support-wise low-risk guarantee \(v_t(b)\ge \alpha V_t\) fails, despite exact aggregate feasibility. Allowing fractional goods would remove the obstruction, but that is precisely the paper’s outcome-space “continuous extension” in Section 3.3, which is outside ChoCo’s scope. Weakening low risk to an ex-ante expectation restores the paper’s random-assignment mechanism, but then the proposed configuration problem contributes no population-level analogue of Theorem 3.4.
There is also an incentive issue. In the paper, a named player’s report affects the random partition but her expected utility is protected item by item. In an atomless population, an individual deviation has zero mass and cannot affect an allocation rule based on the report distribution. If positive-mass deviations are allowed, one needs group-truthfulness or a specified response of the mechanism to changed type masses. The displayed inequalities for fixed lotteries \(\pi_r\) do not supply that mechanism. Repairing this would produce a new continuum mechanism-design theory rather than a continuization of the paper’s mechanism.
The proponent is right that repeated complete valuation types and per-capita supplies describe a sensible high-multiplicity allocation regime. I would not argue that no worthwhile research could study it. The narrower conclusion is stronger: the paper supplies no qualifying computational anchor, and its only plausible quantitative anchor loses its substantive guarantee unless one reintroduces large per-capita inventories or divisible outcomes. Under the programme’s stated standard, that is not a worthwhile continuous mirror of this paper.
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.