Answer: —
Theorem 3.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 3 efficiently computes a 2/3-EFX alloca- tion, when the agents agree upon the set of top 𝑛 items.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_\theta\), item-class supplies \(\sigma_g\), additive valuations \(v_\theta\), and a common top pool \(H\) with \(\sum_{g\in H}\sigma_g=1\), compute a finite-support assignment \(x_{\theta,b}\ge0\) over integral bundles \(b\in\mathbb{Z}_{\ge0}^{G}\) satisfying \(\sum_b x_{\theta,b}=\mu_\theta\), \(\sum_{\theta,b} b_gx_{\theta,b}=\sigma_g\), and \(v_\theta(b)\ge\tfrac{2}{3}v_\theta(b'-e_g)\) whenever \(x_{\theta,b},x_{\theta',b'}>0\) and \(b'_g>0\), with every type ranking \(H\) above \(G\setminus H\).
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_\theta\), normalized by \(\sum_\theta\mu_\theta=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=|G|\) item classes with positive binary-rational supplies \(\sigma_g\), where \(\sum_g\sigma_g>1\). Each type has nonnegative binary-rational additive values \(v_{\theta,g}\). The input includes \(H\subseteq G\) with \(\sum_{g\in H}\sigma_g=1\) and \(v_{\theta,h}\ge v_{\theta,g}\) for every \(\theta\), \(h\in H\), and \(g\notin H\); ties are allowed.
Bundles are integral vectors \(b\in\mathbb Z_{\ge0}^{G}\), permitting multiple copies of a class; empty bundles are allowed. An assignment has finitely many positive rational masses \(x_{\theta,b}\), satisfying \(\sum_bx_{\theta,b}=\mu_\theta\) and \(\sum_{\theta,b}b_gx_{\theta,b}=\sigma_g\) for every class.
The assignment is \(2/3\)-EFX if \(v_\theta(b)\ge\frac23v_\theta(b'-e_g)\) for every pair of positive-mass entries \((\theta,b),(\theta',b')\) and every \(g\) with \(b'_g>0\), including zero-valued items; \(e_g\) is the unit vector for class \(g\). Comparisons include different bundles assigned to the same type.
Let \(L\) be the total binary input length; bundle coordinates and assignment masses use binary encoding.
Is computing a \(2/3\)-EFX assignment, or reporting infeasibility, solvable in time \(\operatorname{poly}(m,\tau,L)\), or is this fixed approximation task NP-hard?
For finite societies with nonnegative additive valuations and a common set of top \(n\) items, a polynomial-time algorithm computes a complete \(2/3\)-EFX allocation, allowing ties across the top-set boundary. [Verified result](https://arxiv.org/html/2308.04860).
No result settling this exact mass-assignment problem was located in the literature search.
The general complexity classification remains unresolved. The progress proved here is:
I first reprove the feasibility and certificate-size results needed to interpret the complexity question.
Write
$$
v_\theta(b)=\sum_{g\in G}v_{\theta,g}b_g.
$$
Let $D$ be the product of the denominators of all masses and supplies. Thus $D\mu_\theta$ and $D\sigma_g$ are integers. Define
$$
M=\sum_{g\in G}D\sigma_g.
$$
Both $\log D$ and $\log M$ are $O(L)$, although their numerical values can be exponential in $L$.
Use the finite theorem supplied in the question: nonnegative additive valuations with a common top set whose cardinality equals the number of agents admit a complete $\frac{2}{3}$-EFX allocation. The theorem allows boundary ties, and its EFX definition includes removal of zero-valued items. See [Definition 4, Section 3.2, and Theorem 4](https://arxiv.org/html/2308.04860).
Construct an explicit finite instance containing:
There are $D$ agents and $M>D$ items. The copies belonging to $H$ form a common top set of cardinality
$$
\sum_{h\in H}D\sigma_h=D.
$$
The common-top-set hypothesis follows directly from the input inequalities.
Apply the finite theorem. If $c_{\theta,b}$ agents of type $\theta$ receive class-count bundle $b$, set
$$
x_{\theta,b}=\frac{c_{\theta,b}}{D},
$$
retaining only positive counts. Counting agents and copies proves the required conservation equations.
For distinct positive entries, choose agents realizing those entries. Removing one copy of a class $g$ from the target gives precisely
$$
v_\theta(b)\ge \frac{2}{3}v_\theta(b'-e_g).
$$
Different bundles of the same type are covered because they are assigned to different finite agents. Self-comparisons follow from nonnegativity.
Thus infeasibility never occurs on promised inputs. The finite construction is an exponential-time construction in the binary encoding, rather than a polynomial-time algorithm.
Put $d=\tau+m$. Associate with each positive entry the integer column
$$
a_{\theta,b}=(e_\theta,b)\in\mathbb Z^d.
$$
Let $A$ consist of these columns and let
$$
r=((\mu_\theta)_\theta,(\sigma_g)_g).
$$
The conservation equations are $Ax=r$.
If the columns are dependent, choose a nonzero rational vector $\lambda$ satisfying $A\lambda=0$. Summing its type-coordinate equations gives
$$
\sum_j\lambda_j=0.
$$
Consequently, $\lambda$ has both positive and negative coordinates. Set
$$
t=\min_{\lambda_j>0}\frac{x_j}{\lambda_j},
\qquad
x'_j=x_j-t\lambda_j.
$$
Then $x'\ge0$, $Ax'=r$, and at least one positive entry disappears. No new bundle is introduced, so every surviving fairness comparison remains valid.
Repeating this operation leaves $k\le d$ independent columns.
Every retained bundle originated in the finite allocation, hence $b_g\le M$. Choose $k$ rows giving a nonsingular integer submatrix $B$. The corresponding right-hand side is $z/D$, where the entries of $z$ are integers bounded by $M$. Cramer’s rule gives
$$
x_j=\frac{\det B_j}{D\det B},
$$
where $B_j$ replaces column $j$ by $z$. The determinant expansion yields
$$
|\det B|,\ |\det B_j|\le k!M^k.
$$
Thus every retained mass has polynomial bit length, and so does every bundle coordinate.
Conclusion. Every promised instance has a polynomial-size rational witness with at most $\tau+m$ positive entries.
Such witnesses are polynomially verifiable: conservation is checked by rational arithmetic, and fairness requires at most $k^2m$ checks of
$$
3v_\theta(b)\ge2v_\theta(b'-e_g).
$$
The bounded-witness search relation is total and polynomially verifiable. Extending it to malformed inputs by an “invalid input” witness places it in $\mathrm{TFNP}$, because the promise conditions themselves are polynomially checkable.
Suppose a deterministic polynomial-time SAT decision procedure used this search problem as an oracle and was correct for every valid bounded oracle-answer transcript. Then $\mathrm{NP}=\mathrm{coNP}$.
Indeed, an NP verifier for unsatisfiability could guess and verify the polynomial-size answer to every adaptive oracle query, simulate the procedure, and accept exactly when it rejects the formula. Totality supplies an accepting transcript for every unsatisfiable formula. Correctness for every valid transcript excludes such a transcript for satisfiable formulas. Hence unsatisfiability would belong to $\mathrm{NP}$.
This does not classify the search problem. It identifies a restriction that an applicable hardness reduction must address.
A partial assignment satisfies the type-mass equations and allocates no more than the supply of each class. Fairness is defined on its positive entries exactly as in the question.
For a given partial assignment, define each type’s minimum utility by
$$
\ell_\theta=\min_{b:x_{\theta,b}>0}v_\theta(b).
$$
The minimum exists because every type has positive mass.
Given an explicitly encoded partial assignment, one can compute, in polynomial time in its encoding length, another assignment which:
If there are $k$ distinct bundles, an output with at most $\tau+k-1$ positive entries can be chosen.
List the distinct bundles as $c^1,\ldots,c^k$, and put
$$
s_j=\sum_\theta x_{\theta,c^j}.
$$
Allow a type–bundle pair $(\theta,j)$ precisely when
$$
v_\theta(c^j)\ge\ell_\theta.
$$
Solve the transportation linear program
$$
\max\sum_{\theta,j}v_\theta(c^j)y_{\theta,j}
$$
subject to
$$
\sum_jy_{\theta,j}=\mu_\theta,\qquad
\sum_\theta y_{\theta,j}=s_j,\qquad
y_{\theta,j}\ge0,
$$
using only allowed pairs.
The original assignment is feasible. The feasible region is bounded, since every variable is at most $1$. All coefficients are rational and have polynomial encoding length. Polynomial-time rational linear programming therefore applies, and we may choose an optimal extreme point.
Every positive output entry has utility at least $\ell_\theta$. If the original assignment was $\alpha$-EFX, then for every original target bundle and permissible removal,
$$
\ell_\theta\ge\alpha v_\theta(c^j-e_g).
$$
The target-bundle multiset is unchanged, so these inequalities prove fairness for the output.
Define the strict-envy graph on positive entries. There is an edge from $(\theta,j)$ to $(\theta',j')$ when
$$
v_\theta(c^{j'})>v_\theta(c^j).
$$
Suppose a simple directed cycle consists of entries
$$
(\theta_1,j_1),\ldots,(\theta_r,j_r),
$$
with indices read cyclically. Let
$$
\delta=\min_i y_{\theta_i,j_i}>0.
$$
Remove mass $\delta$ from each cycle entry and give it the next bundle on the cycle.
The inserted pairs are allowed: each recipient strictly prefers its new bundle to its old bundle, whose value was already at least its utility floor. Type masses and bundle masses are preserved. The objective increases by
$$
\delta\sum_{i=1}^r
\left(v_{\theta_i}(c^{j_{i+1}})
-v_{\theta_i}(c^{j_i})\right)>0,
$$
contradicting optimality. Thus the graph is acyclic.
Finally, there are $\tau+k$ equality rows and one redundancy, obtained by summing either family of conservation equations. An extreme point therefore has at most $\tau+k-1$ positive variables. $\square$
If the type masses and bundle masses are integer multiples of $1/D$, an extreme transportation solution also has all masses in this grid.
To see this, form the bipartite graph of its positive variables, with types on one side and bundles on the other. An undirected cycle would give a nonzero alternating perturbation preserving every equality, contradicting extremality. Thus this graph is a forest.
At a leaf, its unique incident variable equals the remaining marginal mass. Solve that variable, subtract it from the neighboring marginal, and remove the leaf. Induction shows that every variable is an integer multiple of $1/D$.
Thus this rematching operation need not introduce finer denominators.
An acyclic finite directed graph has a source. For a source entry with bundle $c$, the absence of incoming edges says
$$
v_\theta(b)\ge v_\theta(c)
$$
for every positive observing entry $(\theta,b)$. Equivalently,
$$
\ell_\theta\ge v_\theta(c)
$$
for every type $\theta$.
One may subsequently reduce support to at most $\tau+m$ entries using the conservation-column argument in Section 1.2. This introduces no new entry, so fairness, utility floors, and acyclicity survive. Such compression need not preserve the denominator grid.
The preceding proposition supplies a source without expanding the society. The following lemma specifies how many copies can safely be added there.
Suppose a partial assignment is $\frac{2}{3}$-EFX. Let $g$ have positive residual supply, and assume
$$
\ell_\theta\ge2v_{\theta,g}
$$
for every type. Let $c$ be a source bundle.
For each type define
$$
r_\theta(c,g)=
\min_{h\in\operatorname{supp}(c)\cup\{g\}}v_{\theta,h}.
$$
If some type values $g$ positively, set
$$
Q=
\min_{\theta:v_{\theta,g}>0}
\left\lfloor
\frac{\frac32\ell_\theta-v_\theta(c)+r_\theta(c,g)}
{v_{\theta,g}}
\right\rfloor.
$$
If every type values $g$ at zero, set $Q=+\infty$.
Then $Q\ge1$. For any integer $q$ with $1\le q\le Q$, adding $q$ copies of $g$ to a positive rational submass of a source entry preserves $\frac{2}{3}$-EFX, provided the required supply is available.
Because $c$ is a source,
$$
v_\theta(c)\le\ell_\theta.
$$
For any type with $v_{\theta,g}>0$,
$$
\frac32\ell_\theta-v_\theta(c)+r_\theta(c,g)
\ge\frac12\ell_\theta
\ge v_{\theta,g}.
$$
Hence each finite bound defining $Q$ is at least $1$.
For $q\ge1$, the largest value obtainable by removing one item from $c+qe_g$ is
$$
v_\theta(c)+qv_{\theta,g}-r_\theta(c,g).
$$
The definition of $Q$ makes this at most $\frac32\ell_\theta$ whenever $v_{\theta,g}>0$.
When $v_{\theta,g}=0$, the minimum $r_\theta(c,g)$ is zero, and the same bound follows from
$$
v_\theta(c)\le\ell_\theta.
$$
Every observing entry retains utility at least its old utility floor: unchanged entries retain their utility, and changed entries gain nonnegative value. Therefore every comparison against the new target satisfies
$$
v_\theta(b)\ge\ell_\theta
\ge\frac{2}{3}v_\theta(c+qe_g-e_h).
$$
Comparisons against unchanged targets remain valid for the same reason. $\square$
The quantities in this lemma are polynomially computable from the current assignment. It proves a safe augmentation, but does not prove a polynomial bound on the number of augmentations required for completion.
Here the additional hypothesis is
$$
v_{\theta,g}=0
\qquad
\text{for every }\theta\text{ and every }g\notin H.
$$
Values inside $H$ may differ arbitrarily across types.
Under this hypothesis, a complete exact EFX assignment with at most $\tau+m-1$ positive entries can be computed in $\operatorname{poly}(m,\tau,L)$ time.
Process the types in any fixed order. For the current type, repeatedly choose a favorite class among the classes in $H$ with positive remaining supply. Assign one copy to mass
$$
a=\min\{\text{remaining mass of the type},
\text{remaining supply of the chosen class}\}.
$$
The procedure is well-defined: remaining top supply equals remaining unassigned agent mass. Each operation finishes a type or exhausts a class. The final operation does both, so there are at most
$$
\tau+|H|-1
$$
positive entries.
Let $h^*$ be the class used in the final operation. This class had positive remaining supply when every earlier operation chose its favorite class. Consequently, every positive entry $(\theta,e_h)$ satisfies
$$
v_{\theta,h}\ge v_{\theta,h^*}.
$$
Thus the final entry is universally unenvied. At this stage every bundle is a singleton, so the assignment is exact EFX.
Choose a positive entry descended from the final entry, with current mass $x$ and bundle $b$. Its top item is $h^*$, and all its other items, if any, are universally zero-valued.
For an unallocated outside class $g$ with supply $s$, set
$$
q=\left\lfloor\frac{s}{x}\right\rfloor,
\qquad
\delta=s-qx.
$$
Then $0\le\delta<x$.
Replace this entry by:
The aggregate number of newly allocated copies is
$$
q(x-\delta)+(q+1)\delta=qx+\delta=s.
$$
At most one additional positive entry is created. Repeat for every outside class, always using a positive descendant of the final entry.
All utilities remain equal to the values of the top items assigned in Step 1.
A target which remains a singleton has value zero after its only item is removed. Every other target consists of $h^*$ and universally zero-valued items. Removing any item therefore leaves value at most $v_{\theta,h^*}$ to observer type $\theta$.
Every observing entry has utility at least $v_{\theta,h^*}$, by the favorite-choice argument in Step 1. Hence all comparisons satisfy exact EFX, including removals of zero-valued items and comparisons between different bundles of the same type.
Let $D$ clear all input mass and supply denominators. Step 1 uses minima and differences of grid masses, so all its masses are integer multiples of $1/D$.
Step 2 preserves this invariant because
$$
\delta=s-qx
$$
is also an integer multiple of $1/D$. Every positive entry therefore has mass at least $1/D$. Supply conservation implies that every bundle coordinate is at most $D\sigma_g$, which has polynomial bit length.
There are at most $m-|H|$ splits, giving total support at most
$$
(\tau+|H|-1)+(m-|H|)=\tau+m-1.
$$
The number of arithmetic operations and the bit length of every intermediate quantity are polynomially bounded. This completes the proof.
Every promised instance with $m=2$ has a polynomial-time exact EFX construction, regardless of the number of types or total supply.
Because supplies are positive, $H$ is nonempty. Since total supply exceeds $1$, $H\ne G$. Thus write
$$
G=\{h,g\},\qquad H=\{h\},\qquad \sigma_h=1.
$$
The common-top assumption gives
$$
v_{\theta,h}\ge v_{\theta,g}
$$
for every type.
Write
$$
\sigma_g=q+\rho,
\qquad
q=\lfloor\sigma_g\rfloor,\qquad 0\le\rho<1.
$$
For every type assign
$$
x_{\theta,e_h+qe_g}=\mu_\theta(1-\rho),
$$
and, when $\rho>0$,
$$
x_{\theta,e_h+(q+1)e_g}=\mu_\theta\rho.
$$
The type masses and both supplies are correct.
For observer type $\theta$, abbreviate
$$
a=v_{\theta,h},\qquad c=v_{\theta,g}.
$$
Every observing bundle has value at least $a+qc$. Removing an item from the larger possible target leaves either
$$
a+qc
\qquad\text{or}\qquad
(q+1)c.
$$
Since $a\ge c$,
$$
(q+1)c\le a+qc.
$$
The smaller possible target has no larger removal value. Thus every permitted comparison satisfies exact EFX.
There are at most $2\tau$ entries, and all coordinates and masses have polynomial bit length. $\square$
The transportation proposition resolves the problem of finding an unenvied bundle in a compressed assignment while preserving fairness and utility floors. It does not bound the work needed to allocate all residual positive-valued supplies.
A simple example also shows why distributing nearly identical class counts to every type is insufficient.
Take two types of mass $\frac12$ each and three classes $h,a,b$, with
$$
H=\{h\},\qquad
\sigma_h=1,\quad \sigma_a=\frac12,\quad \sigma_b=K,
$$
where $K\ge1$ is an integer. Values are
$$
(v_{1,h},v_{1,a},v_{1,b})=(1,1,0),
$$
$$
(v_{2,h},v_{2,a},v_{2,b})=(1,0,1).
$$
These satisfy the promise.
Suppose each type receives both bundles
$$
e_h+Ke_b,\qquad e_h+e_a+Ke_b
$$
with mass $\frac14$ each. Conservation holds. But type $1$, observing from the first bundle, has utility $1$. Removing a zero-valued $b$ from the second leaves utility $2$, so the required inequality would be
$$
1\ge\frac{4}{3},
$$
which fails.
The instance itself even has an exact EFX assignment: give type $1$ mass $\frac12$ of $e_h+e_a$, and type $2$ mass $\frac12$ of $e_h+2Ke_b$. For type $1$, every removal from the other bundle leaves value at most $1$, below its own value $2$. For type $2$, every removal from the other bundle leaves value at most $1$, below its own value $1+2K$. Self-comparisons follow from nonnegativity.
Thus this example refutes a uniform count-rounding shortcut, without suggesting infeasibility or proving hardness.
For arbitrary distinct valuations with positive-valued outside classes, I have neither a polynomial-time completion algorithm nor an applicable hardness reduction.
⟨structured verdict parsed — rendered above⟩
The output establishes genuine partial results, but it does not resolve the general complexity question in USER_TASK. I found no false mathematical step in the stated partial results. The blocking issue is the absence of either a polynomial-time algorithm for all promised inputs or a hardness reduction.
Verified.
The cited finite theorem applies to nonnegative additive valuations with a common top set containing exactly as many items as there are agents. Its approximate EFX definition quantifies over every item in the target bundle, including zero-valued items, and Section 3.2 explicitly permits ties across the top-set boundary. These match the required hypotheses. [Definition 4, Section 3.2, and Theorem 4](https://arxiv.org/html/2308.04860).
The denominator-clearing construction satisfies those hypotheses:
Aggregating finite agents by type and class-count bundle preserves both conservation equations. Distinct positive entries can be represented by distinct finite agents, including when the entries have the same type. Removing a distinguishable copy corresponds exactly to subtracting $e_g$ from the class-count vector.
The separate treatment of self-comparisons is valid: nonnegativity implies
$$
v_\theta(b)\ge \frac23v_\theta(b-e_g)
$$
whenever $b_g>0$.
Consequently, infeasibility never occurs on promised inputs. This existence argument does not provide polynomial running time in the binary input length, as the prover correctly acknowledges.
Verified.
The support-reduction argument is valid. For a nonzero dependence $A\lambda=0$, summing the type-coordinate equations yields
$$
\sum_j\lambda_j=0.
$$
Thus $\lambda$ has both signs. The specified choice of $t$ preserves nonnegativity and conservation while eliminating at least one positive entry.
Fairness survives because support reduction introduces no new type–bundle pair. It only removes comparisons from the original collection.
Once the remaining columns are independent, their number satisfies $k\le\tau+m$. Selecting a nonsingular row submatrix is justified by column independence.
The Cramer’s-rule formula and determinant bounds are correct. In particular:
The bound $k!M^k$ gives polynomial bit length because $\log D$ and $\log M$ are $O(L)$.
The proposed certificate verifier checks all required comparisons, including comparisons between different bundles assigned to the same type and removals of zero-valued items.
Verified under the explicitly stated reduction notion.
The promise conditions are polynomially checkable using rational arithmetic. Together with the established polynomial witness bound, this supports the claimed total, polynomially verifiable search relation, extended to invalid inputs.
The conditional consequence for SAT is also valid. A guessed adaptive oracle transcript contains polynomially many answers of polynomial size. Each answer can be verified before continuing the simulation.
The two necessary directions are stated:
Thus the asserted implication $\mathrm{NP}=\mathrm{coNP}$ follows under that robust oracle-reduction assumption.
The prover appropriately does not treat this conditional observation as a hardness classification.
Verified.
The transportation program is feasible because every originally positive pair satisfies its type’s utility floor. It is bounded because all variables are nonnegative and total mass is $1$. Its number of variables and coefficient lengths are polynomial in the explicitly encoded input assignment and valuation data.
Choosing an optimal extreme point is a standard applicable consequence of rational linear programming for a nonempty bounded rational polytope.
The fairness argument correctly separates observer utilities from target bundles:
The cycle perturbation is valid even if a type or bundle class appears more than once along the cycle. A simple cycle has distinct entry vertices, so each subtracted variable loses at most $\delta$. Incoming and outgoing changes balance each type marginal and each bundle marginal.
Every inserted pair is allowed, and the objective increase is strictly positive. This contradicts optimality and establishes acyclicity.
The bound $\tau+k-1$ on positive variables follows from the rank bound on the transportation equalities. Additional redundancies would only improve that bound.
These statements are also valid.
An undirected cycle in the positive-variable bipartite graph permits a sufficiently small alternating perturbation in both directions, contradicting extremality. Leaf elimination then establishes preservation of the $1/D$ grid.
The interpretation of a source has the correct edge direction: absence of incoming strict-envy edges implies
$$
v_\theta(b)\ge v_\theta(c)
$$
for every positive observing entry. Taking the minimum gives the stated source inequality.
Subsequent support deletion preserves fairness, utility floors, and acyclicity. The warning that such compression need not preserve the denominator grid is appropriate.
Verified as a preservation lemma.
The minimum defining $r_\theta(c,g)$ is always over a nonempty set because it includes $g$. For $q\ge1$, that set is precisely the support of the augmented bundle.
The source inequality and assumed utility floor imply that every finite bound defining $Q$ is at least $1$.
For observers with $v_{\theta,g}>0$, the floor formula enforces
$$
v_\theta(c)+qv_{\theta,g}-r_\theta(c,g)
\le \frac32\ell_\theta.
$$
For observers with $v_{\theta,g}=0$, including $g$ in the minimum gives $r_\theta(c,g)=0$, and the source inequality supplies the required bound.
Splitting and augmenting a positive rational submass preserves type mass and does not decrease any observer’s utility. The new target comparisons satisfy the displayed bound; unchanged targets remain covered by original fairness.
This lemma supplies neither a polynomial bound on the number of augmentations nor a bound on encoding growth over a completion process. The prover explicitly identifies that limitation.
Verified, including the construction and bit complexity.
In Step 1, remaining top supply equals remaining unassigned type mass. Thus every operation is well-defined and finishes a type or exhausts a class. The support bound follows.
The final class $h^*$ had positive remaining supply at every earlier choice. Each chosen class was therefore at least as valuable as $h^*$ to the choosing type. This establishes the observer inequality used later.
Step 2 allocates exactly the stated supply:
$$
q(x-\delta)+(q+1)\delta=s.
$$
The mass $x-\delta$ remains positive because $\delta<x$. The construction also covers $q=0$ and $\delta=0$.
The fairness proof includes zero-valued removals. Every augmented target contains the top item $h^*$ and only universally zero-valued additional items, so every removal leaves observer value at most $v_{\theta,h^*}$.
The denominator invariant is preserved. Every positive mass is at least $1/D$, and supply conservation therefore bounds each coordinate by $D\sigma_g$. Together with the bound on the number of splits, this justifies polynomial running time and output length.
Verified.
The promises force $H$ to be a singleton when $m=2$, and its class has supply $1$.
The proposed masses sum to $\mu_\theta$ for each type. Aggregate outside supply is
$$
q(1-\rho)+(q+1)\rho=q+\rho.
$$
For any observer, removing an item from the larger bundle leaves either $a+qc$ or $(q+1)c$. The inequality $a\ge c$ makes both at most the minimum observing utility $a+qc$.
Removals from the smaller bundle cannot yield a larger value. This remains valid when $q=0$, $\rho=0$, or either valuation is zero.
The support and bit-length claims are justified.
Verified.
The proposed uniform assignment conserves all supplies. Since $K\ge1$, the target contains a removable $b$ item. Type $1$ values that item at zero, so the indicated removal leaves utility $2$, while the observing bundle has utility $1$. The failed inequality is correctly computed.
The alternative assignment also conserves supplies and satisfies the stated cross-type exact EFX comparisons. Each type has only one positive entry, so nonnegativity handles its self-comparisons.
The example refutes the particular proposed shortcut. It establishes neither general infeasibility nor hardness, as the prover correctly states.
Major incompleteness relative to USER_TASK: the general complexity classification remains open.
No repair is needed to the verified intermediate arguments. To resolve the assigned task, the prover must supply one of the two missing results:
The current output should retain its designation as partial progress.
⟨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.