| paper | Fairness Towards Groups of Agents in the Allocation of Indivisible Items |
| authors | Nawal Benabbou, Mithun Chakraborty, Edith Elkind, Yair Zick |
| venue | IJCAI 2019 |
| 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}\)-complete, even for \(k=3\) and utilities in \(\{0,1,2\}\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given rational profile masses \(\mu_{p,\theta}\) for protected group \(p\) and complete utility profile \(\theta\), rational per-capita supplies \(\sigma_j\) of flat classes \(j\), utilities \(u_{\theta j}\), and threshold \(U\), decide whether there are bundle masses \(b_{pj}\) and flows \(x_{p,\theta,j}\ge0\) satisfying \(\sum_j x_{p,\theta,j}\le\mu_{p,\theta}\), \(\sum_\theta x_{p,\theta,j}\le b_{pj}\), \(\sum_p b_{pj}\le\sigma_j\), with each flow maximizing \(v_p(b_p)=\max_x\sum_{\theta,j}u_{\theta j}x_{p,\theta,j}\), such that \(\sum_p v_p(b_p)\ge U\) and \(v_p(b_p)\ge v_p(b_q)\) for every \(p,q\).
Protected group \(p\) and complete utility profile \(\theta\) form mass-bearing types \((p,\theta)\); item classes \(j\) have scalable supplies \(\sigma_j\). The variables are bundle masses \(b_{pj}\) and aggregate matching flows \(x_{p,\theta,j}\), with utilitarian matching value as objective and exact typewise envy-freeness as the fluid limit of TEF1; finite realizations still assign integral flats to individual agents.
Because one-item slack vanishes, exact typewise envy-freeness may not capture the authors' intended fairness target rather than merely its pointwise limit; the case gives no formal finite-\(n\) rounding theorem connecting the two.
fatal: False
The mirror covers Theorems 3 and 4, while leaving Theorems 1–2, Lemma 1, Proposition 1, the intermediate lemmas and corollaries, and the experiments unmirrored.
The strongest mirror is a high-multiplicity version of the paper’s public-housing interpretation, with the paper’s “types” treated as protected groups and complete utility profiles treated as the actual agent types.
Suppose a large housing authority allocates many indivisible flats. There are finitely many flat classes \(J\), with \(\sigma_j n\) copies of class \(j\), and finitely many protected groups \(p\in[k]\). Within group \(p\), agents have finitely many complete utility profiles \(\theta\in\Theta_p\), where \(\mu_{p,\theta}\) is the fraction of the population having profile \((p,\theta)\). Thus
\[ \sum_{p,\theta}\mu_{p,\theta}=1. \]
The complete type is \((p,\theta)\): it records the protected group and the agent’s utility for every flat class. The number of such types is fixed or modest, while \(n\) is large. A finite approximation has \(n\mu_{p,\theta}\) agents and \(n\sigma_j\) individual, still-indivisible flats. The continuous variables below merely describe aggregate densities; they do not give an individual a fractional flat.
If \(b_{pj}\) is the mass of class-\(j\) flats assigned to group \(p\), define the group’s normalized type-value by
\[ v_p(b)= \max \left\{ \sum_{\theta\in\Theta_p}\sum_{j\in J} u_{\theta j}x_{\theta j}: \sum_j x_{\theta j}\le \mu_{p,\theta}, \ \sum_\theta x_{\theta j}\le b_j, \ x_{\theta j}\ge 0 \right\}. \]
This is exactly the paper’s maximum-weight matching value, now in its transportation or high-multiplicity form. The allocation must satisfy
\[ \sum_p b_{pj}\le \sigma_j \]
for every flat class \(j\). Group \(p\)’s own matching is required to attain \(v_p(b_p)\), just as the paper requires an optimal matching inside every allocated bundle.
My lead anchor is Theorem 3, proved in this paper. The theorem says that ASSIGNTEF1 is NP-complete even with only three types. An instance consists of agents partitioned into types, items, nonnegative utilities \(u(i,j)\), and a threshold \(U\). The question is whether there is an allocation into disjoint type-bundles, with an optimal matching inside each bundle, that is typewise envy-free up to one item and has utilitarian welfare at least \(U\). The paper proves hardness by reducing PARTITION: for numbers \(s_1,\ldots,s_\ell\) summing to \(\sigma\), it creates \(\ell+2\) items, two groups with \(\ell+1\) agents each, a third group with two agents, two special items worth \(\kappa>\sigma\) to the third group, and ordinary item values \(s_j\) for the first two groups. The welfare threshold is \(2\kappa+\sigma\); meeting it while satisfying TEF1 forces the ordinary items to be split into two subsets of value \(\sigma/2\).
The corresponding continuous problem is:
HM-ASSIGNTEF1. Given rational \(\mu_{p,\theta}\), flat supplies \(\sigma_j\), utilities \(u_{\theta j}\), and a welfare threshold \(U\), decide whether there are bundle masses \(b_{pj}\) and within-group matching flows attaining \(v_p(b_p)\) such that
\[ \sum_p v_p(b_p)\ge U \]
and
\[ v_p(b_p)\ge v_p(b_q) \qquad\text{for every }p,q. \]
The latter is the exact continuum limit of TEF1. In an \(n\)-agent approximation, removing one flat changes normalized values by only \(O(1/n)\); hence “envy-free up to one item” converges to typewise envy-freeness. Equivalently, one can study the finite-resolution version with a one-copy slack of mass \(1/n\) and then ask for its limit as \(n\to\infty\).
A solution is therefore a mass allocation \(b\), together with matching flows witnessing each group’s optimal value. The question remains recognisably the authors’ question: it retains groupwise matching valuations, typewise fairness, indivisible assignments in every finite realization, and utilitarian welfare. Only the population and the supply of repeated flat classes have been continuized.
I expect the PARTITION hardness in Theorem 3 not to transfer directly. In its reduction, the difficulty is choosing whole items for one group or the other. In HM-ASSIGNTEF1, each repeated flat class can be split in aggregate between groups, so the two groups can generally balance their values fractionally rather than solve a subset-sum instance. Thus the reduction’s hardness is population-multiplicity hardness that the continuum may dissolve. The fixed-profile, fixed-flat-class subcases look like candidates for Class A, using transportation LPs, configuration formulations, or separation over matching values.
I would not claim that the full problem is automatically polynomial. The constraint \(v_p(b_p)\ge v_p(b_q)\) compares two variable bundles through a maximum-matching value and is not obviously a single LP constraint. If hardness survives after fractional splitting, it would more plausibly be Class C—continuum-specific hardness arising from these cross-group value comparisons—rather than transferred discrete hardness. Natural follow-up questions are whether the three-group case is tractable, whether the two-group case is always tractable, and exactly when the fluid fairness constraints admit an LP or separation oracle.
A second, useful anchor is Theorem 4, also proved here. It states that for binary utilities \(u(i,j)\in\{0,1\}\), every instance admits a non-wasteful TEF1 allocation, and one can compute such an allocation in polynomial time. The constructive PMURR algorithm assigns an item only when it has positive marginal utility for some group, repairs excessive envy by revoking and reallocating items, and proves termination using the decreasing potential
\[ \Phi=\sum_p |M_p|^2. \]
Its continuous counterpart is:
Fluid-Binary-TEF-NW. Given rational group/profile masses, repeated-item supplies, and binary utilities, compute bundle masses \(b_{pj}\) and optimal matching flows that are typewise envy-free and non-wasteful. Non-wastefulness means that no positive mass of an item class is withheld or assigned to a group whose right derivative for that class is zero while some group has positive marginal value for it.
I expect Fluid-Binary-TEF-NW to be Class A. The binary structure that drives Theorem 4 survives aggregation: values are matching capacities, envy relations remain ordered by bundle mass, and the revocation argument should have a flow or infinitesimal-balancing formulation. This is a meaningful boundary result rather than a separate allocation problem.
The mirror covers Theorems 3 and 4, not the paper’s experiments or every auxiliary proposition. Its weakest point is that TEF1 becomes exact typewise envy-freeness after normalization. That is a real modification. I think it is justified because it is forced by the high-multiplicity limit, and because the finite approximants are literally the paper’s indivisible-item problem with \(n\) replicated agents and item supplies. The other vulnerability is the need for repeated flat classes; but the paper itself names public housing as a motivating setting, and large housing programmes with many households and a small catalogue of flat types provide a credible regime in which this is precisely the natural formulation.
The strongest case against the proposed mirror is that both Theorem 3 and Theorem 4 derive their content from indivisible items, not from population multiplicity.
If the item set \(M\) remains finite while the agent population grows, the continuum disappears. Once every positive-mass agent profile has sufficiently many representatives, matching against \(M\) uses at most \(|M|\) agents, so increasing the population changes nothing. With per-capita normalization, all values tend to zero; without it, the mass distribution becomes irrelevant. Theorem 3 then remains a finite partition of named items, while Theorem 4 remains a finite item-transfer argument. Neither produces a genuine continuous society.
The proponent avoids this by replacing each item \(j\) with \(\sigma_j n\) repeated copies. That is mathematically coherent, but it changes the object more substantially than claimed. The partition reduction no longer chooses whole items for one group or the other: it chooses quantities \(z_j\) with \(0\le z_j\le \sigma_j\). Its central condition becomes a fractional balancing constraint rather than PARTITION. Likewise, TEF1 becomes exact typewise envy-freeness, because removing one physical item changes normalized value by \(O(1/n)\):
\[ v_p(b_p)\ge v_p(b_q). \]
This is a sensible fluid fair-division problem, but it is not a stable limit of the paper’s fairness concept in the relevant semantic sense. TEF1 exists precisely because one indivisible item is a meaningful unit of protection. In the continuum that unit vanishes. Retaining a positive slack requires introducing an arbitrary macroscopic parameter \(\varepsilon\), which is no longer “up to one item.”
The same defect affects Theorem 4. PMURR’s proof relies on revoking whole items and on the discrete potential
\[ \Phi=\sum_p |M_p|^2. \]
After item supplies are scaled, transfers occur continuously, and the theorem’s combinatorial termination argument has no limiting object. One can study flow feasibility, marginal capacities, or exact envy-freeness, but that is a new transportation problem rather than a population version of the theorem’s constructive guarantee. A single item approved by two groups illustrates the discontinuity: finite TEF1 permits giving it to either group, whereas exact fluid envy-freeness requires splitting a positive supply of copies between them. Keeping one item preserves the old problem but makes the population irrelevant; scaling copies preserves population relevance but changes the fairness problem.
This is a real objection to calling the proposed formulation an automatic mirror. It does not, however, establish the universal negative claim. The paper explicitly motivates public housing, and a housing authority with many repeated flat classes and finitely many utility profiles is a credible high-multiplicity regime. The programme also expressly permits per-capita supplies as a co-modification. Thus the resulting transportation-based fairness problem is recognisable and potentially worthwhile. The honest conclusion is that the negative case defeats neither anchor outright; it shows only that the proponent’s formulation is a substantive new fluid allocation model, not a direct continuization of Theorems 3 and 4.
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.