On the Structure of EFX Orientations on Graphs

The paper's numbered results are structural existence and characterization statements; its only NP-hardness claim is an unnumbered attribution to [16], so criterion (a) fails. The proposed cohort-and-copy model is a plausible extension of graphical fair division, but its mass questions would be new computational problems rather than continuous analogues of named computational results in this paper. Therefore no anchor can produce green.

The objection that survived

The proposed \(\lambda\)-model changes an edge from a good valued by two named endpoint agents into a good type shareable by two entire cohorts, so it is not a literal high-multiplicity instance of the paper's incidence model.

What the mirror covers

The proposed extension covers the bipartite existence result in Lemma 4.1, the \(0\)-\(1\) characterization in Lemma 3.1, and the chromatic obstruction in Theorem 3.6; it does not cover the cited NP-hardness result or the remaining structural propositions.

Open questions for a prover

The case FOR (proponent)

The strongest honest mirror is a high-multiplicity version of graphical fair division. The paper has no numbered theorem asserting NP-hardness, membership in P, FPT, or similar; its NP-hardness statement is only a prose attribution to Christodoulou et al. [16]. I therefore anchor the case on the paper’s numbered structural results, all proved in this paper.

Take a finite role graph \(H=(V,E)\). A role \(v\) represents a large cohort of otherwise indistinguishable agents: the same incident resource types and the same valuation. Let each role have mass \(q=1/|V|\). For every edge \(e=uv\), let there be mass \(q\) of identical indivisible item copies, each assignable only to a \(u\)-agent or a \(v\)-agent. This is the direct \(N\)-fold blow-up of the paper’s model: \(N\) agents of each role and \(N\) copies of each edge-good, with the number of distinct agent types remaining \(|V|\).

The continuous allocation is a distribution over discrete bundles. Let \(\lambda_{v,B}\) be the mass of role-\(v\) agents receiving bundle \(B\subseteq E(v)\). It must satisfy \(\sum_{B\subseteq E(v)}\lambda_{v,B}=q\) for every \(v\), and for every edge \(e=uv\), \(\sum_{B\ni e}\lambda_{u,B}+\sum_{B\ni e}\lambda_{v,B}=q\). Thus every item copy is assigned to exactly one endpoint. No individual receives a fractional item: \(\lambda\) merely records the measure of agents receiving each integral bundle.

