d4-journals-jair-2011-0054 (d4-journals-jair-2011-0054)

Given worker types \(T\) with rational population shares \(\mu_t\), roles \(R\), eligibility and contribution data, rational linear coverage constraints \(Ax\ge b\), and unit costs \(c_{t,r}\) and qualities \(q_{t,r}\), find a feasible assignment mass vector \(x\) minimizing \(C(x)=\sum_{t,r}c_{t,r}x_{t,r}\), then maximizing \(Q(x)=\sum_{t,r}q_{t,r}x_{t,r}\) among minimum-cost assignments; report infeasibility if none exists. Each worker receives at most one integral role, while \(x_{t,r}\) records the share of type \(t\) assigned to role \(r\).

A society is given by its support: a list \(T\) of \(\tau\) worker types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) roles \(R\), an explicit eligibility relation \(E\subseteq T\times R\), and nonnegative rational unit costs \(c_{t,r}\) and qualities \(q_{t,r}\).
The population of each type is nonatomic: different workers of one type may receive different roles, but each worker receives at most one whole role and may remain unassigned.
An assignment consists of masses \(x_{t,r}\ge0\), with \(x_{t,r}=0\) for \((t,r)\notin E\) and \(\sum_{r\in R}x_{t,r}\le\mu_t\) for every \(t\).
Contribution data and coverage requirements are encoded by an explicitly supplied rational matrix \(A\in\mathbb Q^{k\times(\tau m)}\) and vector \(b\in\mathbb Q^k\); feasibility additionally requires \(Ax\ge b\). Entries of \(A\) and \(b\) may have either sign.
Return a feasible rational assignment minimizing \(C(x)=\sum_{t,r}c_{t,r}x_{t,r}\), then maximizing \(Q(x)=\sum_{t,r}q_{t,r}x_{t,r}\) among minimum-cost assignments; report infeasibility when appropriate. Any remaining ties are acceptable.
Let \(L\) be the total binary input length; state running times in \(m,\tau,k,L\).

Is this continuous lexicographic assignment problem solvable in polynomial time in \(m,\tau,k,L\), or is it NP-hard?

For finite compositional systems with a strict partial order of dominance, filtering feasible compositions first by each most important attribute and then by dominance returns only undominated compositions and returns a nonempty set whenever feasible compositions exist.
This discrete correctness guarantee assumes access to a procedure generating feasible compositions; it establishes neither polynomial-time complexity for the assignment specialization nor a complexity result for its continuous version.

Result

The problem is solvable in polynomial time, with an exact rational output. Two rational linear programs suffice. The running time is
\[ (m\tau+\tau+k+L)^{O(1)} \]
bit operations.

Here polynomial time includes dependence on the binary input length \(L\). No claim of a strongly polynomial algorithm is needed.

1. The feasible assignments form a bounded rational polytope

Let \(n=|E|\leq \tau m\). Retain one variable \(z_{t,r}\) for each eligible pair \((t,r)\in E\), and let \(\widetilde A\) consist of the corresponding columns of \(A\). All omitted coordinates of the returned assignment will be zero.

The feasible set in these variables is
\[ P=\left\{z\in\mathbb R^n: z\geq 0,\quad \sum_{r:(t,r)\in E}z_{t,r}\leq\mu_t\ \text{for every }t,\quad \widetilde A z\geq b \right\}. \]

This description has \(n\) variables and \(n+\tau+k\) inequalities, all with rational coefficients. It is exactly equivalent to the given feasibility conditions: restoring zero coordinates for ineligible pairs preserves every constraint.

Every coordinate satisfies
\[ 0\leq z_{t,r}\leq\mu_t\leq 1. \]
Consequently, \(P\) is bounded. It is also closed, being an intersection of finitely many closed half-spaces. Thus, whenever \(P\) is nonempty, it is compact.

The nonatomic assumption permits different workers of one type to receive different whole roles. Hence fractional assignment masses introduce no integrality requirement.

If \(n=0\), the only assignment is \(x=0\). It is feasible exactly when \(b_i\leq 0\) for every \(i\), which can be checked directly. Below assume \(n\geq 1\).

2. Exact lexicographic optimization

Write \(\widetilde c,\widetilde q\in\mathbb Q^n\) for the eligible cost and quality coefficients.

First solve
\[ \min_{z\in P}\widetilde c^\top z. \]

If this linear program is infeasible, report infeasibility. Otherwise, compactness of \(P\) and continuity of the objective imply that its minimum is attained. Denote the exact optimal value by \(C^\star\).

Next solve
\[ \max\left\{\widetilde q^\top z: z\in P,\quad \widetilde c^\top z=C^\star \right\}. \]

