| paper | Envy-Free Allocations Respecting Social Networks |
| authors | Robert Bredereck, Andrzej Kaczmarczyk, R. Niedermeier |
| venue | ATAL 2018 |
| 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 one valued resource, dyadic masses and supply, and a role graph consisting of disjoint directed cycles of length two. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finitely many positive-mass role types \(T\) with population distribution \(\mu\), a directed role graph \(H=(T,F)\), common \(0/1\) utilities over a finite resource catalogue \(R\), and per-capita supplies \(\rho_r\), find a mass allocation \(\lambda_{t,B}\) over integral bundles \(B\subseteq R\) such that each type receives mass \(\mu_t\), every resource supply is met, and for every role edge \(t\to t'\), every supported bundle of type \(t\) is at least as valuable to type \(t\) as every supported bundle of type \(t'\); otherwise report infeasibility.
A finite role-type population model with masses \(\mu_t\), replicated indivisible resource supplies \(\rho_r\), and decision variables \(\lambda_{t,B}\) assigning mass to integral bundles. The task is feasibility under exact resource conservation and support-wise weak graph-envy constraints.
The proposed role quotient does not preserve the paper’s arbitrary-agent graph or its outdegree-two port construction, so the predicted Class B hardness transfer remains unproved and may require a separate role-network reduction.
fatal: False
The mirror covers complete weak graph-envy-free allocation with identical \(0/1\) preferences, especially Theorem 1 and Corollary 1. It leaves strong graph-envy-freeness, Pareto efficiency, utilitarian welfare, heterogeneous utilities, and the paper’s other graph restrictions unmirrored.
The strongest positive case is a high-multiplicity version of the paper’s complete weak graph-envy-free allocation problem. It keeps the resources indivisible for every individual; only the population becomes continuous.
Let \(T\) be a finite set of population types. A type records an agent’s utility vector and social role: agents of type \(t\) have the same additive utilities and compare themselves with the same role-types. The society is a mass vector \(\mu\), with \(\mu_t\) the fraction of agents of type \(t\). Let \(H=(T,F)\) be the directed role graph. An arc \(t\to t'\) means that every type-\(t\) agent compares its bundle with bundles received by type-\(t'\) agents.
Let \(R\) be a finite catalogue of indivisible resource kinds, with per-capita supply \(\rho_r\). A solution is a distribution \(\lambda_{t,B}\), where \(\lambda_{t,B}\) is the mass of type-\(t\) agents receiving the integral bundle \(B\subseteq R\). It must satisfy
\[ \sum_{B\subseteq R}\lambda_{t,B}=\mu_t \]
and
\[ \sum_{t\in T}\sum_{B\ni r}\lambda_{t,B}=\rho_r \]
for every \(r\in R\). It is graph-envy-free if, whenever \(t\to t'\), every bundle in the support of type \(t\) has at least as much utility for \(t\) as every bundle in the support of type \(t'\):
\[ \lambda_{t,B}>0,\ \lambda_{t',B'}>0 \quad\Longrightarrow\quad u_t(B)\ge u_t(B'). \]
The task is to find such a complete allocation or report that none exists. The \(\lambda\)-values are fractional only because they describe population mass; every individual still receives an integral bundle. Rational \(\mu\) and \(\rho\) have the usual high-multiplicity interpretation: multiplying them by \(M\) gives \(M\mu_t\) agents of each type and \(M\rho_r\) copies of each resource kind.
This is plausible in a large employer or public agency with thousands of employees in repeated job grades, regions, or departments. Employees in the same role have standardized \(0/1\) preferences over a catalogue of rewards, and the organization has a formal comparison policy between role classes. The original three-person team is not a high-multiplicity regime, but a national organization with millions of employees and perhaps dozens of role-types is. The resource supply naturally scales per capita: training seats, office upgrades, recognition awards, or charitable benefits are replicated across the population.
My lead anchor is Theorem 1, proved in this paper. It states:
C-GEF-Allocation for identical \(0/1\) preferences is NP-hard even if every vertex has outdegree at most two.
Here C-GEF-Allocation asks, given agents, indivisible resources, identical \(0/1\) utility functions, and a directed social graph, to find a complete weakly graph-envy-free allocation. The paper proves this by a reduction from Clique; its construction uses strongly connected components as blocks whose agents must receive equal-sized bundles.
The corresponding continuous problem is \(\mathrm{HM\text{-}C\text{-}GEF}_{\infty}^{0/1}\): given \((T,\mu)\), a directed role graph \(H\), common \(0/1\) utilities, and per-capita resource supplies \(\rho\), find a complete mass allocation \(\lambda\) satisfying the exact graph-envy condition above.
I expect this problem to be Class B: hardness should transfer. The reduction’s meaningful choices are not among named individuals but among vertex- and edge-roles in the social network. The large strongly connected components can be represented by large masses. If the component sizes in the proof are \(a_t\) and the total number of agents is \(N\), set \(\mu_t=a_t/N\), and scale the resource supplies by \(1/N\). The graph-envy inequalities still force every agent in a component to receive the same integral number of valued resources. Multiplying the mass equations by \(N\) recovers exactly the integer counting argument in the proof: choosing \(k\) vertex-components and \(\binom{k}{2}\) compatible edge-components is equivalent to choosing a \(k\)-clique.
This is genuine high multiplicity: the number of role-types is roughly the number of vertices and edges in the Clique instance, whereas the population mass represented by the construction is much larger. The continuum has removed individual identity without removing the combinatorics encoded in the role graph. The paper’s exact individual outdegree-two promise does not automatically survive quotienting an arbitrary person-level graph into role-types, so I would treat bounded role outdegree as a follow-up theorem rather than claim it for free. The unrestricted role-graph mirror already captures the named hardness result’s underlying problem.
A useful second anchor is Corollary 1, also proved in this paper:
C-GEF-Allocation for identical \(0/1\) preferences and a strongly connected input graph is solvable in linear time.
The continuous counterpart is \(\mathrm{HM\text{-}SCC\text{-}C\text{-}GEF}_{\infty}^{0/1}\), the same problem restricted to a strongly connected role graph. In this case every directed cycle forces all agents to receive the same number \(q\) of positively valued resources. Since total population mass is \(1\), if
\[ \rho_+=\sum_{r:v(r)=1}\rho_r, \]
then necessarily \(q=\rho_+\), and \(q\) must be an integer. Subject to the obvious per-resource capacity conditions, that condition is also sufficient: distribute \(q\) useful resources to every individual and place universally worthless resources arbitrarily. Thus the finite divisibility test in Corollary 1 becomes a per-capita integrality test. I expect this mirror to be Class A, with a simple arithmetic or flow-based algorithm.
Together these anchors give a credible boundary rather than a tractability-only caricature. The general role-network problem should retain the Clique hardness, while strong connectivity and identical \(0/1\) utilities collapse it to an aggregate equality condition.
The scope is deliberately limited. This mirrors the paper’s complete weak graph-envy-free problem under identical \(0/1\) preferences. It does not claim to continuize the paper’s Pareto-efficiency or utilitarian objectives, nor its strong graph-envy-free results. Those would be separate mirrors. It also does not replace the allocation problem by cake cutting: resource units remain indivisible at the individual level.
The weakest point is the treatment of the social network. A person-level arbitrary sparse graph is generally incompatible with a small finite type space, because an agent’s exact neighborhood can make it a distinct type. My mirror therefore assumes that social comparison is institutionalized between role classes. That is a substantive modelling choice, although it is natural for hierarchical organizations, departments, job grades, and standardized peer-comparison policies. If the authors insist that only arbitrary person-specific networks count, the mirror becomes much weaker. Under the role-based interpretation, however, the paper’s central object—local envy constrained by a directed social relation—survives intact.
The main follow-up questions are whether the hardness transfer can be formalized with bounded role outdegree, whether rational mass solutions admit controlled finite-population rounding, and whether replacing exact support-wise envy by average envy produces a genuinely different, possibly LP-solvable problem.
The strongest case against the proposed mirror is a fidelity objection. In the paper, the social network is a graph on individual agents, and an agent’s network position is part of what distinguishes it. Agents inside one strongly connected component need not be the same type: the reduction in Theorem 1 deliberately uses “port” agents with different outgoing arcs. Thus one cannot simply replace each component by a mass and preserve the paper’s instance. The component’s equality of bundle sizes comes from cycles among distinct agents, whereas the proposed \(\lambda\)-model obtains it by adding an intra-type comparison or self-loop. Replacing individual arcs by complete role-to-role comparisons is a new role-network model, not merely the continuous version of the paper’s arbitrary-agent graph.
Theorem 1 therefore transfers only after two substantive changes: the network becomes institutional and role-based, and the bounded individual outdegree promise is abandoned or reconstructed using additional port types. At that point the combinatorial object being studied is a network of roles with replicated populations, not the paper’s social network. The authors might accept that as a new model, but its plausibility must come from an external organizational story rather than from the paper itself. If that story is rejected, the claimed hardness anchor disappears.
Corollary 1 is an even weaker anchor. In a strongly connected role graph with identical \(0/1\) utilities, envy-freeness forces every agent to receive the same integer number \(q\) of valued resources. The population distribution and almost all network information then vanish; feasibility reduces to whether the per-capita supply satisfies \(\rho_+=q\) for some integer \(q\), together with elementary capacity conditions. This is a divisibility check inherited from the paper’s observation, not a substantive continuous-population phenomenon. Allowing average envy or heterogeneous utilities would make the problem richer, but would no longer mirror Corollary 1.
That is the best negative case, but it is not decisive under the programme’s rules. The proposed role-based organization is a plausible high-multiplicity scenario, and per-capita replication of resources is explicitly an admissible co-modification. With those choices, Theorem 1 does yield a genuine continuous-population question, even if it is a role-network variant. Consequently I cannot honestly sustain the universal claim that no worthwhile mirror exists: the Corollary 1 mirror is nearly degenerate, but the Theorem 1 mirror survives the main objections.
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.