Answer: —
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a $k$-ary fair division instance $I = (N,M,V)$ where $k$ is a constant, an allocation that is both EF1 and fPO can be computed in time $\poly{m,n}$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \( \mu_t \) with \( \sum_t \mu_t=1 \), rational per-capita supplies \( 0\le \sigma_j\le1 \), and additive \( k \)-ary values \( v_{tj} \) for types \( t\in T=[\tau] \) and goods \( j\in[m] \), find masses \( z_{t,B}\ge0 \) for integral bundles \( B\subseteq[m] \) satisfying \( \sum_B z_{t,B}=\mu_t \) and \( \sum_{t,B:j\in B}z_{t,B}=\sigma_j \), such that every pair of positive-mass cohorts satisfies \( \mathrm{EF1} \) under \( v_t(B)=\sum_{j\in B}v_{tj} \), and no capacity-feasible fractional reallocation weakly improves every supported cohort while strictly improving one. Determine whether such an allocation can be computed in time polynomial in \( m,\tau,k \) and the input bit length, independently of the common population denominator.
A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) goods, binary-rational per-capita supplies \(\sigma_j\in[0,1]\), and nonnegative binary-rational additive values \(v_{tj}\). Every good has positive value for some supported type. Each type has at most \(k\) distinct values across goods; these values may differ between types, and \(k\) is an input parameter. Let \(L\) be the total input bit length.
An allocation consists of rational masses \(z_{t,B}\ge0\), for integral bundles \(B\subseteq[m]\), satisfying \(\sum_Bz_{t,B}=\mu_t\) and \(\sum_{t,B:j\in B}z_{t,B}=\sigma_j\). Represent it by listing its positive entries; empty bundles are permitted.
A supported cohort is a pair \((t,B)\) with \(z_{t,B}>0\). Require EF1 for every ordered pair of supported cohorts, comparing their bundles using the first cohort's valuation; removal of at most one good is allowed.
A fractional reallocation assigns each supported cohort per-capita quantities \(x_{t,B,j}\in[0,1]\), subject to \(\sum_{t,B}z_{t,B}x_{t,B,j}\le\sigma_j\) for every good. Require that no such reallocation satisfies \(\sum_jv_{tj}x_{t,B,j}\ge v_t(B)\) for every supported cohort, with strict inequality for at least one.
Is computing such an EF1 and fractionally Pareto-optimal allocation, or reporting that none exists, solvable in time \(\operatorname{poly}(m,\tau,k,L)\), independently of the common population denominator, or is this problem NP-hard?
For discrete agents and indivisible goods, EF1 and fractional Pareto optimality can be achieved in strongly polynomial time for every fixed \(k\); this does not give a polynomial bound uniform in \(k\). The general discrete search problem belongs to \(\mathrm{PLS}\). [Garg–Murhekar](https://arxiv.org/html/2204.14229v2)
No result settling the exact support-and-supply problem above was located.
The general complexity question remains unresolved here. I prove two additional results:
I also reprove the conditional compact-support result needed for the general problem. The verifier’s correction is essential: compact support follows if an EF1 and fractionally Pareto-optimal allocation exists. It does not establish unconditional existence.
The first result covers arbitrary personalized binary valuations and the entire $k=1$ case. It does not cover types having two distinct positive values.
Fix a feasible allocation. Index its supported cohorts by $C$. For $c\in C$, write $t(c)$ for its type, $B_c$ for its bundle, $z_c>0$ for its mass, and
$$
b_{cj}=\mathbf 1_{\{j\in B_c\}},
\qquad
v_{cj}=v_{t(c)j}.
$$
Lemma 1. The allocation is fractionally Pareto optimal if and only if there are $\alpha_c>0$ and $p_j\geq0$ satisfying
$$
j\in B_c\ \Longrightarrow\ \alpha_cv_{cj}\geq p_j,
\qquad
j\notin B_c\ \Longrightarrow\ \alpha_cv_{cj}\leq p_j.
$$
Proof of sufficiency. For any feasible fractional reallocation $x$, an owned good satisfies $x_{cj}-b_{cj}\leq0$, while an unowned good satisfies $x_{cj}-b_{cj}\geq0$. In either case the certificate implies
$$
\alpha_cv_{cj}(x_{cj}-b_{cj})
\leq p_j(x_{cj}-b_{cj}).
$$
Multiplying by $z_c$ and summing gives
$$
\begin{aligned}
\sum_c z_c\alpha_c
\bigl(v_{t(c)}(x_c)-v_{t(c)}(B_c)\bigr)
&\leq
\sum_j p_j
\left(\sum_c z_cx_{cj}-\sigma_j\right)\\
&\leq0.
\end{aligned}
$$
A Pareto improvement would make the left side strictly positive, because every $z_c\alpha_c$ is positive. Thus no such improvement exists.
Proof of necessity. Put $U_c=v_{t(c)}(B_c)$ and use total quantities $y_{cj}=z_cx_{cj}$. Consider the linear program
$$
\begin{aligned}
\text{maximize}\quad&
\sum_{c,j}v_{cj}y_{cj}\\
\text{subject to}\quad&
0\leq y_{cj}\leq z_c,\\
&\sum_c y_{cj}\leq\sigma_j,\\
&\sum_jv_{cj}y_{cj}\geq z_cU_c.
\end{aligned}
$$
The original assignment $y^0_{cj}=z_cb_{cj}$ is feasible, and the feasible region is bounded. Fractional Pareto optimality is equivalent to $y^0$ being optimal: every feasible point weakly improves all cohort utilities, and the objective increases precisely when some cohort improves strictly.
Assign nonnegative dual variables $p_j$ to the supply constraints, $\lambda_c$ to the utility constraints written with negative signs, and $q_{cj}$ to the upper bounds. The dual inequalities are
$$
p_j+q_{cj}\geq(1+\lambda_c)v_{cj}.
$$
The primal is feasible with finite optimum, so linear-programming duality supplies an optimal dual solution. Set $\alpha_c=1+\lambda_c$.
Complementary slackness with $y^0$ gives the required inequalities. If $j\in B_c$, then $y^0_{cj}=z_c>0$, so
$$
p_j+q_{cj}=\alpha_cv_{cj},
$$
and therefore $p_j\leq\alpha_cv_{cj}$. If $j\notin B_c$, the upper bound has positive slack, so $q_{cj}=0$, and consequently $p_j\geq\alpha_cv_{cj}$. This proves necessity. $\square$
In particular, the certificate depends on the supported types and bundles, rather than their masses. Restricting it to a subset of cohorts preserves fractional Pareto optimality whenever the new masses remain feasible.
For each good $j$, let
$$
O_j=\{c:j\in B_c\},
\qquad
N_j=\{c:j\notin B_c\}.
$$
Construct a directed multigraph on $C$. For every good $j$ and every pair $c\in N_j$, $d\in O_j$ with $v_{cj},v_{dj}>0$, introduce an edge
$$
c\longrightarrow d
\quad\text{of weight}\quad
w_{cdj}=\frac{v_{cj}}{v_{dj}}.
$$
Theorem 2. The allocation is fractionally Pareto optimal if and only if both conditions hold:
Proof. A certificate from Lemma 1 immediately excludes the first obstruction: it would require
$$
0<\alpha_cv_{cj}\leq p_j\leq\alpha_dv_{dj}=0.
$$
It also implies, for every graph edge,
$$
\alpha_d\geq w_{cdj}\alpha_c.
$$
Multiplying these inequalities around a cycle shows that its weight product cannot exceed $1$.
Conversely, suppose both conditions hold. For each vertex $d$, define $\alpha_d$ as the maximum product of edge weights along a simple directed path ending at $d$, allowing the length-zero path of product $1$.
These maxima exist because there are finitely many simple paths. Moreover, deleting a directed cycle from a walk cannot decrease its weight product. Hence any walk can be shortened to a simple path without decreasing its product. Appending an edge $c\longrightarrow d$ to a maximizing path for $c$ therefore proves
$$
\alpha_d\geq w_{cdj}\alpha_c.
$$
Define
$$
p_j=\max_{c\in N_j}\alpha_cv_{cj},
$$
with the maximum equal to $0$ when $N_j$ is empty. The nonowner inequalities in Lemma 1 hold by definition.
For a positive-valued owner $d$, every positive-valued nonowner $c$ supplies a graph edge, so
$$
\alpha_cv_{cj}\leq\alpha_dv_{dj}.
$$
Zero-valued nonowners contribute $0$ to the maximum. Thus $p_j\leq\alpha_dv_{dj}$. For a zero-valued owner, the first condition says that every nonowner has value zero, so $p_j=0$. All certificate inequalities hold, and Lemma 1 applies. $\square$
Let $n=|C|$. Initialize $a_c^{(0)}=1$ and perform $n-1$ synchronous rounds
$$
a_d^{(h)}
=
\max\left\{
a_d^{(h-1)},
\max_{c\longrightarrow d}w_{cdj}a_c^{(h-1)}
\right\}.
$$
The resulting value is the maximum product over paths of length at most $n-1$ ending at $d$.
After separately checking the zero-value obstruction, accept exactly when
$$
a_d^{(n-1)}\geq w_{cdj}a_c^{(n-1)}
$$
for every edge.
If every cycle has product at most $1$, the simple-path argument proves these inequalities. Conversely, if they all hold, multiplying them around any cycle excludes a product greater than $1$.
There are at most $mn^2$ edges. Every intermediate number is a product of at most $n-1$ input valuation ratios, so it has polynomial bit length. Thus this is a polynomial-time test using exact rational arithmetic, without logarithmic approximations.
Assume that, for each supported type $t$, there is a positive rational $a_t$ such that
$$
v_{tj}=a_t b_{tj},
\qquad b_{tj}\in\{0,1\}.
$$
For an identically zero-valued type, take $a_t=1$ and $b_{tj}=0$.
Say that type $t$ *likes* good $j$ when $b_{tj}=1$, and define the total liking mass
$$
M_j=\sum_t\mu_tb_{tj}.
$$
The premise that every good has positive value somewhere gives $M_j>0$.
Theorem 3. Under this hypothesis, an EF1 and fractionally Pareto-optimal allocation can always be computed in time $\operatorname{poly}(m,\tau,L)$, independently of the common population denominator.
Partition the goods into
$$
S=\{j:\sigma_j<M_j\},
\qquad
H=\{j:\sigma_j\geq M_j\}.
$$
We first allocate each good in $S$ entirely to people who like it. Subsequently, for every $j\in H$, we give the good to every person who likes it and assign the remaining mass $\sigma_j-M_j$ to people who dislike it.
The scarce-good allocation will minimize
$$
\Phi=\sum_c z_c|B_c|^2,
$$
where, at this stage, $B_c\subseteq S$ and every cohort likes every good it receives.
Write $s=|S|$. If $s=0$, start each type with an empty bundle and proceed to Section 2.5.
For $s>0$, introduce aggregate quantities $y_{tj}$ for $j\in S$, and slot quantities $r_{t\ell}$ for $\ell\in\{1,\ldots,s\}$. Solve
$$
\begin{aligned}
\text{minimize}\quad&
\sum_t\sum_{\ell=1}^{s}(2\ell-1)r_{t\ell}\\
\text{subject to}\quad&
\sum_t y_{tj}=\sigma_j
&&\text{for every }j\in S,\\
&\sum_{j\in S}y_{tj}=\sum_{\ell=1}^{s}r_{t\ell}
&&\text{for every }t,\\
&0\leq y_{tj}\leq\mu_t
&&\text{if }b_{tj}=1,\\
&y_{tj}=0
&&\text{if }b_{tj}=0,\\
&0\leq r_{t\ell}\leq\mu_t.
\end{aligned}
$$
This linear program is feasible. For each scarce good, the eligible capacities sum to $M_j>\sigma_j$, so its supply can be assigned independently among liking types. Each type’s resulting total quantity is at most $s\mu_t$, and therefore fits its slots.
Let
$$
d_t=\sum_{j\in S}y_{tj},
\qquad
u_t=\frac{d_t}{\mu_t}=q_t+\varepsilon_t,
$$
where $q_t=\lfloor u_t\rfloor$ and $0\leq\varepsilon_t<1$.
For fixed $y$, the strictly increasing slot costs force the cheapest slots to be filled first: moving a positive quantity from a used expensive slot to an unfilled cheaper slot strictly reduces the objective. Consequently, in an optimal solution the slot cost for type $t$ is
$$
\mu_t\left(q_t^2+(2q_t+1)\varepsilon_t\right).
$$
When $u_t=s$, this means all slots are full and the cost is $\mu_ts^2$.
We now realize the optimal aggregate quantities using polynomially many cohorts.
Fix a type $t$, enumerate $S$ as $j_1,\ldots,j_s$, and put
$$
x_i=\frac{y_{t j_i}}{\mu_t},
\qquad
c_0=0,
\qquad
c_i=\sum_{h=1}^{i}x_h.
$$
Each $x_i$ lies in $[0,1]$. For $u\in[0,1)$, define
$$
B_t(u)=
\left\{
j_i:
\text{there exists }\ell\in\mathbb Z
\text{ with }c_{i-1}\leq u+\ell<c_i
\right\}.
$$
The intervals $[c_{i-1},c_i)$ partition $[0,u_t)$. Each has length at most $1$, so it contains at most one point of the translated integer lattice $u+\mathbb Z$. Therefore:
The first assertion follows by cutting $[c_{i-1},c_i)$ at integer boundaries and translating the pieces into $[0,1)$; their total length remains $x_i$, and their interiors do not overlap.
Partition $[0,1)$ at the fractional parts of $c_0,\ldots,c_s$, together with the endpoint $1$. On every resulting open interval, $B_t(u)$ is constant. Give that bundle a cohort mass equal to $\mu_t$ times the interval length, using a rational midpoint to identify the bundle.
There are at most $s+1$ such intervals. This produces rational cohort masses, assigns aggregate quantity $y_{tj}$ of every scarce good, and gives type $t$ a squared-cardinality contribution
$$
\mu_t\left((1-\varepsilon_t)q_t^2+
\varepsilon_t(q_t+1)^2\right)
=
\mu_t\left(q_t^2+(2q_t+1)\varepsilon_t\right).
$$
Thus the resulting allocation attains the linear-program objective.
Consider any feasible allocation of the scarce goods in which every received good is liked by its recipient. Define
$$
y_{tj}=\sum_{c:t(c)=t,\ j\in B_c}z_c,
\qquad
r_{t\ell}=\sum_{c:t(c)=t,\ |B_c|\geq\ell}z_c.
$$
These variables satisfy all constraints of the linear program. Moreover,
$$
\begin{aligned}
\sum_t\sum_{\ell=1}^{s}(2\ell-1)r_{t\ell}
&=
\sum_c z_c\sum_{\ell=1}^{|B_c|}(2\ell-1)\\
&=\sum_c z_c|B_c|^2.
\end{aligned}
$$
Hence the linear-program optimum is a lower bound on $\Phi$ for every eligible integral-bundle allocation. Section 2.3 attains that bound. Its allocation therefore globally minimizes $\Phi$.
First consider the scarce-good allocation.
Suppose cohorts $c,d$ violate EF1, with the comparison using type $t=t(c)$. An identically zero-valued type cannot violate EF1, so divide its valuation by $a_t$.
Put
$$
a=|B_c|,
\qquad
r=|B_d|,
\qquad
e=\sum_{j\in B_d}b_{tj}.
$$
Cohort $c$ likes every good in its own bundle, so its normalized utility is $a$. If $e=0$, there is no envy. Otherwise removing a liked good from $B_d$ leaves normalized value $e-1$. Failure of EF1 therefore implies
$$
a<e-1,
\qquad\text{hence}\qquad
r\geq e\geq a+2.
$$
There exists a good $j\in B_d\setminus B_c$ liked by $t$, since $B_d$ contains at least $a+2$ such goods and $B_c$ contains only $a$ goods. Cohort $d$ also likes $j$, because every scarce good was assigned only to a liker.
Choose rational $\delta$ with
$$
0<\delta\leq\min(z_c,z_d).
$$
Split mass $\delta$ from each cohort, adding $j$ to the first bundle and removing it from the second. Type masses and supplies remain unchanged; the recipient did not already own $j$; and all received goods remain liked.
The change in $\Phi$ is
$$
\begin{aligned}
\delta\left((a+1)^2+(r-1)^2-a^2-r^2\right)
&=2\delta(a-r+1)\\
&\leq-2\delta<0,
\end{aligned}
$$
contradicting global minimality. Thus the scarce-good allocation is EF1.
Now process each $j\in H$. Give it to every liking cohort. Assign its remaining mass
$$
\sigma_j-M_j\leq1-M_j
$$
to disliking cohorts, using a fixed ordering and splitting a boundary cohort if necessary. This assigns the exact supply and creates at most one additional cohort per good.
Every person of type $t$ now receives every good in $H$ that $t$ likes. Thus, for any two final cohorts $c,d$,
$$
v_{t(c)}(B_c\cap H)\geq v_{t(c)}(B_d\cap H).
$$
Their projections onto $S$ already satisfy EF1. Adding the displayed inequality to that comparison preserves its removal witness, or preserves the comparison without removal when none was needed. The final allocation is EF1.
For any feasible fractional reallocation $x$, consider normalized aggregate utility
$$
F(x)=\sum_c\frac{z_c}{a_{t(c)}}v_{t(c)}(x_c)
=
\sum_j\sum_{c:b_{t(c)j}=1}z_cx_{cj}.
$$
For each good, the quantity assigned to likers is at most its supply $\sigma_j$ and at most their total mass $M_j$. Therefore
$$
F(x)\leq\sum_j\min(\sigma_j,M_j).
$$
Our allocation attains this bound good by good. Scarce goods are assigned entirely to likers, and every liker receives each surplus good.
Every coefficient $z_c/a_{t(c)}$ is positive. Hence a cohort-level Pareto improvement would strictly increase $F$, contradicting this upper bound. The allocation is fractionally Pareto optimal.
The linear program has $O(\tau m)$ variables and constraints, with polynomial-size rational data. An optimal rational solution can be computed in polynomial time and has polynomial encoding length.
The decomposition uses at most $s+1$ cohorts per type. Its endpoints, interval lengths, and bundle tests require only polynomially many rational operations on numbers of polynomial bit length. Processing surplus goods adds at most $|H|$ cohorts.
Thus the complete construction runs in $\operatorname{poly}(m,\tau,L)$ time. It uses no population replication and no number of operations proportional to a common denominator. The support can further be reduced to at most $m+\tau$ cohorts by the next theorem.
Theorem 4. If a general instance admits an EF1 and fractionally Pareto-optimal allocation, it admits one with at most $m+\tau$ supported cohorts and polynomial encoding length.
Proof. Start with such an allocation and fix its support $C$. Consider the polytope of nonnegative masses on these cohorts satisfying all type-mass and supply equalities.
This polytope is nonempty. It is bounded because its masses sum to $1$. Choose an extreme point.
The equality matrix has $m+\tau$ rows. Its columns are zero-one vectors recording the cohort’s type and owned goods. At an extreme point, the columns corresponding to positive variables must be linearly independent: a nonzero dependence would permit sufficiently small perturbations in both directions while preserving nonnegativity and all equalities. Thus at most $m+\tau$ variables are positive.
The new support is a subset of the old support, so EF1 persists. Fractional Pareto optimality persists by restricting the certificate of Lemma 1.
For the encoding bound, let $r\leq m+\tau$ be the number of positive variables. Choose $r$ independent rows of their columns, obtaining a nonsingular zero-one matrix $A$. Let $Q$ be the product of the input denominators of the masses and supplies. Its bit length is $O(L)$.
Cramer’s rule gives denominators dividing $Q\det A$. Hadamard’s inequality yields
$$
|\det A|\leq r^{r/2}.
$$
For a numerator determinant, the replaced column has entries between $0$ and $Q$, hence Euclidean norm at most $Q\sqrt r$. The other columns have norms at most $\sqrt r$. Consequently, each numerator determinant has absolute value at most $Qr^{r/2}$.
Every mass therefore has bit length
$$
O\!\left(L+r\log(r+1)\right).
$$
Listing the bundles also takes polynomial space. $\square$
Applied to Theorem 3, this gives unconditional existence with at most $m+\tau$ cohorts within the personalized binary class.
For a general yes-instance, Theorem 4 supplies a certificate with polynomially many cohorts and polynomial-size rational masses.
Check the type and supply equalities by exact arithmetic. Check EF1 through
$$
v_{t(c)}(B_c)
\geq
v_{t(c)}(B_d)-\max_{j\in B_d}v_{t(c)j}
$$
for every ordered pair, defining the maximum as $0$ for an empty bundle. Finally, check fractional Pareto optimality by Theorem 2.
All checks take polynomial time. Thus the existence decision problem belongs to $\mathrm{NP}$.
There are
$$
N=\tau2^m
$$
possible cohorts. Put $d=m+\tau$ and enumerate supports of size at most $d$.
For each candidate support:
$$
z_c\geq\delta\geq0.
$$
Accept precisely when the optimum is positive.
The third test is equivalent to the existence of strictly positive feasible masses on that support. Theorem 4 guarantees completeness of the enumeration. Its running time is bounded by
$$
(d+1)(\tau2^m)^d\operatorname{poly}(m,\tau,L).
$$
This removes any replication factor involving the population denominator, but is exponential in the structural parameters.
The new polynomial algorithm handles arbitrary liking patterns, arbitrary supported masses, arbitrary supplies, and type-dependent positive values $a_t$. Its proof relies on the fact that transferring a liked good preserves normalized aggregate welfare. With distinct positive values within a type, that argument no longer applies: the recipient and donor can value the transferred good differently.
The general compact-witness theorem remains conditional. Neither it nor the graph test proves existence for every general instance.
Population replication also does not directly transfer the ordinary discrete result: it introduces multiple copies of each good, while this task permits each individual to receive at most one copy. The ordinary discrete allocation model does not impose that additional restriction. [Garg–Murhekar, problem setting and allocation definitions](https://arxiv.org/html/2204.14229v2)
Accordingly, I have not established either a polynomial-time algorithm uniform in $k$ or an $\mathrm{NP}$-hardness reduction for the general support-and-supply problem.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial partial results, but it does not resolve the general problem in USER_TASK. The personalized binary algorithm, fractional Pareto optimality characterization, and conditional compact-witness theorem withstand verification. I found one minor terminology issue in the graph algorithm, with no effect on its correctness.
The appropriate overall classification is partial. This agrees with the prover’s own stated scope.
The requested conclusion concerns all supported nonnegative additive valuations and a runtime polynomial uniformly in $m,\tau,k,L$, or an $\mathrm{NP}$-hardness result.
Theorem 3 concerns the subclass
$$
v_{tj}\in\{0,a_t\},
$$
with a separate convention for identically zero-valued types. This genuinely covers the entire $k=1$ case: under USER_TASK’s definition, such a type has one value across all goods, which can be positive or zero. Personalized binary valuations with both zero and a positive value generally have $k=2$.
The prover does not confuse this subclass with all instances having $k=2$. Its restriction to at most one distinct positive value is explicit.
Major scope limitation: neither a polynomial algorithm uniform in $k$ nor a hardness reduction is supplied. The output acknowledges this; it is an unanswered part of the assignment, rather than a false claim of completion.
Sufficiency is correct. For owned goods, the quantity change is nonpositive, so multiplying the owner inequality reverses its direction as required. For unowned goods, the quantity change is nonnegative, so the nonowner inequality gives the same displayed bound.
Summing uses exact supply feasibility of the original allocation and supply inequalities for the reallocation. A Pareto improvement makes the weighted utility change strictly positive because every $z_c\alpha_c$ is positive. Zero valuations and zero supplies cause no exception.
Necessity is correct. The substitution $y_{cj}=z_cx_{cj}$ is valid because every supported cohort has positive mass. The box constraints become exactly
$$
0\leq y_{cj}\leq z_c.
$$
The original assignment is feasible, and these bounds make the feasible region bounded. Consequently, finite-dimensional linear-programming strong duality applies.
The dual signs and inequalities are correct. In particular, writing each utility constraint with a negative sign produces
$$
p_j+q_{cj}\geq(1+\lambda_c)v_{cj}.
$$
Complementary slackness gives equality for an owned good because its primal variable is positive. For an unowned good, the upper-bound constraint has strictly positive slack, forcing $q_{cj}=0$. These are exactly the two claimed certificate inequalities.
Setting $\alpha_c=1+\lambda_c$ guarantees strict positivity, including for zero-valued cohorts.
The mass-independence consequence is valid, provided the replacement masses give a feasible allocation, as the prover explicitly requires.
Both necessary conditions follow correctly from Lemma 1. The zero-valued-owner obstruction is a genuine contradiction, and multiplying the positive-weight inequalities around a cycle gives the stated product bound.
The converse also stands:
Empty owner or nonowner sets are handled correctly. In particular, a good with no owners imposes only nonowner lower bounds on its price, while a good with no nonowners can receive price zero.
No missing substantive hypothesis was found.
The acceptance criterion is correct. If all cycles have product at most $1$, cycle deletion reduces any relevant walk to a simple path of length at most $n-1$. Conversely, the accepted edge inequalities themselves exclude every cycle with product greater than $1$.
The edge count is at most $mn^2$. Products retained after the stated rounds contain at most $n-1$ input ratios, so their rational encoding lengths are polynomial. The final edge checks add at most one ratio to a product, preserving that bound. The case $n=1$ requires no rounds and is handled correctly.
Minor terminology issue: the recurrence maximizes products over directed walks of bounded length. If “paths” means paths without repeated vertices, the sentence claiming it maximizes over paths is inaccurate on rejected instances.
For example, take three cohorts with bundles
$$
B_1=\{1\},\qquad B_2=\{2\},\qquad B_3=\varnothing,
$$
valuations
$$
v_1=(1,2),\qquad v_2=(2,1),\qquad v_3=(0,0),
$$
masses all equal to $1/3$, and supplies both equal to $1/3$. The graph has the two edges between the first two cohorts, each of weight $2$. After two rounds, the first cohort’s value is $4$, attained by a repeated-vertex walk; the maximum over simple paths ending there is $2$.
This does not invalidate the test. Minimum clarification: use “walks” for the recurrence’s invariant, reserving “simple paths” for the cycle-deletion argument.
The partition correctly handles zero supplies and the equality case $\sigma_j=M_j$. Every $M_j$ is positive by USER_TASK’s assumption.
Linear-program feasibility is established: each scarce good can independently be assigned within liking-type capacities, and each type’s total assigned quantity is at most $s\mu_t$, its total slot capacity.
The increasing slot costs force earlier slots to fill before later slots. The displayed objective value is correct:
$$
\sum_{\ell=1}^{q_t}(2\ell-1)=q_t^2.
$$
The partially filled next slot contributes $(2q_t+1)\mu_t\varepsilon_t$. The boundary case $u_t=s$ is explicitly handled.
The construction respects the one-copy-per-person restriction. Each half-open interval has length at most $1$ and therefore contains at most one point of $u+\mathbb Z$.
The marginal inclusion measure of good $j_i$ is $x_i$, including when $x_i=0$ or $x_i=1$. The stated bundle cardinalities are also correct for $\varepsilon_t=0$ and $u_t=s$.
Fractional endpoints give at most $s+1$ positive-length intervals. Rational midpoints avoid endpoint ambiguity. Discarding the finitely many partition endpoints changes no mass or marginal.
The reconstructed quantities and squared-cardinality objective match the linear program exactly. Polynomial encoding length is preserved by the rational operations used.
The mapping from any eligible scarce-good allocation to $y_{tj}$ and $r_{t\ell}$ satisfies all linear-program constraints. The identity expressing squared cardinality as the sum of odd slot costs is correct. Thus the constructed allocation globally minimizes $\Phi$ over precisely the eligible allocations used in the exchange argument.
The EF1 contradiction is valid. A violation implies
$$
e\geq a+2,\qquad r\geq e,
$$
because these quantities are integers. Therefore a liked good exists in $B_d\setminus B_c$. Both affected recipients like that good, and splitting positive rational mass preserves type masses, supplies, and eligibility.
Rechecking the objective change gives
$$
2\delta(a-r+1)\leq-2\delta<0.
$$
This contradicts the established minimum. A cohort cannot violate EF1 against itself, so selecting two affected cohorts introduces no self-comparison problem.
The surplus extension is also correct. The required residual mass lies within the total disliking mass. A prefix assignment in a fixed ordering needs at most one boundary split per good.
Every final recipient receives all surplus goods that its own type likes. Hence its surplus contribution weakly dominates any other cohort’s surplus contribution under its valuation. Adding this comparison preserves the scarce-good EF1 witness. The case $s=0$ is covered by the initial empty bundles.
The aggregate normalized utility bound is correct:
$$
F(x)\leq\sum_j\min(\sigma_j,M_j).
$$
The allocation attains it good by good. All utility weights are positive, including under the convention for zero-valued types. Any cohort-level Pareto improvement would therefore contradict the bound.
The linear program has polynomial size, rational data, a nonempty bounded feasible region, and a finite optimum. Standard exact polynomial-time rational linear programming applies and provides a polynomial-size optimal solution. The subsequent decomposition and surplus processing also have polynomial size and bit complexity.
Theorem 3 establishes the claimed denominator-independent polynomial algorithm for its stated subclass.
The mass polytope is nonempty and bounded. Linear independence of its positive columns at an extreme point gives at most $m+\tau$ positive entries.
EF1 survives support deletion. Fractional Pareto optimality survives because Lemma 1’s certificate restricts to the retained cohorts and the new masses remain feasible.
The encoding calculation is correct. The common denominator product has bit length $O(L)$; Cramer’s rule and the stated Hadamard bounds give mass bit length
$$
O\!\left(L+r\log(r+1)\right).
$$
The theorem remains conditional on an existing qualifying allocation. It supplies no unconditional existence result for general valuations.
The existence decision problem belongs to $\mathrm{NP}$: the compact certificate has polynomial length, and feasibility, EF1, and fractional Pareto optimality can all be checked in polynomial time. The empty-bundle convention in the EF1 test is correct.
The finite enumeration is complete by Theorem 4. For a feasible candidate support, a positive optimum for $\delta$ is equivalent to strictly positive masses on every listed cohort. The stated support-count bound and exponential runtime bound are valid.
These results establish neither polynomial-time general search nor hardness.
The replication caveat is supported by the cited discrete model, whose bundles are subsets of individually indexed items. Replicated copies would be separate items, so its allocation definition does not enforce the original-good restriction. [Garg–Murhekar, allocation definitions](https://arxiv.org/html/2204.14229v2)
Actionable feedback: clarify the walk/path terminology in Section 1.3. The stated partial results require no substantive repair. Completing USER_TASK requires an additional general algorithm or hardness argument; the existing verification and compactness results do not supply one.
⟨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.