Answer: \(\mathrm{NP}\)-complete, already for every fixed \(q\ge 2\) under the stated restrictions.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any fixed q ≥2, deciding whether a bi-valued symmetric multigraph G of multiplicity q has an EFX orientation is NP-complete, even if the following hold: 1. G is bipartite; 2. α > qβ; 3. The heavy edges of each heavy component of G induce an NTOM.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite bi-valued symmetric multigraph template \(H=(V,E)\) of multiplicity \(q\), with edge weights \(\alpha>\beta\ge0\), consider a continuum of cells indexed by \(z\in[0,1]\). Each cell has one agent per vertex and one indivisible good per edge, valued by its endpoint agents as in \(H\). Does there exist a measurable rule orienting every cell’s goods so that, for almost every \(z\), the resulting allocation in that cell is EFX?
Let \(H=(V,E)\) be an explicitly listed finite multigraph with \(n=|V|\ge2\), \(m=|E|\ge1\), and multiplicity \(q\), the maximum number of edges sharing an unordered endpoint pair, including loops. Each edge has a binary rational weight in \(\{\alpha,\beta\}\), where \(\alpha>\beta\ge0\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here types are the labelled vertex roles, \(\tau=n\), each with mass \(1/n\); total society mass is \(1\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L,q\).
Cells are indexed by \(z\in[0,1]\) with Lebesgue measure. Every cell contains one agent of each vertex role and a separate indivisible copy of every edge. An agent's additive utility for an edge is its weight if incident to that vertex, and zero otherwise.
A rule assigns every edge copy to one of its endpoints in its own cell; loops go to their sole endpoint. For each edge and endpoint, the set of cells assigning that edge to that endpoint must be Lebesgue measurable.
Writing \(\pi_i(z)\) for agent \(i\)'s bundle, cellwise EFX means \(u_i(\pi_i(z))\ge u_i(\pi_j(z)\setminus\{e\})\) for every \(i\ne j\) and every \(e\in\pi_j(z)\), including goods with zero utility to \(i\). Comparisons are within each cell.
Is deciding whether such a measurable rule is EFX in almost every cell solvable in polynomial time, or is it NP-hard?
Discrete EFX-orientation existence is NP-complete for every fixed \(q\ge2\), even for bipartite templates with \(\alpha>q\beta\) whose heavy edges in every heavy connected component form a tree on at least two vertices after parallel edges are collapsed, with odd multiplicity for every heavy endpoint pair. [Source](https://journals.sagepub.com/doi/10.3233/FAIA251259)
No result addressing this exact measurable, cellwise continuum model was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, already for every fixed multiplicity \(q\ge 2\) under the additional restrictions stated in the question. Consequently, a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
The essential point is that requiring EFX within almost every cell preserves discrete EFX-orientation existence exactly.
A discrete orientation \(o\) assigns every edge to one of its endpoints, with loops assigned to their sole endpoint. Write \(\pi_i^o\) for the resulting bundle of vertex \(i\). Call \(o\) EFX when
\[ u_i(\pi_i^o)\ge u_i(\pi_j^o\setminus\{e\}) \]
for every \(i\ne j\) and every \(e\in\pi_j^o\), including edges of zero utility to \(i\).
Proposition. A measurable rule that is EFX in almost every cell exists if and only if a discrete EFX orientation exists.
Proof. Let \(\Omega\) be the finite set of all discrete orientations. If there are \(\ell\) loops, then \(|\Omega|=2^{m-\ell}\).
Suppose first that a measurable rule is given. For each edge \(e\) and endpoint \(v\), let \(A_{e,v}\subseteq[0,1]\) be the measurable set of cells assigning \(e\) to \(v\). For each orientation \(o\), define
\[ F_o=\bigcap_{e\in E} A_{e,o(e)}. \]
This is a finite intersection of measurable sets. Because the rule assigns each edge to exactly one endpoint, the sets \(F_o\), indexed by \(\Omega\), form a partition of \([0,1]\).
Every cell has the same edges and utility functions. Therefore, on \(F_o\), cellwise EFX holds exactly when \(o\) is a discrete EFX orientation. If \(\Omega_{\mathrm{EFX}}\) denotes the set of such orientations, the set of EFX cells is precisely
\[ G=\bigcup_{o\in\Omega_{\mathrm{EFX}}}F_o. \]
If the rule is EFX almost everywhere, then \(\lambda(G)=1\). Since this is a finite disjoint union, some \(o\in\Omega_{\mathrm{EFX}}\) satisfies \(\lambda(F_o)>0\). In particular, a discrete EFX orientation exists.
Conversely, given a discrete EFX orientation \(o\), use it in every cell. Every assignment set is either \([0,1]\) or the empty set, so the rule is measurable. Its allocation is EFX in every cell. This proves the proposition. \(\square\)
The masses \(1/\tau\), where \(\tau=n\), impose no additional restriction: the specified EFX comparisons concern individual agents within a cell and contain no mass factors.
By the proposition, a certificate consists of one endpoint choice for each non-loop edge, using at most \(m\) bits. It remains to verify its EFX property with exact rational arithmetic.
For a proposed orientation, define:
Because allocations are orientations, the only edges in \(\pi_j\) incident to \(i\ne j\) are edges between \(i\) and \(j\). Hence \(u_i(\pi_j)=S_{ij}\).
If \(k_{ij}=0\), every edge in \(\pi_j\) has zero utility to \(i\), so all EFX inequalities for this ordered pair hold by nonnegativity.
Now suppose \(k_{ij}>0\). Define \(\delta_{ij}\) as the minimum utility to \(i\) of an edge in \(\pi_j\). It is given exactly by
\[ \delta_{ij}= \begin{cases} 0, & d_j>k_{ij},\\ \beta, & d_j=k_{ij}\ \text{and}\ l_{ij}>0,\\ \alpha, & d_j=k_{ij}\ \text{and}\ l_{ij}=0. \end{cases} \]
Indeed, the first case means that \(j\) receives an edge not incident to \(i\); in the other cases every received edge lies between \(i\) and \(j\). This calculation also covers \(\beta=0\).
For this ordered pair, the strongest EFX inequality is therefore exactly
\[ T_i\ge S_{ij}-\delta_{ij}, \]
because removing an edge of minimum utility leaves the largest remaining utility. Checking these inequalities for all distinct vertices verifies the original definition, including removal of zero-valued goods.
All counts can be initialized and accumulated using \(O(m+\tau^2)\) operations. For bit complexity, write \(\alpha=a/b\) and \(\beta=c/d\), with positive denominators, and use the common denominator \(bd\). All comparisons then use integers of \(O(B)\) bits, where \(B=L+\lceil\log_2(m+1)\rceil\).
Using elementary integer arithmetic, a sufficient verifier running-time bound is
\[ O\bigl((m+\tau^2)B^2\bigr). \]
This bound is uniform in \(q\), with \(1\le q\le m\). Thus the measurable decision problem belongs to \(\mathrm{NP}\). Enumerating all certificates also gives a deterministic bound \(O\bigl(2^m(m+\tau^2)B^2\bigr)\).
We apply the discrete theorem supplied in the question. For every fixed \(q\ge2\), discrete EFX-orientation existence is \(\mathrm{NP}\)-complete even for bipartite, symmetric, bi-valued multigraphs of multiplicity \(q\), with \(\alpha>q\beta\), whose heavy edges in each heavy component induce a nontrivial odd multitree. The source’s definition quantifies over every removed edge, matching the zero-utility convention here. [Hsu, *EFX Orientations of Multigraphs*, Theorem 1 and Section 2.2](https://journals.sagepub.com/doi/10.3233/FAIA251259).
The rational-weight requirement is compatible with that hardness construction: for fixed \(q\), its weights can be fixed as \(\alpha=q+1\) and \(\beta=1\), which satisfy \(\alpha>q\beta\).
Given such a discrete instance, construct the continuum instance by retaining its explicitly listed graph and weights and listing one role per vertex, each with mass \(1/n\). This adds \(O(\tau\log(\tau+1))\) bits and takes polynomial time. It preserves the multiplicity, bipartiteness, and heavy-component restrictions.
The proposition proves that the constructed instance admits an almost-everywhere EFX measurable rule exactly when the original instance admits a discrete EFX orientation. Thus this is a polynomial-time many-one reduction, establishing \(\mathrm{NP}\)-hardness for every fixed \(q\ge2\).
Together with the certificate verifier, this completes the proof of \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. The measurable, almost-everywhere cellwise EFX existence problem is \(\mathrm{NP}\)-complete, including the stated restricted instances for every fixed \(q\ge2\). No major or minor mathematical issues were found.
Every non-loop edge has exactly two possible recipients, while each loop has one. Therefore the number of discrete orientations is exactly \(2^{m-\ell}\), where \(\ell\) counts loops. Parallel edges remain separate goods, so they contribute independent choices.
For each orientation \(o\), the set
\[
F_o=\bigcap_{e\in E}A_{e,o(e)}
\]
is measurable because the intersection is finite. The requirement that each edge be assigned to exactly one endpoint ensures that these sets are pairwise disjoint and cover \([0,1]\).
Since the graph, utilities, and allocation associated with \(o\) are identical throughout \(F_o\), EFX holds there exactly when \(o\) is a discrete EFX orientation. Thus the stated finite union describing the EFX cells is correct and measurable.
If that union has measure \(1\), at least one of its finitely many constituent sets has positive measure. Its associated orientation is consequently EFX. This inference does not require selecting a cell from an unspecified exceptional set.
Conversely, applying one discrete EFX orientation in every cell gives measurable endpoint assignment sets and satisfies EFX everywhere. Both directions are established.
The treatment of society masses is also correct: the task imposes comparisons between individual agents within each cell, with no aggregate allocation or mass-weighted utility constraint.
Assessment: Correct and complete.
The endpoint choices for non-loop edges provide a certificate of at most \(m\) bits. Loops require no choices.
For distinct vertices \(i,j\), an edge assigned to \(j\) can be incident to \(i\) only if its endpoints are \(i,j\). Consequently,
\[
u_i(\pi_j)=h_{ij}\alpha+l_{ij}\beta=S_{ij}.
\]
Loops assigned to \(j\) correctly contribute zero to this cross-utility.
When \(k_{ij}=0\), every relevant right-hand side is zero, and nonnegativity of \(T_i\) suffices. This also covers an empty bundle \(\pi_j\), for which the original quantification over removed edges is vacuous.
When \(k_{ij}>0\), the bundle \(\pi_j\) is nonempty, so its minimum edge utility to \(i\) exists. Each branch of the formula for \(\delta_{ij}\) is correct:
These cases are exhaustive because \(d_j\ge k_{ij}\). They remain valid when \(\beta=0\).
Additivity makes each removal inequality equivalent to
\[
T_i\ge S_{ij}-u_i(e).
\]
The largest right-hand side occurs at the minimum edge utility. Therefore checking \(T_i\ge S_{ij}-\delta_{ij}\) is exactly equivalent to checking every removal, including zero-utility goods.
Assessment: Correct, including empty bundles, loops, parallel edges, and zero-weight light edges.
The counts and bundle totals can be accumulated by scanning the edges, with arrays indexed by vertex pairs initialized in \(O(\tau^2)\) operations. The claimed \(O(m+\tau^2)\) operation count is sufficient.
Using the common denominator \(bd\) is valid even when the input fractions are not reduced. Products of input numerators and denominators have \(O(L)\) bits; multiplying by counts bounded by \(m\) increases this by \(O(\log(m+1))\). Thus the stated \(O(B)\) integer-size bound is sound.
Elementary exact integer arithmetic therefore supports the sufficient bound
\[
O\bigl((m+\tau^2)B^2\bigr),
\qquad B=L+\lceil\log_2(m+1)\rceil.
\]
This is polynomial in the explicit input size. The bound is uniform in \(q\), and \(1\le q\le m\) is correct. Enumerating at most \(2^m\) certificates gives the stated deterministic bound.
The equivalence justifies using this finite certificate for the continuum existence problem; a separate encoding of measurable rules is unnecessary.
Assessment: Polynomial verification and membership in \(\mathrm{NP}\) are established.
The cited source matches the required hypotheses. Its Theorem 1 states hardness for every fixed \(q\ge2\), with bipartiteness, \(\alpha>q\beta\), and the heavy-component restrictions. Section 2.2 quantifies over every removed edge without excluding zero-utility edges. The theorem’s proof fixes arbitrary weights satisfying the inequality, supporting the choice \(\alpha=q+1\), \(\beta=1\). [Hsu, *EFX Orientations of Multigraphs*, Sections 2.2 and 3](https://journals.sagepub.com/doi/10.3233/FAIA251259).
Those integer weights meet the binary rational requirement and have constant encoding length for fixed \(q\).
Retaining the explicitly listed graph and weights preserves multiplicity and all structural restrictions. Adding \(\tau=n\) labelled roles with mass \(1/n\) requires \(O(\tau\log(\tau+1))\) bits and polynomial time.
The proved equivalence supplies both directions of the many-one reduction. Hence hardness transfers to precisely the measurable cellwise model in the task.
Assessment: The theorem application and reduction are valid.
The prover establishes both \(\mathrm{NP}\)-hardness and membership in \(\mathrm{NP}\). Its conclusion follows, and its conditional statement concerning \(\mathrm{P}=\mathrm{NP}\) is appropriately qualified.
Required clarification or repair: None.
⟨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.