Answer: Every instance is feasible; a satisfying assignment can be found in polynomial time with polynomial output length.
Lemma 5 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe divider agent is always PROPm-satisfied. All non-divider agents are always PROPm-satisfied as well.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\), per-capita supplies \(q_g\), and nonnegative values \(v_{tg}\) with \(\sum_g q_gv_{tg}=1\), compute a finite-support rational assignment \(\lambda_{t,B}\), where each recipient receives an integral bundle \(B\in\mathbb{Z}_{\ge 0}^{G}\). Require \(\sum_B\lambda_{t,B}=\mu_t\), \(\sum_{t,B}\lambda_{t,B}B_g=q_g\), and, for every \((t,B)\) with \(\lambda_{t,B}>0\), \(v_t(B)+d_t(\lambda)\ge 1\), where \(v_t(B)=\sum_gv_{tg}B_g\) and \(d_t(\lambda)=\max_{C:\exists s,\lambda_{s,C}>0}\min_{g:C_g>0}v_{tg}\), with \(d_t(\lambda)=0\) if no nonempty bundle is assigned. Is such an assignment computable in time polynomial in \(\tau\), \(r\), the input bit length \(L\), and the output length?
A society is atomless and given by its support: the list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types.
There are \(m=r\ge1\) good categories with binary-rational per-capita supplies \(q_g\ge0\). Values are binary rationals satisfying \(0\le v_{tg}\le1\) and \(\sum_gq_gv_{tg}=1\) for each type.
Each recipient receives an integral bundle \(B\in\mathbb Z_{\ge0}^{m}\), valued additively as \(v_t(B)=\sum_gv_{tg}B_g\). An assignment is a finitely supported family of nonnegative rational masses \(\lambda_{t,B}\).
Require \(\sum_B\lambda_{t,B}=\mu_t\) and \(\sum_{t,B}\lambda_{t,B}B_g=q_g\).
Define \(\mathcal C(\lambda)=\{C\ne0:\exists s,\lambda_{s,C}>0\}\) and \(d_t(\lambda)=\max_{C\in\mathcal C(\lambda)}\min_{g:C_g>0}v_{tg}\), taking \(d_t=0\) when \(\mathcal C(\lambda)\) is empty. Bundles held by other recipients of the same type count.
Require \(v_t(B)+d_t(\lambda)\ge1\) whenever \(\lambda_{t,B}>0\). Let \(L\) be the input bit length and \(K\) the binary length of the listed positive assignment entries, including bundle coordinates.
Does every such instance admit an assignment satisfying these conditions?
Is finding one, or reporting infeasibility, possible in time polynomial in \(m=r,\tau,L,K\), or is this search problem NP-hard?
For finite societies, the divider and every other agent are PROPm-satisfied by the constructive allocation; such allocations always exist and are computable in polynomial time in the numbers of agents and goods. [Verified discrete result](https://www.ijcai.org/proceedings/2021/0004.pdf)
No result settling this exact atomless, rational-support problem was located in the literature search.
Every instance admits a satisfying assignment. Such an assignment can be found in polynomial time in \(m,\tau,L\), and its output length \(K\) is polynomially bounded in these parameters.
The construction uses positive, sufficiently small masses of monochromatic bundles to establish the correction terms. It allocates the remaining population by a rational rounding procedure.
Lemma. Let \(x\in\mathbb Q_{\ge0}^{d}\), and let \(c\in\mathbb Q_{\ge0}^{d}\) satisfy \(c_i\le a\) for every \(i\), where \(a>0\). In polynomial time, one can construct a rational probability distribution supported on at most \(2(d+1)\) integral vectors \(B\in\mathbb Z_{\ge0}^{d}\) such that
\[ \mathbb E[B]=x, \qquad c\cdot B>c\cdot x-a \]
for every vector with positive probability. All vectors and probabilities have polynomial encoding length.
Proof. Put \(\ell_i=\lfloor x_i\rfloor\) and \(u_i=\lceil x_i\rceil\). We first construct a distribution on rational vectors \(y\) satisfying
\[ \ell_i\le y_i\le u_i, \qquad c\cdot y=c\cdot x, \qquad \mathbb E[y]=x. \]
Start with probability one on \(x\). Apply the following transformations to each currently supported vector.
Both transformations preserve the expectation and the weighted sum. In every resulting branch, at least one fractional coordinate becomes integral; no integral coordinate becomes fractional.
After each round, compress the distribution to at most \(d+1\) vectors. Explicitly, for the candidate vectors \(y^{(1)},\ldots,y^{(s)}\), solve the rational linear system
\[ p_k\ge0,\qquad \sum_{k=1}^{s}p_k=1,\qquad \sum_{k=1}^{s}p_k y^{(k)}=x. \]
It is feasible because the transformations preserved the expectation. A basic feasible solution has at most \(d+1\) positive entries. Finding such a solution is a standard polynomial-time rational linear-programming operation. Compression retains a subset of the candidate vectors, so it preserves the decrease in the number of fractional coordinates along every surviving branch.
After at most \(d\) rounds, every supported vector has all zero-coefficient coordinates integral and at most one fractional coordinate. Round that last coordinate to its two adjacent integers, preserving its expectation. This produces at most \(2(d+1)\) integral vectors with mean \(x\).
If \(y_i=\ell_i+f\), where \(0<f<1\), rounding downward loses \(c_i f<c_i\le a\). Rounding upward loses nothing. An already integral vector also loses nothing. Since \(c\cdot y=c\cdot x\), every resulting vector satisfies the asserted strict inequality.
For completeness, the arithmetic also has polynomial bit complexity. Choose integers \(D_0,H>0\) clearing the denominators of \(c\) and \(x\), respectively, and write \(A_i=D_0c_i\). Initially \(A_i y_i\) is an integer multiple of \(1/H\). This remains true throughout the transformations: when a two-coordinate move fixes one coordinate at an integer endpoint, its change in weighted value is an integer multiple of \(1/H\), and the other coordinate changes by the opposite amount. Hence, whenever \(A_i>0\), the denominator of \(y_i\) divides \(HA_i\). Zero-coefficient coordinates remain original coordinates or become integer endpoints.
All vectors stay inside the original box, so their numerators also have polynomial bit length. Each compression LP therefore has polynomial dimensions and coefficient length; its basic solution has polynomial bit length by determinant bounds. The final rounding probabilities have polynomial bit length as well. This proves the lemma. \(\square\)
Delete categories with \(q_g=0\), restoring zero coordinates in the output. This is legitimate: nonnegativity and the supply equation force every positive assignment entry to have \(B_g=0\) in such a category. Write \(d\le m\) for the remaining number of categories.
For each type, define
\[ a_t=\max_{g:q_g>0}v_{tg}. \]
Normalization implies \(a_t>0\), since \(\sum_gq_gv_{tg}=1\).
Let \(G\) be the supplied categories valued positively by at least one type, and put \(h=|G|\). Thus \(h\ge1\). For each \(g\in G\), choose a supported type \(s(g)\) with \(v_{s(g),g}>0\), and define
\[ n_g=\left\lceil\frac1{v_{s(g),g}}\right\rceil, \qquad C^{(g)}=n_ge_g. \]
The monochromatic bundle \(C^{(g)}\) has value at least one to its designated recipient type:
\[ v_{s(g)}\!\left(C^{(g)}\right)=n_gv_{s(g),g}\ge1. \]
Let \(D\) be a positive integer clearing all valuation denominators, and put \(S=\sum_{g\in G}n_g\). Choose the positive rational number
\[ \delta= \min\left\{ \frac1{4h}, \min_t\frac{\mu_t}{2h}, \min_{g\in G}\frac{q_g}{2n_g}, \frac1{4DS} \right\}. \]
Assign mass \(\delta\) of type \(s(g)\) to \(C^{(g)}\), for each \(g\in G\).
Let \(z_t\) denote the total witness mass assigned to type \(t\), and let \(W=h\delta\). Then
\[ z_t\le h\delta\le\frac{\mu_t}{2}, \qquad W\le\frac14. \]
The witness bundles consume supply
\[ w_g= \begin{cases} \delta n_g,&g\in G,\\ 0,&g\notin G. \end{cases} \]
For \(g\in G\), we have \(w_g\le q_g/2\). Consequently every remaining supplied category still has positive residual supply.
The remaining type masses are \(\beta_t=\mu_t-z_t>0\), and their sum is \(1-W\). Give every remaining type the same conditional mean bundle
\[ x_g=\frac{q_g-w_g}{1-W}. \]
This is a nonnegative rational vector. For a type \(t\), put
\[ A_t=\sum_{g\in G}n_gv_{tg}. \]
Using normalization,
\[ v_t(x) =\frac{1-\delta A_t}{1-h\delta} =1+\frac{\delta(h-A_t)}{1-W}. \]
Since \(0\le v_{tg}\le1\), we have \(A_t\le S\). Thus
\[ v_t(x) \ge1-\frac{\delta S}{1-W} \ge1-\frac43\delta S \ge1-\frac1{3D}. \]
Apply the rounding lemma to \(x\), with coefficients \(c_g=v_{tg}\) and bound \(a=a_t\). All remaining categories have positive original supply, so \(v_{tg}\le a_t\), as required.
We obtain a rational distribution \(p_{t,B}\), supported on at most \(2(d+1)\) integral bundles, with mean \(x\), such that every positively supported bundle satisfies
\[ v_t(B)>v_t(x)-a_t \ge1-a_t-\frac1{3D} >1-a_t-\frac1D. \]
Both \(v_t(B)\) and \(1-a_t\) are integer multiples of \(1/D\). Therefore this strict inequality implies
\[ v_t(B)\ge1-a_t. \]
Indeed, a grid value below \(1-a_t\) would be at most \(1-a_t-1/D\).
Assign mass \(\beta_t p_{t,B}\) of type \(t\) to each such bundle.
Combine the witness entries with the residual entries, summing masses whenever their type and bundle coincide. All masses are nonnegative rational numbers, and there are finitely many entries.
For every type,
\[ \sum_B\lambda_{t,B} =z_t+\beta_t =\mu_t. \]
For every category, the total assigned supply is
\[ w_g+\sum_t\beta_t\,\mathbb E_{p_t}[B_g] =w_g+(1-W)x_g =q_g. \]
It remains to verify the correction term. For each type \(t\), a category attaining \(a_t\) belongs to \(G\), because \(a_t>0\). Its monochromatic witness bundle has positive assignment mass and minimum item value \(a_t\) from type \(t\)'s perspective. Consequently \(d_t(\lambda)\ge a_t\).
Conversely, all used categories have positive original supply, and every such category has value at most \(a_t\) to type \(t\). The minimum value in any nonempty used bundle is therefore at most \(a_t\). Hence
\[ d_t(\lambda)=a_t. \]
Every residual bundle assigned to type \(t\) satisfies
\[ v_t(B)+d_t(\lambda) \ge(1-a_t)+a_t =1. \]
Every witness bundle has value at least one to its designated recipient type, so it satisfies the same condition. If witness and residual entries coincide, both verifications still apply.
Thus the constructed assignment satisfies all requirements.
The construction introduces at most
\[ h+2\tau(d+1)\le m+2\tau(m+1) \]
positive entries before coincidences are combined.
All preprocessing uses polynomial-time rational arithmetic. In particular:
Multiplying these probabilities by \(\beta_t\), and combining coincident entries, preserves polynomial encoding length. Therefore \(K\) is polynomially bounded in \(m,\tau,L\), and the entire search runs in polynomial time in those parameters—hence also in \(m,\tau,L,K\).
No promised instance is infeasible.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The construction satisfies every requirement of the intended atomless, rational-support problem, and its running time and output length are polynomially bounded. I found no major or minor mathematical issues.
The initial vector lies in the stated box. Rounding a zero-coefficient coordinate to its endpoints preserves the weighted sum, and the conditional probabilities preserving its expectation exist because the coordinate lies strictly between those endpoints.
When two fractional coordinates with positive coefficients are selected, the specified direction satisfies \(c\cdot h=0\). Both maximal step lengths are strictly positive and finite. Each endpoint fixes at least one selected coordinate at an integer boundary. The probabilities \(\beta/(\alpha+\beta)\) and \(\alpha/(\alpha+\beta)\) preserve the original vector’s expectation.
Only fractional coordinates are modified, so integral coordinates remain integral. Consequently, every branch that has not already reached the terminal condition loses at least one fractional coordinate per round. After at most \(d\) rounds, all zero-coefficient coordinates are integral and at most one positive-coefficient coordinate is fractional.
The compression system is feasible because the candidate distribution has expectation \(x\). Its variables are nonnegative and sum to one, so its feasible region is bounded. A basic feasible solution has at most \(d+1\) positive variables, since the system has \(d+1\) equality rows. The stated polynomial-time rational-LP operation applies to this system.
Compression retains candidate vectors, each of which still has weighted sum \(c\cdot x\) and the required progress toward integrality. It therefore preserves both properties.
In the final rounding, a downward move loses \(c_i f\), where \(0<f<1\) and \(0<c_i\le a\). Thus the loss is strictly smaller than \(a\), including when \(c_i=a\). Upward rounding and already integral vectors lose nothing. The strict inequality in the lemma is valid, and the final support has at most \(2(d+1)\) vectors.
The arithmetic invariant is correct. Initially, every \(A_i y_i\) is an integer multiple of \(1/H\). In a two-coordinate move, a coordinate reaching an integer endpoint changes its weighted contribution by an integer multiple of \(1/H\); the other contribution changes by its negative. Hence the invariant persists.
For \(A_i>0\), this bounds the reduced denominator of \(y_i\) by a divisor of \(HA_i\). Zero-coefficient coordinates retain their original values until rounded to integer endpoints. The box bounds then give polynomial numerator lengths as well.
These bounds apply uniformly across all rounds. Each compression LP consequently has polynomial dimensions and coefficient length, and its basic solution has polynomial encoding length. Intermediate branching probabilities and final rounding probabilities also use only polynomial-length rational arithmetic. There is no uncontrolled accumulation of denominator lengths.
Deleting zero-supply categories is valid: nonnegative assignment masses and bundle coordinates force every positively assigned bundle to have zero coordinates there. Restoring those coordinates afterward preserves all requirements.
Normalization ensures that at least one positive-supply category remains and that every \(a_t\) is positive. Thus \(G\) is nonempty, every designated type \(s(g)\) exists, and every \(n_g\) is well-defined. Each witness bundle has value at least one to its assigned type.
Every quantity in the minimum defining \(\delta\) is positive. The stated bounds follow:
\(z_t\le h\delta\le\mu_t/2\), \(W\le1/4\), and \(w_g\le q_g/2\) for \(g\in G\).
Therefore all residual type masses and all retained residual supplies are positive.
The formula
\(v_t(x)=(1-\delta A_t)/(1-h\delta)\)
follows exactly from normalization and witness consumption.
The subsequent bounds use \(A_t\le S\), \(1-W\ge3/4\), and \(\delta S\le1/(4D)\). All constants and inequality directions are correct, yielding \(v_t(x)\ge1-1/(3D)\).
The rounding lemma’s hypotheses hold: \(x\) is nonnegative rational, the coefficients are nonnegative rational, and every retained coefficient is at most \(a_t>0\).
Its strict inequality yields
\(v_t(B)>1-a_t-1/D\).
Both \(v_t(B)\) and \(1-a_t\) are integer multiples of \(1/D\), because bundle coordinates are integral and \(D\) clears all valuation denominators. A grid value below \(1-a_t\) would be at most \(1-a_t-1/D\). The conclusion \(v_t(B)\ge1-a_t\) is therefore justified.
Combining coincident entries preserves nonnegative rational masses and finite support. The type-mass and supply equations follow from the residual distributions’ exact means and \(\sum_t\beta_t=1-W\).
For each type, a category attaining \(a_t\) belongs to \(G\). Its monochromatic witness remains positively assigned and has minimum supported-category value \(a_t\) from that type’s perspective. This proves \(d_t(\lambda)\ge a_t\), including when the witness recipient has the same type.
Conversely, every nonzero assigned coordinate belongs to a retained positive-supply category, whose value is at most \(a_t\). Thus every nonempty assigned bundle has minimum supported-category value at most \(a_t\), establishing \(d_t(\lambda)=a_t\).
Residual bundles satisfy the required inequality by their valuation bound. Witness bundles satisfy it because their designated recipients value them at least one. Zero residual bundles cause no exception: the same bound applies to them.
The support bound \(h+2\tau(d+1)\) is correct. Products clearing denominators, witness counts, rational minima, residual means, and final mass arithmetic all have polynomial binary length. Potentially large bundle coordinates are explicitly counted in the output encoding and remain polynomial in binary length.
The construction therefore provides a polynomial-time algorithm with polynomial output length for every promised instance. No infeasibility case arises within the stated input domain. The argument is self-contained and does not depend on transferring the cited finite-society result to the atomless setting.
No additional clarification or repair is needed.
⟨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.