The second feasible set is nonempty because the first minimum is attained. It is a closed subset of compact \(P\), so its maximum is also attained.

Let \(z^\star\) be an exact optimizer of the second program, and restore the omitted zero coordinates to obtain \(x^\star\). For every feasible assignment \(x\),
\[ C(x)\geq C^\star=C(x^\star). \]
For every feasible assignment \(x\) satisfying \(C(x)=C^\star\), the second optimization gives
\[ Q(x)\leq Q(x^\star). \]
These are precisely the required lexicographic optimality conditions.

3. Exact rational values have polynomial encoding length

The equality involving \(C^\star\) must have polynomial encoding length; otherwise, merely counting two linear programs would not establish polynomial time.

We first justify a bound on vertex coordinates. At any vertex \(v\) of \(P\), the active constraint rows span \(\mathbb R^n\). Indeed, otherwise there would be a nonzero vector \(d\) orthogonal to every active row. Since each inactive constraint has positive slack and there are finitely many constraints, sufficiently small \(\varepsilon>0\) would give both \(v+\varepsilon d\in P\) and \(v-\varepsilon d\in P\). This would contradict that \(v\) is a vertex.

Choose \(n\) linearly independent active rows. Clear denominators separately in each selected equation. The resulting integer system is
\[ Mv=h, \]
where \(M\) is nonsingular. Because the total input length is \(L\), the integer entries obtained by clearing row denominators have absolute value at most \(2^{O(L)}\).

Cramer's rule gives
\[ v_j=\frac{\det M_j}{\det M}, \]
where \(M_j\) replaces column \(j\) by \(h\). Hadamard's inequality bounds both determinants in absolute value by
\[ n^{n/2}\,2^{O(nL)}. \]
Thus each coordinate has binary encoding length
\[ O\!\left(n(L+\log(n+1))\right). \]

For completeness, a nonempty compact polytope has a vertex, and a linear objective attains its optimum at one. Here this can be seen without assuming full dimensionality: take its nonempty optimal set, then successively maximize coordinates \(1,\ldots,n\) within the preceding maximizer set. Each set remains nonempty and compact, and the final set is a singleton. If that point were a proper convex combination of two points of \(P\), optimality of the objective and then of each successive coordinate would force both points into the singleton. It is therefore a vertex of \(P\).

It follows that \(C^\star=\widetilde c^\top v\) for a vertex \(v\) with the coordinate bounds above. Summing these \(n\) rational products gives, even using products of denominators as a coarse bound, an encoding length
\[ O\!\left(n^2(L+\log(n+1))\right) \]
for \(C^\star\).

Therefore the second program has polynomial encoding length. The same vertex argument also applies to its nonempty compact feasible set, establishing the existence of a rational optimizer of polynomial encoding length.

4. Polynomial running time

We use the standard rational linear programming theorem: given an explicitly encoded rational linear program, a deterministic algorithm can determine infeasibility or unboundedness, or return an exact rational optimizer, in time polynomial in the numbers of variables and constraints and the total binary encoding length. Polynomial solvability in this bit complexity model is the classical consequence of Khachiyan's ellipsoid algorithm; see the discussion in [Dadush, Huiberts, Natura, and Végh](https://link.springer.com/article/10.1007/s10107-023-01956-2).

Its hypotheses hold here:

• Both programs have explicitly supplied rational coefficients.
• The first has \(n\) variables and \(n+\tau+k\) inequalities.
• Replacing the cost equality by two inequalities, the second has \(n+\tau+k+2\) inequalities.
• Both programs have encoding length polynomial in \(n,\tau,k,L\), as proved above.
• Whenever feasible, both programs are bounded and attain their optima.

Constructing the programs and restoring all \(\tau m\) output coordinates also takes polynomial time. Hence the complete algorithm uses
\[ (m\tau+\tau+k+L)^{O(1)} \]
bit operations and returns an exact feasible rational lexicographic optimizer, or correctly reports infeasibility.

Arbitrary signs in \(A\) and \(b\) do not affect this argument: they are permitted in rational linear programming. The stated discrete dominance guarantee supplies no complexity conclusion; the continuous problem is settled independently by its explicit linear formulation.

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct and resolves the requested complexity classification: the continuous lexicographic assignment problem is solvable in polynomial time with exact rational output. No major or minor mathematical issues were found.

1. Feasible-set formulation

The reduction to eligible variables is exact. Each feasible assignment determines a vector \(z\) indexed by \(E\), and restoring zero coordinates for ineligible pairs recovers precisely the original assignment constraints. Restricting \(A\) to the corresponding columns preserves \(Ax\ge b\), including when its entries have arbitrary signs.

The constraint count is correct: \(n\) nonnegativity inequalities, \(\tau\) type-capacity inequalities, and \(k\) contribution inequalities, where \(n=|E|\le\tau m\).

