Answer: Polynomial-time solvable in \(m,n,\tau,L\).
Theorem 1 — class: algorithmic
Given a finite family \(H\) of cell templates \(h\), each a finite hypergraph \(G_h\) of girth at least \(4\) with monotone valuations, and rational cell masses \(\alpha_h\), compute a complete allocation \(X^h\) for each positive-mass template such that \(X^h\) is EFX for its local agents. Copying \(X^h\) to almost every cell of type \(h\) must yield an aggregate allocation rule.
A society is given by its support: a list \(H\) of \(\tau\) cell types with positive binary rational masses \(\alpha_h\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each template is an explicitly listed simple hypergraph \(G_h=(V_h,E_h)\), with nonempty vertex set and nonempty hyperedges. Vertices are local agents; edges are local indivisible goods. Girth means Berge girth, with cycle lengths at least \(2\); no cycles of length \(2\) or \(3\) are allowed.
Each agent has a normalized monotone valuation \(v_i^h:2^{E_h}\to\mathbb{Q}_{\geq0}\), represented by a Boolean circuit mapping a bundle's incidence vector to a binary rational. For every \(i\notin e\), require \(v_i^h(S\cup\{e\})=v_i^h(S)\).
Realize the society as an atomless probability space of cells partitioned into measurable type classes of masses \(\alpha_h\). Each cell has its own agents and goods; allocations and fairness comparisons are local to that cell.
The output is one partition \(X^h=(X_i^h)_{i\in V_h}\) of \(E_h\) for each type, allowing a good to be assigned to any local agent. Require \(v_i^h(X_i^h)\geq v_i^h(X_j^h\setminus\{g\})\) for every \(i,j\in V_h\) and every \(g\in X_j^h\), including goods with zero marginal value. Copying these partitions to almost every cell defines the aggregate allocation rule.
Let \(m=\max_h|E_h|\), \(n=\max_h|V_h|\), and \(L\) be the total binary input length, including valuation circuits and masses.
Is computing such an aggregate allocation rule possible in time polynomial in \(m,n,\tau,L\), or is this search problem NP-hard?
For a single finite simple hypergraph of Berge girth at least \(4\), normalized monotone valuations always admit a complete EFX allocation, with a construction polynomial in the numbers of agents and goods, treating valuation evaluations as elementary operations ([Lianeas–Sgouritsa–Sotiriou](https://arxiv.org/html/2608.03171v1)). No result specifically addressing the stated distribution-of-cells problem was verified.
The search problem is polynomial-time solvable in \(m,n,\tau,L\) on inputs satisfying the stated hypotheses. The proof applies the finite-hypergraph algorithm independently to each supported type, implements its valuation queries using the supplied circuits, and verifies that the resulting partitions define a measurable aggregate rule.
We use the following established result: a finite simple hypergraph of Berge girth at least \(4\), with normalized monotone valuations for which nonincident goods are irrelevant, admits a complete EFX allocation computable in polynomial time in the valuation-query model. This is [Theorem 1 and Lemma 3.6 of Lianeas–Sgouritsa–Sotiriou](https://arxiv.org/html/2608.03171v1).
The paper’s definition of EFX requires
\(
v_i(X_i)\geq v_i(X_j\setminus\{g\})
\)
for every \(g\in X_j\), without a positive-marginal-value restriction. Its complete allocations may assign goods to agents outside their hyperedges.
Fix a supported type \(h\). All hypotheses hold:
Consequently, the finite algorithm returns a partition \(X^h\) of \(E_h\) satisfying every required local EFX inequality.
The finite theorem counts valuation evaluations as elementary operations. We must implement them in the input model of this question.
For a bundle \(S\subseteq E_h\), form its incidence vector and evaluate the Boolean circuit representing \(v_i^h\). An explicitly represented Boolean circuit can be evaluated by processing its gates in topological order. Its gate count and output length are bounded by the total input length \(L\), so this evaluation takes polynomial time in \(L+|E_h|\).
Under the stated binary-rational representation, a circuit output supplies a rational number with polynomially many bits. In particular, writing two outputs as \(a/b\) and \(c/d\), with positive denominators, their exact comparison reduces to the integer comparison
\(
ad\geq cb.
\)
The products have polynomially many bits and are computable in polynomial time. Thus comparisons remain efficient even when two valuation outputs are extremely close.
The construction uses polynomially many valuation queries, comparisons, and operations on explicitly represented bundles and the hypergraph. These operations therefore admit a polynomial-time implementation in the Boolean-circuit model. There is a fixed polynomial \(P\) such that its running time on type \(h\) is at most
\(
P(|V_h|,|E_h|,L).
\)
This argument concerns inputs satisfying the valuation promises. It does not require the algorithm to certify monotonicity or irrelevance of an arbitrary input circuit.
For each \(h\in H\), run the finite construction with circuit evaluation supplying the valuation queries. Output the resulting partitions
\(
(X^h)_{h\in H}.
\)
Choose a polynomial upper bound \(P\) that is nondecreasing in its arguments. Since \(|V_h|\leq n\) and \(|E_h|\leq m\), the total running time is bounded by
\(
\sum_{h\in H}P(|V_h|,|E_h|,L)
\leq \tau P(n,m,L).
\)
This is polynomial in \(m,n,\tau,L\).
The output also has polynomial length: recording the recipient of every good requires at most
\(
O\!\left(\tau m\log(n+1)\right)
\)
bits, apart from labels and delimiters.
The algorithm processes exactly the \(\tau\) listed types. Neither the masses’ denominators nor the number of cells require additional repetitions.
Let \((\Omega,\mathcal F,\mu)\) be the given probability space of cells, with measurable type classes \(\Omega_h\) satisfying \(\mu(\Omega_h)=\alpha_h\).
In every cell of type \(h\), assign its local copy of good \(e\in E_h\) to the local copy of the unique agent \(i\) for which \(e\in X_i^h\). This specifies the aggregate rule using the finite output table.
To verify measurability explicitly, consider any valid triple \((h,e,i)\). The set of cells in which the rule assigns the type-\(h\) copy of \(e\) to agent \(i\) is \(\Omega_h\) if \(e\in X_i^h\), and is empty otherwise. Both sets are measurable. Thus the rule’s finitely many assignment coordinates are measurable.
Because \(X^h\) partitions \(E_h\), every local good is assigned exactly once. Moreover, copying the partition preserves valuations and bundles within each cell. Hence, for every cell of type \(h\), every pair of its local agents \(i,j\), and every \(g\in X_j^h\), the finite construction gives
\(
v_i^h(X_i^h)\geq v_i^h(X_j^h\setminus\{g\}).
\)
Therefore the aggregate allocation satisfies the required fairness condition almost everywhere.
There are no fairness comparisons between different cells. Accordingly, the masses impose no additional coupling between the finite allocation problems. Atomlessness is compatible with the construction but is not needed for this step.
The construction completely resolves the stated search problem: it produces the required finite output and the associated measurable aggregate allocation rule in polynomial time.
Under standard polynomial-time search reductions, an NP-hardness claim for this same problem would therefore imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated search problem. The argument establishes polynomial-time solvability in \(m,n,\tau,L\) for inputs satisfying the promises. No major or minor mathematical issues were found.
The cited result matches the theorem used in the write-up. Theorem 1 supplies the polynomial-time EFX construction; Lemma 3.6 supplies its running-time guarantee. The paper’s definitions include arbitrary normalized monotone valuations, the stated nonincident-good irrelevance condition, and EFX comparisons after removing every good. Allocations need not be orientations. Its algorithms use valuation evaluations, comparisons, and explicit bundle operations. These checks support the invocation in Sections 1–2. [Lianeas–Sgouritsa–Sotiriou, Sections 2–3](https://arxiv.org/html/2608.03171v1)
For each supported type, the prover checks the necessary hypotheses:
The conclusion is therefore a complete partition satisfying the required EFX inequalities. Neither restricting recipients to incident agents nor excluding zero-marginal goods is introduced.
Assessment: Correct theorem application; no missing hypothesis.
The conversion from valuation-query complexity to bit complexity is justified.
An explicitly represented Boolean circuit has polynomially many gates and output bits relative to its description length, hence relative to \(L\). Evaluating it on a bundle’s incidence vector takes polynomial time. An output rational consequently has polynomial bit length; its numerical magnitude does not affect this conclusion.
For outputs \(a/b\) and \(c/d\), positive denominators justify the equivalence between comparing the rationals and comparing \(ad\) with \(cb\). Product bit lengths are bounded by the sums of the factor bit lengths, so exact multiplication and comparison remain polynomial-time operations. No lower bound on the difference between distinct valuation outputs is needed.
The finite construction’s polynomial operation count therefore yields a polynomial implementation with the supplied circuits. The prover correctly distinguishes using the valuation promises from certifying them: promise verification is not part of the requested search task.
Assessment: Correct; no hidden precision or promise-certification gap.
The algorithm processes each explicitly listed type once. A single fixed polynomial bounds the same finite construction on every type, so
\[ \sum_{h\in H}P(|V_h|,|E_h|,L)\leq \tau P(n,m,L) \]
is valid after choosing a nondecreasing polynomial upper bound.
The recipient table has the stated polynomial size. The factor \(\log(n+1)\) also accommodates a one-agent template. Input labels and delimiters contribute only polynomial overhead because the templates are explicitly represented within the input.
The masses’ denominators do not cause repeated computation: the task requests one partition per supported type, without any coupling constraint involving masses.
Assessment: Correct total-time and output-size bounds.
The measurable-rule argument addresses the output representation required by the task.
For every assignment coordinate \((h,e,i)\), its set of cells is either the measurable type class \(\Omega_h\) or the empty set. Since the output has finitely many such coordinates, this establishes measurability of the finite assignment table interpreted cellwise.
Completeness follows from each \(X^h\) being a partition. Copying a partition to cells of its type preserves the local bundles and valuation functions, so it preserves every required local inequality.
There are no comparisons between cells. Thus neither atomlessness nor the numerical masses introduce an additional allocation constraint. The prover’s almost-everywhere conclusion also accommodates any null exceptional set in the realization.
Assessment: Correct; no additional measurable-selection result is needed.
The polynomial-time conclusion follows from the verified steps. The final observation about NP-hardness is appropriately conditional on standard polynomial-time search reductions.
There are no blocking issues and no required repairs. The write-up establishes the computational classification requested, rather than merely existence of an aggregate allocation.
⟨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.