d4-conf-aaai-2004-0008 (d4-conf-aaai-2004-0008)

Given request types \(T\) with rational population masses \(\mu_t\), a priority order on types, integral configurations \(Q_t\) satisfying each type’s request, resource vectors \(a(q)\), and per-capita shared capacities \(b\), find a feasible allocation \(z_{tq}\ge 0\) with \(y_t=\sum_{q\in Q_t}z_{tq}\le\mu_t\) and \(\sum_{t,q}a(q)z_{tq}\le b\), whose retained-mass vector \(y\) is lexicographically greatest in the priority order.

A society is given by its support: a list \(T\) of the \(\tau\ge 1\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge 1\) shared resources and a supplied strict total priority order \(t_1,\ldots,t_\tau\), highest priority first. Each type has an explicitly listed finite set \(Q_t\) of admissible integral configurations satisfying its request and all individual background constraints; this set may be empty. Each listed configuration has a binary-rational consumption vector \(a(q)\in\mathbb{Q}_{\ge 0}^{m}\). Shared per-capita capacities \(b\in\mathbb{Q}_{\ge 0}^{m}\) cannot be relaxed.
An allocation assigns masses \(z_{tq}\ge 0\), with \(y_t=\sum_{q\in Q_t}z_{tq}\le\mu_t\) and \(\sum_{t\in T}\sum_{q\in Q_t}a(q)z_{tq}\le b\) componentwise. Mass may be split among configurations; unretained mass consumes no resources. Find an exact allocation whose vector \((y_{t_1},\ldots,y_{t_\tau})\) is lexicographically greatest; any allocation attaining that vector is acceptable.
Let \(N=\sum_{t\in T}|Q_t|\) and let \(L\) be the total binary input length. State running times in \(m,\tau,N,L\).

Is computing this lexicographically greatest retained-mass allocation polynomial-time solvable, or is it \(\mathrm{NP}\)-hard?

