Answer: Polynomial-time solvable; every valid instance is feasible.
Theorem 5.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe randomized allocation implemented by Algo- rithm 1 is ex-ante WSD-EF and ex-post WSD-PROP1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given worker types \(\Theta\) with masses \(\mu_\theta\), entitlement intensities \(e_\theta\) satisfying \(\sum_\theta \mu_\theta e_\theta=1\), class-level ordinal rankings \(\pi_\theta\), class-constant competences \(u_{\theta b}\), and chore classes \(B\) with per-capita supplies \(\rho_b\), where \(N\rho_b\) indivisible copies of class \(b\) are interchangeable and tied in the ordinal domain, find masses \(z_{\theta,S}\) over integral class-count bundles \(S\) such that \(\sum_S z_{\theta,S}=\mu_\theta\), \(\sum_{\theta,S}z_{\theta,S}k_b(S)=\rho_b\), every supported bundle injects into \(q_\theta=\lfloor\rho e_\theta\rfloor+1\) WSD-PROP1 slots with class rank \(R_\theta(b)\ge(\ell-1)/e_\theta\), and \(\sum_S z_{\theta,S}k_b(S)=\mu_\theta e_\theta\rho_b\) for every \(\theta,b\) to realize the BoBW marginal guarantee.
A society is given by its support: the list of \(\tau\geq1\) worker types with positive binary rational masses \(\mu_\theta\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) chore classes \(B\), with positive binary rational per-capita supplies \(\rho_b\); write \(\rho=\sum_b\rho_b\). Each type has a positive binary rational entitlement intensity \(e_\theta\), with \(\sum_\theta\mu_\theta e_\theta=1\), a strict ordering \(\pi_\theta\) of classes from greatest to least disutility, and binary rational competences \(u_{\theta b}\in[0,1]\). Copies within a class are tied and interchangeable; competences impose no additional constraint or objective.
Define the cumulative supply rank \(R_\theta(b)=\sum_{c:\pi_\theta^{-1}(c)\leq\pi_\theta^{-1}(b)}\rho_c\) and \(q_\theta=\lfloor\rho e_\theta\rfloor+1\). A bundle \(S\) is an integral count vector \(k(S)\in\mathbb Z_{\geq0}^{m}\), including the empty bundle.
Call \(S\) admissible for type \(\theta\) if its individual chore occurrences can be injected into distinct slots \(\ell\in\{1,\ldots,q_\theta\}\), with an occurrence of class \(b\) eligible precisely when \(R_\theta(b)\geq(\ell-1)/e_\theta\). This is the WSD-PROP1 bundle condition used here.
Find a finite list of nonnegative binary rational bundle masses \(z_{\theta,S}\), with binary-encoded bundle counts, satisfying \(\sum_S z_{\theta,S}=\mu_\theta\), \(\sum_{\theta,S}z_{\theta,S}k_b(S)=\rho_b\), and \(\sum_Sz_{\theta,S}k_b(S)=\mu_\theta e_\theta\rho_b\) for every \(\theta,b\); every bundle with positive mass must be admissible. The last equalities are the uniform entitlement marginals required for the best-of-both-worlds guarantee. Let \(L\) be the total input bit length.
Is this continuous allocation problem solvable in polynomial time in \(m,\tau,L\), or is its feasibility problem NP-hard?
For explicitly listed agents and indivisible chores with strict item rankings, a lottery with uniform entitlement marginals, ex-ante weighted SD envy-freeness, and ex-post WSD-PROP1 is computable in polynomial time ([Prakash and Nimbhorkar](https://arxiv.org/html/2312.15479)).
No result settling this exact continuous, binary-encoded class-supply formulation was located in the literature search.
Every valid instance is feasible. An exact allocation can be constructed in time polynomial in \(m,\tau,L\), using at most \(\tau(m+1)\) bundles with positive mass.
The construction rounds cumulative entitlement supplies with a common shift. Its proof is self-contained; it does not require extending the explicitly listed matching formulation of [Prakash and Nimbhorkar](https://arxiv.org/html/2312.15479).
Fix a type \(\theta\). Write its classes in decreasing disutility order as \(b_1,\ldots,b_m\), and define
\[ a_0=0,\qquad a_i=e_\theta\sum_{r=1}^{i}\rho_{b_r}, \qquad c_i=\lfloor a_i\rfloor+1. \]
Thus \(a_m=e_\theta\rho\) and \(c_m=q_\theta\). Because supplies and entitlement intensities are positive, the sequence \(a_i\) is strictly increasing.
An occurrence of class \(b_i\) is eligible for slot \(\ell\) exactly when
\[ \ell-1\le e_\theta R_\theta(b_i)=a_i. \]
Consequently, its eligible slots are precisely \(1,\ldots,c_i\).
Lemma. A nonnegative integral count vector \(k\) is admissible for \(\theta\) if and only if
\[ \sum_{r=1}^{i}k_{b_r}\le c_i \qquad\text{for every }i\in\{1,\ldots,m\}. \]
Proof. For necessity, every occurrence among classes \(b_1,\ldots,b_i\) must occupy one of the first \(c_i\) slots: its own eligible-slot set is contained in that set. Injectivity therefore gives the inequality.
For sufficiency, list all occurrences in class order \(b_1,\ldots,b_m\), and assign the \(j\)-th occurrence to slot \(j\). If that occurrence has class \(b_i\), then
\[ j\le\sum_{r=1}^{i}k_{b_r}\le c_i. \]
Hence its slot is eligible. The inequality for \(i=m\) ensures that every assigned slot is at most \(q_\theta\). The assignment is injective. The empty bundle satisfies the same characterization. \(\square\)
Continue with this fixed type. For \(t\in[0,1)\), define counts
\[ k_{b_i}(t)=\lfloor a_i+t\rfloor-\lfloor a_{i-1}+t\rfloor. \]
These are nonnegative integers because \(a_i>a_{i-1}\). Also, \(\lfloor a_0+t\rfloor=0\), so their prefix sums telescope:
\[ \sum_{r=1}^{i}k_{b_r}(t)=\lfloor a_i+t\rfloor \le \lfloor a_i\rfloor+1=c_i. \]
The lemma proves that every resulting bundle is admissible.
Only finitely many bundles arise. Let \(f_i=a_i-\lfloor a_i\rfloor\) be the fractional part of \(a_i\). Form the set of rational endpoints
\[ T=\{0,1\}\cup\{1-f_i:1\le i\le m,\ f_i>0\}. \]
Remove duplicates and sort them:
\[ 0=t_0<t_1<\cdots<t_s=1. \]
There are at most \(m+2\) endpoints, so \(s\le m+1\). Each function \(\lfloor a_i+t\rfloor\) is constant on every half-open interval \([t_j,t_{j+1})\). Therefore the entire count vector is constant there.
For each \(j\in\{0,\ldots,s-1\}\), output the bundle \(S_j\) with count vector \(k(t_j)\) and mass
\[ z_{\theta,S_j}=\mu_\theta(t_{j+1}-t_j). \]
If an identical bundle appears more than once, combine its masses. All masses are positive rational numbers, and every output bundle is admissible.
The interval lengths sum to one, giving
\[ \sum_j z_{\theta,S_j} =\mu_\theta\sum_j(t_{j+1}-t_j) =\mu_\theta. \]
To verify the class marginals, first consider any \(A\ge0\). Write \(A=n+f\), where \(n=\lfloor A\rfloor\) and \(0\le f<1\). On \([0,1)\), the value of \(\lfloor A+t\rfloor\) is \(n\) on an interval of length \(1-f\), and \(n+1\) on an interval of length \(f\). Thus
\[ \int_0^1\lfloor A+t\rfloor\,dt =n(1-f)+(n+1)f=A. \]
Our finite partition contains every breakpoint of the relevant floor functions. Consequently, for each class \(b_i\),
\[ \begin{aligned} \sum_j(t_{j+1}-t_j)k_{b_i}(t_j) &=\int_0^1\bigl(\lfloor a_i+t\rfloor-\lfloor a_{i-1}+t\rfloor\bigr)\,dt\\ &=a_i-a_{i-1}\\ &=e_\theta\rho_{b_i}. \end{aligned} \]
Multiplying by \(\mu_\theta\) proves the required uniform entitlement marginal:
\[ \sum_j z_{\theta,S_j}k_{b_i}(S_j) =\mu_\theta e_\theta\rho_{b_i}. \]
Apply this construction independently to every supported type. For each class \(b\), normalization of the entitlement intensities then yields
\[ \sum_{\theta,S}z_{\theta,S}k_b(S) =\sum_\theta\mu_\theta e_\theta\rho_b =\rho_b. \]
Hence all requested mass, supply, marginal, and admissibility conditions hold.
It remains to check that the construction is polynomial in the binary input length, rather than in the numerical supplies or slot counts.
Write \(\rho_b=p_b/d_b\) and \(e_\theta=h_\theta/g_\theta\), with positive integers encoded in binary. Define
\[ D=\prod_b d_b,\qquad H_\theta=g_\theta D. \]
For the fixed type, every cumulative quantity has the form
\[ a_i=\frac{N_i}{H_\theta}, \qquad N_i=h_\theta\sum_{r=1}^{i}p_{b_r}\frac{D}{d_{b_r}}. \]
The integers \(D,H_\theta,N_i\) have bit lengths bounded by \(O(L+\log m)\): products add factor bit lengths, and summing at most \(m\) terms adds at most \(O(\log m)\) bits.
Every endpoint has denominator \(H_\theta\). More explicitly, when \(N_i\bmod H_\theta\) is nonzero, its associated breakpoint is
\[ \frac{H_\theta-(N_i\bmod H_\theta)}{H_\theta}. \]
Thus endpoint generation and sorting use polynomially many operations on integers of polynomial bit length. At an endpoint \(t_j=T_j/H_\theta\), cumulative rounded counts are computed directly as
\[ \lfloor a_i+t_j\rfloor =\left\lfloor\frac{N_i+T_j}{H_\theta}\right\rfloor. \]
No chore occurrences or slots need to be enumerated.
If \(\mu_\theta=v_\theta/w_\theta\), the corresponding output mass is exactly
\[ z_{\theta,S_j} =\frac{v_\theta(T_{j+1}-T_j)}{w_\theta H_\theta}, \]
which also has polynomial bit length. If “binary rational” specifically means dyadic rational, these masses remain dyadic because the input denominators, and therefore the displayed denominator, are powers of two.
There are at most \(m+1\) bundles per type, each containing \(m\) binary-encoded counts. The algorithm performs \(O(\tau m^2)\) count computations and polynomially many additional arithmetic operations, all on numbers of polynomial bit length. Its running time and output length are therefore polynomial in \(m,\tau,L\).
The continuous class-supply formulation is always feasible and polynomial-time solvable under the stated assumptions. The construction preserves the uniform entitlement marginals exactly and outputs at most \(\tau(m+1)\) admissible bundles. Competences require no processing because they impose neither constraints nor an objective.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the assigned problem. It establishes feasibility for every valid instance and gives an exact construction with polynomial running time and output length. No major or minor mathematical issues were found.
The eligible-slot calculation is correct. For class \(b_i\), eligibility is equivalent to \(\ell-1\le a_i\). Since \(\ell\) is an integer, its eligible slots are exactly \(1,\ldots,\lfloor a_i\rfloor+1\). These slots lie within the permitted range because \(a_i\le a_m\) and \(c_m=q_\theta\).
Both directions of the lemma are justified:
Repeated occurrences and the empty bundle are covered. Equal values among the \(c_i\) cause no difficulty.
All rounding claims hold throughout \(t\in[0,1)\).
Because the \(a_i\) increase, differences of consecutive floors are nonnegative integers. Since \(\lfloor a_0+t\rfloor=0\), the prefix sums telescope exactly to \(\lfloor a_i+t\rfloor\). The bound \(\lfloor a_i+t\rfloor\le\lfloor a_i\rfloor+1\) is valid, so the lemma establishes admissibility for every constructed bundle.
The breakpoint set is complete:
Removing duplicate endpoints preserves this property. There are at most \(m+1\) intervals, each of strictly positive rational length. The endpoint \(1\) is used only as an interval boundary, so the construction never evaluates a bundle outside its stated parameter domain.
Combining identical bundles preserves their total mass, admissibility, and all marginals.
The type-mass identity follows directly from the interval lengths summing to one.
The floor-integral calculation is correct for every \(A\ge0\), including integral \(A\). When the fractional part is zero, the portion assigned the higher floor value has length zero.
Because the partition includes all breakpoints of both floor functions defining each count, the finite weighted sum equals the displayed integral exactly. Subtracting the two floor integrals gives \(a_i-a_{i-1}=e_\theta\rho_{b_i}\). Multiplication by \(\mu_\theta\) therefore establishes every required type-class marginal.
Applying the construction independently across types is legitimate: the remaining coupling condition is aggregate supply, and that follows exactly from the established marginals and \(\sum_\theta\mu_\theta e_\theta=1\).
No approximation or limiting argument is involved.
The arithmetic representation and bit bounds are sound.
The product denominator \(D\) has bit length bounded by the sum of the input denominator bit lengths. Multiplication by \(g_\theta\), and formation of the cumulative numerators \(N_i\), preserve polynomial bit length. The stated \(O(L+\log m)\) bound is valid: products contribute sums of factor bit lengths, and summing at most \(m\) terms contributes at most an additional logarithmic term.
The endpoint numerators, comparisons, floor divisions, bundle counts, and output mass numerators and denominators all have polynomial bit length. Large numerical supplies or slot counts therefore do not require large explicit enumerations.
The stated \(O(\tau m^2)\) count-computation bound follows from at most \(m+1\) intervals per type and \(m\) counts per interval. Sorting, exact arithmetic, and any duplicate-bundle combination also admit polynomial implementation. The output contains at most \(\tau(m+1)\) bundles, with \(m\) binary-encoded counts each.
Under the usual interpretation of binary rationals as binary-encoded rational numbers, the output meets the encoding requirement. Under the dyadic interpretation, the construction also preserves dyadic masses as stated.
The proof addresses the exact continuous formulation in the task, including uniform entitlement marginals, integral bundle counts, admissibility, and polynomial dependence on binary input size. Competences correctly play no role because the task assigns them no constraint or objective.
The argument is self-contained and does not depend on an unverified application of the cited discrete-agent result. 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.