| paper | Tractable Graph Structures in EFX Orientation |
| authors | Václav Blazej, Sushmita Gupta, M. Ramanujan, Peter Strulo |
| venue | SAGT 2025 |
| 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}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
Given a finite typed graph template \(H=(V,E)\) with rational type masses, binary symmetric additive edge values, every \(G_1\)-component equal to \(P_2\), \(P_3\), or \(P_5\), \(G_0\) of maximum degree \(1\), and a nonatomic copy space \(U\), form \(U\times H\), with agents \((u,v)\) and an indivisible good \((u,e)\) joining the corresponding endpoints. Decide whether there is a measurable integral orientation such that, for almost every \(u\), the orientation in that fiber is EFX.
A nonatomic family of repeated finite graphical fair-division instances: vertex roles are agent types with mass \(\mu\), edge roles are indivisible goods, and a measured coupling preserves which endpoints share each good. The decision variable is a measurable endpoint choice for every edge copy, and the objective is EFX feasibility.
The proposed \(y_{\sigma,r}\) variables lose the matching and correlation of \(0\)-edges, while 'positive-mass agent pairs' is ill-defined in an atomless population; the mirror must therefore retain a measured incidence graphing and impose EFX fiberwise or almost everywhere.
fatal: False
The mirror covers the paper's two hardness theorems and their reductions. It leaves the linear-time algorithms, \(P_5\)-free and bounded-treewidth tractability, core structure, and parameterized algorithms as separate follow-up questions.
The strongest positive case is a high-multiplicity version of the paper’s exact EFX-orientation problem, with goods remaining indivisible. The population becomes continuous; the graph incidence structure does not disappear.
A continuum graphical instance has a nonatomic agent population \(X\) of mass \(1\), a finite type set \(Q\), and type masses \(\mu_q\). A type records the agent’s complete local profile: its incident good positions, which goods it values, the values, and the typed incidence relations through which those goods are shared. Goods remain atomic. Each good \(g\) has exactly two endpoint agents, and an orientation assigns \(g\) integrally to one endpoint. Values are symmetric and additive exactly as in the paper.
Formally, if \(A_x\) is the bundle assigned to agent \(x\), the continuous decision problem is to find an orientation such that, for every positive-mass pair of agents \(x,z\) and every \(g\in A_z\), \(w_x(A_z\setminus\{g\})\le w_x(A_x)\). The objective is feasibility: find an EFX orientation for the whole positive-mass population. Fractional quantities describe the mass of agents, goods, or local orientation states; no individual good or bundle is divisible.
The natural regime is a large allocation system with many repeated roles: for example, a public agency repeatedly assigning indivisible bilateral contracts or slots, where each good is relevant to exactly two eligibility roles. There are \(N\) agents per role, \(N\gg |Q|\), and per-capita supplies of each good type scale with \(N\). Agents with the same role and local incidence profile are genuinely indistinguishable. This is not the seven-person inheritance setting; it is a repeated institutional network.
The paper’s Proposition 2, cited from Mehta and Zeng rather than proved here, provides the key bridge. For a preprocessed binary instance whose \(G_1\)-components are trees \(T_1,\ldots,T_t\), an EFX orientation exists exactly when each \(T_i\) can be rooted at some \(r_i\) so that the union \(\bigcup_iN_1(r_i)\) is independent in \(G_0\).
Thus, in the continuum, let \(y_{\sigma,r}\) be the mass of components of component-type \(\sigma\) rooted at \(r\). The constraints are \(\sum_{r\in V(T_\sigma)}y_{\sigma,r}=\eta_\sigma\), together with the requirement that whenever \(y_{\sigma,r}>0\) and \(y_{\sigma',r'}>0\), no positive-mass \(0\)-good joins \(N_1(r)\) to \(N_1(r')\). Each individual component still chooses one integral root; \(y\) only records the aggregate distribution of those choices.
My lead anchor is Theorem 3, the theorem labeled threesatnpc in the manuscript, proved in this paper. It states that EFXO with binary, symmetric, additive valuations is \(\mathrm{NP}\)-complete even when every connected component of \(G_1\) is \(P_2\), \(P_3\), or \(P_5\), \(G_0\) has maximum degree \(1\), and \(G\) is planar. The proof is the paper’s own reduction from Planar Monotone 3-SAT: Lemma 11 constructs planar instances whose \(G_1\)-components are \(P_2\) or \(P_5\), and the zero-degree replacement of Lemma 10 produces the final \(G_0\)-matching and \(P_3\) components.
The corresponding continuous problem is:
\(\textsc{Planar-\{P_2,P_3,P_5\}-EFXO}_\infty\): given a finite type description, rational type masses \(\mu\), per-capita masses of indivisible goods, and a planar typed incidence structure in which every \(G_1\)-component is \(P_2\), \(P_3\), or \(P_5\), every agent has at most one \(0\)-good, and all values are binary, symmetric, and additive, does there exist a measurable integral orientation that is EFX for all positive-mass agents?
I expect hardness to transfer, so this is Class B. Given any finite hard instance from Theorem 3, make every original vertex or local role a type with positive mass, reproduce every edge relation with the corresponding typed good relation, and take \(N\) copies of each type. The root-support constraints are unchanged. If a continuous solution mixed several root states, every state in its positive support would still have to be mutually compatible; choosing one state from each support therefore gives a discrete EFX orientation. The reduction’s combinatorics live in the type graph, the \(P_5\) gadgets, and the \(0\)-edge conflicts—not in the number of named agents—so high multiplicity does not dissolve the hardness.
A second worthwhile anchor is Theorem 2, labeled edgeocttwo, also proved here. It states that EFXO is NP-hard in both of the following cases: first, binary, symmetric, additive valuations on graphs with min-uncut number exactly \(2\); second, symmetric, additive valuations on graphs with min-uncut number exactly \(1\) when all edges except one have binary valuations. The proof is the paper’s reduction from Multicolored Independent Set; the cited \(W[1]\)-hardness of that source problem is external, but the EFXO reductions are proved here.
Its continuous counterpart is \(\textsc{Typed-Min-Uncut-EFXO}_\infty\). The input is the same typed population-and-good structure, with weighted min-uncut mass defined by \(\min_{\chi:Q\to\{0,1\}}\sum_{e:\chi(p(e))=\chi(q(e))}\lambda_e\), where \(\lambda_e\) is the per-capita mass of edge type \(e\). The first promised version requires all edge values to lie in \(\{0,1\}\) and min-uncut mass \(2\). The second requires min-uncut mass \(1\), with exactly one nonbinary symmetric edge type and all other values binary. The question is again whether an integral EFX orientation exists. I again expect Class B: the finite hard instances embed directly, and the weighted min-uncut promise is a natural per-capita version of the paper’s graph parameter.
The authors should recognize both questions as their own problem. The action is still an orientation of each indivisible edge-good; the fairness condition is still EFX; \(G_1\), \(G_0\), roots, induced paths, planarity, and min-uncut remain the same structural objects. Only repeated agents and repeated edge relations are represented by mass. This is population continuization, not outcome-space fractionalization.
The weakest point is that EFXO is relational: a simple distribution over standalone valuation vectors is insufficient. One must carry a typed incidence kernel or measured graph specifying which agents share which goods. That is richer than the central voting model, and some readers may regard it as continuizing the resource network as well as the population. I think that modification is forced by the paper’s own definition: an edge is simultaneously a good and a relation between two agents. The model would be unfaithful if it discarded that relation.
This case deliberately covers only the two hardness anchors above. Further questions are whether fixed \(|Q|\) admits an FPT or polynomial algorithm, whether the paper’s \(P_5\)-free and bounded-treewidth algorithms lift to typed populations, and whether mass-sensitive variants—such as minimizing the mass of agents violating EFX—produce a genuinely Class A or Class C problem rather than the support-purifying Class B behavior of exact EFX feasibility.
The easy negative case is unavailable: threesatnpc and edgeocttwo are genuine computational results proved in the paper. The strongest objection is instead that the proposed continuum does not preserve the paper’s computational object while making population mass meaningful.
An EFX orientation is not determined by the distribution of local valuation types. It is determined by a particular incidence graph \(G\): each \(0\)-edge joins two specific agents, and Proposition 2 turns those specific joins into compatibility constraints between specific root choices. Edge-type masses are only marginals. They do not say which copies of two component types are joined, nor how the several edge incidences of one component are correlated. Two measured graphs can have identical type masses and identical edge-type masses but different pairings, and hence different sets of feasible EFX orientations.
This directly breaks the proponent’s support argument. If \(y_{\sigma,r}>0\) and \(y_{\sigma',r'}>0\), it does not follow that the two root states must be compatible: a copy using \(r\) need only avoid conflict with the particular copies to which its \(0\)-edge stubs are matched. Requiring every positive-support root state to be mutually compatible imposes a new, much stronger “complete mixing” model. It is not the EFX condition in the paper and generally conflicts with the promised \(G_0\)-matching structure. Conversely, if the matching of copies is retained, one needs a measured bounded-degree graph or graphing, not merely a finite type distribution.
Theorem threesatnpc exposes the issue sharply. Its reduction encodes a particular clause occurrence by a particular \(0\)-edge between a clause gadget and a variable gadget. The SAT assignment works because all occurrences referring to the same variable remain tied to one named gadget and one root choice. If those relations are retained, the continuum is just a measurable collection of copies of the finite relational instance; exact EFX is checked copy by copy, and a constant measurable choice exists exactly when the original finite instance has a solution. Population mass contributes no new decision variable. If the relations are averaged away, different copies can make inconsistent variable choices and the reduction no longer proves hardness. Thus the stated continuous counterpart has not established a faithful lift of the theorem.
The same problem invalidates the proposed reading of edgeocttwo. The paper’s min-uncut number is defined by coloring individual vertices. In a genuine population blow-up, the natural analogue is something like
\[ \inf_{\chi:X\to\{0,1\}} \Lambda\bigl(\{(x,y)\in E:\chi(x)=\chi(y)\}\bigr), \]
where \(\Lambda\) is the measure of edge incidences. The proponent’s formula instead colors types, \(\chi:Q\to\{0,1\}\), thereby forcing every clone of a type onto the same side for no reason supplied by the original problem. If clones may be colored independently, type masses and edge marginals do not determine the parameter; if they may not, the type graph is simply carrying the original finite instance and the masses are passive. The “one nonbinary edge” case has the same defect: one literal exceptional edge becomes null in an atomless population, while replicating an exceptional edge type creates a different promise.
There is also a quantifier problem. In an atomless population no individual agent has positive mass, so “EFX for every positive-mass agent pair” is empty literally. One must choose between almost-everywhere EFX, support-wise EFX over integral local bundles, or a type-level aggregate condition. The first makes isolated exceptional gadgets invisible; the last two require retaining the full coupling between bundles, components, and edge incidences. None is represented by the proposed variables \(y_{\sigma,r}\) alone.
A repaired model with a measurable graphing, per-capita repeated goods, finite motif types, and support-wise EFX would be mathematically coherent. Repeated institutional networks could make it plausible, and I would not call that impossible or “already done.” But it would be a new networked fair-division problem whose essential input is the graphing/coupling, not a continuous society described by a distribution over types. The paper’s two hardness theorems therefore do not, as stated, supply the promised continuous mirrors.
That is the strongest defensible negative case. It defeats both proposed anchors, but it does not justify the universal claim that no worthwhile repaired mirror exists. The honest verdict is a strong rejection of the proponent’s finite-type formulation, not an airtight rejection of every high-multiplicity graphing version.
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.