Answer: —
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateWith n agents and m goods, it is possible to guarantee EF1 using top-k rankings if and only if k ⩾ m −n, if m mod n = 0; m −2, if m mod n = 1; m −(m mod n), if m mod n > 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(T\) of top-\(k\) ranking types with mass distribution \(\mu\), finite good classes \(G\) with \(\rho_g\) indivisible copies per unit population, and class-symmetric rankings \(\sigma_t\), decide whether there exist masses \(x_{t,A}\ge0\) over integral bundles \(A\) such that \(\sum_A x_{t,A}=\mu_t\), \(\sum_{t,A}A_gx_{t,A}=\rho_g\) for every \(g\), and whenever \(x_{t,A}>0\) and \(x_{s,B}>0\), every additive unit-sum valuation \(v\succeq\sigma_t\) satisfies \(v(A)\ge v(B)\) or \(v(A)\ge v(B\setminus\{g\})\) for some \(g\in B\).
Let \(G\) be a set of \(m\ge1\) good classes, with positive binary-rational supplies \(\rho_g\) of indivisible copies per unit population. A society is given by its support: the list of its \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
Each type reports an ordered list \(\sigma_t\) of its top \(k\) distinct classes, with a common \(0\le k\le m\). Copies within a class have equal value. Consistent valuations are vectors \(v\in\mathbb R_{\ge0}^{G}\) with \(\sum_gv_g=1\): values weakly decrease along the reported list, and every ranked class is weakly preferred to every unranked class. Ties may be ordered arbitrarily; unranked classes have no further constraints.
An integral bundle is \(A\in\mathbb Z_{\ge0}^{G}\), including the empty bundle, with \(v(A)=\sum_g A_gv_g\). There is no individual bound on copies beyond aggregate supply. An allocation consists of nonnegative real masses \(x_{t,A}\), indexed by all integral bundles, satisfying \(\sum_Ax_{t,A}=\mu_t\) and \(\sum_{t,A}A_gx_{t,A}=\rho_g\) for every \(g\).
Require robust EF1 across the entire positive support: for every \((t,A),(s,B)\) with \(x_{t,A}x_{s,B}>0\), including \(t=s\), and every valuation \(v\) consistent with \(\sigma_t\), either \(v(A)\ge v(B)\), or there exists \(g\) with \(B_g>0\) such that \(v(A)\ge v(B)-v_g\). The removed copy may depend on \(v\).
Is deciding whether such an allocation exists solvable in polynomial time in \(m,\tau,k,L\), or is it NP-hard?
For finite societies with \(n\ge2\) agents and \(m\) distinct goods, polynomial-time rules guarantee robust EF1 for every top-\(k\) profile exactly when \(k\ge m-n\) if \(m\bmod n=0\), \(k\ge m-2\) if \(m\bmod n=1\), and \(k\ge m-(m\bmod n)\) otherwise. [Halpern and Shah](https://www.cs.toronto.edu/~nisarg/papers/distortion-fair-division.pdf)
No result settling this exact mass feasibility problem was located in the literature search.
This is a partial resolution. The general complexity classification remains open.
I prove a stronger polynomial-time special case than the one in the notes:
If every type reports the same set of ranked classes, feasibility is decidable in polynomial time. The reported orders may differ.
In particular, this resolves every instance with a single type.
The decision in this case depends only on the supplies of the unranked classes and the fractional part of the total ranked supply. Individual ranked supplies need not be integral.
I also give self-contained proofs of the pairwise verification criterion and membership in $\mathrm{NP}$, which are used below.
For a bundle $A$ and a set $S\subseteq G$, write
$$
A(S)=\sum_{g\in S}A_g,
\qquad
|A|=\sum_{g\in G}A_g.
$$
For a real number $z$, write $z_+=\max\{z,0\}$.
Fix a type $t$ with report
$$
\sigma_t=(g_{t,1},\ldots,g_{t,k}).
$$
Let $R_t$ be its ranked set, $U_t=G\setminus R_t$, and
$$
P_{t,j}=\{g_{t,1},\ldots,g_{t,j}\}.
$$
Proposition. Bundle $A$ satisfies robust EF1 toward bundle $B$, under type $t$'s report, exactly when
$$
B(P_{t,j})-A(P_{t,j})\le 1
\qquad
(1\le j\le k)
$$
and
$$
B(R_t)-A(R_t)
+\sum_{g\in U_t}(B_g-A_g)_+
\le 1.
$$
Proof. For a consistent valuation $v$, put
$$
M_B(v)=\max\bigl(\{v_g:B_g>0\}\cup\{0\}\bigr).
$$
The required EF1 condition is equivalent to
$$
v(B)-v(A)\le M_B(v).
$$
Indeed, if envy is positive, removing a copy attaining this maximum eliminates it exactly when the inequality holds. If there is no envy, the inequality holds automatically.
Call a set $S$ upper if membership of a class forces membership of every class constrained to precede it. The nonempty upper sets are the ranked prefixes and the sets $R_t\cup W$, where $W\subseteq U_t$, excluding the empty set.
For every nonempty upper set $S$, the valuation $\mathbf 1_S/|S|$ is consistent. Robust EF1 therefore implies
$$
B(S)-A(S)\le 1.
$$
If $B(S)=0$, this inequality follows directly from $A(S)\ge0$.
Conversely, suppose these upper-set inequalities hold. Let the distinct positive coordinate values of a consistent valuation be
$$
0<a_1<\cdots<a_\ell,
\qquad a_0=0,
$$
and put $S_i=\{g:v_g\ge a_i\}$. Each $S_i$ is upper, and
$$
v=\sum_{i=1}^{\ell}(a_i-a_{i-1})\mathbf 1_{S_i}.
$$
If $B(S_i)=0$, its contribution to $v(B)-v(A)$ is nonpositive. Otherwise, its contribution is at most $a_i-a_{i-1}$. Consequently,
$$
v(B)-v(A)
\le
\sum_{i:B(S_i)>0}(a_i-a_{i-1})
=M_B(v).
$$
The equality follows because precisely the thresholds at or below $M_B(v)$ intersect $B$.
Finally,
$$
\max_{W\subseteq U_t}
\bigl(B(R_t)-A(R_t)+B(W)-A(W)\bigr)
=
B(R_t)-A(R_t)+\sum_{g\in U_t}(B_g-A_g)_+.
$$
This gives the claimed finite test. $\square$
Let
$$
s=\sum_{g\in G}\rho_g.
$$
Proposition. Every supported bundle in a feasible allocation has size $\lfloor s\rfloor$ or $\lceil s\rceil$. Every feasible instance has a certificate with at most $m+\tau$ positive type–bundle pairs, with polynomial-length rational masses. Thus the general problem belongs to $\mathrm{NP}$.
Proof. The uniform valuation $v_g=1/m$ is consistent with every report. Applying robust EF1 in both directions gives
$$
\bigl||A|-|B|\bigr|\le1
$$
for any two supported bundles.
The nonempty set of supported bundle sizes has a minimum $q$, since its elements are nonnegative integers. All supported sizes are therefore $q$ or $q+1$. There are only finitely many integral bundles of these sizes, so the allocation has finite support.
The allocation equalities imply
$$
\sum_{t,A}x_{t,A}=1,
\qquad
\sum_{t,A}|A|x_{t,A}=s.
$$
Thus $s$ is their weighted average. If both sizes occur, $q<s<q+1$; otherwise the common size equals $s$. This proves the size restriction.
Associate to a type–bundle pair the integer column
$$
c_{t,A}=(e_t,A)\in\mathbb Z^{m+\tau}.
$$
The allocation constraints are
$$
\sum_{t,A}x_{t,A}c_{t,A}
=
b,
\qquad
b=(\mu_1,\ldots,\mu_\tau,\rho_1,\ldots,\rho_m).
$$
If the positive-support columns are dependent, choose a nonzero dependence $\sum_i\lambda_i c_i=0$. Summing the type coordinates gives $\sum_i\lambda_i=0$, so the dependence has both positive and negative coefficients. Set
$$
\varepsilon=\min_{\lambda_i>0}\frac{x_i}{\lambda_i},
\qquad
x_i'=x_i-\varepsilon\lambda_i.
$$
This preserves all equations, keeps all masses nonnegative, and removes at least one support entry. Robust EF1 is preserved because the support only shrinks.
Repeating yields at most $m+\tau$ linearly independent columns. Choose an invertible square row submatrix $C$ of these columns. The remaining masses are uniquely determined by its rational equations and hence are rational.
Every bundle coordinate is at most $\lceil s\rceil$, whose bit length is polynomial in the input length. A common denominator $D$ of $b$ can be obtained by multiplying the input denominators; its bit length is also polynomial. Cramer's rule writes each surviving mass as
$$
x_i=\frac{\det C_i}{D\det C},
$$
where $C_i$ replaces the corresponding column by the selected coordinates of $Db$.
If these matrices have dimension $h$ and entries bounded in absolute value by $H$, their determinants are bounded by $h!H^h$. Here $h\le m+\tau$ and $\log H$ is polynomial in the input length. Thus every mass has polynomial bit length.
A verifier checks the allocation equalities and the criterion from Section 1 for every ordered support pair. All these checks take polynomial time. $\square$
Assume from now on that every type ranks the same set $R$, although its order on $R$ may differ. Write
$$
U=G\setminus R,
\qquad
z=(\rho_g)_{g\in U},
$$
and
$$
S_R=\sum_{g\in R}\rho_g,
\qquad
q=\lfloor S_R\rfloor,
\qquad
r=S_R-q.
$$
For a nonnegative vector $w$ on $U$, write $|w|=\sum_{g\in U}w_g$. All vector inequalities below are coordinatewise.
The set $R$ is upper for every type. Hence the counts $A(R)$ of supported bundles differ by at most one. Their average is $S_R$.
If $r=0$, every supported bundle has ranked total $q$.
If $0<r<1$, every supported bundle has ranked total $q$ or $q+1$. The total mass with ranked total $q+1$ is exactly $r$, and the remaining mass is $1-r$.
In the latter case, let $\mathcal L$ and $\mathcal H$ be the distinct unranked vectors occurring with ranked totals $q$ and $q+1$, respectively. Both families are nonempty.
Within either family, Section 1 gives
$$
\sum_{g\in U}(B_g-A_g)_+\le1
$$
for every ordered pair.
For $L\in\mathcal L$ and $H\in\mathcal H$, the comparison from the low ranked total to the high ranked total gives
$$
1+\sum_{g\in U}(H_g-L_g)_+\le1,
$$
so $H\le L$. The reverse comparison gives
$$
-1+\sum_{g\in U}(L_g-H_g)_+\le1.
$$
Together these are exactly
$$
H\le L,
\qquad
|L-H|\le2.
$$
The supply vector must therefore satisfy
$$
z=(1-r)\,\mathbb E[L]+r\,\mathbb E[H]
$$
for distributions on these families.
The ranked coordinates can be supplied without imposing any further restrictions on these unranked distributions.
To prove this, choose a positive integer $N$ divisible by the denominators of all type masses and ranked supplies. Create $N\mu_t$ agents of each type and $N\rho_g$ copies of every ranked class. Allocate these copies by cyclic round robin, with each agent choosing its highest-ranked available class.
Every agent receives $q$ or $q+1$ ranked copies. The proportion receiving $q+1$ is $r$.
The allocation satisfies every ranked-prefix inequality. Indeed, fix agents $i,j$ and a prefix $P$ of $i$'s report. Each pick of $i$ maximizes the indicator value $\mathbf 1_P$ among available copies.
If $i$ precedes $j$ in the cycle, match every pick of $j$ to $i$'s pick in the same cycle. The latter occurs earlier, and $i$ has at least as many picks. Hence
$$
A_j(P)\le A_i(P).
$$
If $i$ follows $j$, match every pick of $j$ after its first to $i$'s pick in the preceding cycle. The latter occurs earlier, and the required picks exist. Hence
$$
A_j(P)\le A_i(P)+1.
$$
Comparing an agent with itself is automatic.
Aggregate this ranked allocation to masses $y_{t,K}$, where $K$ is a ranked bundle. Given conditional unranked distributions $\lambda_{\mathcal L}$ and $\lambda_{\mathcal H}$, define
$$
x_{t,K+V}
=
\begin{cases}
y_{t,K}\lambda_{\mathcal L}(V),&|K|=q,\\
y_{t,K}\lambda_{\mathcal H}(V),&|K|=q+1.
\end{cases}
$$
Here $K$ and $V$ have disjoint coordinate sets.
This preserves type masses and ranked supplies. Its unranked supply is the required mixture with weights $1-r$ and $r$. Ranked-prefix inequalities are preserved. The final inequality of Section 1 holds within each level by the within-family condition, and between levels by $H\le L$ and $|L-H|\le2$.
For $r=0$, the same argument works with one unranked distribution whose support satisfies the within-family condition.
The expansion by $N$ proves existence only. The decision algorithm below never performs this expansion.
The following elementary lemma supplies the needed classification.
Lemma. Let $\mathcal A$ be a finite nonempty family of nonnegative integral vectors satisfying
$$
\sum_g(B_g-A_g)_+\le1
\qquad
(A,B\in\mathcal A).
$$
Then $\mathcal A$ is contained in one of the forms
$$
\{C\}\cup\{C+e_g:g\in U\},
$$
or
$$
\{D\}\cup\{D-e_g:g\in U,\ D_g>0\},
$$
for a nonnegative integral center $C$ or $D$.
Proof. Let $c_g=\min_{A\in\mathcal A}A_g$. Each coordinate varies by at most one, so
$$
A=c+\mathbf 1_{S_A}.
$$
The resulting sets satisfy
$$
|S_B\setminus S_A|\le1
$$
for every ordered pair. Their sizes consequently differ by at most one.
Let their maximum size be $h$. If $h=0$, the family is a singleton. Otherwise, add a new symbol $*$ to every set of size $h-1$, leaving the sets of size $h$ unchanged. All augmented sets have size $h$ and still have directed differences of size at most one. For sets $S,T$ of sizes $h-1,h$, this follows because
$$
|T\setminus S|-|S\setminus T|=1,
\qquad
|T\setminus S|\le1,
$$
which forces $S\subseteq T$.
An equal-size family with these differences either contains a common $(h-1)$-element subset or lies in a common $(h+1)$-element set. Here is a proof. Choose distinct members
$$
X=I\cup\{a\},
\qquad
Y=I\cup\{b\},
$$
where $|I|=h-1$ and $a\ne b$. If all members contain $I$, the first alternative holds. Otherwise, a member omitting $u\in I$ must be
$$
(I\setminus\{u\})\cup\{a,b\},
$$
because it differs from each of $X,Y$ by at most one element. All members omitting part of $I$ therefore lie in $J=I\cup\{a,b\}$. A member containing $I$ has form $I\cup\{z\}$; if $z\notin\{a,b\}$, its difference from the chosen member omitting $u$ contains both $u$ and $z$, a contradiction. Thus all members lie in $J$.
Deleting $*$ from the first alternative yields a common set with at most one element added. Deleting it from the second yields a common set with at most one element removed. Adding back $c$ gives the stated vector forms. $\square$
Lemma. Suppose nonempty finite families $\mathcal L,\mathcal H$ satisfy the within-family condition above and
$$
H\le L,
\qquad
|L-H|\le2
\qquad
(L\in\mathcal L,\ H\in\mathcal H).
$$
At least one of the following descriptions holds:
$$ \mathcal L\subseteq\{D,D+e_g:g\in U\}, \qquad \mathcal H\subseteq\{D,D-e_g:g\in U,\ D_g>0\}. $$
$$
\mathcal L\subseteq
\{C+E\}\cup\{C+E-e_g:E_g>0\},
$$
and every used low vector satisfies $|L-C|\le2$.
$$
\mathcal H\subseteq
\{D-E\}\cup\{D-E+e_g:E_g>0\},
$$
and every used high vector satisfies $|D-H|\le2$.
Proof. Define coordinatewise extrema
$$
C_0=\min_{L\in\mathcal L}L,
\qquad
D_0=\max_{H\in\mathcal H}H.
$$
The cross inequalities imply $D_0\le C_0$. Put
$$
a=\max_{L\in\mathcal L}|L-C_0|,
\quad
b=\max_{H\in\mathcal H}|D_0-H|,
\quad
d=|C_0-D_0|.
$$
For every cross pair,
$$
|L-H|=|L-C_0|+d+|D_0-H|.
$$
Choosing members attaining $a$ and $b$ gives
$$
a+b+d\le2.
$$
First suppose $a,b\le1$. Choose an integer $\ell$ satisfying
$$
\max\{0,a+d-1\}\le\ell\le\min\{d,1-b\}.
$$
This interval is nonempty: $a\le1$ gives $a+d-1\le d$, and $a+b+d\le2$ gives $a+d-1\le1-b$; also $0\le d$ and $0\le1-b$.
There is an integral vector $T$ between $D_0$ and $C_0$ with $|T-D_0|=\ell$: distribute $\ell$ units among the coordinate capacities $C_0-D_0$. Then
$$
|L-T|\le a+d-\ell\le1,
\qquad
|T-H|\le b+\ell\le1.
$$
Since $H\le T\le L$, these differences are zero or unit vectors. This proves description 1.
If $a=2$, the inequality $a+b+d\le2$ forces $b=d=0$. Hence $\mathcal H=\{C_0\}$. By the preceding lemma, $\mathcal L$ lies in a lower or upper family.
A family lying in $\{Q,Q+e_g\}$ has maximum distance from its coordinatewise minimum at most one. For a singleton this distance is zero; otherwise the minimum is $Q$, since two distinct added coordinates, or the center itself, occur. Thus the lower alternative is impossible when $a=2$.
Consequently, $\mathcal L\subseteq\{Q,Q-e_g\}$. Put $E=Q-C_0\ge0$. Choose $L$ attaining $|L-C_0|=2$. Since $Q-L$ is zero or a unit vector,
$$
|E|=|Q-L|+|L-C_0|\le3.
$$
Only coordinates with $E_g>0$ can be deleted while retaining $L\ge C_0$. This proves description 2.
If $b=2$, then $a=d=0$ and $\mathcal L=\{D_0\}$. The preceding lemma applies to $\mathcal H$. A family in an upper form has maximum distance from its coordinatewise maximum at most one, so that alternative is impossible. Thus
$$
\mathcal H\subseteq\{Q,Q+e_g\}
$$
for nonnegative integral $Q$. Set $E=D_0-Q\ge0$. Choosing $H$ attaining $|D_0-H|=2$ gives
$$
|E|=|D_0-H|+|H-Q|\le3.
$$
Only coordinates with $E_g>0$ can be added while retaining $H\le D_0$. This proves description 3.
These cases exhaust the nonnegative integers satisfying $a+b+d\le2$. $\square$
We now turn the structural classification into an algorithm.
Suppose $r=0$. Define
$$
F_U=\sum_{g\in U}\bigl(z_g-\lfloor z_g\rfloor\bigr),
\qquad
H_U=\sum_{g\in U}\bigl(\lceil z_g\rceil-z_g\bigr).
$$
Claim. Feasibility is equivalent to
$$
F_U\le1
\quad\text{or}\quad
H_U\le1.
$$
Proof. All ranked totals equal $q$, so the unranked support satisfies the lemma in Section 4.1.
In its lower form, its expectation satisfies
$$
z_g\ge C_g,
\qquad
\sum_g(z_g-C_g)\le1.
$$
Since integral $C_g\le z_g$ implies $C_g\le\lfloor z_g\rfloor$, this gives $F_U\le1$. The upper form similarly gives $H_U\le1$.
Conversely, if $F_U\le1$, use unranked bundle $\lfloor z\rfloor+e_g$ with probability $z_g-\lfloor z_g\rfloor$, and $\lfloor z\rfloor$ with the remaining probability. Its expectation is $z$, and its support has the required directed differences.
If $H_U\le1$, use $\lceil z\rceil-e_g$ with probability $\lceil z_g\rceil-z_g$, and $\lceil z\rceil$ with the remaining probability. A positively used deletion has $\lceil z_g\rceil\ge1$, so its bundle is nonnegative. Section 3.2 supplies the ranked coordinates.
If $U=\varnothing$, both sums are zero. The unranked distribution consists solely of the empty vector, and the ranked round-robin construction supplies the entire allocation. This explicitly handles the boundary omitted in the notes. $\square$
Notice that this argument requires only $S_R$ to be integral. It does not require the individual ranked supplies to be integral.
Suppose $0<r<1$, and put $p=1-r$.
Feasibility is equivalent to passing at least one of the following three tests. All integral vectors below are indexed by $U$.
Test I. There exists a nonnegative integral vector $D$ such that
$$
\sum_g(z_g-D_g)_+\le p,
\qquad
\sum_g(D_g-z_g)_+\le r.
$$
Test II. There exist nonnegative integral vectors $C,E$, with $e=|E|\le3$, such that
$$
h_g=E_g-\frac{z_g-C_g}{p}
$$
satisfies
$$
h_g\ge0,
\qquad
h_g=0\ \text{when }E_g=0,
\qquad
\sum_g h_g\le1,
$$
and, if $e=3$,
$$
\sum_g h_g=1.
$$
Test III. There exist nonnegative integral vectors $D,E$, with $E\le D$ and $e=|E|\le3$, such that
$$
a_g=E_g-\frac{D_g-z_g}{r}
$$
satisfies
$$
a_g\ge0,
\qquad
a_g=0\ \text{when }E_g=0,
\qquad
\sum_g a_g\le1,
$$
and, if $e=3$,
$$
\sum_g a_g=1.
$$
Proof of equivalence.
In description 1 of Section 4.2, write the conditional low and high expectations as
$$
D+\alpha,
\qquad
D-\beta,
$$
where $\alpha,\beta\ge0$ and $|\alpha|,|\beta|\le1$. Thus
$$
z=D+p\alpha-r\beta.
$$
Coordinatewise,
$$
(z_g-D_g)_+\le p\alpha_g,
\qquad
(D_g-z_g)_+\le r\beta_g,
$$
which proves necessity of Test I.
Conversely, when Test I holds, set
$$
\alpha_g=\frac{(z_g-D_g)_+}{p},
\qquad
\beta_g=\frac{(D_g-z_g)_+}{r}.
$$
Use conditional low probabilities $\alpha_g$ on $D+e_g$, and conditional high probabilities $\beta_g$ on $D-e_g$, putting each remaining probability on $D$. The probability sums are at most one. A positive $\beta_g$ implies $D_g>z_g>0$, so the deletion is valid. These distributions have the required expectation and compatibility.
In description 2, the high vector is $C$. Let $h_g$ be the conditional probability of low vector $C+E-e_g$. The remaining probability is on $C+E$. Deletions can occur only where $E_g>0$. If $|E|=3$, the center itself is forbidden by $|L-C|\le2$, so the deletion probabilities sum to one. The expectation is
$$
z=C+p(E-h),
$$
which is precisely Test II.
Conversely, Test II defines these probabilities. Since $h_g\le1$ and positive $h_g$ requires integral $E_g\ge1$, every deletion remains at least $C$. If $e\le2$, every used low vector differs from $C$ by at most two copies. If $e=3$, only deletion vectors are used, and each differs by exactly two copies. Within the low family, directed positive differences are at most one. Thus all required conditions hold.
In description 3, use conditional probabilities $a_g$ on high vectors $D-E+e_g$ and the remaining probability on $D-E$. The center is forbidden when $|E|=3$. Its mixture with the constant low vector $D$ has expectation
$$
z=D-r(E-a).
$$
This gives Test III. Conversely, its conditions define valid nonnegative high bundles, all at most $D$, whose distance below $D$ is at most two. Within-family directed differences are at most one.
The structural lemma proves necessity of the union of the tests. The constructions and Section 3.2 prove sufficiency. $\square$
Let $u=|U|$.
For Test I, each coordinate must satisfy
$$
z_g-p\le D_g\le z_g+r.
$$
Write $f_g=z_g-\lfloor z_g\rfloor$. Since $p+r=1$:
At an ambiguous coordinate, choosing the floor contributes exactly $p$ to the first budget, while choosing the ceiling contributes exactly $r$ to the second. Therefore at most one ambiguous coordinate can be rounded down and at most one can be rounded up. With more than two ambiguous coordinates, Test I fails. Otherwise there are at most four candidate vectors to check.
For Test II, enumerate all nonnegative integral $E$ with $|E|\le3$. Their number is
$$
\binom{u+3}{3}.
$$
Let $J=\{g:E_g>0\}$, so $|J|\le3$.
Outside $J$, the conditions force $C_g=z_g$, so these supplies must be integral. Inside $J$, the conditions imply
$$
0\le z_g-C_g=p(E_g-h_g)\le3.
$$
Here $E_g-h_g\ge0$ because $E_g\ge1$ and $h_g\le1$. Thus enumerate
$$
C_g\in[z_g-3,z_g]\cap\mathbb Z_{\ge0}.
$$
There are at most four choices per coordinate and at most $4^3$ candidate vectors for each $E$. Check the displayed Test II conditions exactly.
For Test III, outside $J$ one must have $D_g=z_g$. Inside $J$,
$$
0\le D_g-z_g=r(E_g-a_g)\le3.
$$
Thus enumerate
$$
D_g\in[z_g,z_g+3]\cap\mathbb Z_{\ge0},
$$
again with at most $4^3$ candidates, checking also $D\ge E$.
The tests use $O((u+1)^4)$ rational arithmetic operations. Candidate coordinates have polynomial bit length. Computing $r$, dividing by $r$ or $1-r$, and checking all rational inequalities also require polynomial bit length. The algorithm therefore runs in polynomial time in the binary input size.
This completes the promised polynomial-time result for a common ranked set.
Consider one type reporting only $a$, with
$$
\rho_a=\frac12,
\qquad
\rho_b=\frac14,
\qquad
\rho_c=\rho_d=\frac38.
$$
Here $r=p=1/2$. Test I fails: every unranked supply is below $p$, so its sole candidate is $D=0$, whose positive-deviation sum is $1>p$.
Nevertheless, Test II succeeds with
$$
C=0,
\qquad
E=(1,1,1),
\qquad
h=\left(\frac12,\frac14,\frac14\right).
$$
An explicit allocation is
$$
\begin{aligned}
x_{e_a}&=\frac12,\\
x_{e_c+e_d}&=\frac14,\\
x_{e_b+e_d}&=\frac18,\\
x_{e_b+e_c}&=\frac18.
\end{aligned}
$$
The supplies are exactly those specified. The three low ranked-total bundles have directed differences at most one. Their unranked vectors contain the high ranked-total vector $0$ and differ from it by two copies, satisfying the cross conditions.
By contrast, with the same report and
$$
\rho_a=\rho_b=\rho_c=\rho_d=\frac12,
$$
the instance is infeasible:
Thus nonintegral ranked supply does not simply remove the obstruction: its interaction with unranked supplies is captured by the three tests.
The results proved here establish:
Also, every instance with $k\ge m-1$ is feasible: each report then specifies a complete class order, and the round-robin argument from Section 3.2 applies to all classes. Aggregating a denominator-expanded finite allocation gives the required mass allocation.
What remains unresolved is the general intermediate-information case with different ranked sets. The structural reduction above uses a common ranked-total coordinate; when ranked sets differ, its two-level decomposition is unavailable. No general polynomial-time algorithm or hardness reduction is proved here.
⟨structured verdict parsed — rendered above⟩
The output is a valid partial resolution of the task. It establishes membership in $\mathrm{NP}$ for arbitrary reports and a polynomial-time decision algorithm when all types share the same ranked set. It does not settle the requested complexity classification for arbitrary ranked sets, and it explicitly acknowledges this limitation.
I found no false central step. There is one minor omitted case in the proof of the structural lemma.
The proposition in Section 1 is correct.
$$
v(B)-v(A)\le M_B(v)
$$
correctly permits the removed copy to depend on $v$. The definition of $M_B(v)$ also handles the empty bundle.
$$
B(S)-A(S)\le1.
$$
If $B(S)=0$, the inequality holds directly.
$$ \sum_{g\in U_t}(B_g-A_g)_+. $$
Thus the finite test is both necessary and sufficient, including the boundaries $k=0$ and $k=m$.
Section 2 is correct.
The uniform valuation is consistent with every report. Applying robust EF1 in both directions gives the claimed bound on supported bundle sizes. The minimum supported size exists because sizes are nonnegative integers. Once all supported sizes lie in two consecutive values, only finitely many bundles can occur.
The weighted-average argument correctly refines those two values to $\lfloor s\rfloor$ and $\lceil s\rceil$. In particular, when $s$ is integral, two different sizes cannot both have positive mass.
The support-reduction argument is valid:
The surviving independent columns determine rational masses through an invertible square row submatrix. The denominator clearing and determinant formula are correct. Bundle coordinates, input denominator products, and the resulting determinants all have polynomial bit length.
Finally, checking the allocation equations and every ordered support pair using Section 1 takes polynomial time. This establishes membership in $\mathrm{NP}$, but does not determine whether the problem is polynomial-time solvable or $\mathrm{NP}$-hard.
Section 3.1 is correct.
For a nonempty common ranked set $R$, the upper-set inequalities in both directions bound the difference in ranked totals by one. When $R$ is empty, the same conclusion holds immediately because every ranked total is zero.
The average ranked total is $S_R$. Therefore:
Within one level, the final criterion from Section 1 reduces to the stated directed positive-difference bound.
Across levels, the low-to-high comparison forces $H\le L$. With that restriction, the reverse comparison becomes exactly $|L-H|\le2$. The mixture equation for $z$ follows from the allocation supplies.
Section 3.2 is correct.
The denominator expansion produces integral numbers of agents and ranked copies. Cyclic round robin gives each agent $q$ or $q+1$ ranked copies, with the prescribed proportions.
The prefix comparison is valid even when types order $R$ differently: an agent whose prefix is being evaluated chooses a class in that prefix whenever any such class remains available. The same-cycle and preceding-cycle matchings have the required temporal order and sufficient picks. They establish every ordered prefix inequality.
The product construction preserves type masses and ranked supplies. Its unranked expectation has the required mixture weights. Compatibility follows from the within-level and cross-level restrictions already derived.
The potentially large expansion by $N$ is used only to prove existence. The output correctly avoids presenting it as a polynomial-time implementation.
The structural claim is correct, and the proof is sound apart from a minor omitted singleton case.
The coordinatewise minimum representation is justified because each coordinate varies by at most one. The resulting sets have directed differences at most one and sizes differing by at most one.
The augmentation by $*$ preserves the directed-difference condition. In particular, a smaller original set must be contained in any larger original set with which it is compared.
For an augmented family containing two distinct members, the proof of the common-subset or common-superset alternatives is correct. The argument restricting members that omit an element of $I$, and then excluding an additional element outside $\{a,b\}$, checks out. Deleting $*$ produces the claimed vector forms.
Minor issue: If the augmented family is a singleton with positive size, the instruction to choose distinct members $X,Y$ cannot be followed. Only the case $h=0$ was explicitly discharged.
Minimum clarification: Explicitly handle a singleton augmented family before choosing distinct members. This is a routine omitted case and does not affect the lemma’s substance.
The two-level classification is correct.
The cross inequalities imply $D_0\le C_0$, so the displayed distance decomposition uses only nonnegative coordinate differences. Since low and high members can be chosen independently to attain $a$ and $b$, it follows that
$$
a+b+d\le2.
$$
When $a,b\le1$, all inequalities needed to show the interval for $\ell$ is nonempty are supplied. An integral vector with the specified intermediate total exists within the integer coordinate capacities. The subsequent distance bounds yield description 1.
When $a=2$, the bound forces $b=d=0$, making the high family a singleton. The exclusion of the lower form from Section 4.1 is valid: such a family has maximum distance from its coordinatewise minimum at most one. The upper center dominates $C_0$, and the calculation giving $|E|\le3$ is correct.
The argument for $b=2$ correctly reverses these considerations. These cases exhaust the possible nonnegative integer values satisfying the displayed bound.
Section 5.1 is correct.
In the lower form, the integral center lies coordinatewise below $\lfloor z\rfloor$, so the expectation bound implies $F_U\le1$. The upper form gives $H_U\le1$ by the corresponding ceiling argument.
The proposed distributions have nonnegative probabilities summing to one, yield expectation $z$, and satisfy the directed-difference condition. Every positively used deletion is valid.
The empty-unranked-set case is explicitly and correctly handled. Individual ranked supplies need not be integral.
All three tests in Section 5.2 correctly encode the structural descriptions.
For Test I, necessity follows from the conditional expectation equation and the two deviation budgets. Conversely, the positive and negative parts define valid conditional probabilities. Any positively used high deletion has $D_g>z_g>0$, hence removes a copy from a positive integer coordinate.
For Test II, the expectation equation is correct. The condition on zero coordinates of $E$ restricts deletions to admissible coordinates. When $|E|=3$, requiring deletion probabilities to sum to one correctly excludes the center, whose distance from $C$ would exceed two. The remaining bundles satisfy all compatibility conditions.
Test III correctly expresses the reversed construction. The restriction $E\le D$ guarantees nonnegative centers, and the probability and support restrictions keep the high bundles below $D$ with the required distance.
Thus the union of the tests is necessary and sufficient, subject only to the minor proof omission in Section 4.1.
Section 5.3 is correct.
For Test I, the interval for $D_g$ has length one. The floor/ceiling classification, including the equality case $f_g=p$, is accurate. Each ambiguous floor choice consumes the entire first budget, and each ambiguous ceiling choice consumes the entire second budget. More than two ambiguous coordinates therefore cannot be accommodated.
For Tests II and III, the enumeration count
$$
\binom{u+3}{3}
$$
is correct. Each enumerated $E$ has at most three positive coordinates. Outside those coordinates the center is forced; inside them the length-three intervals contain at most four integers per coordinate.
The stated arithmetic-operation bound is valid. All candidate coordinates and exact rational calculations have polynomial bit length, including division by a potentially small positive $r$ or $1-r$.
Therefore the common-ranked-set algorithm is polynomial in the binary input size.
Both examples in Section 6 check out.
In the first example, Test I fails because its only candidate is zero and the positive-deviation total is $1$, exceeding $p=1/2$. The displayed Test II probabilities sum to one. The explicit allocation supplies $a$, $b$, $c$, and $d$ in exactly the claimed amounts, and its support satisfies the required compatibility conditions.
In the second example, Test I has three ambiguous coordinates. For Tests II and III, the three nonintegral supplies force all three coordinates of $E$ to be positive; the total bound then forces $E=(1,1,1)$. The resulting zero deletion or addition probabilities contradict the required sum of one. The infeasibility conclusion follows.
The final claim for $k\ge m-1$ is also valid. Each report then determines a complete weak class order compatible with round-robin choices. Applying the supplied prefix-matching argument to all classes and aggregating the finite allocation proves feasibility.
The genuine established results are:
The general classification for different ranked sets remains unproved. This is an acknowledged limitation, not a false claim of completion.
The only write-up repair needed for the established results is to handle the singleton case in Section 4.1 explicitly. Settling the original general question would require an additional argument beyond the present output.
⟨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.