Answer: Polynomial-time solvable in \(m,\tau,L\); the maximizing selections are independent of the positive type masses.
Proposition 3.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists an algorithm that computes a leximin allocation in time polynomial in the input size. We now come to our main result of this section, which establishes the truthfulness of the leximin solution.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Input a rational quota \(\alpha\in(0,1)\), a finite type set \(T\), rational masses \(\mu_t\ge0\) with \(\sum_{t\in T}\mu_t=1\), and rational-endpoint desired pieces \(W_t\subseteq[0,1]\). Choose \(A\subseteq[0,1]\) with \(\ell(A)\le\alpha\) maximizing the leximin ordering of the multiset containing \(n\mu_t\) copies of \(u_t(A)=\ell(A\cap W_t)\), for any common denominator \(n\) of \(\mu\); output \(A\), equivalently its selected lengths on breakpoint intervals, with blocking \(A_t=A\cap W_t\).
A society is given by its support: a list \(T\) of \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a desired piece \(W_t\subseteq[0,1]\), a finite union of closed intervals with rational endpoints and \(\ell(W_t)>0\); \(\ell\) denotes length. Input also includes a binary-rational quota \(\alpha\in(0,1)\).
A feasible selection \(A\) is a finite union of intervals with \(\ell(A)\le\alpha\). Blocking assigns \(A_t=A\cap W_t\), giving the unnormalized utility \(u_t(A)=\ell(A\cap W_t)\).
The objective is leximin on the multiset containing \(n\mu_t\) copies of \(u_t(A)\) for each type, where \(n\) is any common denominator of the masses. Output any maximizing selection; arbitrary tie-breaking is allowed.
Let \(m\) be the number of intervals between consecutive distinct desired-piece endpoints, including \(0\) and \(1\), and let \(L\) be the total binary input length. Represent the output by rational selected lengths on these intervals, and state running times in \(m,\tau,L\).
Is computing this mass-based leximin selection solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For an explicitly listed finite society, a leximin selection is computable in polynomial time in the input size.
In that finite-agent setting, all leximin selections give each agent the same utility.
Computing the mass-based leximin selection is polynomial-time solvable in \(m,\tau,L\).
More strongly, the maximizing selections are independent of the positive masses \(\mu_t\). An exact algorithm uses at most \(\tau\) stages and \(O(\tau^2)\) rational linear programs, each with at most \(m+1\) variables and \(O(m+\tau)\) constraints. We prove both correctness and polynomial bit complexity.
Let the distinct desired-piece endpoints, together with \(0,1\), be
\(0=e_0<e_1<\cdots<e_m=1\),
and put \(d_j=e_j-e_{j-1}\). On every open interval \((e_{j-1},e_j)\), membership in each desired piece is constant. Define
\(b_{tj}=1\) if \((e_{j-1},e_j)\subseteq W_t\), and \(b_{tj}=0\) otherwise.
For a selection \(A\), let \(x_j=\ell(A\cap(e_{j-1},e_j))\). Its feasibility and utilities are exactly
\(x\in P:=\{x\in\mathbb R^m:0\le x_j\le d_j,\ \sum_{j=1}^m x_j\le\alpha\}\),
\(u_t(x)=\sum_{j=1}^m b_{tj}x_j\).
Conversely, every \(x\in P\) is realizable by selecting a segment of length \(x_j\) within each corresponding interval. Endpoint inclusion does not affect length or utility.
Thus the feasible utility set is the linear image of the nonempty compact convex polytope \(P\). This convexity will allow simultaneous improvement of all types whose utilities are not forced to remain fixed.
Initialize \(P_0=P\) and \(R_0=T\). Here \(R_r\) denotes the types not yet fixed.
At stage \(r\), assuming \(R_{r-1}\ne\varnothing\), compute
\(\lambda_r=\max_{x\in P_{r-1}}\min_{t\in R_{r-1}}u_t(x)\).
This is the linear program maximizing \(z\), subject to
\(x\in P_{r-1},\qquad 0\le z\le1,\qquad u_t(x)\ge z\quad(t\in R_{r-1})\).
Define the nonempty compact convex polytope
\(P_r=\{x\in P_{r-1}:u_t(x)\ge\lambda_r\text{ for every }t\in R_{r-1}\}\).
Next identify the types forced to attain this threshold:
\(H_r=\{t\in R_{r-1}:u_t(x)=\lambda_r\text{ for every }x\in P_r\}\).
For each remaining type, one LP determines membership in \(H_r\):
\(t\in H_r\quad\Longleftrightarrow\quad\max_{x\in P_r}u_t(x)=\lambda_r\).
Finally set \(R_r=R_{r-1}\setminus H_r\).
Suppose \(H_r=\varnothing\). For each \(t\in R_{r-1}\), there would then exist \(x^{(t)}\in P_r\) with \(u_t(x^{(t)})>\lambda_r\).
Their average \(\bar x\) belongs to \(P_r\), by convexity. For any \(s\in R_{r-1}\), every averaged utility is at least \(\lambda_r\), and the contribution from \(x^{(s)}\) is strictly greater. Linearity therefore gives \(u_s(\bar x)>\lambda_r\).
Since \(R_{r-1}\) is finite, this implies
\(\min_{s\in R_{r-1}}u_s(\bar x)>\lambda_r\),
contradicting the definition of \(\lambda_r\). Hence \(H_r\ne\varnothing\).
If \(R_r\ne\varnothing\), each \(t\in R_r\) has a witness \(x^{(t)}\in P_r\) with \(u_t(x^{(t)})>\lambda_r\). Averaging these witnesses as above produces a point of \(P_r\) at which every type in \(R_r\) has utility strictly greater than \(\lambda_r\). Thus
\(\lambda_{r+1}>\lambda_r\).
Consequently the algorithm terminates after \(k\le\tau\) stages. The sets \(H_1,\ldots,H_k\) partition \(T\), and every \(x\in P_k\) satisfies
\(u_t(x)=\lambda_r\quad\text{whenever }t\in H_r\).
We first record an elementary fact about sorted multisets.
Let \(B,C\) be finite multisets of equal cardinality, sorted increasingly. For any finite multiset \(D\), their lexicographic comparison is unchanged when \(D\) is added to both.
Indeed, if \(B\ne C\), let \(v\) be the smallest value having different multiplicities in \(B\) and \(C\). All smaller-value multiplicities agree. At the first differing position, the multiset containing fewer copies of \(v\) has the larger entry, so its sorted vector is lexicographically greater. Adding \(D\) changes both multiplicities equally at every value and preserves this comparison.
Fix any common denominator \(n\) of the masses and write \(c_t=n\mu_t\). Each \(c_t\) is a positive integer.
Choose \(x^\star\in P_k\), and consider any \(y\in P\).
If \(y\in P_k\), then \(u_t(y)=u_t(x^\star)\) for every type, so their repeated utility multisets agree.
Otherwise, let \(r\) be the first stage for which \(y\notin P_r\). Then \(y\in P_{r-1}\). Every previously fixed type has the same utility at \(y\) and \(x^\star\):
\(u_t(y)=u_t(x^\star)=\lambda_i\quad(t\in H_i,\ i<r)\).
Remove all copies belonging to these types from both multisets. Lemma 3 permits this cancellation.
The remaining types are exactly \(R_{r-1}\). Because \(y\notin P_r\),
\(\min_{t\in R_{r-1}}u_t(y)<\lambda_r\).
Because \(x^\star\in P_r\),
\(\min_{t\in R_{r-1}}u_t(x^\star)\ge\lambda_r\).
Every remaining type has positive multiplicity. Therefore the first entry of the remaining sorted multiset for \(x^\star\) is strictly greater than that for \(y\). Lemma 3 gives the same strict comparison for the full multisets.
Thus every point of \(P_k\) is leximin maximizing, and every point outside \(P_k\) is strictly worse. This proves the theorem.
In particular, all maximizing selections give each type the same utility. Neither these utilities nor the set of maximizing selections depends on the positive masses. The denominator \(n\) is used only in the proof and is never expanded by the algorithm.
A polynomial bound on the number of LPs alone is insufficient: we must also bound the encodings of the intermediate thresholds. We do this without recursively multiplying bit-length estimates.
Let \(N=m+\tau+1\). Consider the groups \(H_1,\ldots,H_k\) produced by the algorithm and introduce the auxiliary polytope
\(Q=\{(x,\beta_1,\ldots,\beta_k):x\in P,\ 0\le\beta_1\le\cdots\le\beta_k\le1,\ u_t(x)=\beta_r\text{ for }t\in H_r\}\).
Its dimension is at most \(m+k<N\), and every constraint coefficient belongs to \(\{-1,0,1\}\). Its right-hand sides are among \(0,1,\alpha,d_1,\ldots,d_m\).
Every \(x^\star\in P_k\) makes \((x^\star,\lambda_1,\ldots,\lambda_k)\) feasible in \(Q\).
We show that the lexicographic maximum of \((\beta_1,\ldots,\beta_k)\) over \(Q\) is precisely \((\lambda_1,\ldots,\lambda_k)\).
Suppose \((x,\beta)\in Q\) and \(\beta_i=\lambda_i\) for all \(i<r\). Every type in an earlier group \(H_i\) has utility \(\lambda_i\). Every type in a group \(H_j\) with \(j\ge r\) has utility \(\beta_j\), which is at least every earlier threshold. These observations imply \(x\in P_{r-1}\).
Furthermore, because \(H_r\ne\varnothing\) and the \(\beta_j\) are ordered,
\(\min_{t\in R_{r-1}}u_t(x)=\beta_r\).
Hence \(\beta_r\le\lambda_r\). The point arising from \(x^\star\) attains equality simultaneously for every coordinate, proving the claimed lexicographic maximum.
Sequentially maximizing the linear coordinates \(\beta_1,\ldots,\beta_k\) defines a nonempty face of \(Q\). A nonempty face of a compact polytope contains a vertex of that polytope. Thus some vertex of \(Q\) has the entire threshold vector as its \(\beta\)-coordinates.
Let \(D\) be the product of the denominators of all input endpoints and of \(\alpha\). Its binary length is \(O(L)\), and \(Dd_j,D\alpha\) are integers.
Scale every coordinate of \(Q\) by \(D\). The resulting polytope has constraint coefficients in \(\{-1,0,1\}\), integer right-hand sides of magnitude at most \(D\), and fewer than \(N\) variables.
At a vertex, a full-rank set of active constraints determines the coordinates. Hadamard’s inequality bounds the corresponding determinant by \(N^{N/2}\). Cramer’s rule then gives every coordinate a rational encoding of length
\(B=O\bigl(L+N\log(N+1)\bigr)\).
For completeness, the Cramer numerator is bounded by the determinant bound times \(D\), since every scaled coordinate lies in \([0,D]\). Dividing the coordinates back by \(D\) adds only \(O(L)\) bits.
By Lemma 4, every intermediate threshold \(\lambda_r\) satisfies this same bound.
The stage polytopes can be stored compactly as
\(P_r=\{x\in P:u_t(x)=\lambda_i\text{ for }t\in H_i,\ i\le r;\ u_t(x)\ge\lambda_r\text{ for }t\in R_r\}\).
This equals their nested definition: previously fixed utilities remain fixed, and the increasing thresholds make the newest lower bounds imply all earlier ones.
Each stage uses one threshold LP and at most \(|R_{r-1}|\) testing LPs. Since at least one type is removed per stage, the total is at most
\(\tau+\tau(\tau+1)/2\),
followed by one feasibility LP to obtain a rational \(x\in P_k\).
Each LP has at most \(m+1\) variables and \(O(m+\tau)\) constraints. A dense encoding has length
\(S=O(N^2+NB)\), where \(B=O(L+N\log(N+1))\).
Rational linear programming admits exact polynomial-time optimization and rational output; this is the standard polynomial-time LP theorem, applicable here because every LP is explicitly represented, rational, nonempty, and bounded. See the [MIT lecture on the ellipsoid method](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
Writing \(\operatorname{LP}(v,c,s)\) for a polynomial bit-time bound for exact LP with these dimensions and encoding length, the running time is
\(O\bigl(\tau^2\operatorname{LP}(m+1,O(m+\tau),S)\bigr)+\operatorname{poly}(m,\tau,L)\).
This is polynomial in \(m,\tau,L\). The final rational vector \((x_1,\ldots,x_m)\) has polynomial encoding length and is exactly the requested representation by selected interval lengths. Its realization as a finite union of segments is a maximizing selection.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes an exact polynomial-time algorithm in \(m,\tau,L\), including polynomial bounds on intermediate rational encodings. No major or minor mathematical issues were found.
The endpoint partition is valid: membership in each \(W_t\) is constant on every open elementary interval. Endpoints have zero length, so ignoring them preserves both feasibility and utilities.
The constraints defining \(P\) exactly describe the achievable selected lengths. Conversely, the proposed segment construction realizes every \(x\in P\) as a finite union of intervals. Thus the continuous selection problem and the stated linear utility problem are equivalent.
The polytope \(P\) is nonempty, compact, and convex. All utilities are linear and lie in \([0,\alpha]\subseteq[0,1]\).
At every stage, maximizing the minimum remaining utility is equivalent to the LP with auxiliary variable \(z\). The restriction \(0\le z\le1\) does not change the optimum because of the utility bounds.
Compactness guarantees attainment of \(\lambda_r\), making \(P_r\) nonempty. Its defining linear inequalities preserve compactness and convexity.
On \(P_r\), every remaining utility is at least \(\lambda_r\). Consequently, the testing condition
\[
\max_{x\in P_r}u_t(x)=\lambda_r
\]
is exactly equivalent to that utility being identically \(\lambda_r\) throughout \(P_r\). These maxima are attained, so the membership tests are valid.
The averaging argument is correct. Under the contrary assumption, each type has a witness where its utility exceeds \(\lambda_r\), while every witness satisfies all remaining lower bounds.
In the average, each remaining type therefore receives utility strictly above \(\lambda_r\). Since there are finitely many remaining types, their minimum also strictly exceeds \(\lambda_r\), contradicting optimality. This establishes \(H_r\ne\varnothing\).
For each type outside \(H_r\), the definition supplies a witness with utility strictly greater than \(\lambda_r\). Averaging these witnesses establishes the claimed strict increase whenever another stage is needed.
Removing at least one type per stage gives termination within \(\tau\) stages. The groups partition \(T\). Utilities fixed on \(P_r\) remain fixed on its subsequent subsets, validating the asserted terminal utility vector.
The lemma is correct for finite multisets of equal cardinality. At the smallest value whose multiplicities differ, the multiset with fewer copies has the larger entry at the first differing sorted position.
Adding a common multiset preserves all multiplicity differences and hence preserves the comparison. The case of identical multisets also remains identical. Its use for cancellation in the theorem is justified.
For every allowed common denominator, each multiplicity \(c_t=n\mu_t\) is a positive integer. No expansion of these multiplicities is required by the algorithm.
If \(y\notin P_k\), the first failed stage exists because the polytopes are nested and \(y\in P_0\). Membership in \(P_{r-1}\) ensures that all previously fixed utilities coincide with those of \(x^\star\).
After cancelling those common copies, the remaining multisets have equal cardinality. Their minimum entries are precisely the minimum utilities over \(R_{r-1}\), because every remaining type has positive multiplicity. The strict minimum comparison therefore proves strict lexicographic dominance.
If \(y\in P_k\), all type utilities agree with those of \(x^\star\). Thus the theorem correctly characterizes all maximizing selections, establishes utility uniqueness by type, and establishes independence from positive masses.
The polytope \(Q\) is nonempty and compact, and its coefficients and right-hand sides have the claimed form.
In the sequential comparison, agreement of earlier \(\beta\)-coordinates with their thresholds, together with their ordering, ensures satisfaction of every earlier stage’s lower bounds. Hence \(x\in P_{r-1}\), as asserted.
Since \(H_r\ne\varnothing\), the minimum remaining utility is exactly \(\beta_r\), giving \(\beta_r\le\lambda_r\). The terminal point attains all threshold coordinates simultaneously.
Sequential maximization produces a nonempty face of \(Q\); such a face contains a vertex of \(Q\). This remains valid if \(Q\) has lower affine dimension.
The product \(D\) has binary length \(O(L)\) and clears the denominators of every stated right-hand side. Scaling coordinates preserves the coefficient matrix and gives integral right-hand sides of magnitude at most \(D\).
At a vertex, a full-rank active subsystem determines all coordinates. Hadamard’s determinant bound applies to its matrix with entries in \(\{-1,0,1\}\). The claimed numerator bound follows from Cramer’s rule and the coordinate bounds \([0,D]\).
Scaling back therefore gives the stated encoding bound
\[
B=O\bigl(L+N\log(N+1)\bigr).
\]
Lemma 4 applies this bound to every threshold simultaneously. The reasoning does not assume that those thresholds already have short encodings, so there is no circularity.
The compact description of \(P_r\) is equivalent to the nested definition: fixed equalities retain all previous fixed utilities, and the latest threshold dominates previous lower bounds.
The LP count, variable count, constraint count, and dense encoding bound are correct. Exact rational linear programming supplies polynomial bit-time optimization and polynomial-size rational output for these explicitly represented, nonempty, bounded rational LPs. The cited [MIT lecture](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf) supports polynomial-time LP feasibility and optimization, including polynomial precision bounds.
The resulting rational vector is exactly the requested output representation, and its stated realization is feasible and maximizing.
Repair feedback: None required. The output resolves the assigned complexity question and substantiates its stronger mass-independence claim.
⟨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.