The EFX condition is imposed pointwise on the support of \(\lambda\): whenever \(\lambda_{v,B}>0\), \(\lambda_{w,B'}>0\), and \(g\in B'\), require \(f_v(B)\ge f_v(B'\setminus\{g\})\). The objective is feasibility of a full allocation; equivalently, maximize assigned edge mass subject to these constraints and ask whether the optimum equals \(q|E|\).

My lead anchor is Lemma 4.1, proved here: “Any bipartite graph is strongly EFX-orientable.” The corresponding continuous problem is:

\(\textsf{Bipartite-Mass-EFX}\): given a bipartite role graph \(H=(A\cup B,E)\) and a monotone graphical valuation \(f_v\) for every role \(v\), does a full mass allocation \(\lambda\) satisfying the above EFX constraints exist?

This is recognisably the authors’ problem, not a softened unrelated one. The graph still determines which goods each agent can receive, goods are still indivisible for individuals, and EFX is still an individual guarantee. Only repeated agents and repeated edge-goods have been aggregated.

The proof of Lemma 4.1 lifts directly. Each \(a\in A\) chooses a most-valued incident edge, and all copies of that edge are assigned to \(a\). Because \(A\) is independent, no edge is chosen by two vertices in \(A\). Every remaining edge-copy is assigned to its \(B\)-endpoint. Each \(A\)-agent receives one favourite item; a \(B\)-agent can share at most one item type with any fixed \(A\)-agent; and every \(A\)-bundle has one item, so envy toward it disappears after deleting that item. This gives a constructive Class A result, requiring only the favourite-edge queries and a simple mass assignment. It is arguably the cleanest continuous theorem suggested by the paper.

The second anchor is Lemma 3.1, also proved here, giving a complete characterization of \(0\)-\(1\) strongly EFX-orientable graphs. Its continuous counterpart is:

\(\textsf{Strong-0/1-Mass-EFX}\): given \(H\), decide whether, for every binary additive profile \(a_{v,e}\in\{0,1\}\), where \(f_v(B)=\sum_{e\in B}a_{v,e}\), there exists a full mass-EFX allocation \(\lambda\).

The paper’s forest condition becomes a candidate structural certificate for this problem: for every forest \(H'\) with tree components \(T_1,\ldots,T_k\), one asks whether suitable representatives \(x_i\in T_i\) prevent the positive-mass “envied” roles from interacting. The high-multiplicity version adds a meaningful question: can agents of the same role be distributed among several bundle configurations in a way that preserves EFX for every agent, or does the forest obstruction survive mass replication?

I expect this problem to be Class A in the programme’s intended finite-type regime: with bounded degree or fixed \(|V(H)|\), bundle configurations and binary valuation profiles can be enumerated and the remaining mass feasibility problems solved by linear programming. For unrestricted \(H\), the support-selection problem may itself become continuum-specifically hard, so I would not claim an unqualified polynomial theorem.

These mirrors cover Lemma 4.1 and Lemma 3.1, not the cited NP-hardness result from [16]. They also generate a useful boundary question from Theorem 3.6: does the conclusion \(\chi(H)\le3\) remain true for strong mass-EFX orientability, or can mass replication make some \(\chi(H)\ge4\) graphs feasible? If the odd-subdivision obstruction survives the blow-up, hardness is likely agenda-driven and should transfer; if bundle mixing defeats it, that would be a genuine Class C phenomenon.

The weakest point is that the paper has one item per edge, whereas the mirror requires many copies of every edge-good. Without repeated goods, a large population cannot receive meaningful graphical allocations at all. Also, the continuous bundle distribution may enlarge the feasible set relative to one-copy orientations. That concession matters especially for the paper’s negative examples. It does not undermine the lead case: the bipartite construction is pointwise, uses only integral bundles, and is implemented exactly by finite high-multiplicity blow-ups.

The case AGAINST (opponent, writing after the proponent)

The negative case is that this paper is a poor fit for ChoCo’s computational agenda. Its own contributions are structural and axiomatic: Lemma 3.1, Lemma 4.1, Theorem 3.6, and the propositions classify graphs or prove existence. The only complexity statement is a prose attribution to Christodoulou et al. [16], not a numbered computational result of this paper. Thus every proposed mirror must invent the computational question rather than continuize one the paper actually studies.

There is also a serious modelling problem. In the paper, an agent is a vertex and a good is an individual edge, with the incidence relation between them doing essential work. Replacing each vertex by \(N\) agents and each edge by \(N\) copies does not preserve this model. If every copy remains incident to two named agents, the result is essentially \(N\) copies of the original graph. If, as the proposed \(\lambda_{v,B}\) formulation does, every role-\(v\) agent may receive any copy of every incident edge type, then an item is no longer valued by the two endpoint agents of the graph; it is valued by two entire cohorts. That is a new role-based fair-division model, not a high-multiplicity version of the paper’s graphical valuation model.

Lemma 4.1 is the weakest anchor. In the role-based redesign, its proof lifts mechanically: each \(A\)-role receives its favourite edge type and the remaining mass goes to \(B\). In the faithful repeated-copy model, one simply repeats the same orientation in every copy. Either way, the mass variable contributes no computational content. The proposed decision problem is only an existence restatement with the same one-paragraph constructive proof. Maximizing assigned mass, minimizing violations, or optimizing over randomized orientations could be interesting, but each would be a new optimization problem rather than a continuous mirror of Lemma 4.1.

Lemma 3.1 fares little better. If all agents of a role have the same valuation, the universal valuation assignment is just the original finite graph problem with repeated copies attached. Splitting a cohort among several bundles introduces a distribution over integral allocations, not a new population-level object. Under pointwise EFX, only which bundles have positive mass matters; the numerical masses disappear from the fairness constraints. The resulting feasibility question is therefore a finite support-selection or lottery problem. If EFX is instead imposed only in expectation, the model has changed to probabilistic or fractional fair division, which is explicitly outside ChoCo’s population-continuization scope.

Theorem 3.6 cannot repair this. For a fixed role graph \(H\), replication does not alter \(\chi(H)\). If one expands the graph itself, its chromatic number concerns the chosen expanded incidence graph rather than the paper’s role graph. The suggested question—whether mixing bundles can defeat the odd-subdivision obstruction—is consequently a question about randomized or fractional orientations. It may be mathematically worthwhile, but it is no longer a mirror of the theorem’s object, which is one integral orientation of one graph.

A stronger proposed scenario would repeat a fixed graph motif across many geographically separate communities. That is defensible as a high-multiplicity story, but the continuum is then only a distribution over finitely many motif-level allocations; the number of copies is an implementation device for a lottery. Alternatively, making edge types globally shareable yields the role-based redesign above. Neither route preserves both the paper’s individual edge-agent incidence and a substantive continuous population axis.

The negative case is not airtight. If ChoCo is willing to treat cohort-level edge types as a legitimate new graphical fair-division model, then Lemma 4.1 gives a valid, though very elementary, Class A mass theorem. But under the programme’s stricter standard—population continuity plus a genuine computational question—the paper supplies no strong anchor. The proposed mirrors either repeat a finite structural proof, collapse to a lottery over orientations, or change the underlying allocation model.

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.