| paper | Truthful assignment without money |
| authors | S. Dughmi, Arpita Ghosh |
| venue | SIGECOM 2010 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Both anchors clearly satisfy the computational-result requirement, and the proposed continuous mass-assignment problems are concrete. However, both mirrors replace unilateral reports by whole-cohort deviations; in a nonatomic population, individual truthfulness is vacuous, while cohort truthfulness is a different strategic requirement. The opponent's objection defeats the faithful mirror under individual semantics, but the proponent gives a plausible author-recognizable cohort variant, so the acceptance of that co-modification remains genuinely undecided.
fails bit b-changes — the continuum limit changes the question
For both anchors, a single job's report is replaced by a positive-mass cohort's report, so the paper's individual truthfulness theorem does not transfer to the proposed continuum mechanism.
fatal: True
It is undecided whether cohort-level or group-strategyproofness is an acceptable high-multiplicity reformulation of the paper's individual-job truthfulness. The grade would become green if that co-modification is accepted, and red if the paper's individual strategic semantics must be preserved.
The proposed mirror covers Theorems 3.3 and 4.6; it leaves the other matching, size-invariant, value-invariant, and generalized-assignment results unaddressed.
The strongest honest case is a high-multiplicity version of the paper’s private-graph assignment model. The continuous object is the population of jobs; machines remain discrete. I would use cohort-level truthfulness: a positive-mass cohort of indistinguishable jobs reports its common compatibility set. This is necessary because individual truthfulness becomes vacuous in a truly nonatomic population: one job cannot change the aggregate distribution.
A type \(t\) therefore contains a complete job description: its public values \(v_{tj}\), public sizes \(s_{tj}\), and private compatibility set \(E_t\). Its mass \(\mu_t\) is the fraction of all jobs of that type, with \(\sum_t\mu_t=1\). Machine capacities are normalized per capita. A solution is an aggregate assignment \(x_{tj}\), where \(x_{tj}\) is the mass of type \(t\) assigned to machine \(j\). This is not fractional assignment of an individual: because the population is nonatomic, the mass of one type can be partitioned into subsets, each receiving one integral machine assignment.
My lead anchor is Theorem 3.3, proved in this paper. It states that no deterministic truthful mechanism without money for maximum-weight bipartite matching in the private-graph model can achieve an approximation ratio better than \(2\). It also states that no randomized mechanism truthful in expectation can achieve an approximation ratio better than
\[
\frac{2}{2\sqrt{2}-1}\approx 1.0938.
\]
The corresponding continuous problem, Continuum Private-Graph Weighted Matching, is this. The input consists of machines \(j\in[m]\), type masses \(\mu_t\), public edge values \(v_{tj}\), private compatibility sets \(E_t\), and normalized machine capacities \(b_j\). The mechanism receives reported sets \(\widehat E_t\) and returns masses \(x_{tj}\) satisfying
\[
\sum_j x_{tj}\le \mu_t,\qquad
\sum_t x_{tj}\le b_j,\qquad
x_{tj}=0\ \text{if }j\notin\widehat E_t.
\]
Its welfare is
\[
\sum_{t,j}v_{tj}x_{tj}.
\]
For every cohort \(t\), truthfulness requires
\[
\sum_{j\in E_t}v_{tj}x_{tj}(E_t,E_{-t})
\ge
\mathbb{E}\!\left[
\sum_{j\in E_t}v_{tj}x_{tj}(\widehat E_t,E_{-t})
\right]
\]
for every false report \(\widehat E_t\).
I expect the Theorem 3.3 lower bounds to survive exactly in this mirror. The paper’s obstruction already appears with two jobs and two machines, so replace those jobs by two positive-mass cohorts and scale capacities and welfare by the same factor. The approximation ratios are unchanged. Thus this is a Class B-style boundary: the obstruction lives in the machine/value geometry and strategic externality, not in population multiplicity. Continuization does not automatically remove every difficulty.
The cleaner constructive anchor is Theorem 4.6, also proved in this paper. It states that there is a polynomial-time, \(2\)-approximate, no-money mechanism for multiple knapsack in the private-graph model that is truthful in expectation.
Its continuous mirror, Continuum Private-Graph Multiple Knapsack, has type data \((\mu_t,v_t,s_t,E_t)\), where value and size are invariant across machines, exactly as in the paper’s MKP. The question is to compute a truthful no-money allocation of mass maximizing
\[
\sum_{t,j}v_t x_{tj}
\]
subject to
\[
\sum_jx_{tj}\le\mu_t,\qquad
\sum_t s_tx_{tj}\le b_j,\qquad
x_{tj}=0\ \text{if }j\notin E_t.
\]
Cohort truthfulness is
\[
v_t\sum_{j\in E_t}x_{tj}(E_t,E_{-t})
\ge
\mathbb{E}\!\left[
v_t\sum_{j\in E_t}x_{tj}(\widehat E_t,E_{-t})
\right].
\]
Here I expect a Class A result stronger than the paper’s finite-population theorem: an exact polynomial-time mechanism. The paper’s Algorithm 4.2 and Lemma 4.5 already give an optimal truthful fractional mechanism for MKP. In the continuum, its fractional solution is an actual assignment of mass, implementable by partitioning each type cohort. The finite \(2\)-factor comes from the integrality gap and randomized rounding needed for individual finite jobs; that loss disappears when a type’s mass can be divided continuously. The resulting problem is a maximum-cost circulation with \(O(\tau m)\) variables, solvable in polynomial time in \(m\), \(\tau\), and the encoding length.
This is not a collision with the paper’s LP formulation. The paper keeps \(n\) named jobs and uses fractional variables as an intermediate relaxation before producing an integral finite assignment. The mirror makes the job population itself continuous; every individual still receives an integral bundle. The paper’s fractional mechanism is therefore supporting machinery for the mirror, not an already-studied continuous population model.
The natural regime is large batches of interchangeable jobs: many tasks with the same public value, processing size, and hardware or machine compatibility pattern. For example, a scheduling service may receive millions of jobs from a few hundred recurring job classes. Then \(n\) is enormous while \(\tau\) is moderate, and capacities scale with population size. The authors would recognize this as their assignment problem: same jobs, same machines, same welfare objective, same private compatibility information, and the same no-money incentive requirement, expressed at cohort scale.
The main follow-up questions are whether the exact MKP result extends to size-invariant and fully generalized assignment, whether pricing remains tractable when types are represented succinctly rather than explicitly, and whether the two-job lower bound of Theorem 3.3 persists under finite high-multiplicity populations with individual—not cohort—deviations.
My weakest point is the cohort-truthfulness convention. If a referee insists that only individual jobs may deviate, then a truly nonatomic continuum makes truthfulness trivial, and Theorem 3.3 does not transfer in its original sense. The proposed mirror must therefore be understood as a positive-mass, type-level or coalitional version of the mechanism-design problem. That is a real modeling choice, not a cosmetic reformulation. Even so, it preserves the paper’s substantive structure and yields a meaningful boundary: exact welfare optimization for continuous MKP, but a two-type strategic obstruction for weighted matching.
The negative case turns on one issue: both anchors are strategic results, and the paper’s strategic object is a named job—not a population type.
For Theorem 3.3, a unilateral deviation by job \(i\) changes one row of the finite instance. In a genuinely nonatomic society, changing one agent’s report changes the distribution by zero measure, so an aggregate allocation \(x(\mu)\) cannot change. Individual truthfulness therefore becomes vacuous: every mechanism satisfies it because the deviator has no aggregate influence. The two-job lower-bound gadget does not survive as stated.
The proponent’s cohort repair is mathematically coherent but changes the problem. If two positive-mass cohorts report collectively, the scaled two-job gadget can indeed reproduce the same approximation lower bound. But the strategic agent is now a coalition, and the requirement is group-strategyproofness for a mass of agents. That is not Theorem 3.3’s private-graph model, whose quantifier is over one named job changing \(E_i\). Restricting deviations to whole cohorts is artificial; allowing arbitrary subcohort deviations requires a new mechanism and a new truthfulness theorem. Retaining named individual deviations instead keeps the finite \(n\)-job model rather than producing a population-only continuum.
The same problem defeats Theorem 4.6. The maximum-cost circulation over type masses is a sensible welfare problem, and its aggregate solution can be implemented by partitioning a nonatomic cohort into individually integral assignments. But the paper’s truthfulness proof is row-wise. In the proposed flow, a row represents an entire cohort, so the proof establishes—at most—a new cohort-level or coalitional incentive condition. If rows represent individual jobs, one must retain all \(n\) rows and the finite-agent mechanism; if they represent masses, the paper’s individual strategic semantics have been replaced.
Thus the claimed exact continuous MKP result is not a transfer of Theorem 4.6’s finite truthful-in-expectation mechanism. It is the paper’s already-known fractional mechanism reinterpreted as a mass allocation, together with a new coalition-truthfulness question. That may be a worthwhile new mechanism-design problem, but it is not a faithful continuous mirror of the theorem’s computational object.
The high-multiplicity scheduling scenario is plausible, so “no repeated types exist” would be a bad objection. The strongest negative is narrower: preserving individual truthfulness makes the continuum strategically empty; restoring nontrivial incentives by positive-mass deviations changes the strategic agents. Under a strict mirror standard, neither anchor survives.
I should be candid, however: if ChoCo explicitly accepts cohort truthfulness as a legitimate co-modification and regards group-strategyproof mass allocation as author-recognizable, then the proponent has a surviving mirror—especially for Theorem 3.3. The universal negative is therefore not airtight; it succeeds only under the stricter requirement that the paper’s individual-job incentive semantics be preserved.
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.