Answer: \(\mathrm{P}\)
Corollary 4 — class: algorithmic
Given a fixed course set \(C\), a finite set \(T\) of applicant types, rational type masses \(\mu_t\) summing to \(1\), and per-capita course capacities \(\kappa_c\), each type specifying a complete course preference ordering with ties and an individual quota, take as input a feasible allocation \(x_{t,S}\) of each type’s mass to acceptable, quota-feasible integral bundles \(S\). Is there a reassignment that preserves each type’s mass, respects every course capacity, gives each reassigned mass a bundle weakly preferred to its current bundle, and gives a positive mass a strictly preferred bundle?
Let \(C\) be an input course set with \(m=|C|\). A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Courses have no preferences and have nonnegative binary-rational per-capita capacities \(\kappa_c\).
Each type \(t\) has an integer quota \(0\le b_t\le m\) and a complete weak ordering of its acceptable subset \(A_t\subseteq C\), represented by ordered indifference classes \(D_{t,1},\ldots,D_{t,r_t}\). Its feasible bundles are \(\mathcal B_t=\{S\subseteq A_t:|S|\le b_t\}\), including the empty bundle; each course occurs at most once in a bundle.
Define \(\chi_t(S)=(|S\cap D_{t,1}|,\ldots,|S\cap D_{t,r_t}|)\). Bundle preference compares these vectors lexicographically: \(U\succ_t S\) means \(\chi_t(U)>_{\mathrm{lex}}\chi_t(S)\), and \(U\succeq_t S\) also permits equality, without breaking ties.
The input allocation explicitly lists its positive binary-rational entries \(x_{t,S}\), with unlisted entries zero, satisfying \(\sum_{S\in\mathcal B_t}x_{t,S}=\mu_t\) and \(\sum_t\sum_{S\ni c}x_{t,S}\le\kappa_c\). Let \(K\) be the number of listed entries and \(L\) the total input bit length.
A reassignment consists of nonnegative real masses \(z_{t,S,U}\), indexed by \(S,U\in\mathcal B_t\), satisfying \(\sum_U z_{t,S,U}=x_{t,S}\), \(z_{t,S,U}=0\) unless \(U\succeq_t S\), and \(\sum_t\sum_{S,U:c\in U}z_{t,S,U}\le\kappa_c\). It improves the allocation if \(\sum_t\sum_{S,U:U\succ_t S}z_{t,S,U}>0\); all feasible destination bundles are allowed, including bundles absent from the input allocation.
Is deciding whether an improving reassignment exists in \(\mathrm P\), with running time polynomial in \(m,\tau,K,L\), or is it NP-hard?
For finite applicants with these bundle preferences, testing Pareto optimality of a given matching is polynomial-time solvable ([source](https://arxiv.org/pdf/1507.02866)). No result settling the exact mass-reassignment problem above was identified in the literature search.
Result. Deciding whether an improving reassignment exists is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,K,L\).
The key is to partition destinations according to the first indifference class at which they improve upon their source bundle. Each part has an integral polytope of course marginals. These polytopes yield an exact, polynomial-size linear program.
1. An integrality lemma. Let \(A\) be a finite set partitioned into classes \(D_1,\ldots,D_r\). For integer bounds \(\ell_h,u_h\) and an integer \(b\), define
\[ P=\left\{v\in[0,1]^A:\ \ell_h\le\sum_{c\in D_h}v_c\le u_h\text{ for every }h,\quad \sum_{c\in A}v_c\le b\right\}. \]
Every vertex of \(P\) is integral. Consequently, if \(P\) is nonempty, it is the convex hull of the incidence vectors of subsets satisfying these cardinality constraints.
*Proof.* Suppose a vertex \(v\) has a fractional coordinate, meaning a coordinate strictly between \(0\) and \(1\).
If some class contains two fractional coordinates, increase one and decrease the other by the same sufficiently small positive amount. Both signs of this perturbation preserve all class sums and the total sum, and remain within the coordinate bounds. Thus \(v\) is the midpoint of two distinct feasible points, contradicting extremality.
We may therefore assume that each class contains at most one fractional coordinate. Any class containing such a coordinate has a noninteger sum, since its other coordinates are integral. Its sum consequently equals neither of its integer bounds: both class inequalities have positive slack.
If there are fractional coordinates in two different classes, perturb them in opposite directions by the same sufficiently small amount. The total sum remains unchanged, and the affected class inequalities remain satisfied because they have positive slack. Again \(v\) is not a vertex.
Finally, if there is exactly one fractional coordinate, the total sum is noninteger and therefore cannot equal the integer \(b\). The total-quota inequality and the affected class inequalities all have positive slack. Perturbing this coordinate slightly in either direction again contradicts extremality.
Hence every vertex is integral. The convex-hull assertion follows because a nonempty bounded polyhedron is the convex hull of its vertices. \(\square\)
2. Partitioning the permitted destinations. Index the listed positive allocation entries by \(i\in\{1,\ldots,K\}\). Write their types, source bundles, and masses as \(t_i,S_i,x_i\). Set
\[ a_{i,h}=|S_i\cap D_{t_i,h}|,\qquad r_i=r_{t_i},\qquad A_i=A_{t_i},\qquad b_i=b_{t_i}. \]
For each entry \(i\), define the following families of destination bundles:
There are no further restrictions on classes after \(j\), beyond bundle feasibility.
By the definition of lexicographic comparison, these families are disjoint and satisfy
\[ \{U\in\mathcal B_{t_i}:U\succeq_{t_i}S_i\} =\bigcup_{j=0}^{r_i}F_{i,j}. \]
Indeed, equal characteristic vectors give branch \(0\). Otherwise, the first differing coordinate must increase, giving its unique branch \(j\). Every bundle in branch \(0\) is indifferent to \(S_i\), and every bundle in a positive-index branch strictly improves upon \(S_i\).
Let \(P_{i,j}\) be the polytope obtained by replacing the bundle-incidence coordinates in the definition of \(F_{i,j}\) with real coordinates \(v_c\), imposing \(0\le v_c\le1\) and \(\sum_{c\in A_i}v_c\le b_i\).
Each \(P_{i,j}\) has exactly the form of the integrality lemma. For unrestricted classes use bounds \(0\) and \(|D_{t_i,h}|\); for fixed counts use equal lower and upper bounds; for the improving class use lower bound \(a_{i,j}+1\) and upper bound \(|D_{t_i,j}|\). All these bounds and the quota are integers. Thus, whenever this polytope is nonempty,
\[ P_{i,j}=\operatorname{conv}\{\mathbf1_U:U\in F_{i,j}\}. \]
This identity guarantees that its fractional coordinates are realizable as marginals of a distribution over actual feasible bundles.
3. A polynomial-size linear program. For each \(i\) and \(j\in\{0,\ldots,r_i\}\), introduce a nonnegative variable \(\lambda_{i,j}\), representing the mass sent through branch \(j\). For every \(c\in A_i\), introduce \(y_{i,j,c}\), representing the mass in that branch assigned course \(c\).
Impose the following constraints:
\[ \sum_{j=0}^{r_i}\lambda_{i,j}=x_i\qquad\text{for every }i. \]
\[ 0\le y_{i,j,c}\le\lambda_{i,j}\qquad\text{for every }i,j,c\in A_i, \]
\[ \sum_{c\in A_i}y_{i,j,c}\le b_i\lambda_{i,j}\qquad\text{for every }i,j. \]
\[ \sum_{c\in D_{t_i,h}}y_{i,0,c}=a_{i,h}\lambda_{i,0} \qquad\text{for every }i,h. \]
\[ \sum_{c\in D_{t_i,h}}y_{i,j,c}=a_{i,h}\lambda_{i,j} \qquad\text{for every }h<j, \]
\[ \sum_{c\in D_{t_i,j}}y_{i,j,c}\ge(a_{i,j}+1)\lambda_{i,j}. \]
\[ \sum_{i:\,c\in A_i}\sum_{j=0}^{r_i}y_{i,j,c}\le\kappa_c \qquad\text{for every }c\in C. \]
Maximize the objective
\[ M=\sum_{i=1}^{K}\sum_{j=1}^{r_i}\lambda_{i,j}. \]
The program is feasible: put all source mass in branch \(0\), setting \(\lambda_{i,0}=x_i\) and \(y_{i,0,c}=x_i\mathbf1_{\{c\in S_i\}}\), with all other variables zero. The input allocation’s feasibility verifies all constraints.
Also, \(0\le M\le\sum_i x_i=1\), and all variables are bounded by their source masses. Therefore an optimum exists.
4. Exact equivalence with reassignment. We prove that the LP objective is exactly the attainable strictly improving mass.
*From a reassignment to the LP.* For a listed source entry \(i\), define
\[ \lambda_{i,j}=\sum_{U\in F_{i,j}}z_{t_i,S_i,U}, \qquad y_{i,j,c}=\sum_{U\in F_{i,j}:\,c\in U}z_{t_i,S_i,U}. \]
The destination families partition all permitted destinations. Therefore the source-mass equality holds. Each destination contains each course at most once and has size at most \(b_i\), giving the course and quota bounds. Its branch membership gives the class-count constraints. Summing course marginals gives precisely the reassignment’s course consumption, so capacities hold.
Finally, positive-index branches contain exactly the strictly preferred destinations. Thus \(M\) equals the strictly improving mass of the reassignment.
*From the LP to a reassignment.* Consider any feasible LP solution. If \(\lambda_{i,j}=0\), the course bounds force \(y_{i,j,c}=0\) for every \(c\). This branch contributes no mass.
If \(\lambda_{i,j}>0\), define \(v_c=y_{i,j,c}/\lambda_{i,j}\). Dividing the branch constraints by \(\lambda_{i,j}\) shows that \(v\in P_{i,j}\). By the proved convex-hull identity, there are finitely many bundles \(U_q\in F_{i,j}\) and weights \(\alpha_q\ge0\), with \(\sum_q\alpha_q=1\), such that
\[ v=\sum_q\alpha_q\mathbf1_{U_q}. \]
Send mass \(\lambda_{i,j}\alpha_q\) from source \(S_i\) to destination \(U_q\). Combining these contributions over all branches defines the reassignment.
For each source entry, its outgoing mass is \(\sum_j\lambda_{i,j}=x_i\). All destinations are weakly preferred, and the resulting course consumption is exactly the LP’s course marginal sum, hence respects every capacity. For unlisted sources set all outgoing masses to zero, as required by their zero input mass.
Every positive-index branch sends all its mass to strictly preferred destinations; branch \(0\) sends none to such destinations. Consequently, the resulting reassignment has strictly improving mass exactly \(M\).
Therefore,
\[ \text{an improving reassignment exists}\quad\Longleftrightarrow\quad M^*>0, \]
where \(M^*\) is the LP optimum.
5. Polynomial running time. Empty indifference classes, if present in the representation, can be deleted without changing preferences. Thus \(r_i\le m\). The LP has at most
\[ K(m+1)(m+1) \]
variables and \(O(K(m+1)^2+m)\) constraints.
Its coefficients, apart from the input rational right-hand sides, are integers of absolute value at most \(m+1\). The right-hand sides are the explicitly supplied masses \(x_i\), capacities \(\kappa_c\), and zeros. Hence the LP’s binary encoding length is polynomial in \(m,\tau,K,L\).
The standard polynomial-time theorem for rational linear programming computes the optimum exactly in time polynomial in this encoding length. Its hypotheses hold here: the LP has rational data and a nonempty bounded feasible region. Exact rational comparison of \(M^*\) with zero therefore decides whether an improving reassignment exists, even when the improvement is arbitrarily small.
⟨structured verdict parsed — rendered above⟩
The claimed polynomial-time result is correct. The LP represents exactly the permitted reassignments and their strictly improving mass. No major or minor mathematical issues were found.
The perturbation proof is valid and covers every possible fractional vertex:
Each case contradicts extremality. The passage from integral vertices to the convex-hull identity correctly uses the stated theorem that a nonempty bounded polyhedron is the convex hull of its vertices. Boundedness follows from the coordinate bounds.
Inconsistent cardinality bounds simply produce an empty polytope, which the statement handles. An empty ground set causes no difficulty.
The families form precisely the claimed disjoint partition.
An equal characteristic vector belongs to branch \(0\). Any strictly larger lexicographic vector has a unique first differing coordinate, and that coordinate increases by at least one because its entries are integers. Conversely, the restrictions defining a positive-index branch guarantee strict lexicographic improvement regardless of later coordinates.
Each branch polytope satisfies the integrality lemma’s hypotheses: the classes partition the acceptable set, all cardinality bounds and quotas are integers, and coordinate bounds are imposed. Consequently, its convex-hull identity is justified whenever it is nonempty.
The LP correctly scales each branch’s marginal polytope by its assigned mass:
The proposed source-preserving solution is feasible because each source belongs to its indifferent branch and the input allocation respects capacities.
Nonnegativity and source-mass conservation give \(0\le\lambda_{i,j}\le x_i\). The coordinate bounds then give \(0\le y_{i,j,c}\le x_i\). Thus the feasible region is closed, bounded, and nonempty, so an optimum exists. The objective bound \(M\le1\) follows from the total input mass.
Both directions are rigorous.
For reassignment to LP, summing destination masses and course incidences within each branch preserves source masses, branch constraints, capacities, and the strictly improving mass. Unlisted sources have zero outgoing mass because their nonnegative outgoing entries sum to zero.
For LP to reassignment, a zero-mass branch necessarily has zero course marginals. For a positive-mass branch, division by its mass yields a point in the corresponding branch polytope. The proved convex-hull identity supplies an actual distribution over feasible destination bundles with exactly those marginals.
Combining these distributions preserves source masses and capacities. The objective equals strictly improving mass because precisely the positive-index branches contain strictly preferred destinations.
Empty branch families cannot receive positive LP mass: such mass would, upon normalization, yield a point in their empty polytope. This also rules out spurious improvement from infeasible branches.
Therefore the equivalence between existence of an improving reassignment and \(M^*>0\) is established.
After deleting empty classes, \(r_i\le m\). The stated variable and constraint bounds are valid, including the constraints for all pairs of branch indices and earlier classes.
The LP can be constructed directly from the listed sources and preference classes. Its dimensions, coefficient bit lengths, and rational right-hand-side bit lengths are polynomial in the specified input parameters. Even an explicit dense encoding remains polynomial in those parameters.
The invoked rational-LP theorem is stated sufficiently precisely for this application: exact optimization takes polynomial time in the binary encoding length. The constructed LP has rational data and a nonempty bounded feasible region, satisfying its stated hypotheses. Exact comparison with zero therefore handles arbitrarily small positive improvement.
Zero quotas, empty acceptable sets, zero capacities, and absence of any feasible improving branch are all covered by the construction. No additional argument is required for these cases.
No repair or additional clarification is needed.
⟨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.