Answer: polynomial-time solvable
Theorem 4.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven an $\SPLC$ fair division instance, $\SPLCins$, Algorithm $\ref{alg:splc-mms-complete}$ gives each agent a bundle $A_i$ such that $v_i(A_i) \geq \frac{1}{2} \MMS_i$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many types \(T\), rational masses \(\mu_t\) summing to \(1\), per-capita supplies \(q_j\), and SPLC valuations \(u_t(b)=\sum_j\sum_{r=1}^{b_j}v_{tjr}\) on integral bundles \(b\in\mathbb{Z}_{\ge 0}^{J}\), define \(\sigma_t(q)\) as the supremum of \(z\) for which a distribution over integral bundles has expected use of each good \(j\) at most \(q_j\) and gives every bundle in its support value at least \(z\). Find finite bundle masses \(\lambda_{t,b}\ge 0\) such that \(\sum_b\lambda_{t,b}=\mu_t\), \(\sum_{t,b}\lambda_{t,b}b_j\le q_j\) for each good, and every bundle with positive mass satisfies \(u_t(b)\ge \sigma_t(q)/2\).
A society is given by its support: a list \(T\) of \(\tau\geq1\) types with positive binary rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) kinds of goods, with nonnegative binary rational per-capita supplies \(q_j\). For each good, an explicitly listed finite marginal sequence specifies each type's SPLC valuation: \(v_{tj1}\geq\cdots\geq v_{tjK_j}\geq0\), all binary rationals; set \(v_{tjr}=0\) for \(r>K_j\). Integral bundles are \(b\in\mathbb Z_{\geq0}^{m}\), including the empty bundle, and \(u_t(b)=\sum_{j=1}^{m}\sum_{r=1}^{b_j}v_{tjr}\).
Define \(\sigma_t(q)=\sup\{z\geq0:\exists\text{ a probability distribution }P\text{ on integral bundles with }\mathbb E_P[b_j]\leq q_j\text{ for every }j,\ P(b)>0\Rightarrow u_t(b)\geq z\}\).
The allocation problem is to output finitely many nonzero binary rational masses \(\lambda_{t,b}\geq0\) satisfying \(\sum_b\lambda_{t,b}=\mu_t\), \(\sum_{t,b}\lambda_{t,b}b_j\leq q_j\), and \(\lambda_{t,b}>0\Rightarrow u_t(b)\geq\sigma_t(q)/2\). Supplies may be left unused. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\), and \(\sum_jK_j\).
Can this \(\tfrac12\)-share allocation be computed in polynomial time for every instance, or is computing such an allocation NP-hard?
For finite societies with SPLC valuations, a \(\tfrac12\)-MMS allocation exists and is computable in polynomial time; the guarantee also holds for symmetric APS ([verified source](https://arxiv.org/abs/2312.08504)). No result settling the precise distribution-over-types problem above was identified in the literature search.
The allocation problem is polynomial-time solvable. Let \(N=\sum_{j=1}^{m}K_j\). The construction below runs in \(\operatorname{poly}(m,\tau,L,N)\) bit operations and outputs polynomially many rational masses, each encoded with polynomially many bits.
The key observation is that type-specific lotteries can be combined without exceeding the supplies. The main work is therefore to construct, for each type, a lottery guaranteeing half its benchmark.
Suppose that, for every type \(t\), we construct a finitely supported rational probability distribution \(P_t\) satisfying
\(\mathbb E_{P_t}[b_j]\leq q_j\) for every good \(j\),
and
\(P_t(b)>0\Longrightarrow u_t(b)\geq \sigma_t(q)/2.\)
Define \(\lambda_{t,b}=\mu_tP_t(b)\), omitting zero entries. Then
\(\sum_b\lambda_{t,b}=\mu_t,\)
and, for every good \(j\),
\(\sum_{t,b}\lambda_{t,b}b_j=\sum_t\mu_t\mathbb E_{P_t}[b_j]\leq\sum_t\mu_tq_j=q_j.\)
The utility guarantee also holds for every positive allocation mass. Thus it suffices to solve the following single-type problem: construct a rational lottery with expected bundle at most \(q\), all of whose supported bundles have utility at least \(\sigma(q)/2\).
Fix one type and suppress its subscript.
Define
\(\mathcal B=\prod_{j=1}^{m}\{0,1,\ldots,K_j\}.\)
For any integral bundle \(b\), let \(\bar b_j=\min\{b_j,K_j\}\). Because all marginals beyond \(K_j\) are zero,
\(u(\bar b)=u(b)\quad\text{and}\quad \bar b_j\leq b_j.\)
Pushing any lottery forward under this truncation preserves utilities and weakly decreases expected consumption. Consequently, the definition of \(\sigma(q)\) is unchanged if lotteries are restricted to the finite set \(\mathcal B\).
Let \(\mathcal V=\{u(b):b\in\mathcal B\}\). A feasible lottery on \(\mathcal B\) has a minimum supported utility belonging to \(\mathcal V\). Conversely, that minimum is itself a feasible threshold. Since the empty-bundle lottery makes threshold zero feasible, it follows that
\(\sigma(q)=\max\{x\in\mathcal V:\text{some lottery on }\mathcal B\text{ has expected bundle at most }q\text{ and supported utilities at least }x\}.\)
In particular, this maximum is attained. This argument establishes attainment; the algorithm will not enumerate \(\mathcal B\) or compute \(\sigma(q)\) exactly.
For each good, define its prefix utility
\(U_j(k)=\sum_{r=1}^{k}v_{jr},\qquad 0\leq k\leq K_j.\)
Let \(U=\sum_jU_j(K_j)\). Then \(\sigma(q)\leq U\).
If \(U=0\), the empty-bundle lottery solves the problem. Otherwise, let \(\ell\) be the smallest positive listed marginal. Every positive bundle utility is at least \(\ell\). By attainment,
\(\sigma(q)>0\Longrightarrow \ell\leq\sigma(q)\leq U.\)
Fix a positive rational number \(a\). Set
\(\delta=\frac{a}{4m},\qquad H=3m,\)
and define rounded prefix scores
\(w_j(k)=\min\left\{H,\left\lfloor\frac{U_j(k)}{\delta}\right\rfloor\right\}.\)
Call a bundle \(b\in\mathcal B\) accepted when
\(\sum_{j=1}^{m}w_j(b_j)\geq H.\)
The following two implications provide the approximation guarantee.
Suppose \(u(b)\geq a\). If any score \(w_j(b_j)\) equals \(H\), acceptance follows immediately.
Otherwise, none of the scores is capped, so
\(\sum_jw_j(b_j)=\sum_j\left\lfloor U_j(b_j)/\delta\right\rfloor\geq\sum_jU_j(b_j)/\delta-m=u(b)/\delta-m\geq4m-m=H.\)
Thus \(b\) is accepted.
For every prefix, \(w_j(k)\leq U_j(k)/\delta\). Hence an accepted bundle satisfies
\(u(b)=\sum_jU_j(b_j)\geq\delta\sum_jw_j(b_j)\geq\delta H=3a/4.\)
Together, the lemmas show that the accepted bundles contain every bundle of utility at least \(a\), while every accepted bundle has utility at least \(3a/4\).
Construct a directed acyclic multigraph with vertices
\((j,s),\qquad 0\leq j\leq m,\quad 0\leq s\leq H.\)
For every good \(j\), score \(s\), and quantity \(k\in\{0,\ldots,K_j\}\), introduce an arc
\((j-1,s)\longrightarrow\bigl(j,\min\{H,s+w_j(k)\}\bigr),\)
labelled with quantity \(k\) of good \(j\). Distinct quantity choices remain distinct arcs even if their endpoints coincide.
The source is \((0,0)\), and the sink is \((m,H)\). A path chooses exactly one quantity for every good. Its final score is \(\min\{H,\sum_jw_j(b_j)\}\). Therefore, source-to-sink paths correspond exactly to accepted bundles.
Introduce a nonnegative flow variable \(f_e\) for every arc. Require unit source-to-sink flow, with conservation at every other vertex. For each good \(j\), additionally require
\(\sum_{e\text{ in layer }j}k(e)f_e\leq q_j,\)
where \(k(e)\) is the quantity labelling arc \(e\).
This rational LP is feasible if and only if an accepted-bundle lottery with expected bundle at most \(q\) exists:
For completeness, decomposition is constructive. Follow positive-flow arcs from the source to the sink, subtract the minimum flow on that path, and repeat. Conservation ensures that a positive-flow path cannot stop at an intermediate vertex. Every subtraction eliminates at least one positive arc, so at most the number of arcs many paths are produced.
The graph has \((m+1)(H+1)=O(m^2)\) vertices and
\((H+1)\sum_j(K_j+1)=O\bigl(m(N+m)\bigr)\)
arcs. Thus exact rational LP feasibility and, when feasible, a rational accepted-bundle lottery can be computed in polynomial time.
Two consequences will be used:
Assume \(U>0\). Test all thresholds
\(a_i=\ell(3/2)^i,\qquad i=0,1,\ldots,\quad a_i\leq U.\)
For each threshold, solve the LP from Section 3.
If no LP is feasible, output the empty-bundle lottery. This is correct: if \(\sigma(q)>0\), then \(\ell\leq\sigma(q)\), and the LP for \(a_0=\ell\) would be feasible. Thus the absence of a feasible candidate implies \(\sigma(q)=0\).
Otherwise, choose the largest feasible threshold \(a\) and output its flow-decomposition lottery.
To prove its guarantee, first consider \(\sigma(q)>0\). Let \(a_*\) be the largest grid threshold satisfying \(a_*\leq\sigma(q)\). Such a threshold exists, and maximality gives
\(a_*\leq\sigma(q)<(3/2)a_*.\)
The LP for \(a_*\) is feasible. Consequently, the chosen feasible threshold satisfies \(a\geq a_*\). Every output bundle therefore has utility at least
\(3a/4\geq3a_*/4>\sigma(q)/2.\)
If \(\sigma(q)=0\), the empty-bundle lottery suffices; indeed, no positive candidate can be feasible, since feasibility would itself provide a strictly positive feasible benchmark threshold.
The algorithm tests all candidates and does not assume that LP feasibility is monotone along the grid.
All computations use rationals represented by binary numerators and denominators.
Every positive input marginal is at least \(2^{-L}\), and every input marginal is at most \(2^L\). Hence, when \(U>0\),
\(U/\ell\leq N\,2^{2L}.\)
The number of grid thresholds is therefore \(O(L+\log(N+1))\). Each threshold has \(O(L+\log(N+1))\) bits: its numerator and denominator are obtained from those of \(\ell\) by multiplying by powers of three and two of that order.
Prefix utilities, rounded scores, and graph construction are computable by polynomial-time rational arithmetic. Each feasibility LP has:
The standard polynomial-time theorem for rational linear programming applies directly: these are explicitly represented rational linear constraints. It decides feasibility exactly and, when feasible, returns a rational feasible point with polynomial encoding length.
Flow decomposition uses at most \(O\bigl(m(N+m)\bigr)\) paths. Its rational subtractions also have polynomial bit complexity. To see the latter explicitly, put the returned arc flows over the common denominator obtained by multiplying their denominators. This denominator has polynomial bit length; all subsequent path weights and residual flows retain that common denominator.
Performing the construction for all types gives the running-time bound
\(\tau\,O(L+\log(N+1))\cdot\operatorname{poly}\bigl(m(N+m),\,L+\log(N+m+1)\bigr),\)
which is polynomial in \(m,\tau,L,N\).
There are at most \(O\bigl(\tau m(N+m)\bigr)\) output entries before merging repeated bundles. Multiplication of each path probability by \(\mu_t\) preserves polynomial encoding length.
For each type, the algorithm constructs a finite rational lottery with expected quantities at most \(q\) and supported utilities at least \(\sigma_t(q)/2\). Weighting these lotteries by the type masses yields exactly the required allocation.
Thus the precise distribution-over-types problem in the question admits a polynomial-time algorithm.
⟨structured verdict parsed — rendered above⟩
The claimed polynomial-time algorithm is correct. The proof resolves the stated distribution-over-types problem, including rational output and polynomial bit complexity. I found no major or minor issues requiring repair.
The reduction is valid. If each type’s lottery has expected consumption at most \(q_j\), multiplying its probabilities by \(\mu_t\) gives total consumption at most \(\sum_t\mu_tq_j=q_j\). The masses assigned to type \(t\) sum to \(\mu_t\), and positive masses inherit the lottery’s utility guarantee.
This uses precisely the supplied hypotheses \(\mu_t>0\) and \(\sum_t\mu_t=1\). There is no additional compatibility condition between the lotteries.
Truncation at \(K_j\) preserves utility because every later marginal is zero, and it weakly decreases every consumed quantity. Consequently, pushing a distribution forward under truncation preserves its threshold guarantee and resource feasibility. This applies to arbitrary distributions in the benchmark definition, not merely finitely supported ones.
After truncation, the bundle set is finite. Every probability distribution on it has a nonempty finite support, so its minimum supported utility exists and belongs to \(\mathcal V\). Every feasible threshold is bounded above by such a feasible minimum. Conversely, each feasible minimum is a feasible threshold. Thus the maximum over feasible values in \(\mathcal V\) indeed equals the original supremum and is attained.
The empty bundle establishes feasibility at zero. Nonnegative marginals establish \(\sigma(q)\leq U\). When \(U>0\), the smallest positive listed marginal \(\ell\) exists, and every positive bundle utility is at least \(\ell\). Therefore the stated implication \(\sigma(q)>0\Rightarrow\ell\leq\sigma(q)\leq U\) is valid.
Both lemmas hold with the stated constants.
For Lemma 1, a capped score immediately supplies the required total \(H\). Otherwise the scores equal their uncapped floors, and the floor inequality gives
\(\sum_j w_j(b_j)\geq u(b)/\delta-m\geq4m-m=3m=H\).
For Lemma 2, capping does not invalidate \(w_j(k)\leq U_j(k)/\delta\). Hence acceptance implies \(u(b)\geq\delta H=3a/4\).
These arguments apply to every positive rational candidate \(a\), including candidates larger than the benchmark. No unstated restriction on \(a\) is needed.
The graph correctly represents accepted bundles. Each source-to-sink path selects one quantity for each good, and repeated saturation of the accumulated score produces exactly \(\min\{H,\sum_jw_j(b_j)\}\). Maintaining separate arcs for separate quantities is necessary and is explicitly specified.
The lottery-to-flow construction preserves expected consumption. Conversely, the graph is acyclic, and conservation prevents positive flow from terminating at a vertex other than the sink. Thus a feasible unit flow decomposes into source-to-sink paths.
The described subtraction procedure is valid: each subtraction preserves nonnegativity and conservation, eliminates at least one positive arc, and produces path weights summing to one. The resource constraints therefore give exactly the required expected-quantity bounds.
The vertex and arc counts are correct: respectively \(O(m^2)\) and \(O(m(N+m))\). The conservation constraints, source/sink requirements, resource constraints, and variable nonnegativity give an explicitly represented rational LP of polynomial size.
When the benchmark is positive, \(a_0=\ell\leq\sigma(q)\), so at least one tested LP is feasible.
The largest grid threshold \(a_*\leq\sigma(q)\) satisfies \(\sigma(q)<(3/2)a_*\). This remains valid at the upper endpoint of the tested grid: if the next grid threshold exceeds \(U\), it also exceeds \(\sigma(q)\).
Since the LP for \(a_*\) is feasible, the largest feasible tested threshold \(a\) satisfies \(a\geq a_*\). Every bundle extracted from its flow consequently has utility at least \(3a/4\geq3a_*/4>\sigma(q)/2\).
The algorithm does not require feasibility to be monotone across candidates; testing every candidate and selecting the largest feasible one is sufficient.
The zero-benchmark case is also handled correctly. Any feasible positive candidate would provide a lottery guaranteeing \(3a/4>0\), contradicting \(\sigma(q)=0\). Thus the empty-bundle output is appropriate.
Under the explicitly stated binary numerator-and-denominator representation, each positive marginal lies between \(2^{-L}\) and \(2^L\). Therefore \(U/\ell\leq N2^{2L}\), giving \(O(L+\log(N+1))\) candidates. Multiplication by the relevant powers of three and two preserves the claimed polynomial encoding length.
Prefix sums, rational comparisons, floor operations, and capped scores can all be computed exactly with polynomially many bits. The LP coefficients consist of rational supplies and bounded integer incidence and quantity coefficients, so their stated bit-length bound is valid.
The invoked rational linear-programming theorem is stated sufficiently for this application: exact feasibility of an explicitly represented rational LP can be decided in polynomial time, and a feasible rational point of polynomial encoding length can be returned. Its hypotheses are satisfied here.
The common-denominator argument correctly bounds the encoding length during flow decomposition: multiplying polynomially many denominators of polynomial bit length produces a denominator of polynomial bit length. Subsequent subtractions retain that denominator.
Finally, decomposition produces polynomially many paths, multiplication by the input masses preserves polynomial encoding length, and zero entries can be omitted. The stated running time and output-size bounds meet the task’s requirements.
No additional clarification is needed to make the argument verifiable.
⟨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.