For finite constraint systems, QUICKXPLAIN terminates and, with a complete consistency checker, reports consistency or returns a preferred irreducible conflict; this is a correctness result, without an unconditional polynomial-time guarantee. Lexicographically preferred retained subsets are also constructible using consistency checks. [Junker](https://cdn.aaai.org/AAAI/2004/AAAI04-027.pdf)
No result settling exactly the mass-allocation problem specified here was identified in the searches.

The problem is polynomial-time solvable. An exact algorithm uses at most \(\tau\) rational linear programs. The integrality of the listed configurations imposes no integrality requirement on the allocation variables, because mass may be split.

1. The feasible allocation polytope

Index the variables by the listed pairs \((t,q)\), and define
\[ \]
\(f_i(z)=\sum_{q\in Q_{t_i}}z_{t_iq}\).

An empty sum is zero. The feasible set is
\[ \]
\(P=\{z\in\mathbb R_{\ge0}^{N}: f_i(z)\le\mu_{t_i}\text{ for every }i,\ \sum_{t\in T}\sum_{q\in Q_t}a(q)z_{tq}\le b\}\).

All resource inequalities are componentwise. This is a rational polytope described by \(m+\tau\) inequalities and \(N\) nonnegativity constraints.

The origin belongs to \(P\), since the capacities are nonnegative. Moreover, every variable satisfies \(0\le z_{tq}\le\mu_t\le1\). Thus \(P\) is nonempty and compact.

If \(N=0\), the unique allocation is the empty allocation, with every retained mass zero; this case takes \(O(L)\) time. Assume henceforth that \(N\ge1\).

2. The algorithm and its correctness

Set \(F_0=P\). For \(i=1,\ldots,\tau\), compute exactly
\[ \]
\(\alpha_i=\max\{f_i(z):z\in F_{i-1}\}\),

and set
\[ \]
\(F_i=\{z\in F_{i-1}:f_i(z)=\alpha_i\}\).

Equivalently, the linear program at stage \(i\) maximizes \(f_i(z)\) subject to the original allocation constraints and the equalities \(f_j(z)=\alpha_j\) for \(j<i\). Every \(F_i\) is nonempty and compact: a continuous linear function attains its maximum on the preceding nonempty compact set.

Return an optimal allocation from the last stage. It belongs to \(F_\tau\) and therefore has retained vector \((\alpha_1,\ldots,\alpha_\tau)\).

To prove lexicographic optimality, let \(w\in P\) have a different retained vector, and let \(k\) be its first differing coordinate. Then \(f_j(w)=\alpha_j\) for every \(j<k\), so \(w\in F_{k-1}\). By the definition of \(\alpha_k\), \(f_k(w)\le\alpha_k\). Since these coordinates differ, \(f_k(w)<\alpha_k\). Consequently, the returned vector is lexicographically greater.

The algorithm fixes only previously optimized retained masses. Configuration assignments remain variables throughout, allowing earlier types to change their configuration mixtures when optimizing later priorities.

3. Exact values have polynomial encoding length

It remains to show that inserting the exact values \(\alpha_i\) into later programs does not cause excessive growth in input length.

First, every \(F_i\) is a face of the original polytope \(P\). Here a face has the property that if an interior point of a segment between two points of \(P\) belongs to the face, both endpoints belong to it.

This follows inductively. Suppose \(x=\lambda u+(1-\lambda)v\in F_i\), where \(u,v\in P\) and \(0<\lambda<1\). Since \(F_{i-1}\) is a face, \(u,v\in F_{i-1}\). Both \(f_i(u)\) and \(f_i(v)\) are at most \(\alpha_i\); their weighted average is \(f_i(x)=\alpha_i\). Hence both equal \(\alpha_i\), giving \(u,v\in F_i\).

Every nonempty compact polytope has a vertex. A vertex of a face is a vertex of the original polytope: any nontrivial segment representation in the original polytope would, by the face property, also be a segment representation within the face. Thus each \(\alpha_i\) is attained at a vertex of \(P\).

We now bound the coordinates of those vertices using only the original input. Clear denominators separately in each original inequality. Under the usual binary numerator-and-denominator encoding, the resulting integer coefficients and right-hand sides have absolute value at most \(M=2^{O(L)}\). Indeed, multiplying by the product of the denominators in a row increases bit length by at most the sum of their input bit lengths.

At a vertex \(v\), the active constraint normals span \(\mathbb R^N\). Otherwise, a nonzero direction orthogonal to all active normals would allow sufficiently small perturbations of \(v\) in both directions: active constraints would remain equalities, and every inactive constraint has positive slack. This would contradict extremality.

Choose \(N\) linearly independent active rows, obtaining an integer system \(Cv=d\) with \(C\) nonsingular. By Cramer’s rule, every coordinate of \(v\) has the common denominator \(D=|\det C|\). The determinant expansion gives
\[ \]
\(1\le D\le N!M^N\).

Because \(0\le v_{tq}\le1\), its coordinates can be written as \(p_{tq}/D\) with integer numerators satisfying \(0\le p_{tq}\le D\). Each retained mass at this vertex likewise has denominator \(D\) and numerator between zero and \(D\), since \(0\le f_i(v)\le1\).

It follows that every \(\alpha_i\), in reduced rational form, has encoding length
\[ \]
\(H=O\!\left(N\left(L+\log(N+1)\right)\right)\).

This bound comes from vertices of the original polytope, independently of the values inserted at preceding stages.

4. Polynomial running time

We use the standard exact rational linear-programming theorem: a linear program with rational coefficients can be solved in time polynomial in its numbers of variables and constraints and its total binary encoding length; when its optimum is finite and attained, an exact rational optimal solution can be returned. See [Theorem 17.1 in Haotian Jiang’s linear-programming notes](https://courses.cs.washington.edu/courses/cse521/22au/521-lecture-16.pdf).

The hypotheses hold at every stage: all coefficients and fixed optimal values are rational, and the feasible set is nonempty and compact. The theorem also permits equality constraints and feasible sets of lower dimension; no interior-point assumption is needed.

Replacing each equality by two inequalities, every stage has \(N\) variables and at most \(m+3\tau+N\) inequalities. A dense encoding of each program has length at most
\[ \]
\(B=O\!\left(L+N(m+\tau+N)+\tau N\left(L+\log(N+1)\right)\right)\).

The terms account respectively for the original input, generated matrix entries, and previously fixed rational optimal values. Therefore the total running time is
\[ \]
\(O\!\left(\tau\,\operatorname{poly}\!\left(N,m+\tau+N,B\right)\right)=\operatorname{poly}(m,\tau,N,L)\).

This is a polynomial bound in binary bit complexity, with exact rational output. It settles the specified mass-allocation problem without requiring a complexity guarantee for QUICKXPLAIN.

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated problem correctly: computing an exact lexicographically greatest retained-mass allocation is polynomial-time solvable. No major or minor mathematical gaps were found.

• The model matches the task. The variables \(z_{tq}\) represent divisible allocation masses, so imposing nonnegativity without integrality is correct. The constraints defining \(P\) encode precisely the type-mass limits and shared resource capacities. Individual constraints already enter through the explicitly supplied configuration lists.

• Feasibility, boundedness, and edge cases are handled correctly. Nonnegative capacities make the origin feasible. Nonnegativity and the type-mass constraints imply \(0\le z_{tq}\le\mu_t\le1\). The finite intersection of closed halfspaces is therefore compact. Empty configuration sets contribute zero retained mass. When \(N=0\), the empty allocation is the unique allocation; the stated \(O(L)\) bound is sufficient.

• The sequential optimization algorithm is well-defined. Each stage maximizes a continuous linear function over a nonempty compact set. Consequently, its maximum exists, and the next restricted feasible set remains nonempty and compact. The solution returned by the last stage belongs to \(F_\tau\).

• The lexicographic correctness argument is complete. For any feasible allocation with a different retained vector, its first differing coordinate \(k\) places it in \(F_{k-1}\). The stage-\(k\) optimality inequality then gives \(f_k(w)<\alpha_k\). This establishes the claimed lexicographic dominance. Keeping configuration variables free at later stages correctly permits reassignment of earlier types while preserving their retained masses.

• The face argument is valid. The induction uses exactly the defining segment property of a face. Its base case, \(F_0=P\), is immediate. The weighted-average argument correctly forces both endpoint objective values to equal \(\alpha_i\). The stated standard fact that every nonempty compact polytope has a vertex applies to each \(F_i\); the segment argument correctly shows that its vertices are vertices of \(P\). Thus every \(\alpha_i\) is attained at an original vertex.

• The rational encoding bound checks out. Clearing denominators row by row gives integer entries bounded by \(M=2^{O(L)}\). The active-normal argument applies even when \(P\) has lower dimension and correctly yields a nonsingular system of \(N\) active constraints. Cramer’s rule and the determinant expansion give \(1\le D\le N!M^N\). The bounds on coordinates and retained masses justify numerators between zero and \(D\). Hence the claimed bound \(H=O(N(L+\log(N+1)))\) is valid and does not depend recursively on previously inserted optimal values.

• The LP theorem is applicable. The prover states the requisite exact rational LP theorem and checks rationality, nonempty feasibility, and attained finite optima. The cited [Theorem 17.1](https://courses.cs.washington.edu/courses/cse521/22au/521-lecture-16.pdf) states polynomial-time LP solvability in binary encoding length; the notes also discuss exact optimal values and removal of the full-dimensionality restriction. Equality constraints can be represented by two inequalities, as the prover specifies. No additional interior assumption is required.

• The running-time accounting is sufficient. At stage \(i\), the inequality count is \(m+\tau+N+2(i-1)\), within the stated bound \(m+3\tau+N\). The dense encoding bound \(B\) includes original coefficients, generated entries, and fixed optimal values of polynomial encoding length. At most \(\tau\) exact LP calls therefore give the claimed \(\operatorname{poly}(m,\tau,N,L)\) bit complexity and an exact rational allocation.

No additional clarification or repair is needed. The empty display-math delimiters in the supplied text are cosmetic and do not obscure any definition or claim.

⟨structured verdict parsed — rendered above⟩