The nonatomic interpretation is consistent with the task’s explicit definition of an assignment. No integrality constraint is required.

Finding: Correct; no gap.

2. Boundedness, compactness, and the empty eligibility case

For each eligible pair, nonnegativity and the type-capacity constraint imply \(0\le z_{t,r}\le\mu_t\). The positive masses sum to one, so \(\mu_t\le1\). Thus every feasible coordinate lies in \([0,1]\).

The feasible set is closed because all its inequalities are non-strict linear inequalities. Consequently, when nonempty, it is compact.

When \(n=0\), the sole assignment is zero. Its contribution constraints are exactly \(0\ge b_i\) for every \(i\); the remaining constraints hold automatically. The stated feasibility check is therefore correct, including when there are no contribution constraints.

Finding: Correct; relevant edge cases are covered.

3. Lexicographic optimization

The first objective is continuous on the nonempty compact feasible set, so its minimum is attained.

The second feasible set consists exactly of the feasible assignments attaining that minimum. It is nonempty and compact, so the quality maximum is also attained.

The two inequalities used to certify the returned assignment have the correct quantifiers:

• Every feasible assignment has cost at least \(C^\star\).
• Every feasible assignment with cost \(C^\star\) has quality at most that of the second optimizer.

These establish precisely the requested ordering of objectives. Arbitrary remaining ties are permitted by the task.

Finding: Correct; the second optimization preserves minimum cost exactly.

4. Active constraints and rational vertex coordinates

The active-row argument is valid even when the polytope is not full dimensional. If the active rows failed to span \(\mathbb R^n\), a nonzero orthogonal direction would preserve all active constraints. Because there are finitely many inactive constraints and each has positive slack, sufficiently small perturbations in both directions would preserve those constraints as well. The purported vertex would then lie between two distinct feasible points, a contradiction.

Selecting \(n\) independent active rows therefore produces a nonsingular system. Clearing denominators row by row yields integer entries bounded by \(2^{O(L)}\): the denominator and numerator bit lengths involved in any selected input row are bounded by the total input length. The generated capacity and nonnegativity coefficients do not invalidate this estimate.

The stated Hadamard bound \(n^{n/2}2^{O(nL)}\) applies to both the coefficient matrix and each column-replacement matrix. Cramer’s rule then gives the claimed coordinate encoding bound \(O(n(L+\log(n+1)))\). Reducing the resulting fractions cannot increase this bound.

Finding: Correct; the critical determinant and encoding estimates check out.

5. Existence of an optimal vertex

The coordinate-maximization argument establishes the assertion rather than assuming full dimensionality.

Each successive maximizer set is nonempty and compact. After all coordinates have been fixed, the final set contains exactly one point. If this point were a proper convex combination of two feasible points, optimality of the original linear objective would force both points into the original optimal set. Successive coordinate optimality would then force both into every subsequent maximizer set, contradicting their distinctness.

Thus an optimal vertex exists.

Finding: Correct; no missing vertex-existence lemma remains.

6. Encoding the second program and its output

An optimal vertex supplies the value \(C^\star=\widetilde c^\top v\). The stated bound \(O(n^2(L+\log(n+1)))\) is a valid coarse bound for summing the rational products, even using products of denominators.

Therefore adding the equality \(\widetilde c^\top z=C^\star\) increases the encoding length only polynomially. Applying the same vertex-coordinate reasoning to the second compact rational polytope establishes an optimizer with polynomial rational encoding length.

This argument establishes existence and encoding bounds; the subsequent exact linear programming theorem supplies the algorithm for finding the optimizer.

Finding: Correct; there is no circular dependence on already knowing \(C^\star\).

7. Algorithmic theorem and total running time

The prover states the rational linear programming theorem with the necessary scope: explicitly encoded rational coefficients, deterministic polynomial bit complexity, feasibility classification, and exact rational optimization.

Its application requires neither full dimensionality nor positive coefficients. Both programs meet its hypotheses, and compactness rules out unbounded objectives whenever they are feasible. Replacing the second program’s equality with two inequalities gives the stated constraint count.

The [cited paper’s introduction](https://link.springer.com/article/10.1007/s10107-023-01956-2) confirms the classical polynomial bit-complexity result attributed to Khachiyan. The prover invokes that standard theorem, rather than the paper’s specialized algorithm with its separate hypotheses.

Program construction, exact objective-value computation, and restoration of the \(\tau m\) coordinates all have polynomial cost. The final bound \((m\tau+\tau+k+L)^{O(1)}\) therefore follows.

The discrete dominance guarantee is correctly identified as supplying no complexity conclusion for this continuous problem.

Finding: Correct. No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