Answer: Polynomial-time solvable; every valid instance is feasible, with an explicit rational realizable profile of welfare \(1\).
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor Utilitarian welfare and MMS fairness, the price of fairness is at least Ω(√n) and at most O(n).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(N\), a template of \(q\) ordered indivisible items, rational type masses \(\mu_t\), and type weights \(w_{t,j}\ge 0\) with \(\sum_{j=1}^{q}w_{t,j}=1\), form a path of \(N\) repeated templates where each copy of item \(j\) is worth \(w_{t,j}/N\) to type \(t\). Find a realizable mass profile \(x_{t,I}\) of contiguous integral intervals, with type mass \(\mu_t\), such that every assigned interval is MMS-fair for its type and \(\sum_{t,I}x_{t,I}N v_t(I)\ge 1/4\).
A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Input also consists of positive integers \(N,q\), with \(N\) encoded in unary, and binary-rational weights \(w_{t,j}\geq0\) satisfying \(\sum_{j=1}^q w_{t,j}=1\). The path \(E\) consists of \(N\) repetitions of the ordered template, so \(m=Nq\). Values are additive, and each copy of template item \(j\) has type-\(t\) value \(w_{t,j}/N\).
Let \(\mathcal I\) contain all intervals of whole items and the empty bundle. Let \(\Pi_N(E)\) consist of partitions covering every item exactly once with \(N\) contiguous bundles, allowing empty bundles. Define \(M_t=\max_{(B_1,\ldots,B_N)\in\Pi_N(E)}\min_k v_t(B_k)\).
A rational profile \(x_{t,I}\geq0\) is realizable if it is a convex combination of normalized count profiles of type-labelled partitions in \(\Pi_N(E)\): each occurrence of a bundle \(I\) labelled \(t\) contributes \(1/N\) to its profile coordinate. Type labels may repeat; require \(\sum_I x_{t,I}=\mu_t\). Type counts need only match these masses in the mixture.
The required profile satisfies \(x_{t,I}>0\Rightarrow v_t(I)\geq M_t\) and \(\sum_{t,I}x_{t,I}N v_t(I)\geq1/4\). Let \(L\) be the total input bit length.
Is finding such a realizable profile, or determining that none exists, solvable in time polynomial in \(m,\tau,L\), or is its feasibility problem NP-hard?
For finite societies with normalized additive nonnegative values, a polynomial-time algorithm finds a contiguous MMS allocation with utilitarian welfare at least \(1/4\); the corresponding price of fairness lies between \(\Omega(\sqrt N)\) and \(O(N)\). [Source](https://ira.lib.polyu.edu.hk/bitstream/10397/109708/1/FAIA-372-FAIA230522.pdf)
No result settling this exact distribution-over-types problem was located in the literature search.
The problem is polynomial-time solvable, and every valid instance in the question is feasible. The repeated-template assumption gives a common MMS partition for all types. A rational mixture of monochromatically labelled copies of this partition matches the prescribed masses exactly and has welfare \(1\).
I first prove this construction, then give a polynomial-size linear program addressing the more general distribution-over-types question.
For \(r\in\{1,\ldots,N\}\), let \(C_r\) be the interval consisting of the \(r\)-th complete template copy. For every type \(t\),
\[ v_t(C_r)=\sum_{j=1}^{q}\frac{w_{t,j}}{N}=\frac1N. \]
Consequently, the partition \((C_1,\ldots,C_N)\) proves \(M_t\geq 1/N\).
Conversely, for any partition \((B_1,\ldots,B_N)\in\Pi_N(E)\), additivity, exact coverage, and normalization imply
\[ \sum_{k=1}^{N}v_t(B_k)=v_t(E)=1. \]
The minimum of these \(N\) values cannot exceed their average \(1/N\). Taking the maximum over partitions therefore gives \(M_t\leq 1/N\).
Thus \(M_t=1/N\) for every type \(t\).
Define \(x_{t,C_r}=\mu_t/N\) for every type \(t\) and copy \(r\), and set all other coordinates to zero.
For each type \(t\), consider the labelled partition \(P_t\) that uses the bundles \(C_1,\ldots,C_N\) and labels every bundle with \(t\). Its normalized count profile has coordinate \(1/N\) at each \((t,C_r)\), and zero elsewhere.
Taking \(P_t\) with probability \(\mu_t\) produces exactly \(x\). These probabilities are positive rationals summing to one, so this is a valid convex combination proving realizability. Each component partition is permitted to use a single type because the task requires masses to match only in the mixture.
The mass constraints hold because
\[ \sum_{I\in\mathcal I}x_{t,I} =\sum_{r=1}^{N}\frac{\mu_t}{N} =\mu_t. \]
Every positive coordinate is MMS-admissible: \(v_t(C_r)=M_t=1/N\). Finally,
\[ \sum_{t,I}x_{t,I}N v_t(I) =\sum_{t=1}^{\tau}\sum_{r=1}^{N} \frac{\mu_t}{N}\,N\,\frac1N =\sum_{t=1}^{\tau}\mu_t =1. \]
Hence the welfare requirement is satisfied.
This construction has \(\tau N\) nonzero coordinates. Dividing each input mass by \(N\) increases its rational encoding length by at most \(O(\log N)\). Since \(N\leq m\), constructing the profile and its explicit mixture takes time polynomial in \(m,\tau,L\). A dense output containing every interval coordinate also has polynomial size.
The common partition above settles the stated task. To address the substantive distribution-over-types issue, the following formulation works even for an arbitrary path with rational nonnegative additive values.
Assume first that the thresholds \(M_t\) are known. Number the items \(1,\ldots,m\), and write \(I(i,j)=\{i+1,\ldots,j\}\) when \(i<j\), and \(I(i,i)=\varnothing\).
Construct a directed graph with vertices \((k,i)\), where \(0\leq k\leq N\) and \(0\leq i\leq m\). Whenever \(k<N\), \(i\leq j\), and \(v_t(I(i,j))\geq M_t\), include a type-labelled arc
\[ (k,i)\longrightarrow(k+1,j). \]
A path from \(s=(0,0)\) to \(z=(N,m)\) specifies exactly \(N\) admissible labelled bundles covering the items in order. Arcs with \(i=j\) represent empty bundles. Conversely, any admissible labelled partition can be represented by such a path: order its nonempty bundles spatially and insert its empty bundles into that order. This preserves its normalized count profile.
Introduce a nonnegative variable \(f_e\) for each arc and impose unit-flow conservation:
\[ \sum_{e\text{ leaving }u}f_e-\sum_{e\text{ entering }u}f_e = \begin{cases} 1,&u=s,\\ -1,&u=z,\\ 0,&\text{otherwise}. \end{cases} \]
Impose the additional constraints
\[ \sum_{e\text{ labelled }t}f_e=N\mu_t \quad\text{for every }t, \qquad \sum_e f_e\,v_{t(e)}(I(e))\geq\frac14. \]
Here \(t(e)\) and \(I(e)\) denote the type and interval associated with arc \(e\).
A mixture of admissible labelled partitions yields a feasible unit flow by taking the corresponding mixture of path incidence vectors. The type and welfare constraints are precisely its required expected counts and welfare.
Conversely, the graph is acyclic because every arc increases \(k\). Any nonnegative unit flow therefore decomposes into \(s\)-to-\(z\) paths with nonnegative coefficients summing to one. Explicitly, follow positive-flow arcs from \(s\), subtract the minimum flow on the resulting path, and repeat. Conservation prevents a positive-flow path from terminating anywhere except \(z\), and each subtraction eliminates at least one positive arc. Any residual flow after the source flow is exhausted must vanish: a nonzero residual circulation cannot exist in an acyclic graph.
For a rational feasible flow, this procedure produces rational mixture coefficients. Define
\[ x_{t,I}=\frac1N \sum_{\substack{e:\,t(e)=t\\I(e)=I}}f_e. \]
The path decomposition proves realizability. The type constraints give the required masses, every used arc satisfies its MMS threshold, and
\[ \sum_{t,I}x_{t,I}N v_t(I) =\sum_e f_e\,v_{t(e)}(I(e)) \geq\frac14. \]
Thus the linear program is exactly equivalent to profile feasibility.
There are at most \((N+1)(m+1)\) vertices and \(N\tau(m+1)(m+2)/2\) arcs.
For completeness, arbitrary-path MMS thresholds are computable by dynamic programming. Let \(D_t(k,j)\) be the best minimum bundle value among partitions of the first \(j\) items into \(k\) contiguous bundles, allowing empties. Initialize \(D_t(0,0)=+\infty\) and \(D_t(0,j)=-\infty\) for \(j>0\). Then
\[ D_t(k,j)= \max_{0\leq i\leq j} \min\{D_t(k-1,i),v_t(I(i,j))\}. \]
The recurrence follows by choosing the starting boundary \(i\) of the final bundle. Every such choice combines a prefix partition with that final bundle, and every partition has such a boundary. Hence \(M_t=D_t(N,m)\). This requires \(O(\tau Nm^2)\) rational comparisons after computing prefix values.
Interval values have polynomial encoding length, and the recurrence selects among those values. The resulting linear program therefore has polynomially many variables and constraints with polynomial coefficient encoding length. The standard polynomial-time theorem for rational linear programming decides feasibility and returns a rational feasible point when one exists. The aggregation above then produces the requested profile.
The cited [Sun–Li paper](https://ira.lib.polyu.edu.hk/bitstream/10397/109708/1/FAIA-372-FAIA230522.pdf) establishes a polynomial-time contiguous MMS allocation algorithm with utilitarian welfare at least \(1/4\) for finite societies. Its application is unnecessary here: the repeated template directly gives welfare \(1\), while the flow formulation handles exact type masses in a mixture without expanding rational masses into a large finite population.
⟨structured verdict parsed — rendered above⟩
The output correctly resolves the stated task. Every valid instance is feasible, and the explicit profile is computable in polynomial time. I found no mathematical errors or gaps requiring clarification. The supplementary flow formulation is also sound under the stated encoding assumptions.
The complete template copies \(C_1,\ldots,C_N\) are nonempty contiguous intervals, disjoint, and cover all \(m=Nq\) items. Thus they form a permitted partition.
For every type \(t\) and copy \(r\), normalization gives
\[
v_t(C_r)=\sum_{j=1}^{q}\frac{w_{t,j}}{N}=\frac1N.
\]
This establishes \(M_t\geq1/N\).
For any permitted partition, exact coverage and additivity give
\[
\sum_{k=1}^{N}v_t(B_k)=v_t(E)=1.
\]
Its minimum bundle value is at most its average, \(1/N\), including when some bundles are empty. Therefore \(M_t\leq1/N\).
Finding: The equality \(M_t=1/N\) is fully established for every supported type.
The construction assigns
\[
x_{t,C_r}=\frac{\mu_t}{N}
\]
and zero to all other coordinates.
Each \(P_t\) is a valid labelled partition: its underlying bundles are the complete template copies, and repeated type labels are explicitly permitted. Its normalized count profile has value \(1/N\) at each coordinate \((t,C_r)\).
The proposed mixture coefficients are exactly the positive rational masses \(\mu_t\), which sum to one. Consequently, the mixture produces exactly the claimed profile.
The mass calculation is correct:
\[
\sum_I x_{t,I}=\sum_{r=1}^{N}\frac{\mu_t}{N}=\mu_t.
\]
Finding: Realizability and exact type masses are proved. No integer population expansion or per-partition matching of type masses is required by the task.
Every positive coordinate corresponds to a complete copy, whose value is exactly \(M_t\). Thus the support condition holds.
The welfare calculation correctly retains the normalization factor \(N\):
\[
\sum_{t,I}x_{t,I}N v_t(I)
=\sum_{t=1}^{\tau}\sum_{r=1}^{N}
\frac{\mu_t}{N}\,N\,\frac1N
=\sum_{t=1}^{\tau}\mu_t
=1.
\]
This exceeds the required \(1/4\).
Finding: Both required profile inequalities are verified.
There are \(\tau N\) nonzero coordinates. Each interval can be specified by its two endpoints, requiring \(O(\log m)\) bits.
Dividing an input rational mass by \(N\) increases its encoding length by at most \(O(\log N)\); reduction to lowest terms cannot increase this bound. Since \(q\geq1\), \(N\leq m\), so the construction takes polynomial time in \(m,\tau,L\).
A dense representation also has polynomial size because there are
\[
\frac{m(m+1)}2+1
\]
interval coordinates per type, including the empty bundle.
The cases \(N=1\), \(q=1\), a single supported type, and zero individual item weights cause no failure. Each complete copy still has value \(1/N\).
Finding: The explicit construction alone proves the claimed polynomial-time result.
The graph representation correctly models ordered partitions into exactly \(N\) bundles:
The graph is a directed multigraph when different types label arcs with identical endpoints; the use of type-labelled arcs and separate variables makes this unambiguous.
The admissibility restriction is compatible with the original profile definition. Nonnegative convex combinations cannot give zero weight to an inadmissible coordinate if a positively weighted component uses it.
The flow constraints correctly impose expected type counts \(N\mu_t\). The welfare constraint has the correct scaling because aggregation divides arc counts by \(N\), while the profile objective multiplies them by \(N\).
The decomposition argument is valid. Acyclicity excludes residual circulations, conservation prevents extraction from getting stuck at an intermediate vertex, and each subtraction removes at least one positive arc. Rational flows yield rational mixture coefficients.
Finding: The claimed equivalence between the LP and admissible realizable profiles is correct.
The dynamic program uses valid base cases: zero bundles cover only the empty prefix, and \(+\infty\) correctly serves as the initial minimum.
For \(k\geq1\), every ordered partition of a prefix has a final boundary \(i\), including \(i=j\) when its final bundle is empty. Thus the stated recurrence correctly handles all permitted partitions.
The \(O(\tau Nm^2)\) operation count is valid. Prefix sums and interval values have polynomial rational encoding length, and finite dynamic-programming values are selected from interval values.
The vertex and arc bounds are correct. The LP has polynomially many constraints and rational coefficients of polynomial encoding length. The stated rational linear-programming theorem applies: it decides feasibility and can return a rational feasible point in polynomial time.
Finding: The supplementary algorithm is justified with \(N\) unary, as required by the task. It does not establish polynomial dependence on \(\log N\) for a different encoding, nor does the stated task require that.
The attribution to Sun and Li is supported by their paper: Algorithm 3 and its accompanying results give a contiguous MMS allocation with utilitarian welfare at least \(1/4\), and the paper states polynomial-time guarantees. [Sun–Li paper](https://ira.lib.polyu.edu.hk/bitstream/10397/109708/1/FAIA-372-FAIA230522.pdf)
That result is not used in the construction or the LP argument. The proof therefore does not depend on transferring a finite-society theorem to rational type masses.
Actionable feedback: No repair or additional clarification is needed. Sections 1–2 and the output-size argument already settle the exact task; the general LP is supplementary.
⟨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.