Answer: polynomial-time solvable
Theorem 7.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of computing leximin allocations is NP-hard even when agents have $\{-p, q\}\ADD$ valuations for any co-prime positive integers $p$ and $q$ such that $p \ge 3$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite complete valuation types \(T\), item classes \(O\), rational type masses \(\mu_t\), rational per-capita supplies \(\rho_o\), and additive valuations \(v_t(B)=\sum_{o\in B}a_{t,o}\) with \(a_{t,o}\in\{-p,q\}\), choose masses \(x_{t,B}\ge0\) of type-\(t\) agents receiving integral bundles \(B\subseteq O\), subject to \(\sum_Bx_{t,B}=\mu_t\) and \(\sum_{t,B:o\in B}x_{t,B}=\rho_o\). Compute an allocation maximizing continuum leximin: maximize the lowest attained utility level, then minimize the mass at that level, then maximize the next attained level, and so on over the finite set of attainable utilities.
A society is given by its support: the list of \(\tau\geq1\) valuation types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) item classes \(O\), with binary-rational per-capita supplies \(\rho_o\in[0,1]\). Common positive integers \(p,q\), supplied in binary, satisfy \(p\geq3\) and \(\gcd(p,q)=1\); each type explicitly specifies \(a_{t,o}\in\{-p,q\}\) for every class. Let \(L\) be the total input bit length.
An agent receives an integral bundle \(B\subseteq O\), possibly empty, containing at most one item of each class, with additive utility \(v_t(B)=\sum_{o\in B}a_{t,o}\).
An allocation consists of nonnegative bundle masses \(x_{t,B}\), represented by its nonzero entries, satisfying \(\sum_{B\subseteq O}x_{t,B}=\mu_t\) and \(\sum_{t,B:o\in B}x_{t,B}=\rho_o\); all supply must be allocated.
Write the distinct attainable utilities as \(u_1<\cdots<u_K\), and define \(h_j(x)=\sum_{t,B:v_t(B)=u_j}x_{t,B}\). Continuum leximin lexicographically minimizes \((h_1(x),\ldots,h_K(x))\); zero-mass levels are unoccupied, and allocations with identical histograms are tied.
Is computing an exact continuum leximin allocation solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite agents and indivisible items, computing a complete leximin allocation is NP-hard for every fixed coprime pair \(p,q>0\) with \(p\geq3\). [Source](https://arxiv.org/html/2307.12516#S7)
No complexity classification for this exact continuum problem was identified in the literature search.
Computing an exact continuum leximin allocation is polynomial-time solvable in \(m,\tau,L\). An optimal allocation can be returned with at most \(\tau(m+1)^3\) nonzero bundle masses, each having polynomial bit length.
The proof constructs a polynomial-size linear program that represents bundle distributions exactly, optimizes its histogram lexicographically, and reconstructs explicit integral bundles.
For every type \(t\), define
\(G_t=\{o\in O:a_{t,o}=q\}\) and \(C_t=\{o\in O:a_{t,o}=-p\}\).
These sets partition \(O\).
A bundle containing \(g\) classes from \(G_t\) and \(c\) classes from \(C_t\) has utility \(qg-pc\). Define the possible count pairs by
\(I_t=\{(g,c):0\leq g\leq |G_t|,\ 0\leq c\leq |C_t|,\ g,c\text{ integers}\}\).
Every pair in \(I_t\) is realized by some bundle. Thus the set of distinct attainable utilities is exactly
\(U=\bigcup_{t=1}^{\tau}\{qg-pc:(g,c)\in I_t\}\).
Because every pair satisfies \(g+c\leq m\), its cardinality satisfies \(K=|U|\leq(m+1)^2\). Enumerating these pairs, calculating their utilities, and sorting the distinct results takes polynomial time. Each utility has bit length polynomial in \(L+\log(m+1)\), even though \(p,q\) are supplied in binary.
For each \(t\) and \((g,c)\in I_t\), introduce:
Let \(P\) be the polytope defined by the following constraints:
\(z_{t,g,c}\geq0,\qquad 0\leq y_{t,g,c,o}\leq z_{t,g,c}\).
\(\sum_{(g,c)\in I_t}z_{t,g,c}=\mu_t\qquad\text{for every }t.\)
\(\sum_{o\in G_t}y_{t,g,c,o}=g z_{t,g,c},\qquad \sum_{o\in C_t}y_{t,g,c,o}=c z_{t,g,c}\qquad\text{for every }t,g,c.\)
\(\sum_{t=1}^{\tau}\sum_{(g,c)\in I_t}y_{t,g,c,o}=\rho_o \qquad\text{for every }o.\)
There are \(N=\sum_t|I_t|\leq\tau(m+1)^2\) count groups and \(n=N(m+1)\leq\tau(m+1)^3\) variables. The number of constraints is also polynomial. All matrix coefficients are integers of absolute value at most \(m\); the right-hand sides are input masses, input supplies, or zero.
Every allocation induces a point in \(P\), by setting
\(z_{t,g,c}=\sum_{B:\,|B\cap G_t|=g,\ |B\cap C_t|=c}x_{t,B}\)
and
\(y_{t,g,c,o}=\sum_{B:\,|B\cap G_t|=g,\ |B\cap C_t|=c,\ o\in B}x_{t,B}\).
The displayed constraints then follow directly from the allocation constraints and the fixed counts.
The essential converse is proved next.
Lemma. Let \(G,C\) partition \(O\), let \(g,c\) be nonnegative integers, and suppose rational numbers \(z>0\) and \(w_o\) satisfy
\(0\leq w_o\leq z,\qquad \sum_{o\in G}w_o=gz,\qquad \sum_{o\in C}w_o=cz.\)
Then one can construct at most \(m+1\) bundles \(B_\ell\) with positive rational masses \(\lambda_\ell\), satisfying
\(|B_\ell\cap G|=g,\qquad |B_\ell\cap C|=c,\)
\(\sum_\ell\lambda_\ell=z,\qquad \sum_{\ell:o\in B_\ell}\lambda_\ell=w_o.\)
The construction takes polynomial time in the input bit length.
Proof. Maintain a residual mass \(r\), initially \(z\), and residual inclusion masses \(w_o\), initially their given values. Their invariant is
\(0\leq w_o\leq r,\qquad \sum_{o\in G}w_o=gr,\qquad \sum_{o\in C}w_o=cr.\)
Suppose \(r>0\). In each group \(E\in\{G,C\}\), let its required count be \(k\in\{g,c\}\). Choose exactly \(k\) classes, including every class with \(w_o=r\) and excluding every class with \(w_o=0\).
This choice exists: the equality \(\sum_{o\in E}w_o=kr\) implies that at most \(k\) classes have \(w_o=r\), and at least \(k\) have \(w_o>0\). Fill any remaining positions with classes satisfying \(0<w_o<r\).
Let \(B\) be the union of the choices from the two groups. Define
\(\lambda=\min\bigl(\{w_o:o\in B\}\cup\{r-w_o:o\notin B\}\bigr).\)
Since \(m\geq1\), this minimum is over a nonempty set. Every quantity in that set is positive by construction, so \(0<\lambda\leq r\).
Emit bundle \(B\) with mass \(\lambda\), and update
\(r'=r-\lambda,\qquad w'_o=w_o-\lambda\mathbf{1}_{\{o\in B\}}.\)
For selected classes, \(\lambda\leq w_o\) gives \(w'_o\geq0\), while \(w_o\leq r\) gives \(w'_o\leq r'\). For unselected classes, \(\lambda\leq r-w_o\) gives \(w'_o=w_o\leq r'\). The two count equalities remain valid because exactly \(g\) and \(c\) inclusion masses were reduced by \(\lambda\).
If \(\lambda=r\), the residual mass and all residual inclusion masses become zero, so the construction terminates.
Otherwise, at least one previously fractional coordinate becomes a boundary coordinate:
Previously boundary coordinates remain boundary coordinates: zero coordinates are excluded, and coordinates equal to \(r\) are selected. Therefore every nonterminal iteration reduces the number of coordinates strictly between zero and the residual mass. There are at most \(m\) such coordinates initially, giving at most \(m+1\) emitted bundles.
The updates subtract precisely the emitted bundle’s inclusion masses. At termination, telescoping therefore gives the required total mass and marginals.
Finally, only comparisons and subtractions are used. After putting the initial rationals over a common denominator, every residual and emitted mass retains that denominator. Its bit length is polynomial in the initial encoding length, and every mass lies between zero and \(z\). Hence the construction has polynomial bit complexity. \(\square\)
Apply this lemma separately to every group with \(z_{t,g,c}>0\), taking \(w_o=y_{t,g,c,o}\). Groups with zero mass have zero inclusion masses and are omitted.
The resulting allocation has exactly the prescribed type masses and supplies. It also preserves every count-group mass, hence every histogram coordinate. Its number of nonzero entries is at most
\(N(m+1)\leq\tau(m+1)^3.\)
Thus \(P\) represents the feasible allocations exactly for the quantities needed here.
Sort \(U\) as \(u_1<\cdots<u_K\). Define the linear histogram functions
\(H_j(z,y)=\sum_{t,(g,c)\in I_t:\,qg-pc=u_j}z_{t,g,c}.\)
By the preceding equivalence, \(H_j=h_j\) for every represented allocation.
The polytope \(P\) is bounded: every \(z_{t,g,c}\leq\mu_t\leq1\), and every inclusion mass lies between zero and its group mass.
It is also nonempty. For each type, take a uniform parameter \(\theta\) in \([0,1]\) and assign bundle \(B(\theta)=\{o:\theta<\rho_o\}\). Splitting the type mass according to the finitely many resulting bundles gives inclusion mass \(\mu_t\rho_o\) for class \(o\). Summing over types gives precisely \(\rho_o\).
Starting with \(P_0=P\), successively compute
\(\eta_j=\min\{H_j(z,y):(z,y)\in P_{j-1}\}\)
and set
\(P_j=\{(z,y)\in P_{j-1}:H_j(z,y)=\eta_j\},\qquad j=1,\ldots,K.\)
Each minimum exists because its feasible set is nonempty and compact. The final linear program returns a point in \(P_K\).
To verify lexicographic optimality, take any feasible point with a different histogram and let \(j\) be its first coordinate differing from \((\eta_1,\ldots,\eta_K)\). Its preceding coordinates equal the preceding optima, so it belongs to \(P_{j-1}\). Consequently its \(j\)-th coordinate is at least \(\eta_j\), and, since it differs, is strictly greater. Its histogram is therefore lexicographically worse. Identical histograms remain tied, exactly as specified in the question.
We use the standard theorem that explicitly specified rational linear programs can be solved exactly in time polynomial in their encoding length, returning a rational optimal solution when feasible and bounded. See [Trevisan’s linear-programming notes, Lecture 5](https://theory.stanford.edu/~trevisan/books/cs261.pdf). The preceding sections verify feasibility, boundedness, and polynomial formulation size.
We must additionally bound the encoding lengths of the successively fixed optima.
Let \(D\) be the product of the denominators of the input masses and supplies. Its bit length is \(O(L)\). At any vertex \(v\) of the original polytope \(P\), there are \(n\) linearly independent active constraints, giving a system
\(Mv=b,\)
where \(M\) is an integer matrix with entries of absolute value at most \(m\), and \(Db\) is integral. By Cramer’s rule, every coordinate of \(v\) has a common possible denominator \(D\det M\). The determinant bound
\(|\det M|\leq n!m^n\)
shows that this denominator has bit length
\(O\bigl(L+n\log(n+1)+n\log(m+1)\bigr).\)
All coordinates lie in \([0,1]\), so their numerators also have polynomial bit length. Each \(H_j(v)\), being a sum of coordinates with this common denominator and lying in \([0,1]\), has the same polynomial bit bound.
Each \(P_j\) is an optimal face of \(P_{j-1}\), and hence a face of \(P\). Explicitly, if a convex combination of two points in \(P_{j-1}\) attains the minimum of \(H_j\), both points must attain that minimum. Induction establishes the face property relative to \(P\). A vertex of such a face is a vertex of \(P\), because any decomposition into points of \(P\) would, by the face property, be a decomposition within that face.
The minimum defining \(\eta_j\) is attained at a vertex of \(P_{j-1}\), therefore at a vertex of \(P\). It follows that every \(\eta_j\) has the uniform polynomial bit bound above, independent of the number of earlier optimization stages.
Thus every intermediate linear program has polynomial encoding length. There are only \(K\leq(m+1)^2\) stages, so the entire optimization takes polynomial time. Its final rational solution has polynomial bit length, and the reconstruction lemma produces the required explicit allocation in polynomial time.
The cited [finite-agent hardness theorem](https://arxiv.org/html/2307.12516#S7) requires assigning one bundle to each indivisible agent. Here, a type’s mass may be split among several integral bundles. The reconstruction lemma proves that this permitted splitting realizes every point of the compact linear formulation exactly.
The algorithm above settles the continuum problem as posed. In fact, its proof does not require \(p\geq3\) or coprimality.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes a polynomial-time algorithm for the exact continuum problem as stated, including an explicit allocation with polynomial support size and polynomial bit length. I found no major or minor mathematical issues requiring repair.
For each type, the sets \(G_t\) and \(C_t\) partition the item classes. Consequently, every bundle has utility \(qg-pc\) for a count pair in \(I_t\), and every pair in \(I_t\) is attainable.
The bound \(K\leq(m+1)^2\) remains valid across all types: every type’s count pairs belong to the same universal set of integer pairs satisfying \(g,c\geq0\) and \(g+c\leq m\). Taking a union over types therefore does not introduce an additional factor of \(\tau\) into this bound.
Enumerating the pairs and sorting their utility values requires polynomial time. Binary encoding of \(p,q\) causes no difficulty: the algorithm enumerates count pairs, rather than all integers between the smallest and largest utilities.
The variables record count-group masses and class inclusion masses. Every displayed constraint follows from these interpretations:
The bounds on the numbers of variables and constraints are polynomial. After moving terms to the left, the coefficients are integers of absolute value at most \(m\), including the case \(m=1\).
When \(r>0\), the equality \(\sum_{o\in E}w_o=kr\), together with \(0\leq w_o\leq r\), justifies both conditions needed for selection: at most \(k\) coordinates equal \(r\), and at least \(k\) coordinates are positive. The required selection therefore exists.
Every candidate in the minimum defining \(\lambda\) is positive. Selected coordinates have positive inclusion mass, and unselected coordinates have inclusion mass strictly below \(r\). Because \(m\geq1\), the candidate set is nonempty.
Both residual inequalities are preserved. For selected coordinates, subtracting \(\lambda\) from both the inclusion mass and the residual mass preserves the upper bound; the minimum guarantees nonnegativity. For unselected coordinates, the candidate \(r-w_o\) guarantees the new upper bound. The count equalities are preserved because the selected bundle has exactly the prescribed counts.
If \(\lambda<r\), a minimizing coordinate must have been fractional: existing boundary coordinates contribute only the candidate value \(r\). A minimizing fractional coordinate becomes a boundary coordinate, while existing boundary coordinates remain on the boundary. Thus each nonterminal iteration strictly reduces the number of fractional coordinates.
The bound of at most \(m+1\) emitted bundles follows. When \(\lambda=r\), the invariant forces all residual inclusion masses to vanish. Telescoping establishes the claimed total mass and marginals.
Empty categories, zero required counts, full required counts, and bundles that are empty or contain every class are all covered by the stated construction. Zero-mass groups are correctly omitted.
The common-denominator argument is sound: the product of the initially encoded denominators has polynomial bit length, and comparisons and subtractions introduce no new denominators. The iteration bound therefore yields polynomial bit complexity.
The uniform-parameter construction gives class inclusion mass \(\mu_t\rho_o\) within each type. Normalization of the type masses then yields precisely \(\rho_o\). Supplies equal to zero or one are covered; parameter endpoints have zero mass.
The polytope is closed and bounded, and hence compact. Each successive minimizing set is nonempty and compact.
The first-differing-coordinate argument proves exactly the histogram objective specified in USER_TASK. It also correctly preserves ties between allocations with identical histograms.
The reconstruction lemma is stated for rational points. This suffices for the algorithm: every feasible allocation maps into the real polytope, while the exact LP solver returns a rational optimum that the lemma reconstructs. No restriction to rational competing allocations is needed.
The invoked theorem applies to explicitly encoded rational linear programs with feasible sets and finite optima. These hypotheses hold at every stage. The cited notes discuss polynomial-time LP algorithms and recovery of exact rational optima in Lecture 5, Sections 5.2.4–5.2.5. [Trevisan’s notes](https://theory.stanford.edu/~trevisan/books/cs261.pdf)
The determinant argument correctly bounds coordinates of vertices of the original polytope. It applies even if the polytope is lower dimensional: at a vertex, the active constraints have full rank in the ambient variable space.
Clearing right-hand-side denominators with \(D\) and applying Cramer’s rule gives a common denominator dividing \(D|\det M|\). The bound \(|\det M|\leq n!m^n\) gives the asserted polynomial bit length. Since coordinates and histogram sums lie in \([0,1]\), their numerators satisfy corresponding bounds.
The face argument correctly shows that successive optimal faces have vertices that are vertices of the original polytope. Therefore each \(\eta_j\) has the uniform original-vertex bit bound. This addresses the potential growth of encoding lengths across successive optimizations.
Reconstruction preserves every optimized histogram coordinate, every type mass, and every supply equality. Its support bound is \(N(m+1)\leq\tau(m+1)^3\); merging repeated entries can only reduce this number.
The polynomial number of LP stages, polynomial intermediate encoding lengths, and polynomial reconstruction cost establish the claimed complexity. The proof does not use \(p\geq3\) or coprimality, so its final observation is justified.
The distinction from finite-agent hardness is consistent with the model: splitting a type’s mass among bundles is expressly permitted here. The continuum conclusion does not rely on applying the finite-agent hardness theorem.
Actionable feedback: No mathematical repair or additional clarification is required.
⟨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.