Answer: The decision problem is \(\mathrm{NP}\)-complete, and producing a law when one exists is \(\mathrm{NP}\)-hard; every positive instance has the one-point law \(q(A)=1\) for an EFX orientation \(A\).
Theorem 4.9 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any fair division instance on bipartite multi- graph with additive valuations, EFX allocations always exist and can be computed in polynomial time. Now, as a corollary, we obtain the following theorem that says that we can compute EFX orientations that are 1/2-EFX in polyno- mial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite catalogue of local bipartite multigraph types \(G_\theta=(V_\theta,E_\theta)\), rational copy masses \(\alpha_\theta\), and rational additive valuations \(v^\theta_u(e)\), where each copy contains one agent of every role \(u\in V_\theta\) and one indivisible item for every edge \(e\in E_\theta\), output nonnegative masses \(z_{\theta,X}\) over complete integral allocation patterns \(X\) such that \(\sum_X z_{\theta,X}=\alpha_\theta\) and every pattern with \(z_{\theta,X}>0\) is EFX for its local market.
A rational bipartite multi-tree template is a finite multigraph \(G=(V,E)\) whose skeleton is a tree, with rational additive values \(v_u(e)>0\) exactly when \(u\) is an endpoint of \(e\). An integral orientation \(A\) assigns every edge to one of its endpoints; it is EFX under these additive endpoint valuations. A nonatomic society consists of independent copies of this template, and a measurable law \(q\) is a probability distribution over the finite set of complete orientations, applied independently to copies; every orientation in \(\operatorname{supp}(q)\) must be EFX. A finite description lists its supported orientations and probabilities.
Is deciding whether such a law \(q\) exists, and producing a finite description when it does, solvable in polynomial time or NP-hard?
For a discrete additive multi-tree instance, deciding whether an EFX orientation exists is NP-complete, even for symmetric instances with a constant number of agents (Afshinmehr et al., 2025, Theorem 3.6).
Under the stated definitions, existence of a law is equivalent to existence of a single EFX orientation. Consequently, the decision problem is \(\mathrm{NP}\)-complete, and the accompanying production problem is \(\mathrm{NP}\)-hard. Randomization and nonatomic replication do not change feasibility.
Let \(\mathcal O_{\mathrm{EFX}}(G)\) denote the set of complete EFX orientations of the template \(G\).
Lemma. A law \(q\) satisfying the definition exists if and only if \(\mathcal O_{\mathrm{EFX}}(G)\neq\varnothing\).
Proof.
Suppose first that \(q\) exists. Because \(q\) is a probability distribution on a finite set,
\[ \sum_{A}q(A)=1. \]
Hence \(\operatorname{supp}(q)\neq\varnothing\). Choose \(A\in\operatorname{supp}(q)\). The definition of an admissible law requires every orientation in \(\operatorname{supp}(q)\) to be EFX. Therefore \(A\in\mathcal O_{\mathrm{EFX}}(G)\).
Conversely, suppose \(A\in\mathcal O_{\mathrm{EFX}}(G)\). Define the Dirac law
\[ q_A(A)=1,\qquad q_A(B)=0\quad\text{for every }B\neq A. \]
Then \(\operatorname{supp}(q_A)=\{A\}\), so every supported orientation is EFX. Applying this law independently to the copies therefore satisfies all the stated requirements. Its finite description consists of the single pair \((A,1)\). ∎
Thus the law-existence language is exactly
\[ \{G:\text{an admissible law exists}\} = \{G:\text{an EFX orientation exists}\}. \]
In particular, mixtures cannot repair a non-EFX orientation because fairness is imposed separately on every supported orientation, rather than only on an expected allocation.
An orientation is specified by one endpoint choice for every edge, requiring \(O(|E|)\) bits.
For an orientation \(A\), write \(A_u\) for the bundle assigned to \(u\). Under the standard EFX definition, one must verify, for every \(u,w\in V\) and every \(e\in A_w\),
\[ v_u(A_u)\geq v_u(A_w\setminus\{e\}). \]
Because the valuations are additive, this is the rational inequality
\[ \sum_{f\in A_u}v_u(f) \geq \sum_{f\in A_w}v_u(f)-v_u(e). \]
There are polynomially many such inequalities. Sums and comparisons of binary-encoded rational numbers have polynomial bit complexity: summing at most \(|E|\) input rationals produces numerators and denominators whose bit lengths remain polynomial in the total input length. One can also check in polynomial time that every edge was assigned to one of its endpoints.
Therefore an EFX orientation is a polynomially verifiable certificate. By the support-collapse lemma, it is also a certificate for existence of an admissible law. Hence the law-existence problem lies in \(\mathrm{NP}\).
Afshinmehr et al., Theorem \(3.6\), prove that deciding whether an additive multi-tree instance admits an EFX orientation is \(\mathrm{NP}\)-complete, even for symmetric instances with eight agents. Their definitions match the present template restrictions:
These facts and the theorem are stated in the primary [AAMAS \(2025\) paper](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p32.pdf).
Given an instance \(I\) from that restricted problem, construct the nonatomic-template instance \(T(I)\) by retaining exactly the same multigraph and valuations. This transformation merely changes the interpretation of the data and is computable in linear time. The support-collapse lemma gives
\[ I\text{ has an EFX orientation} \quad\Longleftrightarrow\quad T(I)\text{ admits an admissible law}. \]
Thus the cited \(\mathrm{NP}\)-hard problem reduces to law existence. Combined with membership in \(\mathrm{NP}\), law existence is \(\mathrm{NP}\)-complete. The hardness already holds for symmetric templates with a constant number of vertices.
Whenever the answer is positive, no large-support representation is necessary. From any EFX orientation \(A\), output
\[ q=\{(A,1)\}. \]
This description has polynomial size.
Conversely, any algorithm that decides feasibility and produces a finite law on positive instances would decide the \(\mathrm{NP}\)-complete existence problem. Moreover, from its nonempty support one may extract an EFX orientation directly. Therefore this combined decision-and-production task is \(\mathrm{NP}\)-hard and cannot be solved in polynomial time unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The equivalence is correct.
Thus law existence is exactly equivalent to existence of one EFX orientation.
The certificate and verification argument are correct.
Therefore the law-existence language belongs to \(\mathrm{NP}\).
The cited theorem has the required scope. The published statement says that deciding EFX-orientation existence on additive multi-trees is NP-complete, including symmetric instances with a constant number of agents; its proof explicitly constructs an eight-vertex multi-tree. This matches the source problem asserted in the task and the structural restrictions used by the reduction. See [Afshinmehr et al., Theorem 3.6](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p32.pdf).
The identity transformation preserves the multigraph, valuations, and orientations. Combined with the support-collapse lemma, it preserves yes-instances in both directions. Consequently, the NP-hardness conclusion follows.
For every positive instance, the one-point law \(\{(A,1)\}\) is a valid polynomial-size output.
The claimed NP-hardness applies to the combined task described by the target: an algorithm that decides feasibility and outputs a law on positive instances would decide the NP-complete existence language. Extracting any supported orientation also yields an EFX orientation.
Every essential claim follows from the definitions or the cited nearest-known theorem. No logical, quantifier, encoding, or edge-case gap affects the conclusion.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.