| paper | Almost Envy-Freeness in Group Resource Allocation |
| authors | M. Kyropoulou, Warut Suksompong, A. Voudouris |
| 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}\text{-complete}\), already for \(\varepsilon=0\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 3.7
statement extracted from the paper’s text layer
Given finite indivisible goods \(G\) and a rational distribution \(\mu\) over types \(t=(i,v)\), where \(i\in\{1,2\}\) is the fixed group and \(v\in\{0,1\}^{|G|}\) is a binary additive valuation, choose a partition \(B_1\dot\cup B_2=G\) minimizing \(D_\mu(B_1,B_2)=\sum_t\mu_t\mathbf{1}[t\text{ is not EF1 under }(B_1,B_2)]\); decide whether \(D_\mu\le\varepsilon\), with \(\varepsilon=0\) as the exact analogue of Proposition 3.7.
Two fixed libraries or public-resource pools share indivisible goods; each type \(t=(i,v)\) is a recurring cohort of mass \(\mu_t\), and only the partition \(B_1\dot\cup B_2=G\) is chosen. The objective is dissatisfied population mass, where a type in group \(i\) is dissatisfied when \(v(B_i)<v(B_{3-i})-\max_{g\in B_{3-i}}v(g)\), with the empty maximum defined as \(0\).
The exact \(\varepsilon=0\) problem ignores mass, while \(\varepsilon>0\) changes universal EF1 into weighted democratic EF1; the latter is a genuine extension rather than a literal restatement.
fatal: False
It covers Proposition 3.7's fixed-two-group binary EF1 existence decision and its Monotone 3-SAT hardness; it leaves the positive existence theorems, EFX results, variable-group model, and graph-theoretic structural arguments untouched.
My lead, and in fact my only serious anchor, is Proposition 3.7. It is proved in the paper. It states that, given two fixed groups of agents with binary valuations for indivisible goods, deciding whether there exists an EF1 allocation is NP-complete. Membership in NP follows by checking a proposed allocation. The hardness proof reduces from Monotone 3-SAT with distinct literals: each variable becomes a good; each positive clause becomes an agent in group \(A_1\) who desires exactly its three variable-goods; and each negative clause becomes an agent in \(A_2\) with the analogous valuation. Such an agent is EF1 exactly when her group receives at least one desired good. Thus assigning a good to \(A_1\) represents setting the variable true, assigning it to \(A_2\) represents false, and an EF1 allocation exists exactly when the formula is satisfiable.
I would mirror this with Continuous Fixed-Group EF1 Coverage. The goods remain indivisible, since the paper allocates public bundles to groups; only the population is continuized.
An instance consists of a finite set \(G\) of goods and a finite-support distribution \(\mu\) over types \(t=(i,v)\), where \(i\in\{1,2\}\) is the agent’s fixed group and \(v\in\{0,1\}^{|G|}\) is the agent’s binary additive valuation. Two agents have the same type precisely when they belong to the same group and have the same valuation of every good. The mass \(\mu_t\) is the fraction of the whole population of that type. The distribution may be given explicitly by rational masses, with \(\sum_t\mu_t=1\).
The decision variable is a partition \(B_1\mathbin{\dot\cup}B_2=G\). For \(t=(i,v)\), write \(t\) as EF1 under this partition when
\[ v(B_i)\geq v(B_{3-i})-\max_{g\in B_{3-i}}v(g), \]
taking the maximum to be \(0\) when \(B_{3-i}=\varnothing\). Define the dissatisfied mass
\[ D_\mu(B_1,B_2) = \sum_{t\in T}\mu_t \mathbf{1}\!\left[t\text{ is not EF1 under }(B_1,B_2)\right]. \]
The continuous problem is to find a partition minimizing \(D_\mu\), or, in decision form, to determine whether there is a partition with \(D_\mu\leq\varepsilon\). The exact mirror of Proposition 3.7 is the zero-threshold case \(\varepsilon=0\): every positive-mass type must be EF1.
This is a plausible high-multiplicity regime. Imagine two fixed libraries, institutions, or public-resource pools receiving bundles of indivisible goods. Each has a large population of users, but users fall into recurring demand cohorts: for example, many users may all desire exactly the same three licences, books, or facilities. The number of people \(N\) can be enormous while the number of distinct group-and-demand types \(\tau\) is moderate. In a finite approximation, type \(t\) represents \(N\mu_t\) agents. This is exactly the paper’s group model: goods are shared within a group, and agents may have different preferences inside that group.
The hardness anchor survives the passage to the continuum. Given the Monotone 3-SAT instance from Proposition 3.7, create one positive-mass type for each clause, with its group and three desired goods as in the paper. A positive-clause type is EF1 precisely when at least one of its three goods goes to \(A_1\); a negative-clause type is EF1 precisely when at least one goes to \(A_2\). Hence \(D_\mu=0\) exactly when the formula is satisfiable. Equivalently, one can create \(q\) agents of every clause type, making \(N=q\tau\) arbitrarily larger than the number of types without changing the normalized problem.
I therefore expect this mirror to be Class B: hardness transfers rather than dissolves. The combinatorics in the reduction live in the goods and the pattern of distinct valuation types, not in the number of named agents. The mass-sensitive optimization version also generates a natural further question: how efficiently can one minimize the fraction of the population that fails EF1, or approximate that optimum, when the population is given by type masses?
The weakest point is that the exact condition \(D_\mu=0\) depends only on which types have positive mass, not on their precise masses. That is unavoidable for a universal guarantee: requiring EF1 for almost every agent makes every positive-mass type relevant. The mass-minimization formulation is what makes the continuum quantitatively meaningful, but it is a natural optimization companion rather than a theorem explicitly studied in the paper. I would not claim that the paper supplies a tractable continuous relaxation; I would claim that Proposition 3.7 supplies a clean, recognizable continuous-population problem whose natural exact boundary remains NP-complete.
The strongest negative case is that Proposition 3.7 itself does not contain a population-level object. For a finite type support \(T\), let \(F_t(B_1,B_2)\) indicate whether type \(t\) is EF1. The exact continuous problem is simply whether there exists a partition satisfying \(F_t=1\) for every \(t\) with \(\mu_t>0\). Thus \(D_\mu=0\) depends only on \(\operatorname{supp}(\mu)\), not on the masses. Replicating every clause agent \(q\) times merely pads the population; it changes neither the feasible allocations nor the decision problem.
This makes the zero-threshold formulation a quotient of the original finite instance, rather than a substantive continuization. The hard object remains the finite set of goods together with the distinct valuation types. There is no mass transfer, aggregate utility, per-capita resource constraint, or other mechanism through which population mass affects the allocation. The proposed “continuous” population is therefore computationally inert.
The positive-threshold repair is more serious. Minimizing \(D_\mu\) turns Proposition 3.7 into weighted Max-Monotone-3-SAT: each clause type receives its population weight, and a clause is dissatisfied exactly when its corresponding clause is falsified. A library-cohort interpretation makes that problem quite plausible, and per-group dissatisfaction constraints would not remove its legitimacy.
But this is no longer the named result’s mirror; it is a new democratic relaxation of group fairness. Preserving the paper’s universal EF1 requirement forces the zero threshold, where the masses disappear. Making masses matter requires changing the fairness objective, not merely continuizing the population. That is the only substantial objection available.
It is not, however, enough to support the requested universal negative verdict. The cohort scenario is genuinely high-multiplicity and the weighted problem is a recognizable computational question. The proponent’s anchor therefore survives the stronger scrutiny: the exact version is thin, but the natural mass-sensitive version is worthwhile. I cannot honestly argue that no useful continuous mirror exists.
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.