Answer: Polynomial-time solvable for every fixed positive approximation tolerance; the algorithm achieves nearly full MMS.
Theorem 4.1 — class: algorithmic
Given a finite type set \(T\), rational society masses \(\mu\in\Delta_T\), per-capita supplies \(q_g\) of indivisible good kinds, additive values \(v_{rg}\), and non-atomic cake densities \(f_r\) in the Robertson–Webb model, compute a finite-support mass allocation \(x_{r,b}\) of integral bundles \(b\in\mathbb{Z}_{\ge0}^{\mathcal{G}}\) together with a finite cake-allocation protocol, satisfying \(\sum_b x_{r,b}=\mu_r\) and \(\sum_{r,b}x_{r,b}b_g\le q_g\), such that every type-\(r\) recipient receives at least \((1-\epsilon)\alpha' s_r\), where \(\alpha'\ge\min\left\{1,\frac12+\min_{r:\mu_r>0}\frac{h_r}{2s_r}\right\}\), \(h_r=\int f_r\), and \(s_r\) is the per-capita MMS benchmark obtained by partitioning normalized resources into unit mass of integral bundles and cake shares.
Let \(T\) be a finite set of types with rational masses \(\mu\in\Delta_T\). Good kind \(g\) has rational per-capita supply \(q_g\); a recipient gets an integral bundle \(b\in\mathbb Z_{\ge0}^{\mathcal G}\), valued by type \(r\) at \(\sum_g v_{rg}b_g\). Type \(r\) values a cake share \(y\) at \(\int_0^1 f_r(t)y(t)\,dt\), where \(f_r\) is nonnegative and non-atomic, and \(h_r=\int_0^1 f_r(t)\,dt\) is rational.
A finite-support mass allocation assigns mass \(x_{r,b}\ge0\) and a cake share \(y_{r,b}(t)\ge0\) to each occupied type–bundle class. It requires \(\sum_b x_{r,b}=\mu_r\), \(\sum_{r,b}x_{r,b}b_g\le q_g\), and \(\sum_{r,b}x_{r,b}y_{r,b}(t)\le1\) almost everywhere. Every recipient in that class obtains value \(\sum_g v_{rg}b_g+\int_0^1 f_r(t)y_{r,b}(t)\,dt\).
Define \(s_r\) as the supremum of the least recipient value when type \(r\) partitions these normalized supplies into unit mass of integral bundles and cake shares under the same supply constraints. For fixed \(\epsilon>0\), the output consists of a finite-support mass allocation, finitely described cake shares, and \(\alpha'\ge\min\{1,\tfrac12+\min_{r:\mu_r>0,\ s_r>0}h_r/(2s_r)\}\); omit zero-benchmark types from this minimum. Each occupied class must receive at least \((1-\epsilon)\alpha's_r\). Cake densities are accessed by unit-cost Robertson–Webb evaluation and cut queries.
Is this allocation problem solvable in polynomial time in the rational input length, \(|T|\), \(|\mathcal G|\), and Robertson–Webb queries for every fixed \(\epsilon>0\), or is it NP-hard?
For finitely many agents, a polynomial-time algorithm achieves \((1-\epsilon)\alpha'\)-MMS with \(\alpha'\ge\min\{1,\tfrac12+\min_i u_i(C)/(2(n-1)\operatorname{MMS}_i)\}\). That result does not address a society specified by type masses.
The problem is polynomial-time solvable for every fixed \(\epsilon>0\). In fact, the mass model admits the stronger guarantee \(\alpha'=1\): every occupied class can receive at least \((1-\epsilon)s_r\).
Here, goods values are understood to be rational input numbers, as required by the stated rational-input complexity model. Negative goods values, if allowed, can be discarded separately for each type: supplies are upper bounds, so removing negatively valued goods never hurts feasibility or value.
1. Combining single-type allocations
Suppose that, for each positive-mass type \(r\), we construct a unit-mass allocation with:
Set \(x_{r,b}=\mu_rp_{r,b}\) and \(y_{r,b}(t)=c_{r,b}\). Then
\[ \sum_{r,b}x_{r,b}b_g \leq \sum_r\mu_rq_g=q_g, \qquad \sum_{r,b}x_{r,b}y_{r,b}(t) \leq\sum_r\mu_r=1. \]
Recipient values are unchanged. Thus it suffices to approximate the benchmark for one type using constant cake shares.
Fix that type, and write its positive goods values as \(v_g\), its total cake value as \(h\), and its benchmark as \(s\). Goods with nonpositive value will not be used.
For any feasible single-type partition, let \(c_b\) denote the cake value received in class \(b\). Nonnegativity and the cake supply constraint imply
\[ \sum_b p_bc_b =\int_0^1 f(t)\sum_b p_by_b(t)\,dt \leq h. \]
If \(h>0\), replacing each share by the constant function \(c_b/h\) preserves recipient values and feasibility. If \(h=0\), cake contributes no value. Consequently, only the scalar \(h\) matters for the single-type problem.
2. A rounding lemma for small goods
We need a rounding procedure whose support does not depend on the magnitudes of bundle coordinates.
Lemma. Given positive rational weights \(w_1,\ldots,w_k\) and a rational vector \(a\in\mathbb R_{\geq0}^k\), one can compute, in polynomial time, a distribution on at most \(k+1\) integral vectors \(B\) such that
\[ \mathbb E[B_i]=a_i, \qquad \sum_i w_iB_i\geq\sum_i w_ia_i-\max_iw_i \]
for every vector in its support.
Proof. Reorder coordinates so that \(w_1\geq\cdots\geq w_k\). Write \(a_i=\lfloor a_i\rfloor+r_i\), where \(0\leq r_i<1\), and set \(R_j=\sum_{i=1}^j r_i\), with \(R_0=0\).
For \(U\) uniform on \([0,1)\), define
\[ B_i(U)=\lfloor a_i\rfloor+ \lfloor R_i+U\rfloor-\lfloor R_{i-1}+U\rfloor. \]
Each added term belongs to \(\{0,1\}\). The identity
\(\mathbb E[\lfloor x+U\rfloor]=x\) gives \(\mathbb E[B_i]=a_i\).
Let
\[ E_j=\sum_{i=1}^j(B_i-a_i) =\lfloor R_j+U\rfloor-R_j. \]
Then \(-1<E_j<1\). Summation by parts gives
\[ \sum_{i=1}^k w_i(B_i-a_i) = \sum_{j=1}^{k-1}(w_j-w_{j+1})E_j+w_kE_k \geq-w_1. \]
Finally, the vector \(B(U)\) changes only at the at most \(k\) breakpoints where some \(R_j+U\) is integral. Sorting those rational breakpoints gives at most \(k+1\) intervals, whose lengths are the required probabilities. All computations and output numbers have polynomial bit complexity. \(\square\)
3. A polynomial-size feasibility relaxation
Fix a rational constant \(\delta\in(0,1)\) and a positive rational target \(z\).
Call a good *large* if \(v_g\geq\delta z\), and *small* otherwise. Put
\[ K=\lceil1/\delta\rceil, \qquad S=\sum_{g\text{ small}}v_gq_g, \qquad F=S+h. \]
Enumerate all large-good configurations \(C\) containing at most \(K\) items in total, including the empty configuration. Write
\[ V(C)=\sum_{g\text{ large}}v_gC_g, \qquad d_C=\max\{0,z-V(C)\}. \]
For fixed \(\delta\), there are at most \((|\mathcal G|+1)^K\) configurations. Solve the rational linear feasibility problem
\[ p_C\geq0,\qquad \sum_Cp_C=1, \]
\[ \sum_Cp_CC_g\leq q_g \quad\text{for every large good }g, \]
\[ \sum_Cp_Cd_C\leq F. \tag{*} \]
This LP has polynomial size for fixed \(\delta\).
We establish both properties needed for the algorithm.
Necessity. If a unit-mass partition gives every recipient value at least \(z\), then \((*)\) is feasible.
For each recipient, consider its large goods. If their total value is below \(z\), retain all of them; their number is less than \(1/\delta\). Otherwise, retain goods in any order until their total first reaches \(z\). Before the last retained item, the total is below \(z\), so fewer than \(1/\delta\) items have been retained. Including the last item gives at most \(K\) items.
Thus every retained configuration is enumerated. Its deficit \(d_C\) is at most the recipient’s original small-good value plus cake value: this is immediate when \(V(C)\geq z\), and otherwise no large goods were removed.
Aggregating configurations over the unit population gives the mass and large-good constraints. Aggregating the preceding deficit inequality gives
\[ \sum_Cp_Cd_C\leq S+h=F. \]
This proves necessity. In particular, if the LP is infeasible, then \(s\leq z\): otherwise the definition of supremum would supply a partition with minimum value greater than \(z\).
Constructive sufficiency with loss. If \((*)\) is feasible, we can construct a unit-mass allocation with minimum value at least \((1-\delta)z\).
First suppose \(F>0\). For each occupied configuration \(C\), prescribe the fractional small-good vector and constant cake share
\[ a_{Cg}=\frac{d_Cq_g}{F} \quad(g\text{ small}), \qquad y_C(t)=\frac{d_C}{F}. \]
Their combined value is exactly the deficit:
\[ \sum_{g\text{ small}}v_ga_{Cg} +h\frac{d_C}{F} =d_C. \]
Apply the rounding lemma to the small-good vector for each \(C\), splitting its mass according to the resulting distribution. Since each small-good value is below \(\delta z\), every resulting recipient obtains value at least
\[ V(C)+d_C-\delta z\geq(1-\delta)z. \]
Let \(D=\sum_Cp_Cd_C\leq F\). Expected counts are preserved exactly, so each small-good supply constraint holds:
\[ \sum_Cp_Ca_{Cg}=\frac{D}{F}q_g\leq q_g. \]
The cake constraint also holds pointwise:
\[ \sum_Cp_Cy_C(t)=\frac{D}{F}\leq1. \]
The LP already enforces the large-good constraints.
If \(F=0\), every occupied configuration has \(d_C=0\), and the large configurations alone achieve \(z\).
The construction uses at most \((|\mathcal G|+1)\) subclasses per configuration and has polynomial bit complexity. Bundle coordinates may be large, but they are written in binary.
4. Locating a sufficiently good target
It remains to choose \(z\) without knowing \(s\). We give explicit bounds and a binary-search invariant; the LP need not be an exact feasibility test.
Every feasible minimum value is at most the average value, hence
\[ s\leq B:=h+\sum_{g:v_g>0}v_gq_g. \]
We can also detect the zero-benchmark case and obtain a positive rational lower bound otherwise.
If \(h>0\), giving everyone the constant cake share \(1\) shows \(s\geq h\). Set \(L_0=h\).
Suppose \(h=0\), and put \(Q=\sum_{g:v_g>0}q_g\).
In every positive-benchmark case, \(L_0\) is attained by an explicit partition, so the target-\(L_0\) LP is feasible by necessity.
Initialize \(L=L_0\), \(U=B\), retaining a feasible LP solution at \(L\). Repeatedly test the midpoint \(z=(L+U)/2\):
Throughout this procedure, \(U\geq s\), because every infeasible test implies \(s\leq z\). Also, the retained LP at \(L\) is feasible. Stop when
\[ U-L\leq\delta L_0. \]
The number of iterations is polynomial in the input bit length: \(B\) and \(L_0\) are positive rationals of polynomial encoding length, and the interval width halves at each iteration.
At termination,
\[ L\geq U-\delta L_0 \geq s-\delta L_0 \geq(1-\delta)s. \]
Applying the constructive sufficiency result to the retained LP gives minimum recipient value at least
\[ (1-\delta)L\geq(1-\delta)^2s. \]
For any fixed \(0<\epsilon<1\), choose a fixed rational \(\delta\) with \(0<\delta\leq\epsilon/3\). Then \((1-\delta)^2\geq1-\epsilon\), as required. For \(\epsilon\geq1\), the empty allocation already satisfies the requested value inequality.
5. Final allocation and complexity
Run the single-type algorithm for each positive-mass type with positive benchmark. For a zero-benchmark type, give its entire mass the empty bundle and zero cake. Combine the unit-mass allocations as in Section 1.
If subclasses of one type have the same integral bundle, merge them by summing their masses and averaging their constant cake shares with those masses as weights. Feasibility is preserved, and their common lower value bound is preserved because cake value is linear.
For fixed \(\epsilon\), the resulting algorithm has:
Set \(\alpha'=1\). The required lower bound on \(\alpha'\) is at most \(1\), and every occupied class receives at least \((1-\epsilon)s_r\).
The crucial feature is the ability to split type mass among integral bundles. This permits both exact preservation of expected item counts during rounding and the combination of independently constructed single-type partitions.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed approximation under the usual interpretation that the rational numerical data, including the cake totals, count toward the input encoding length. The mathematical construction is sound. There are minor omissions concerning empty sets, trivial allocations, and the stated oracle complexity.
Scaling each unit-mass allocation by \(\mu_r\) preserves the type-mass constraints. Its goods consumption becomes at most \(\mu_rq_g\), and its aggregate constant cake consumption becomes at most \(\mu_r\). Summing over types establishes both supply constraints because \(\sum_r\mu_r=1\).
This step does not require different types to agree on the spatial distribution of cake value: each single-type allocation uses constant shares, whose value for type \(r\) is its constant multiplier times \(h_r\).
For a single type, the replacement of cake shares by constants is also valid. The inequality \(\sum_b p_bc_b\leq h\) implies that the replacement shares satisfy the cake constraint pointwise. When \(h=0\), nonnegativity of the density ensures that cake contributes no value.
Discarding nonpositive goods is legitimate under upper-bound supply constraints. In particular, this restriction does not lower the benchmark: removing those goods from any partition weakly increases its recipient values.
Since each fractional part lies in \([0,1)\), each floor increment is either zero or one. The stated expectation identity gives the exact coordinate means.
The prefix error formula follows by telescoping, including the fact that \(\lfloor U\rfloor=0\). Its bounds are valid, and summation by parts yields a loss of at most \(w_1\), since all coefficients are nonnegative and sum to \(w_1\).
There are at most \(k\) change points in \([0,1)\), so the support bound and rational-probability construction follow. Sorting and rational arithmetic have polynomial bit complexity.
Minor issue: The algorithm can have no small goods, whereas the lemma uses \(\max_iw_i\) and \(w_1\), which are undefined when \(k=0\).
Minimum clarification: State explicitly how the construction handles an empty small-good coordinate set, without invoking the lemma in that case.
For fixed \(\delta\), the integer \(K\) is constant, so enumeration of configurations containing at most \(K\) large items is polynomial in the number of good kinds. All LP coefficients have polynomial encoding length in the rational data and target.
The truncation argument respects the item-count bound. If the retained value remains below \(z\), the number of retained items is less than \(1/\delta\). If the threshold is reached, the number before the final item is less than \(1/\delta\), giving at most \(\lceil1/\delta\rceil\) items after that item.
Truncation only decreases large-good consumption. The deficit inequality holds in both stated cases, and aggregation yields the last LP constraint.
The conclusion from infeasibility is correctly stated as \(s\leq z\). It does not assume that the benchmark supremum is attained.
For \(F>0\), the prescribed small-good vector and constant cake share provide total fractional value exactly \(d_C\). Rounding preserves each coordinate expectation and loses less than \(\delta z\) whenever there are small goods. Thus the claimed recipient lower bound follows.
The aggregate small-good and cake calculations are correct: each is scaled by \(D/F\leq1\). Large-good consumption is unchanged by subdivision and remains LP-feasible.
When \(F=0\), nonnegativity forces every positive-mass configuration to have zero deficit. The stated treatment is therefore valid.
The support and encoding claims also hold: there are polynomially many configurations and subdivisions, and the rounded coordinates and probabilities have polynomial binary descriptions. Large bundle coordinates do not invalidate this conclusion.
The average-value upper bound \(B\) applies to every feasible partition, hence also to the supremum.
When \(h=0\) and \(Q<1\), a positive fraction of the population must receive no positively valued item. Consequently, no positive minimum is possible; assigning empty bundles establishes the zero benchmark.
When \(Q\geq1\), the described one-item distribution is feasible and establishes the positive lower bound. When \(h>0\), the constant cake allocation establishes the alternative lower bound.
The search does not require monotonicity of LP feasibility. Its two maintained facts—\(U\geq s\) and a feasible LP at \(L\)—are sufficient. Halving the interval gives polynomially many iterations in the encoding lengths of \(B\) and \(L_0\).
At termination, every inequality in \(L\geq U-\delta L_0\geq s-\delta L_0\geq(1-\delta)s\) has the correct direction. The final multiplicative guarantee and the choice \(\delta\leq\epsilon/3\) are valid.
Minor issue: For \(\epsilon\geq1\), “the empty allocation” could literally mean no occupied classes, which would violate the positive type-mass constraints.
Minimum clarification: Specify that each type’s full mass receives the empty bundle and zero cake.
The final scaling argument applies to all positive-mass types. Assigning empty bundles to zero-benchmark types is feasible and meets their value requirement.
Merging classes with identical bundles is valid: their goods values coincide, and averaging their constant cake shares preserves the weighted cake consumption and the common recipient lower bound.
Setting \(\alpha'=1\) meets the requested bound whenever that bound is defined. The result is stronger than the requested approximation.
Polynomial-time rational LP feasibility applies here: the LP has explicit rational coefficients, polynomially many variables and constraints for fixed \(\epsilon\), and polynomial coefficient encoding length.
Minor issue: The final sentence about obtaining \(h_r\) by evaluation queries establishes the query count, but does not by itself establish a bound on the binary length of the returned rationals. Rationality alone supplies no such bound.
Minimum clarification: State that the running-time bound counts the encoding lengths of the rational totals \(h_r\), including when they are supplied by queries, or explicitly specify an oracle arithmetic model. As written, the proof establishes polynomial bit complexity for supplied rational totals; its oracle-only extension needs this convention.
The output resolves the substantive allocation question. The identified repairs concern boundary conventions and the precise computational model; no missing mathematical approximation argument was found.
⟨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.