| paper | The Complexity of Envy-Free Graph Cutting |
| authors | Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak |
| venue | IJCAI 2022 |
| filed under | fairalloc · cake |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
Given a connected graph \(G=(V,E)\), an integer capacity scale \(N\), rational type masses \(N\mu_t\), and utilities \(u_t:E\to\mathbb{Q}_{\ge0}\), decide whether measures \(\lambda_t\) over connected pieces of the scaled graph exist with total mass \(N\mu_t\), fully allocate every edge point, and satisfy \(u_t(P)\ge u_t(Q)\) for \(\lambda_t\)-almost every \(P\) and \(\lambda_s\)-almost every \(Q\), for all types \(t,s\).
A nonatomic high-multiplicity graph-cutting model with complete utility types \(t\), population distribution \(\mu\), mass allocation measures \(\lambda_t\), extensive edge capacity, and pointwise envy-free feasibility.
The opponent's \(O(|E|)\)-bound on cross-edge pieces and the need to scale edge capacity mean the mirror may wash out the paper's graph-topological hardness and may not be population-only under the strictest normalization.
fatal: False
The mirror covers the main EF-GC and EF-VDGC feasibility results, including Theorems 4 and 9, while leaving the auxiliary lemmas, portfolio-enumeration details, and the future FPT questions aside.
The strongest case is a population-scaled version of EF-GC, with the graph, connectedness requirement, and envy relation unchanged. My lead anchor is Theorem 4, proved in this paper: “EF-VDGC and EF-GC are NP-hard” even with two agents on graphs of treewidth \(2\) and maximum degree \(3\). The reduction is from NUMBER PARTITIONING, so the hardness is driven by graph structure and edge utilities rather than by a large number of named agents.
A faithful continuous setting is a large network-service population. The graph represents a road, rail, or computing-capacity network; each agent is a crew or team receiving a connected piece. Agents have standardized utility profiles over edges. A type \(t\) is the complete vector \(u_t:E\to\mathbb{Q}_{\ge0}\), including every preference and parameter used by the problem. The population has type masses \(\mu_t\), with \(\sum_t\mu_t=1\), and \(N\mu_t\) agents of type \(t\) at population scale \(N\). The intended regime is \(N\gg\tau\): millions of crews or service requests, but only a small catalogue of standardized utility types.
The scale \(N\) matters. With one fixed graph and \(N\to\infty\), almost every agent would receive a vanishingly small piece. A plausible high-multiplicity model therefore scales each edge to capacity \(N\), representing \(N\) repeated service units or shifts, while retaining the same graph topology and edge-utility densities.
Call the resulting problem \(\mathrm{Mass\text{-}EF\text{-}GC}_{\infty}\). An instance consists of \(G=(V,E)\), \(N\), rational type masses \(\mu\), and utility vectors \(u_t\). A solution is a mass allocation \(\lambda\): for every type \(t\), \(\lambda_t\) is a measure over connected pieces \(P\) of the scaled graph, with total mass \(N\mu_t\). For an edge point \(x\), the resource must be fully allocated:
\[ \sum_{t}\int \mathbf{1}[x\in P]\,d\lambda_t(P)=1. \]
The utility of type \(t\) for \(P\) is \(u_t(P)=\sum_{e\in E}u_t(e)\lvert P\cap e\rvert\). The allocation is envy-free when, for every type \(t\), almost every piece assigned to \(t\) is valued by \(t\) at least as highly as almost every piece assigned to any type \(s\). The objective is feasibility, or equivalently maximizing the minimum envy slack and asking whether it is nonnegative.
When \(N\) is integral, the masses \(N\mu_t\) are integral, and each \(\lambda_t\) is restricted to unit atoms, this is exactly the paper’s finite EF-GC problem after uniform rescaling of edge lengths. Allowing arbitrary real mass allocations is the high-multiplicity relaxation. Thus this is not merely “the cake is divisible”—that is already true in the paper. The new continuous object is the population of agents and its distribution over complete utility types.
I expect the treewidth-\(2\), degree-\(3\) restriction of \(\mathrm{Mass\text{-}EF\text{-}GC}_{\infty}\) to be Class B: hardness should transfer because the reduction’s combinatorics live in the connected graph partition, not in individual-agent multiplicity. The particularly attractive feature is that the source hardness already holds with two agents, suggesting that replacing named agents by mass should not remove the essential topological obstruction. The exact lifting still has to be proved: a genuinely fractional mass allocation might split a type over more pieces than the reduction permits. That is a real technical issue, not something I would silently assume away.
The second anchor is Theorem 9, also proved here: both EF-GC and EF-VDGC can be solved in time \(\lvert A\rvert^{O(\lvert E(G)\rvert^2)}\). It gives a different, algorithmic mirror. Call it \(\mathrm{Mass\text{-}EF\text{-}GC}_{\infty}[k]\), where \(k=\lvert E(G)\rvert\). It has the same instance and solution definition, but asks for an exact mass allocation on an arbitrary graph, parameterized by \(k\).
This is a particularly plausible continuization because the proof already consists of branching, linear programming, geometric ordering, and a final matching step. In the mass version, guesses of named agents can be replaced by guesses of types and mass thresholds; the variables \(x_e^0,\delta_e,x_e^1\) remain LP variables; envy-critical-agent orderings become orderings of utility types; and the final bipartite matching becomes a capacitated flow matching type masses to residual pieces. The natural expected bound is something like \(\tau^{O(k^2)}\operatorname{poly}(L)\), hence polynomial for every fixed number of edges, with the sharper question being whether the dependence on \(k\) can be made fixed-parameter rather than XP.
I therefore expect this second mirror to be Class A in the bounded-edge regime. It generates concrete questions: is the type-mass version actually FPT in \(k\)? Does the geometric portfolio argument remain polynomial in \(\tau\)? Can an exact mass solution be rounded to a finite \(N\)-agent allocation with controlled envy loss? Do the same results hold for the vertex-disjoint variant?
I would not use Theorems 2 or 3 as additional anchors. Theorem 4 already supplies the stronger bounded-degree hardness direction, while Theorem 9 supplies the natural LP-based tractability direction. Together they cover the paper’s central structural contrast without pretending that every theorem has an equally meaningful population analogue.
The weakest point is that \(\lambda\) permits fractional type mass to be distributed over bundle patterns. That is more than simply replacing a list of agents by a histogram, and it may destroy the NUMBER PARTITIONING reduction. The resource scaling is another necessary modelling choice absent from the paper’s one-graph presentation. But both choices are explicit consequences of taking population continuity seriously: fixed resources make the nonatomic limit degenerate, while fractional mass allocation is the natural high-multiplicity relaxation. The resulting questions preserve the paper’s graph, utilities, connected pieces, and envy-free objective closely enough that the authors should recognize them as continuizations—and they expose exactly where their discrete hardness does or does not survive.
The strongest negative case is that both anchors share a modelling mismatch: EF-GC partitions one fixed finite graph into exactly one connected piece per named agent. Making the population nonatomic either makes those individual pieces disappear or changes the resource model as well.
With the paper’s fixed graph, the continuum limit is degenerate. A finite-measure graph cannot contain uncountably many disjoint positive-length pieces. Almost every infinitesimal agent must therefore receive a zero-measure piece, with utility \(0\). Envy-freeness becomes \(0\ge 0\) almost everywhere. To avoid this, the proponent scales every edge’s capacity with \(N\). That may be sensible, but it is no longer a population-only continuization: the resource supply has also been replicated. The resulting problem is capacitated graph cutting, a new model whose relation to the paper must be justified rather than assumed.
There is a sharper topological obstruction. The paper’s own proof of Theorem 9 observes that on each edge at most two agents can receive a piece that continues onto another edge. Hence, for a graph with \(k\) edges, at most \(2k\) agents participate in the genuinely graph-connected part of a partition. If \(N\) agents are placed on a fixed graph, this is zero population mass in the limit. Almost all agents receive intervals lying wholly inside single edges. The graph-cutting structure that drives Theorem 4 is therefore carried by exceptional named agents, not by the population distribution.
This defeats Theorem 4 as a population anchor. Its reduction has exactly two agents with identical valuations, and its NUMBER PARTITIONING structure is encoded by the two global connected pieces they receive. Replacing them by many copies of one utility type does not produce two positive-mass connected blocs: each copy may receive its own connected piece, and the type mass may be distributed over many edge-local pieces. Introducing a requirement that each type or bloc receive one connected aggregate piece would restore the reduction, but that is an additional bloc-contiguity constraint, not the paper’s individual envy-free graph cutting. Keeping only two macro-agents avoids the problem by abandoning population continuity.
Theorem 9 has the same dilemma. Its algorithm branches on exceptional named agents and envy-critical named agents, then finishes with a one-to-one matching between agents and pieces. Replacing the matching by capacitated flow is valid only after changing the fairness condition to an aggregate or expected-envy condition. Under the paper’s pointwise envy-freeness, every positive-mass piece assigned to a type must be at least as good for that type as every other assigned piece; in particular, pieces in the support of one type must lie on an appropriate equal-utility level. A flow does not enforce this support condition. Enforcing it produces a new configuration/support problem, not an automatic \(\tau^{O(k^2)}\) version of the theorem.
The alternatives are not better. Retaining unit agents and integral multiplicities gives a legitimate high-multiplicity formulation, but not a continuous population problem. Allowing fractional type mass gives a new fractional allocation model. Scaling the graph or repeating its cells gives a joint population-and-resource limit. Letting the graph grow with \(N\) may preserve a nonzero fraction of cross-edge agents, but then the graph—not merely the society—is carrying the growing combinatorics.
So the proponent has not established either claimed mirror under the programme’s strict population-only scope. The negative case is nevertheless not airtight: if ChoCo is willing to study capacitated graphs with nonatomic agent mass and a carefully formalized pointwise envy notion, that is a coherent new research programme. What fails is the stronger claim that Theorems 4 and 9 already provide faithful 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.