| paper | A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna |
| authors | Yu Zhou, Tianze Wei, Minming Li, Bo Li |
| venue | IJCAI 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
Given finitely many complete agent roles \(a\), item roles \(e\), rational masses \(\mu_a\) and \(\lambda_e\), a finite typed incidence schema whose rational blow-up supplies each item copy to its endpoint agent copies, and additive endpoint values, decide whether an incidence-preserving mass allocation of indivisible item copies exists such that every supported integer bundle configuration satisfies \(\mathrm{EFX}^{+}_{0}\) against every supported configuration, and construct it. The variables \(z_{a,B}\) distribute role-\(a\) agent mass over integer bundle configurations \(B\), subject to \(\sum_B z_{a,B}=\mu_a\), item-supply and incidence constraints, and the original strict-positive deletion rule.
A relational high-multiplicity allocation model with finite complete local agent and item types, rational population and item masses, a finite typed incidence schema, and \(z_{a,B}\) over indivisible bundle configurations; feasibility is ex-post \(\mathrm{EFX}^{+}_{0}\), not fractional utility or lottery fairness.
The opponent's strongest unresolved point is that Theorem 4 may concentrate many non-good items on a vanishing-mass agent, so a limiting mass allocation can lose tightness or make one-item EFX degenerate; the proponent specifies indivisible configurations but does not resolve this scaling issue.
fatal: False
The mirror covers Theorem 4's additive mixed-manna allocation existence and construction, and the implied Corollary 3 guarantee; it leaves the orientation results, including Theorem 1, Corollaries 1–2, and Theorem 2, untouched.
My strongest case is anchored on Theorem 4, proved in this paper:
“For any graph, an \( \mathrm{EFX}^{+}_{0} \) allocation always exists and can be computed in polynomial time.”
I would mirror its additive mixed-manna subcase.
The plausible regime is a large federation of repeated local communities: many municipalities, districts, teams, or research groups, connected by recurring shared resources or jobs. Each agent belongs to one of finitely many complete roles: the role specifies its valuation vector, which item channels are incident to it, and whether each incident item is a good, chore, or dummy. Each edge-item likewise belongs to one of finitely many recurring edge roles. A population mass \( \mu_a \) is the fraction of agents of role \(a\), while \( \lambda_e \) is the corresponding mass of indivisible items of edge-role \(e\). A realistic instance might have millions of agents and items but only dozens or hundreds of local roles.
The graph structure cannot be replaced by bare marginal type counts. The continuous object must retain a rational incidence table or regular blow-up specification saying how edge-role copies are paired with endpoint-agent copies. Thus the type records the local incidence pattern, not merely a valuation. Clearing denominators produces a finite graph with many cloned agents and repeated, but still indivisible, edge-items.
I would call the problem:
Typed-Population \( \mathrm{EFX}^{+}_{0} \)-Allocation. An instance consists of finitely many agent roles, item roles, rational agent masses, rational item masses, endpoint-incidence data, and additive endpoint valuations. A solution is an incidence-preserving mass allocation of the indivisible item copies to agent copies. Equivalently, let \(z_{a,B}\) be the mass of role-\(a\) agents receiving the integer bundle configuration \(B\). The variables must satisfy
\[ \sum_B z_{a,B}=\mu_a \]
for every agent role \(a\), and
\[ \sum_{a,B} z_{a,B} B_e=\lambda_e \]
for every item role \(e\), together with the incidence constraints. Every bundle configuration in the support must satisfy \( \mathrm{EFX}^{+}_{0} \) against every other supported configuration, using the original one-item deletion rule: the removed item from the envied bundle must have strictly positive value to the envious agent, while the removed item from the envious agent’s own bundle may be any non-good item. The output is the mass allocation \(z\), not a fractional bundle: each \(B\) contains integer item copies.
The question is whether such a \(z\) exists, and, if so, to construct one. Rational masses can be denominator-cleared into a finite high-multiplicity graph, so this has the required rational-clone interpretation. It is not a cake-cutting or fractional-outcome reformulation: population frequencies are continuous, but edge-items and individual bundles remain discrete.
I expect this structured problem to be Class A, although that is a conjectural classification rather than something proved by Theorem 4. The proof of Theorem 4 already reduces the construction to local cases based on whether an edge is a good for an endpoint, whether an agent has nonnegative total incident value, and where non-good items can safely be placed. In the typed regime, those cases should aggregate into transportation or configuration-LP constraints over roles and bundle configurations. The natural algorithmic question is whether the configuration columns admit a polynomial pricing or separation routine in the number of roles and the encoding length of the masses, rather than in the expanded population size.
This is recognisably the authors’ problem: vertices are still agents, edges are still indivisible items, endpoint locality is retained, mixed signs are retained, and the fairness predicate is exactly \( \mathrm{EFX}^{+}_{0} \). The scenario changes only the population regime—from named agents to repeated complete roles. Existing high-multiplicity allocation work would support the legitimacy of this regime rather than undermine its novelty.
I would not claim that this mirrors the whole paper. It covers Theorem 4, including its additive mixed-manna subcase. I deliberately would not use Theorem 1 or Theorem 2 as additional anchors without a separate synchronization construction, because their reductions exploit topology and Boolean choices that type aggregation might erase.
The weakest point is precisely that topology and atom-level indivisibility matter. A model containing only \( \mu_a \) and \( \lambda_e \), with no incidence coupling and no integer bundle configurations, would be an invalid fractional relaxation: it could make an agent appear to value an item merely because the corresponding role is incident somewhere in the population. Even with the richer model above, it remains open whether Theorem 4’s per-edge construction compresses to time polynomial in the number of roles and \( \log \lambda_e \). That is a real technical gap, but it is a gap in a faithful, author-recognisable continuous question—not a reason to reject the mirror.
The only anchor raised is Theorem 4, and it is a genuine named computational result. The negative case therefore cannot rely on the paper lacking an algorithmic theorem. It has to attack whether the proposed typed population is actually a continuous society.
The problem is that the graph is not determined by masses of agent and item roles. EFX is evaluated on individual bundles, while an edge is valuable precisely to its two particular endpoints. The same agent-role masses, edge-role masses, and endpoint-role counts can be realized by different pairings of endpoints and hence by different incidence neighbourhoods. Those differences can change which allocations are EFX. To preserve them, the model must retain a matching, lift, rooted network, or graphon-like object specifying the atom-level incidence relation. At that point the “type” is no longer a finite complete agent type; it includes its relational neighbourhood. The proposed \(z_{a,B}\) variables have the same problem: if \(B\) is defined over actual edge copies, they reintroduce the original graph, and if \(B\) is defined only over edge roles, they generally lose the information EFX needs.
The strongest repair is to impose a regular blow-up or repeated-community structure. But this leads to a scaling dilemma. If one repeats a fixed finite graph, the continuous object is only a mixture of allocations of that finite template. It does not make the population itself the computational object; it records frequencies of already finite local instances. If instead edge supply and incidence scale with the population, individual bundles grow. The deletion of one indivisible item then becomes negligible relative to bundle values, so \( \mathrm{EFX}^{+}_{0} \) approaches ordinary envy-freeness rather than retaining the paper’s one-item relaxation. If supply is held fixed while the population grows, almost every agent has an empty bundle and the fairness condition becomes degenerate.
The proof of Theorem 4 exposes this difficulty rather than solving it. It may place all non-good edges into the bundle of one specially chosen agent. Under a growing clone construction, that agent can have vanishing population mass while absorbing a positive fraction of the items, so the bundle distribution is not tight: mass escapes to configurations whose size tends to infinity. Spreading those items over a positive-mass cohort would be a new fairness model, not the theorem’s allocation semantics.
The other possible repairs change the object. A graphon or fractional-incidence model makes items divisible; an ex-ante distribution over bundles replaces ex-post EFX by an average or lottery condition; and a positive-mass deletion rule replaces “remove any one item” by a coalition-level notion. Each could be interesting, but none is a direct continuization of Theorem 4. Existing high-multiplicity allocation work would support the plausibility of repeated roles; it does not resolve this identity-and-indivisibility obstruction.
Thus the proponent has identified a legitimate extension, but not yet a continuous-population mirror in the programme’s central sense. Preserving the graph makes the model a compressed representation of an atom-level allocation instance; removing the graph makes EFX ill-defined or changes it into a different fairness notion. I would reject this as a worthwhile direct ChoCo mirror, while conceding that the negative case is not absolute: a carefully specified sparse-network or finite-template extension could still be publishable, just not as the claimed continuization.
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.