| paper | Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory |
| authors | Pasin Manurangsi, Warut Suksompong |
| venue | IJCAI 2021 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard for every fixed \(k\ge 2\), even when \(r=\lfloor c_k\sqrt{\tau}\rfloor\) for a positive rational constant \(c_k\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5.2
Given indivisible goods \(G=[m]\), \(k\) groups, rational additive types \(t=(i,v)\), and a rational mass distribution \(\mu\) over those types, together with \(r\), distinguish whether there is a partition \((A_1,\ldots,A_k)\) such that every type with \(\mu_t>0\) has exact consensus \(1/k\)-division, or whether no partition is \(\mathrm{PROP}_r\) for every such type.
The society is a finite-support distribution \(\mu\) over group-labelled additive valuation types; the decision variable is a \(0\)-\(1\) partition of indivisible goods, and the objective is the worst typewise EF/PROP deletion count, with exact consensus as the zero-error case.
The strongest objection is that universal typewise fairness makes the masses semantically irrelevant: changing multiplicities preserves feasibility, and the proposed \(\sqrt{n'}\) threshold changes under expansion of the same distribution.
fatal: False
The mirror covers Theorem 5.2's gap hardness and Corollary 5.1's constructive approximate allocations, with the algorithmic bound expressed in terms of support size \(\tau\); it leaves the discrepancy lemmas, purely existential bounds, and nonadditive future variants aside.
The strongest positive case is a high-multiplicity mirror of the paper’s group fair-division problem, led by Theorem 5.2. The mirror continuizes the population only: goods remain indivisible, each good is assigned wholly to one group, and every member of a group evaluates the group’s bundle.
Consider \(k\) large public-service districts or organizations sharing a catalogue \(G=[m]\) of indivisible goods. A complete type is a pair \((i,v)\), where \(i\) is the group and \(v\in\mathbb{Q}_{\ge 0}^{m}\) is an additive valuation, with \(v(S)=\sum_{\ell\in S}v_\ell\). The society is a rational mass distribution \(\mu_{i,v}\), with \(\sum_{i,v}\mu_{i,v}=1\). A realistic regime would have millions of residents but perhaps only tens or hundreds of recurring demographic or occupational valuation types. The mass \(\mu_{i,v}\) records the fraction of society of each type; group membership is part of the type because it determines which bundle is “one’s own.”
An allocation is still a partition \((A_1,\ldots,A_k)\) of the indivisible goods. For every positive-mass type \((i,v)\), the paper’s fairness conditions are imposed typewise. For example, \(\mathrm{PROP}_r\) requires some \(B\subseteq G\setminus A_i\), \(|B|\le r\), such that \(v(A_i)\ge v(G)/k-v(B)\). Exact consensus \(1/k\)-division requires \(v(A_p)=v(A_q)\) for every pair of bundles \(p,q\). This is faithful to the paper’s “every agent” guarantee: a rare type still matters, just as one exceptional agent matters in the finite model.
My lead anchor is Theorem 5.2, proved in this paper. It states that for every constant \(k\ge2\), there is a constant \(\varepsilon_k>0\) such that it is NP-hard, given \(m\) goods and \(k\) groups each containing \(n'\) agents with additive utilities, to distinguish between: (YES) there exists a consensus \(1/k\)-division; and (NO) no allocation is proportional up to \(\varepsilon_k\sqrt{n'}\) goods.
The corresponding continuous problem is:
\(\textsc{Gap-Continuous-Group-Fair-Division}_k\). Given \(m\), \(k\), rational additive type valuations \(v\), a rational mass distribution \(\mu\), and an integer \(r\), distinguish between:
The intended hardness threshold is \(r=\lfloor\varepsilon_k\sqrt{n'}\rfloor\) when the distribution is the empirical distribution of a finite instance.
The finite-to-continuous dictionary is exact. Given the paper’s \(n'\) agents in each group, assign mass \(\mu_{i,v}\) equal to the fraction of group \(i\) having valuation \(v\), aggregating duplicate agents. A finite allocation satisfies consensus or proportionality exactly when the corresponding continuous allocation does. Conversely, any rational distribution can be expanded using a common denominator into a finite high-multiplicity instance. Thus the continuous problem is not an outcome-space relaxation or an averaging surrogate; it is the same indivisible-goods question with indistinguishable agents represented by masses.
I expect the general problem to be Class B: hardness transfers. The combinatorics in Theorem 5.2 live in the goods and valuation matrix—ultimately in discrepancy and set-splitting gadgets—not in the names of individual agents. Aggregating identical agents preserves every relevant inequality. The continuum therefore does not turn the allocation into an LP: the decision variable remains a \(0\)-\(1\) partition of goods. The paper’s theorem does not, by itself, prove hardness under the additional restriction that the number of types is tiny compared with the population; that sharper high-multiplicity question is precisely worth studying. But it gives a direct hardness anchor for the unrestricted type-distribution problem, and there are already simple partition-type obstructions even with very few valuation types.
A useful secondary anchor is Corollary 5.1, also stated and established in this paper, although its discrepancy subroutines come from earlier work. It says that there is a deterministic polynomial-time algorithm which, given the goods and additive utilities, computes a consensus \(1/k\)-division, an envy-free allocation, or a proportional allocation up to \(O(\sqrt n)\) goods.
Its continuous counterpart is \(\textsc{Type\text{-}Compressed\text{-}Consensus\text{-}Division}\). Given \((G,k,\mu)\), let \(\tau\) be the number of positive-mass group-labelled types. Output a partition minimizing
\(\max_{(i,v):\mu_{i,v}>0}\max_{p,q}\min\{|B|:B\subseteq A_q,\ v(A_p)\ge v(A_q\setminus B)\}\).
The paper’s discrepancy construction should give a deterministic polynomial-time solution with value \(O(\sqrt{\tau})\), rather than \(O(\sqrt N)\), where \(N\) is the number of named agents represented by the distribution. Repeated valuation rows are redundant in the discrepancy instance, so this is a genuine benefit of the high-multiplicity representation. I would classify this approximate problem as Class A. The same type-compressed formulation can be made for the paper’s EF and PROP guarantees.
The authors should recognise both questions as their problem: the setting remains additive utilities, indivisible goods, group bundles, and the same EF/PROP/consensus notions. The mirror covers the paper’s main computational contribution, especially Theorem 5.2 and Corollary 5.1; it does not try to continuize the discrepancy theory itself or make the goods divisible.
The weakest point is that, for the paper’s worst-case fairness notions, the exact masses often affect only representation size, not feasibility: a type with mass \(10^{-6}\) can veto an allocation just like a type with mass \(1/2\). The opposing case can therefore call this “profile compression” rather than a fully mass-sensitive continuum. That criticism is fair. It does not invalidate the mirror, because universal fairness is exactly what the paper studies and high multiplicity is precisely the identification of indistinguishable agents. It does suggest the natural next problems: allow an \(\alpha\)-fraction of population mass to violate fairness, introduce unequal group entitlements, and determine whether exact consensus remains hard when \(\tau\) is fixed while the population mass becomes arbitrarily large.
The proponent’s dictionary is exact, but it exposes the central problem: in this paper, population mass is not part of the computational object.
For any two distributions \(\mu\) and \(\nu\) with the same positive support of group-labelled valuation types, the feasible allocations and all EF, PROP, and consensus conditions are identical. A society consisting of ten copies of one valuation type and one consisting of a billion copies have the same continuous instance \(\mu=\delta_v\). Likewise, changing the masses from \(0.999\) and \(0.001\) to \(0.5\) and \(0.5\) changes nothing, because the paper universally quantifies over agents rather than weighting them. This is not an objection based on individual identity: agents of the same complete type really are interchangeable. It is a stronger point that multiplicity itself has no semantic role.
That defeats the proposed reading of Theorem 5.2. Its parameter \(n'\) counts independent valuation rows in a discrepancy instance. The reduction does not establish hardness when \(n'\) is large because each of a small number of types is repeated. If identical rows are aggregated, the relevant parameter is the number \(\tau\) of distinct valuation constraints, not the population size. The proposed threshold \(r=\varepsilon_k\sqrt{n'}\) is not even an invariant of \(\mu\): the same distribution can be expanded to \(n'\) agents or \(qn'\) agents, producing different thresholds while leaving every allocation and every exact fairness condition unchanged. With fixed \(m\), the threshold eventually exceeds \(m\), at which point PROP becomes vacuous.
The proponent’s more modest gap problem with an independently supplied integer \(r\) is well-defined, but it is simply the paper’s finite indivisible-goods problem indexed by the support of \(\mu\). The masses can be deleted from the input. That is profile compression, not a population continuum. Requiring \(\tau\ll n'\) does not repair it: it makes the population larger while leaving the problem exactly unchanged, and Theorem 5.2 provides no hardness or asymptotic phenomenon in that regime.
Corollary 5.1 fares no better. Deduplicating identical valuation rows and running the same discrepancy algorithm plausibly gives an \(O(\sqrt{\tau})\) bound. But this is an ordinary row-compression or parameterized formulation. The algorithm never uses \(\mu\), and the improvement comes solely from replacing the number of named agents by the number of distinct constraints. It does not yield a continuous optimization problem, a mass-transfer problem, or a population-sensitive computational question. A high-multiplicity treatment can certainly be useful in other fair-division models, but here the paper’s universal fairness guarantees make multiplicity algorithmically redundant.
The best attempted repair would make mass matter: require only a \(1-\alpha\) fraction of the population to satisfy EF or PROP, or minimize the \(\mu\)-mass of violating types. That could be an interesting new weighted fair-division problem. It is not, however, a mirror of either named result. It replaces the paper’s \(\ell_\infty\), every-agent guarantee—the very feature used in its discrepancy bounds and Theorem 5.2—with a quantile or average objective. Using group masses as entitlements similarly changes proportionality rather than continuizing it.
Thus the paper has genuine computational results, but its agents are used as independent constraint rows, not as a population whose mass affects a decision. With few types, the continuum disappears; with many types, the representation is essentially the original instance. The honest negative case is therefore strong for the proposed mirrors, though not a proof that mass-weighted variants are uninteresting. Those variants would be new research problems, not worthwhile continuous mirrors 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.