Answer: \(\mathrm{NP}\)-hard
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIf the two functions maximize and solve are both correct and both halt, then algorithm 1 halts and solves the MaxLeximinCSP problem. In the next proofs, we will write soli and sol′ i for respec- tively sol(Xi, Di, Ci) and sol(Xi, D′ i, Ci). We will also write (soli)↓Xj and (sol′ i)↓Xj for the same sets of solutions pro- jected on Xj (with j < i). We can notice that sol0 = sol(X, D, C), and that ∀i, sol′ i ⊆soli.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of worker types \(T\) with rational population masses \(\mu_t\), a finite-state network of legal integral rosters \(a\) for each type, each roster's utility \(u_t(a)\) and resource use \(r_t(a)\), and per-capita resource constraints, compute a feasible allocation \(x_{t,a}\ge 0\) with \(\sum_a x_{t,a}=\mu_t\) that lexicographically minimizes \((p_{q_1},\ldots,p_{q_k})\), where \(q_1<\cdots<q_k\) are the attainable utility levels and \(p_q=\sum_{t,a:u_t(a)=q}x_{t,a}\); report infeasibility if no such allocation exists.
A society is given by its support: the list of \(\tau\ge 1\) worker 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.
For each type, an input finite-domain constraint network has explicitly listed nonnegative integer domains and constraints specified by explicit tables of allowed tuples. A legal integral roster \(a\in A_t\) is a complete satisfying assignment; rosters are represented implicitly by this network.
Designated variables give the utility \(u_t(a)\in\mathbb Z_{\ge0}\), on a common interpersonal scale, and resource uses \(r_{t,j}(a)\in\mathbb Z_{\ge0}\) for \(1\le j\le d\). Capacities \(b_j\ge0\) are binary rationals.
An allocation consists of masses \(x_{t,a}\ge0\) satisfying \(\sum_{a\in A_t}x_{t,a}=\mu_t\) and \(\sum_t\sum_{a\in A_t}r_{t,j}(a)x_{t,a}\le b_j\) for every resource. There are no further constraints between types.
Let \(q_1<\cdots<q_k\) be all utility values realized by legal rosters, and define \(p_q=\sum_t\sum_{a\in A_t:u_t(a)=q}x_{t,a}\). Compute an allocation lexicographically minimizing \((p_{q_1},\ldots,p_{q_k})\), or report infeasibility; any optimal allocation is acceptable. Represent the allocation by its positive rational masses and their rosters.
Is this continuous allocation problem solvable in polynomial time, or is it NP-hard? State running times in \(m\), the maximum number of variables in a type network, \(\tau\), \(d\), and the total input bit length \(L\).
The discrete analogue has a terminating, correct cardinality-based algorithm conditional on terminating, correct feasibility and single-objective optimization routines; this gives no polynomial-time guarantee. [Bouveret–Lemaître](https://www.ijcai.org/Proceedings/07/Papers/008.pdf)
No result settling this exact continuous problem was identified in the literature search.
The problem is \(\mathrm{NP}\)-hard, even with one worker type, one resource, binary domains, and guaranteed feasibility. Thus a polynomial-time algorithm for all inputs would imply \(\mathrm{P}=\mathrm{NP}\).
An exact algorithm runs in \(L^{O(m)}(m+\tau+d+L)^{O(1)}\) time. In particular, it is polynomial-time for every fixed \(m\). Every feasible instance has a lexicographically optimal allocation with at most \(\tau+d\) positive rational masses, each of polynomial bit length.
Merely asking whether a type network has a legal roster already contains constraint satisfaction. The following reduction establishes hardness even when a feasible allocation and both utility levels are guaranteed to exist.
Let \(F\) be a \(3\)-CNF formula on Boolean variables \(X_1,\ldots,X_n\). Construct a society with \(\tau=1\), \(\mu_1=1\), \(d=1\), and \(b_1=0\).
Its type network has the variables \(X_1,\ldots,X_n,Y,Z\), all with domain \(\{0,1\}\). Designate \(Y\) as utility and \(Z\) as resource use:
\(u(a)=a(Y),\qquad r_1(a)=a(Z).\)
For each clause \(C\), introduce a constraint on \(Y,Z\) and the distinct variables appearing in \(C\). Its allowed tuples are exactly those satisfying
\(Y=0\quad\text{or}\quad Z=1\quad\text{or}\quad C\text{ is true}.\)
Each constraint has arity at most five and at most \(32\) allowed tuples. Consequently, the network is constructible in polynomial time, with \(m=n+2\). All numerical data belong to \(\{0,1\}\).
Feasibility and realized utilities. Any assignment with \(Y=0,Z=0\) is legal. Placing mass one on such a roster gives a feasible allocation. Any assignment with \(Y=1,Z=1\) is also legal. Thus the realized utility levels are always exactly \(q_1=0,q_2=1\), independently of whether \(F\) is satisfiable.
Effect of capacity. Every feasible allocation satisfies
\(\sum_a a(Z)x_a\le 0.\)
Every summand is nonnegative. Hence every roster receiving positive mass has \(Z=0\). For such a roster, \(Y=1\) is legal precisely when its assignment to \(X_1,\ldots,X_n\) satisfies every clause of \(F\).
It follows that:
Thus
\(F\text{ is satisfiable}\quad\Longleftrightarrow\quad\text{the optimal value of }p_0\text{ is }0.\)
A polynomial-time algorithm producing any optimal allocation would decide \(3\)-SAT by inspecting the utilities of its positively allocated rosters. This proves the claimed \(\mathrm{NP}\)-hardness. Fractional masses do not alter the argument: zero capacity excludes every positively allocated roster with \(Z=1\).
Write \(m_t\le m\) for the number of variables of type \(t\), and let \(D\) be the largest domain cardinality, taking \(D=1\) if all domains are empty.
Enumerate all complete assignments of every type and check each against its constraint tables. This requires at most
\(\sum_{t=1}^{\tau}D^{m_t}\le \tau D^m\)
assignment checks. Each check takes polynomial time in \(m\) and \(L\). If some \(A_t\) is empty, report infeasibility, since \(\mu_t>0\).
Otherwise, let \(N=\sum_t|A_t|\). The explicitly represented allocation polytope is
\(P=\left\{x\in\mathbb{R}_{\ge0}^{N}:\ \sum_{a\in A_t}x_{t,a}=\mu_t\text{ for every }t,\ \sum_t\sum_{a\in A_t}r_{t,j}(a)x_{t,a}\le b_j\text{ for every }j\right\}.\)
This is a rational polytope. It is bounded because \(0\le x_{t,a}\le\mu_t\le1\). An exact rational linear-programming algorithm therefore either reports infeasibility or can optimize every subsequent linear objective.
Determine the realized utility levels \(q_1<\cdots<q_k\) from the enumerated rosters. Starting with \(P_0=P\), recursively compute
\(v_i=\min_{x\in P_{i-1}}p_{q_i}(x),\qquad P_i=\{x\in P_{i-1}:p_{q_i}(x)=v_i\},\qquad 1\le i\le k.\)
Each minimum exists: its feasible set is nonempty and compact. By induction, \(P_i\) consists exactly of the allocations that optimize the first \(i\) utility coordinates lexicographically. Thus \(P_k\) is exactly the set of requested optimal allocations.
Furthermore, each \(P_i\) is a face of \(P\). Indeed, suppose \(x=\lambda y+(1-\lambda)z\in P_i\), where \(y,z\in P\) and \(0<\lambda<1\). Inductively, membership of \(x\) in the face \(P_{i-1}\) forces \(y,z\in P_{i-1}\). Both objective values are at least \(v_i\), and their convex combination equals \(v_i\), so both equal \(v_i\). Hence \(y,z\in P_i\).
To obtain a vertex, successively minimize all \(N\) allocation coordinates over \(P_k\), retaining each minimum as an equality. These operations produce nested nonempty faces. After all coordinates have been fixed, the remaining face is a singleton, so its point is a vertex of the original polytope \(P\). This uses at most \(N\) additional linear programs.
Let \(\rho=\tau+d\).
Every vertex of \(P\) has at most \(\rho\) positive allocation coordinates.
To prove this, suppose a vertex \(x\) has positive-coordinate set \(S\) with \(|S|>\rho\). Associate to each roster coordinate its column of coefficients in the \(\tau\) type equations and \(d\) resource inequalities. These columns lie in \(\mathbb{R}^{\rho}\), so those indexed by \(S\) are linearly dependent.
There is therefore a nonzero vector \(h\), supported on \(S\), preserving all type totals and resource uses. For sufficiently small \(\varepsilon>0\), both \(x+\varepsilon h\) and \(x-\varepsilon h\) remain nonnegative and feasible. They are distinct, and their midpoint is \(x\), contradicting extremality.
Since the preceding algorithm returns a lexicographically optimal vertex of \(P\), an optimum with at most \(\tau+d\) positive masses always exists.
Fix a vertex \(x\), with positive-coordinate set \(S\) and \(s=|S|\le\rho\). The type equations together with the tight resource inequalities, restricted to \(S\), have rank \(s\).
Otherwise, a nonzero null direction would preserve those equations. A sufficiently small perturbation in either direction would preserve positivity on \(S\) and all resource inequalities with positive slack, contradicting extremality.
Choose \(s\) independent rows. They give a nonsingular integer system
\(H x_S=c,\)
where entries of \(H\) are type indicators or resource uses, and entries of \(c\) are masses or capacities. Every entry of \(H\) has absolute value at most \(2^L\).
Let \(Q\) be the product of the denominators of all input masses and capacities. Their total encoding length is at most \(L\), so \(Q\le2^L\), and every entry of \(Qc\) has absolute value at most \(2^{2L}\). Cramer’s rule gives
\(x_{S,\ell}=\dfrac{\det H_\ell(Qc)}{Q\det H},\)
where \(H_\ell(Qc)\) replaces column \(\ell\) of \(H\) by \(Qc\). The determinant expansion bounds both numerator and denominator in absolute value by
\(s!\,2^{(s+1)L}.\)
Consequently, each positive mass has bit length
\(O\!\left((\tau+d)\bigl(L+\log(\tau+d+1)\bigr)\right).\)
A roster uses at most \(O(mL)\) bits. Thus the complete sparse output has polynomial length in \(m,\tau,d,L\).
The same bound controls intermediate optimization values. Every intermediate feasible set is a face of \(P\), and a linear minimum over that face is attained at a vertex of \(P\). At such a vertex, all positive coordinates have the common denominator \(Q\det H\). Summing coordinates to obtain a utility mass therefore retains polynomial bit length. Coordinate minima used to select a vertex have the same property.
Because utility is a designated variable, every realized utility belongs to an explicitly listed utility domain. Hence
\(k\le\sum_{t=1}^{\tau}|D_{t,u}|\le L.\)
The algorithm performs at most \(1+k+N\) rational linear programs. Their dimensions and coefficient bit lengths are polynomial in \(N,m,\tau,d,L\), by the preceding bounds. The standard polynomial-time theorem for explicitly represented rational linear programming applies: all coefficients are rational, and every optimization problem considered has a nonempty bounded feasible set.
Together with enumeration, the total bit-operation running time is
\((\tau D^m)^{O(1)}(m+\tau+d+L)^{O(1)}.\)
Explicit domain listing implies \(D\le L\), giving the requested bound
\(L^{O(m)}(m+\tau+d+L)^{O(1)}.\)
Accordingly, the problem is polynomial-time for fixed \(m\), and polynomial-time when all legal rosters are supplied explicitly. For unrestricted implicitly represented networks, the reduction in Section 1 proves \(\mathrm{NP}\)-hardness.
The cardinality algorithm in [Bouveret–Lemaître, Proposition 1](https://www.ijcai.org/Proceedings/07/Papers/008.pdf) assumes correct, terminating feasibility and optimization routines. That conditional guarantee supplies no polynomial-time bound; the continuous problem here is settled by the direct reduction above.
⟨structured verdict parsed — rendered above⟩
The output settles the assigned problem: the continuous allocation problem is NP-hard under the stated implicit representation, including instances with guaranteed feasibility. The enumeration algorithm, running-time bounds, and sparse rational output bounds are also sound. I found one minor terminology issue and no substantive gap.
Construction and encoding. The constructed instance satisfies the task’s requirements: \(\tau=1\), \(\mu_1=1\), \(d=1\), and \(b_1=0\). All domains are explicitly listed, and utility and resource use are designated variables with nonnegative integer values.
A clause contains at most three distinct Boolean variables. Adding \(Y,Z\) gives constraint arity at most five, hence at most \(2^5=32\) allowed tuples. Listing the tuples satisfying the displayed condition takes constant work per clause, apart from encoding variable identifiers. The reduction therefore has polynomial size and construction time. Repeated variables or tautological clauses do not invalidate this construction.
Guaranteed feasibility. With \(Y=0,Z=0\), every clause constraint is satisfied regardless of the assignment to the original variables. Allocating mass one to such a roster respects the type total and the zero resource capacity.
Realized utility levels. Legal rosters with \(Y=0\) exist, and legal rosters with \(Y=1,Z=1\) exist. Since \(Y\) has domain \(\{0,1\}\), the realized utility levels are exactly \(0,1\). The latter rosters need not be allocatable under the capacity constraint: the task defines realized utility levels using legal rosters, so this distinction is handled correctly.
Zero-capacity argument. Every resource term is nonnegative. Consequently, the inequality \(\sum_a a(Z)x_a\le 0\) forces every positively allocated roster to have \(Z=0\). There is no possibility of cancellation through fractional masses.
For \(Y=1,Z=0\), each allowed-tuple condition reduces exactly to satisfaction of its original clause. Thus such a legal roster exists precisely when the formula is satisfiable.
Optimal values and extraction.
Any optimal allocation therefore distinguishes the two cases by its positively allocated rosters. This is a valid reduction to the requested exact search problem, and it establishes the claimed hardness even on guaranteed-feasible instances.
Assignment enumeration. A type with \(m_t\) variables has at most \(D^{m_t}\) complete assignments. Summing gives the stated upper bound \(\tau D^m\). Checking an assignment against explicitly listed tables takes polynomial time in the original input size.
Empty domains cause no difficulty: they produce no complete assignments. The convention \(D=1\) when all domains are empty still supplies an upper bound. If any \(A_t\) is empty, positive \(\mu_t\) makes allocation infeasible, so reporting infeasibility is correct.
Allocation polytope. After enumeration, the displayed polytope contains exactly the feasible allocations. Its coefficients are rational. Each coordinate satisfies \(0\le x_{t,a}\le\mu_t\le1\), so the polytope is bounded and closed.
Nonempty roster sets alone do not guarantee resource feasibility. The output correctly includes an LP feasibility check before proceeding with optimization. All subsequent existence statements are valid on the branch where that check succeeds.
Successive utility objectives. Each objective \(p_{q_i}\) is linear. Minimizing it over the previously retained optimal set and imposing its attained value as an equality implements lexicographic minimization in the required increasing utility order. The induction identifying \(P_i\) with the allocations optimizing the first \(i\) coordinates is correct.
Face argument. The supplied convex-combination argument verifies the defining face property. Membership in \(P_{i-1}\) follows by induction; minimality of \(v_i\) then forces both endpoint objective values to equal \(v_i\). No unsupported face assertion is needed.
Vertex selection. Successively minimizing all allocation coordinates retains nonempty faces. Fixing every coordinate leaves a singleton, which is a face of the original polytope and hence a vertex. These additional objectives preserve all previously optimized utility coordinates.
Support bound. If a vertex had more than \(\tau+d\) positive coordinates, their columns in the combined type/resource matrix would be linearly dependent. The resulting nonzero direction preserves every type total and every resource use.
Because the direction is supported only on positive coordinates, sufficiently small perturbations in both directions preserve nonnegativity. Both perturbed points remain feasible, contradicting extremality. Thus the stated support bound is correct, including when some resource constraints are redundant or slack.
Rank of tight constraints. The type rows and tight resource rows restricted to the positive support must have full column rank. Otherwise the stated perturbation preserves those rows, while sufficiently small perturbations also preserve all finitely many slack inequalities. This correctly establishes the existence of the nonsingular subsystem.
Minor terminology issue. The phrase “a nonsingular integer system” is imprecise: \(H\) has integer entries, but \(c\) can have nonintegral rational entries because masses and capacities are binary rationals.
Minimum clarification: describe this as a nonsingular system with an integer coefficient matrix and a rational right-hand side. The subsequent denominator-clearing calculation already treats it correctly.
Denominator and determinant calculations. The product \(Q\) of input denominators satisfies \(Q\le2^L\). Matrix entries are bounded by \(2^L\), and entries of \(Qc\) by \(2^{2L}\).
Cramer’s rule gives the displayed fraction with denominator \(Q\det H\). A determinant term in the numerator contains one entry from \(Qc\) and \(s-1\) entries from \(H\), so its absolute value is at most \(2^{(s+1)L}\). There are at most \(s!\) terms. The denominator satisfies the same stated bound. Thus the resulting bit-length estimate is valid.
The roster encoding and the bound on the number of positive coordinates yield polynomial total output length.
Intermediate optimization values. Every retained feasible set is a face of the original polytope, and a linear minimum on a nonempty compact face is attained at one of its vertices. Those vertices are also vertices of the original polytope. Summing at most \(s\) coordinates with their common denominator increases the numerator length by at most a logarithmic term, which the stated polynomial bound absorbs. Coordinate-selection minima satisfy the same bound.
Since utility is a designated variable, every realized utility value appears in an explicitly listed utility domain. The bound \(k\le L\) is valid under ordinary explicit binary encoding.
The algorithm uses at most \(1+k+N\) LP calls. Each LP is explicitly represented, with dimensions and total encoding length polynomial in \(N,m,\tau,d,L\). The standard exact rational LP polynomial-time theorem applies to feasibility detection and optimization; after feasibility is established, the optimization sets are nonempty and bounded.
Combining these bounds with \(N\le\tau D^m\) gives the claimed running time \((\tau D^m)^{O(1)}(m+\tau+d+L)^{O(1)}\). Explicit listing gives \(D\le L\), yielding \(L^{O(m)}(m+\tau+d+L)^{O(1)}\). This is polynomial for each fixed \(m\); it does not claim polynomial dependence on unrestricted \(m\).
The polynomial-time statement for explicitly supplied rosters is also justified by the same LP procedure, measured in that representation’s input length.
The description of [Bouveret–Lemaître, Proposition 1](https://www.ijcai.org/Proceedings/07/Papers/008.pdf) is accurate: its termination and correctness guarantee is conditional on correct, terminating feasibility and optimization routines. It supplies no polynomial-time guarantee and is not needed for the reduction.
⟨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.