| paper | On Truthful Mechanisms for Maximin Share Allocations |
| authors | Georgios Amanatidis, Georgios Birmpas, E. Markakis |
| venue | IJCAI 2016 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.3
Given a finite catalogue of complete additive valuation types \(V\), rational population masses \(\mu\), rational per-capita supplies \(q\), and a target ratio \(\rho\), decide whether there exists a clone-stable truthful no-money mechanism assigning integral bundles with mass variables \(x_{v,b}\) satisfying \(\sum_b x_{v,b}=\mu_v\) and \(\sum_{v,b}b_kx_{v,b}=q_k\), while every assigned type \(v\) receives bundles with \(v\cdot b\ge\rho\,\operatorname{MMS}_v(q)\), where \(\operatorname{MMS}_v(q)=\sup_{\pi:\,\mathbb E_\pi[b]=q}\min_{b\in\operatorname{supp}(\pi)}v\cdot b\), and every denominator-cleared finite clone realization is individually truthful.
A high-multiplicity configuration mechanism model: valuation types \(v\) carry mass \(\mu_v\), integral bundle configurations \(b\) receive fractional population mass \(x_{v,b}\), supplies scale through \(q\), and the objective is the largest clone-stable truthful MMS-approximation ratio \(\rho\).
The aggregate variables \(x_{v,b}\) do not by themselves determine how one clone's report changes its assigned bundle, so clone-stable truthfulness requires a specified denominator-compatible finite implementation and is not a canonical property of \(\mu\) alone.
fatal: False
The mirror covers the cardinal-model truthful approximation barrier of Theorem 3.3; it leaves the ordinal and public-rankings mechanisms, their positive approximation theorems, and the other impossibility results unmirrored.
The strongest honest positive case is a high-multiplicity mirror of the paper’s cardinal model, anchored by Theorem 3.3. This is an impossibility anchor rather than an NP-hardness theorem: the paper contains no named NP-hardness or polynomial-time classification. Theorem 3.3 is proved in the paper, through Lemmas 3.4 and 3.5, rather than merely cited.
The theorem says that for \(n=2\), \(m\ge4\), and every \(\varepsilon\in(0,1/2]\), there is no truthful \((1/2+\varepsilon)\)-approximation mechanism for the cardinal model. The proof establishes the result already for \(m=4\), then extends it to larger \(m\) by adding zero-value dummy items. The impossibility remains even on highly restricted valuation profiles whose rows are permutations of either \(\{2+\varepsilon,1+\varepsilon,1-\varepsilon,\varepsilon/2\}\) or \(\{2-\varepsilon,1+\varepsilon,1-\varepsilon,\varepsilon/2\}\).
I would mirror this with Continuous Cardinal MMS Mechanism Design, \(\mathrm{CMMS}_\infty\).
There are finitely many recurring indivisible good classes \(K=\{1,\ldots,m\}\), finitely many complete valuation types \(V=\{v^1,\ldots,v^\tau\}\), and a rational population distribution \(\mu\), where \(\mu_v\) is the mass of agents having the complete additive valuation \(v\). There is also a rational per-capita supply vector \(q\): a population of size \(N\) has \(Nq_k\) copies of good \(k\). The number of agents and goods therefore grows together, while \(\tau\) and \(m\) remain small relative to the population.
This is a plausible regime for a large public-benefits or educational-allocation system: many applicants have one of a small number of recurring valuation profiles, and the system has many copies of each standardized resource. The valuation vector is the complete type; agents of the same type are indistinguishable for the purposes of the mechanism.
Bundles remain integral. A bundle is \(b\in\mathbb Z_{\ge0}^m\), with value \(v(b)=v\cdot b\). Only the mass of agents assigned to each integral bundle is fractional. If \(x_{v,b}\) is the mass of type \(v\) receiving bundle \(b\), a feasible allocation satisfies
\[ \sum_b x_{v,b}=\mu_v \]
and
\[ \sum_{v,b} b_kx_{v,b}=q_k \]
for every good \(k\). Thus a type may be split across several integral bundles, but no individual receives a fractional good.
The appropriate continuous maximin-share benchmark is the high-multiplicity limit
\[ \operatorname{MMS}_v(q) = \sup_{\pi} \left\{ \min_{b:\pi_b>0} v(b): \sum_b \pi_b b=q,\; \sum_b\pi_b=1 \right\}, \]
where \(\pi\) is a finite-support distribution over integral bundles. Clearing denominators shows the dictionary exactly: a rational \(\pi\) can be repeated across sufficiently many cloned agents to produce a finite partition, and every finite partition induces such a \(\pi\).
The continuous problem is:
Given \(V\), \(q\), \(\mu\), and \(\rho\), does there exist a truthful no-money mechanism which, from reported valuation types, assigns integral bundles so that every positive-mass type \(v\) receives only bundles \(b\) satisfying
\[ > v(b)\ge \rho\,\operatorname{MMS}_v(q)? > \]
Equivalently, find the largest achievable \(\rho\).
Truthfulness needs to be stated carefully. Literal atomless individual strategyproofness can become vacuous because one agent has zero mass and cannot change \(\mu\). The faithful version should therefore require clone-stable truthfulness: after clearing denominators, every rational continuous instance induces a finite allocation rule on cloned agents, and every individual clone must satisfy the paper’s original inequality
\[ v_i(A_i(V))\ge v_i(A_i(V_i',V_{-i})). \]
This preserves the paper’s strategic question while taking the high-multiplicity limit. It is a deliberate extension, and should be labelled as such rather than hidden.
The authors should recognize this as their problem. It preserves additive cardinal utilities, indivisible bundles, maximin-share guarantees, no monetary transfers, and truthful reporting. The only new modelling move is the one the programme asks for: replace a large population of repeated valuation types by masses and scale the recurring good supply accordingly.
I would expect the high-multiplicity version to be more tractable than Theorem 3.3’s finite two-player obstruction, at least for bounded \(m\) and \(\tau\). Its allocation layer is a configuration LP over integral bundles, with incentive constraints added on top. The four-item contradiction in Theorem 3.3 relies heavily on scarcity and on forcing a named player between a small number of allocations. In the continuous regime, a positive mass of identical agents can be distributed across several integral bundles without fractionalizing any individual outcome. The \(1/2\) barrier may therefore dissolve.
The likely classification is Class A in bounded-catalogue regimes, using configuration LPs and column generation, with a possible Class C boundary when bundle pricing or MMS-threshold computation becomes knapsack-like. Further questions include whether clone-stable truthfulness permits ratios strictly above \(1/2\), whether exact \(\mathrm{MMS}_\infty\) allocation is feasible, and what finite-population rounding loss is necessary.
The weakest point is genuine: the source theorem concerns a fixed finite set of named players and deterministic individual deviations, whereas the serious continuous formulation needs a clone-stable or ex-ante interpretation of truthfulness. If one refuses that repair, strategyproofness becomes vacuous. The mirror is therefore strongest as a high-multiplicity extension of the cardinal mechanism-design problem, not as a literal replacement of two players by an atomless population.
The proponent’s only serious anchor is Theorem 3.3, but it does not survive continuization without changing the object that theorem studies.
Theorem 3.3 is a deterministic, ex-post truthfulness impossibility for two named players sharing four one-copy items. Both its strategic quantifier and its maximin-share benchmark are inherently finite. If we let the number of agents grow while retaining the four physical items, then every sufficiently large partition contains empty bundles, so each player’s maximin share is \(0\) (or the partition problem becomes undefined if empty bundles are forbidden). The approximation guarantee then becomes vacuous.
The proposed repair—scaling the supply to \(Nq\) as the population grows—is mathematically coherent, but it is not a population version of the theorem’s object. It replaces two players and four scarce items by \(N\) players and a replicated per-capita market. The benchmark becomes
\[ \sup_{\pi:\,\mathbb E_\pi[b]=q}\min_{b\in\operatorname{supp}(\pi)} v(b), \]
a packing benchmark over recurring bundle types, rather than the two-way partition benchmark in Theorem 3.3. That is a potentially interesting fair-division problem, but it is a new replicated-market model, not a continuous formulation of the paper’s finite-player impossibility.
More fundamentally, the proposed mass allocation \(x_{v,b}\) cannot express the paper’s truthfulness condition. The theorem compares the utility of a particular player \(i\) before and after that player changes her report:
\[ v_i(A_i(V))\ge v_i(A_i(V_i',V_{-i})). \]
An aggregate plan records only how much mass of each type receives each bundle. It does not say which individual receives which bundle, nor how the allocation responds to one clone’s deviation. The same \(x\) can be implemented by a deterministic assignment, a lottery, or a type-dependent coalition rule, and these have different incentive properties.
The proposed “clone-stable truthfulness” does not repair this. Clearing denominators gives many possible finite implementations of the same mass plan, with potentially different responses to an individual report. To require truthfulness for every such implementation is not a property of the continuous instance; to choose one implementation is to retain the full named-agent mechanism that continuization was supposed to eliminate. Since one clone has vanishing mass, an aggregate mechanism cannot even observe the deviation that the theorem quantifies over.
The available repairs each change the paper’s problem. Randomly assigning integral bundles yields truthfulness in expected utility rather than the paper’s deterministic ex-post inequality. Requiring a whole type to receive one bundle removes the splitting that makes the configuration LP continuous. Letting an entire type or mass report strategically replaces individual truthfulness with coalition or population truthfulness. None is a harmless formal adjustment.
The fact that valuations repeat does not solve this issue. High multiplicity can legitimately erase idiosyncratic valuation data in an allocation problem, but here the central object is precisely an individual’s ability to misreport while other individuals remain fixed. Agents of the same valuation type may be interchangeable for welfare, yet they are not interchangeable in the incentive constraint.
Thus the proposed \(\mathrm{CMMS}_\infty\) can be made worthwhile only as a new research problem in continuum mechanism design, with a newly chosen notion of randomization, implementation, or population-level truthfulness. The paper itself supplies no faithful continuous-population computational result to mirror. The universal negative cannot be proved—such a new model might well be valuable—but the proponent has not shown a continuous mirror of Theorem 3.3; they have replaced its strategic unit and its fairness benchmark.
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.