Answer: —
Theorem 4.7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any number of agents, an EF1M and non-wasteful allocation always exists and can be found in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite type set \(T\), good-class set \(G\), rational population distribution \(\mu\in\Delta(T)\), rational per-capita supplies \(q_g\), valuations \(v_t(g)\), and divisible-good sets \(D_t\), find a finite-support allocation \(x_{t,b}\) of type mass to bundles \(b\) satisfying \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=q_g\), with \(b_g\in[0,1]\) for \(g\in D_t\) and \(b_g\in\{0,1\}\) for \(g\notin D_t\). Require non-wastefulness and the paper's EF1M comparison for every pair of supported bundles, and find such an allocation in time polynomial in \(|T|\), \(|G|\), and the input bit length, independently of population denominators.
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. There are \(m\geq 1\) good classes \(G\), with binary-rational per-capita supplies \(q_g\in(0,1]\). Let \(L\) be the total input bit length.
Each type has binary-rational values \(v_t(g)\geq 0\) and a divisible-good set \(D_t\subseteq\{g:v_t(g)>0\}\). Every class is positively valued by some supported type. A bundle \(b\) has \(b_g\in[0,1]\) for \(g\in D_t\) and \(b_g\in\{0,1\}\) otherwise when assigned to type \(t\).
For any bundle \(c\), its value to type \(t\) is \(u_t(c)=\sum_{g\in D_t}v_t(g)c_g+\sum_{g\notin D_t:c_g=1}v_t(g)\). Thus a proper fraction of an indivisible good has zero value to that type, even in comparisons.
An allocation is a finite list of rational bundles and positive rational masses \(x_{t,b}\), satisfying \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=q_g\). Non-wastefulness requires \(b_g>0\Rightarrow v_t(g)>0\) for every supported \((t,b)\).
For every ordered pair of supported assignments \((t,b),(s,c)\), including pairs of the same type, define \(I_t(c)=\{g\notin D_t:c_g=1,\ v_t(g)>0\}\). EF1M requires \(u_t(b)\geq u_t(c)\) if \(I_t(c)=\varnothing\); otherwise it requires \(u_t(b)\geq u_t(c)-v_t(g)\) for some \(g\in I_t(c)\).
Is constructing such an allocation, or correctly reporting infeasibility, solvable in time polynomial in \(m,\tau,L\), independently of population denominators except through \(L\), or is this problem NP-hard?
For finite lists of agents with subjective divisibility, complete EF1M and non-wasteful allocations always exist and are polynomial-time computable ([Bei, Liu, and Lu](https://arxiv.org/html/2310.00976v2#S4.SS2)). No result settling the exact distribution-over-types problem above was located in the literature search.
The general polynomial-time-versus-NP-hardness question remains unresolved. The following restriction admits a stronger result than those established in the notes.
Theorem. Suppose that at most one class is divisible for any supported type:
$$
\left|\bigcup_{t\in T}D_t\right|\leq 1.
$$
Then:
$$ (m+\tau)(\tau 2^m)^{m+\tau}\operatorname{poly}(m,\tau,L). $$
This theorem permits arbitrarily many indivisible classes and arbitrary subjective divisibility of the remaining class. It establishes neither polynomial-time solvability nor NP-hardness of the unrestricted problem.
We first prove the support bound, since it is needed for the complexity conclusions.
Lemma. Every feasible allocation has a feasible allocation with at most $m+\tau$ assignments. This holds both for rational allocations and for the variant allowing real masses and bundle coordinates.
Proof. Index the supported assignments by $i=1,\ldots,n$. Let their types, bundles, and masses be $t_i,b^i,x_i$. Define
$$
a^i=(e_{t_i},b^i)\in\mathbb{R}^{\tau+m},
$$
where $e_t$ is the coordinate vector corresponding to type $t$. The mass and supply equations become
$$
\sum_{i=1}^n x_i a^i=(\mu,q).
$$
If $n>m+\tau$, choose a nonzero linear dependence
$$
\sum_{i=1}^n\lambda_i a^i=0.
$$
Summing the first $\tau$ coordinates gives $\sum_i\lambda_i=0$. Thus some $\lambda_i$ are positive and some are negative.
Set
$$
\varepsilon=\min_{\lambda_i>0}\frac{x_i}{\lambda_i},
\qquad
x'_i=x_i-\varepsilon\lambda_i.
$$
Every $x'_i$ is nonnegative, at least one is zero, and all mass and supply equations remain satisfied. Delete the assignments of zero mass.
The bundles have not changed. Every remaining ordered pair was present before deletion, so admissibility, non-wastefulness, and EF1M remain satisfied. Repeating gives the bound.
For a rational allocation, the columns $a^i$ are rational, so the dependence can be chosen rational. The modified masses then remain rational. $\square$
Assume now that
$$
D_t\subseteq\{h\}\qquad\text{for every }t\in T
$$
for some class $h$. If every $D_t$ is empty, choose any $h\in G$, which is possible because $m\geq1$.
Consider a proposed support of $n$ assignments. Its discrete pattern specifies, for each assignment $i$:
Write $y_i=b^i_h$. The pattern imposes:
Let
$$
F=\{i:z_i=0,\ h\in D_{t_i}\}.
$$
Reject the pattern if some $a_{ig}=1$ has $v_{t_i}(g)=0$, or if some $z_i=1$ has $v_{t_i}(h)=0$. After these checks, non-wastefulness holds for every bundle consistent with the pattern: variable positive $h$ coordinates occur only for types whose divisible-good set contains $h$, and those types value $h$ positively.
For a comparing type $t$, define
$$
A_{tj}=\sum_{g\neq h}v_t(g)a_{jg}.
$$
For a bundle respecting the pattern,
$$
u_t(b^j)=A_{tj}+
\begin{cases}
v_t(h)y_j,&h\in D_t,\\
v_t(h)z_j,&h\notin D_t.
\end{cases}
$$
The second branch uses the task’s convention that a proper fraction of an indivisible class has zero comparison value.
Define the fixed removal allowance
$$
r_{tj}=
\max\left(
\{v_t(g):g\neq h,\ a_{jg}=1,\ v_t(g)>0\}
\cup
\{v_t(h):h\notin D_t,\ z_j=1,\ v_t(h)>0\}
\cup\{0\}
\right).
$$
Lemma. For a pattern-consistent bundle, EF1M for the ordered pair $(t_i,b^i),(t_j,b^j)$ is equivalent to
$$
u_{t_i}(b^i)\geq u_{t_i}(b^j)-r_{t_i j}.
$$
Proof. If $I_{t_i}(b^j)$ is empty, then $r_{t_i j}=0$, and this is the required ordinary non-envy inequality.
Otherwise, $r_{t_i j}$ is the largest value of an allowed removal. Removing such a good gives the displayed inequality. Conversely, an inequality satisfied after some allowed removal is also satisfied after removing a good of maximum allowed value. $\square$
There are consequently two kinds of constraints.
If $h\notin D_{t_i}$, EF1M is the fixed rational inequality
$$
A_{t_i i}+v_{t_i}(h)z_i
\geq
A_{t_i j}+v_{t_i}(h)z_j-r_{t_i j}.
$$
Reject the pattern if any such inequality fails.
If $h\in D_{t_i}$, then $v_{t_i}(h)>0$, and EF1M becomes the difference inequality
$$
y_i-y_j\geq
\frac{A_{t_i j}-A_{t_i i}-r_{t_i j}}{v_{t_i}(h)}.
$$
These constraints include every ordered pair, including assignments of the same type.
Let $P\subseteq[0,1]^n$ be the closed polytope defined by these difference inequalities and the fixed-coordinate equations above, temporarily replacing $y_i<1$ by $y_i\leq1$ for $i\in F$. Define
$$
P^\circ=\{y\in P:y_i<1\text{ for every }i\in F\}.
$$
The actual admissible, non-wasteful, EF1M completions of the pattern are exactly $P^\circ$. Points in $P\setminus P^\circ$ are auxiliary boundary points: their comparison formulas still use the fixed pattern flags, so they are used only to compute bounds.
The difference-inequality structure gives a useful property.
Lemma. If $P$ is nonempty, it has a coordinatewise least point $y^-$ and a coordinatewise greatest point $y^+$. Both are computable in polynomial time and have polynomial rational encoding length.
Proof. First, $P$ is closed under coordinatewise minimum and maximum.
For minimum, suppose $a,b\in P$, and write $c_i=\min(a_i,b_i)$. Consider a constraint
$$
y_i\geq y_j+d.
$$
If $c_i=a_i$, then
$$
c_i=a_i\geq a_j+d\geq c_j+d.
$$
The case $c_i=b_i$ is identical.
For maximum, write $e_i=\max(a_i,b_i)$. If $e_j=a_j$, then
$$
e_i\geq a_i\geq a_j+d=e_j+d.
$$
Again, the other case is identical. Bounds and fixed-coordinate equations are also preserved.
Since $P$ is compact, each coordinate attains its minimum. Choose a point attaining the minimum of coordinate $i$, for every $i$, and take their coordinatewise minimum. Closure under minimum shows that the resulting point belongs to $P$ and simultaneously attains every coordinate minimum. This is $y^-$. Coordinatewise maximum gives $y^+$.
Thus
$$
y^-\leq y\leq y^+\qquad\text{coordinatewise for every }y\in P.
$$
The point $y^-$ is the unique minimizer of $\sum_i y_i$ over $P$: any different feasible point has a strictly larger coordinate and no smaller coordinate. Similarly, $y^+$ uniquely maximizes that sum.
We use the standard rational linear-programming theorem: a rational LP of polynomial encoding length can be solved exactly in polynomial time, with a polynomial-size rational optimizer when its optimum is attained. Here the variables are bounded, the number of constraints is polynomial, and all coefficients have polynomial encoding length. Therefore the two optimizers have the asserted complexity and encoding bounds. $\square$
It follows that
$$
P^\circ\neq\varnothing
\quad\Longleftrightarrow\quad
y^-_i<1\text{ for every }i\in F.
$$
Indeed, $y^-$ itself proves sufficiency. For necessity, if $y^-_i=1$, every point of $P$ has coordinate $i$ equal to $1$.
Henceforth suppose that $P^\circ$ is nonempty.
For a positive mass vector $x$, define
$$
a(x)=\sum_i x_i y^-_i,
\qquad
b(x)=\sum_i x_i y^+_i.
$$
Lemma. The supplies of class $h$ attainable with this fixed positive mass vector are exactly
$$
\left\{\sum_i x_i y_i:y\in P^\circ\right\}
=
\begin{cases}
[a(x),b(x)],&y^+\in P^\circ,\\
[a(x),b(x)),&y^+\notin P^\circ.
\end{cases}
$$
Proof. Coordinatewise extremality bounds every attainable supply between $a(x)$ and $b(x)$. The lower endpoint is attained at $y^-\in P^\circ$.
If $y^+\in P^\circ$, the upper endpoint is attained. Convex interpolation between $y^-$ and $y^+$ attains every intermediate value.
If $y^+\notin P^\circ$, some $k\in F$ satisfies $y^+_k=1$. Every $y\in P^\circ$ has $y_k<1$, and $x_k>0$. Consequently,
$$
\sum_i x_i y_i<b(x).
$$
For every $0\leq\lambda<1$, however,
$$
y(\lambda)=(1-\lambda)y^-+\lambda y^+
$$
belongs to $P^\circ$. It belongs to $P$ by convexity, and each proper coordinate remains strictly below $1$ because the corresponding coordinate of $y^-$ is strictly below $1$.
Moreover,
$$
\sum_i x_i y_i(\lambda)
=(1-\lambda)a(x)+\lambda b(x).
$$
This attains every value in the half-open interval. In this case $a(x)<b(x)$, because $y^-_k<y^+_k$ and all masses are positive. $\square$
The mass constraints for the fixed pattern, excluding class $h$, are
$$
\sum_{i:t_i=t}x_i=\mu_t
\qquad(t\in T),
$$
$$
\sum_i x_i a_{ig}=q_g
\qquad(g\neq h),
$$
$$
x_i>0
\qquad(i=1,\ldots,n).
$$
The preceding interval characterization eliminates the remaining bilinear supply equation.
Proposition. A discrete pattern has a valid completion if and only if all previous pattern checks pass, $P^\circ$ is nonempty, and the following linear system is feasible:
Proof. Any completion has $y\in P^\circ$, so the interval lemma proves necessity.
Conversely, take a mass vector satisfying this system. If $a(x)=b(x)$, its inequalities force $q_h=a(x)$, and use $y=y^-$.
Otherwise, define
$$
\lambda=\frac{q_h-a(x)}{b(x)-a(x)},
\qquad
y=(1-\lambda)y^-+\lambda y^+.
$$
The inequalities give $0\leq\lambda\leq1$. If $y^+\notin P^\circ$, the strict upper inequality gives $\lambda<1$. Thus the interval lemma gives $y\in P^\circ$, and
$$
\sum_i x_i y_i=q_h.
$$
Use these $y_i$ as the $h$ coordinates and the fixed $a_{ig}$ as all other coordinates. Membership in $P^\circ$ establishes admissibility, non-wastefulness, and every required EF1M comparison. The mass and supply equations hold by construction. $\square$
Strict feasibility in this system is polynomial-time decidable. Introduce a common margin $\varepsilon$ and impose
$$
0\leq\varepsilon\leq1,
\qquad
x_i\geq\varepsilon\quad\text{for every }i.
$$
When the upper supply inequality is strict, replace it by
$$
b(x)\geq q_h+\varepsilon.
$$
Keep all other equations and weak inequalities, and maximize $\varepsilon$.
The original strict system is feasible exactly when this LP has a positive optimum. A strictly feasible point has a positive common margin because there are finitely many strict inequalities. Conversely, a positive margin satisfies all of them.
This LP is bounded: summing the type-mass equations gives $\sum_i x_i=1$, so its nonnegative masses lie in $[0,1]$. Its coefficients, including $y^-$ and $y^+$, have polynomial encoding length. Exact rational LP therefore supplies polynomial-size rational masses whenever a completion exists.
Finally, $a(x)$, $b(x)$, $\lambda$, and the interpolated coordinates are computed using polynomially many rational arithmetic operations on polynomial-size numbers. Their encoding lengths are polynomial as well. This proves both polynomial-time completion and polynomial-size rational output for a fixed pattern.
Let
$$
N=m+\tau.
$$
A feasible real allocation can be compressed to at most $N$ assignments by Section 1. Its discrete pattern passes the completion criterion. Section 4 then constructs a rational allocation for that same pattern, with polynomial encoding length.
Thus, under the one-divisible-class hypothesis:
For $\mathrm{NP}$ membership, a certificate can specify only the discrete pattern of at most $N$ assignments. Its length is
$$
O\bigl(N(m+\log\tau)\bigr).
$$
The completion algorithm verifies it in polynomial time. Equivalently, its resulting polynomial-size rational allocation can be checked directly.
For an exact deterministic algorithm, enumerate all ordered patterns of lengths $1,\ldots,N$. Each assignment has at most $\tau 2^m$ patterns: one type choice and $m$ binary flags. Therefore the number of candidates is at most
$$
N(\tau 2^m)^N.
$$
Complete each candidate using the polynomial-time procedure. If all candidates fail, support compression proves infeasibility. This establishes the claimed running-time bound without expanding any population denominator.
The theorem resolves the rational encoding question for instances satisfying
$$
\left|\bigcup_t D_t\right|\leq1.
$$
It also gives a polynomial-time completion algorithm after their discrete patterns are fixed.
For several divisible classes, a supported assignment has several fractional coordinates. Its utility comparisons can involve sums of those coordinates, and the closed completion set need not have coordinatewise least and greatest points. There are also several bilinear supply equations to satisfy simultaneously. The scalar interval argument proved here therefore does not establish a completion algorithm or a polynomial rational encoding bound in that setting.
Even within the one-divisible-class restriction, the pattern enumeration remains exponential. No polynomial-time algorithm or NP-hardness reduction is established here.
⟨structured verdict parsed — rendered above⟩
The restricted theorem is correct as written under the displayed hypothesis
$$
\left|\bigcup_{t\in T}D_t\right|\leq 1.
$$
I found no mathematical error or substantive gap in its proof. It establishes genuine results about support size, rational encoding, and completion of a fixed discrete pattern.
The output does not resolve the polynomial-time-versus-NP-hardness question in USER_TASK, and it explicitly acknowledges this limitation. The appropriate overall classification is partial.
The displayed hypothesis permits at most one class that is divisible for any supported type. It is stronger than requiring each type individually to have at most one divisible class. All subsequent arguments consistently use the displayed, stronger hypothesis.
The output claims a restricted theorem and explicitly leaves the unrestricted question open. There is no unsupported claim that membership in $\mathrm{NP}$ or exponential enumeration settles the requested complexity classification.
The compression argument is valid, including for arbitrary divisibility sets.
The vectors
$$
a^i=(e_{t_i},b^i)
$$
have $m+\tau$ coordinates. When there are more than $m+\tau$ assignments, a nonzero linear dependence exists.
Summing its type coordinates gives
$$
\sum_i\lambda_i=0.
$$
A nonzero vector with this property has both positive and negative entries, so the specified minimum defining $\varepsilon$ exists and is positive.
The update
$$
x'_i=x_i-\varepsilon\lambda_i
$$
preserves all mass and supply equations. For positive $\lambda_i$, the definition of $\varepsilon$ guarantees nonnegative updated masses; for nonpositive $\lambda_i$, masses cannot decrease. At least one assignment acquires zero mass.
Deleting assignments preserves all bundle restrictions and non-wastefulness. It also preserves EF1M because the surviving ordered pairs are a subset of the original ordered pairs. This includes comparisons between assignments of the same type.
For rational columns, a rational nonzero dependence exists by linear algebra over $\mathbb{Q}$. Consequently, the update preserves rational masses. Repeated deletion terminates with at most $m+\tau$ assignments.
This lemma establishes a support bound, but by itself does not bound bundle encoding length. The output correctly supplies that separate argument later.
Under $D_t\subseteq\{h\}$, every coordinate other than $h$ is indivisible for every type. Thus the binary coordinates $a_{ig}$ describe those coordinates completely.
The three restrictions on $y_i$ correctly distinguish:
The non-wastefulness checks are sufficient. Any potentially positive variable coordinate belongs to a type whose divisible-good set contains $h$, and the task requires such a type to value $h$ positively.
The formula for $u_t(b^j)$ correctly implements the task’s unusual comparison convention. When $h\notin D_t$, a proper fraction contributes zero, while a whole coordinate contributes $v_t(h)$.
The removal allowance $r_{tj}$ is exactly the maximum value among eligible whole indivisible goods, with zero added to handle an empty eligible set. Goods other than $h$ are all indivisible for the comparing type under the restriction.
Consequently, replacing the existential removal choice by subtraction of $r_{tj}$ is valid. If the eligible set is nonempty, its maximum is attained by an eligible good; if it is empty, the allowance is zero and ordinary non-envy is required.
The resulting fixed inequalities and difference inequalities are therefore correct.
The set $P^\circ$ correctly describes actual pattern-consistent bundle completions before masses and supplies are imposed.
The closed relaxation $P$ can contain points whose actual whole-coordinate status differs from the chosen flags. The output explicitly acknowledges this and does not treat those boundary points as valid allocations. Their use as auxiliary points is legitimate because the subsequent arguments concern the fixed linear inequalities defining $P$.
The coordinatewise minimum and maximum arguments correctly preserve every constraint of the form
$$
y_i\geq y_j+d.
$$
Bounds and fixed-coordinate equations are also preserved.
Compactness gives coordinate extrema. Taking finitely many coordinatewise minima or maxima produces points simultaneously attaining all coordinate extrema. Hence the coordinatewise least and greatest points exist whenever $P$ is nonempty.
Their claimed uniqueness as optimizers of $\sum_i y_i$ follows from coordinatewise extremality. A different point must differ strictly in at least one coordinate and cannot compensate in the opposite direction.
The stated rational linear-programming theorem applies: the polytope has rational coefficients, polynomially many constraints in the supplied pattern size, bounded variables, and attained optima. The divisions defining the difference-constraint constants are legitimate because $h\in D_{t_i}$ implies $v_{t_i}(h)>0$.
For the later complexity consequences, the pattern size is bounded by $m+\tau$, so these encoding and running-time bounds are polynomial in $m,\tau,L$.
Assuming $P$ is nonempty, the criterion
$$
P^\circ\neq\varnothing
\quad\Longleftrightarrow\quad
y^-_i<1\text{ for every }i\in F
$$
is valid. Sufficiency uses $y^-$ itself. Necessity follows because a least coordinate equal to one forces that coordinate to equal one throughout $P$.
The attainable-supply lemma is also valid for a fixed positive mass vector.
Coordinatewise extremality bounds every supply between $a(x)$ and $b(x)$. The lower endpoint is attained.
When $y^+$ belongs to $P^\circ$, interpolation attains both endpoints and every intermediate value.
When $y^+$ does not belong to $P^\circ$, some coordinate in $F$ equals one at $y^+$. Every admissible completion has a strictly smaller value in that coordinate. Strict positivity of its mass, together with the weak coordinatewise bounds elsewhere, gives a strictly smaller total supply than $b(x)$.
Interpolation with parameter $\lambda<1$ preserves every strict coordinate restriction. The same coordinate also proves $a(x)<b(x)$, so interpolation covers the entire stated half-open interval.
No endpoint case is omitted.
The completion proposition correctly combines the mass equations, the supplies outside $h$, and the attainable-supply interval.
Necessity follows directly from the interval lemma.
For sufficiency, the case $a(x)=b(x)$ is handled separately, avoiding division by zero. Otherwise,
$$
\lambda=\frac{q_h-a(x)}{b(x)-a(x)}
$$
has the required range. When the upper endpoint is excluded, the strict supply inequality ensures $\lambda<1$.
The reconstructed bundles therefore satisfy the original coordinate restrictions, non-wastefulness, every EF1M comparison, and every mass and supply equation.
The common-margin formulation correctly decides the strict inequalities. A strictly feasible point has a positive minimum slack because there are finitely many strict inequalities. Conversely, a positive margin enforces each original strict inequality.
The margin LP is bounded: its constraints imply nonnegative masses summing to one, and $\varepsilon$ is explicitly bounded. Exact rational LP therefore gives a rational witness of polynomial encoding length whenever the system is feasible.
The subsequent rational calculations are explicit sums, products, and quotients of polynomial-size rationals. Their encoding lengths remain polynomial.
The real-to-rational feasibility argument is valid for the finite-allocation variant under consideration. Compression retains a finite support of size at most $m+\tau$, and completion of its pattern supplies a rational allocation.
The $\mathrm{NP}$ certificate size is correctly bounded. It records at most $m+\tau$ assignments, each with a type index and $m$ binary flags. Polynomial-time completion supplies a valid deterministic verifier.
The enumeration count is correct. Each assignment has at most $\tau 2^m$ patterns, and
$$
\sum_{n=1}^{m+\tau}(\tau 2^m)^n
\leq
(m+\tau)(\tau 2^m)^{m+\tau}.
$$
Here $\tau\geq1$ follows from the positive masses summing to one, and $m\geq1$ is assumed.
Completing each candidate gives the claimed exponential-time bound without population expansion.
The output establishes a sound restricted theorem and a general support-compression lemma. It establishes neither a polynomial-time algorithm nor NP-hardness for the unrestricted problem.
Even under the one-divisible-class restriction, polynomial-time completion of a supplied pattern does not imply polynomial-time selection of a feasible pattern. The output correctly recognizes that its enumeration remains exponential.
The minimum additional work needed to settle USER_TASK is a valid polynomial-time construction-and-infeasibility algorithm for the unrestricted instances, or an appropriate NP-hardness reduction. This requires new mathematics, rather than clarification of the present proof.
⟨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.