Answer: polynomial-time solvable
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe time complexity of DA-OT is O(|X|3), where X is the set of all contracts.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite schools \(C\), overlapping labels \(T\), complete applicant types \(\Theta\) containing membership sets, strict preferences, and priority blocks at every school, rational masses \(\mu_\theta\), and per-capita bounds \(\bar q_c\) and \(\bar p_{c,t}\), compute the mass assignment \(x_{\theta,c,t}\) produced by DA-OT: schools first accept highest-priority proposal mass up to each \(\bar p_{c,t}\), then fill capacity up to \(\bar q_c\), splitting mass when a quota cuts through a type block. Determine whether this stable, student-optimal assignment is computable in time polynomial in the compressed input size and rational bit length.
Let \(C\) be finite schools and \(T\) overlapping labels. Each complete applicant type \(\theta\in\Theta\) has rational mass \(\mu_\theta\), a nonempty membership set \(\tau(\theta)\subseteq T\), and a strict preference over eligible contracts \((c,t)\) with \(t\in\tau(\theta)\). Each school strictly orders the contract-type priority blocks \((\theta,c,t)\); mass within a block is indistinguishable. All contracts are acceptable.
Each school has rational capacity \(\bar q_c\) and soft reserves \(\bar p_{c,t}\), with \(\sum_t\bar p_{c,t}\leq\bar q_c\) and \(\sum_c\bar q_c\geq\sum_\theta\mu_\theta\). Its choice rule first retains the highest-priority proposed mass for each \(t\), up to \(\bar p_{c,t}\), then retains the highest-priority remaining proposed mass up to total capacity \(\bar q_c\). A quota may split a block. Each unit of mass occupies at most one contract, so membership in several labels does not fill several reserves.
In student-proposing DA-OT, rejected mass proposes to its next preferred contract; schools reconsider held and new proposals by this choice rule. Let \(x_{\theta,c,t}\) be the resulting assignment mass.
Is exact computation of \(x_{\theta,c,t}\) from the compressed rational input in polynomial time, or is it NP-hard?
For finite individual applicants, DA-OT computes the student-optimal stable matching in \(O(|X|^3)\) time, where \(X\) is the contract set. Continuum deferred acceptance has also been studied with adaptive priority rules, but that result uses a different school choice rule.
Exact computation is polynomial-time solvable in the compressed rational input. The key is to replace each contract by two consecutive alternatives—reserve and open—and apply the strongly polynomial algorithm for stable allocation in ordered polymatroid intersection. The proof below verifies that this computes the specified DA outcome.
1. Scaling and the expanded contracts
Let \(E_0\) be the set of eligible contract-type blocks, and write \(e=(\theta,c,t)\).
Choose a common denominator \(D\) for all masses, capacities, and reserves. Set
\(m_\theta=D\mu_\theta,\qquad q_c=D\bar q_c,\qquad p_{c,t}=D\bar p_{c,t}.\)
These are nonnegative integers. Taking the product of the input denominators suffices, so their binary encoding lengths are polynomial in the input length. Scaling commutes with every choice operation.
For each \(e\in E_0\), introduce two coordinates \(e^R,e^O\). Replace each applicant preference list
\(e_1\succ_\theta e_2\succ_\theta\cdots\)
by
\(e_1^R\succ_\theta e_1^O\succ_\theta e_2^R\succ_\theta e_2^O\succ_\theta\cdots.\)
Let \(E\) denote this expanded ground set. Thus \(|E|=2|E_0|\).
Write \(E_\theta\) for the coordinates belonging to type \(\theta\), \(E_c\) for those belonging to school \(c\), \(R_{c,t}\) for its reserve coordinates of label \(t\), and \(O_c\) for its open coordinates.
The expanded feasibility constraints are
\(z(E_\theta)\le m_\theta\quad(\theta\in\Theta),\)
\(z(E_c)\le q_c\quad(c\in C),\qquad z(R_{c,t})\le p_{c,t}\quad(c\in C,\ t\in T),\)
together with \(z\ge0\). Here \(z(A)=\sum_{a\in A}z_a\).
Each school ranks all reserve coordinates above all open coordinates. Within either class, it uses its original strict block priority. It chooses greedily in this order, respecting its displayed capacity constraints.
The applicant constraint counts both versions together. Consequently, the expansion does not duplicate applicant mass.
2. The expansion preserves deferred acceptance
We first establish this independently of any polynomial-time algorithm.
Temporarily interpret the scaled population as \(m_\theta\) individual copies of each type. This potentially enormous expansion is used only for the proof. Within each block, break priority ties by increasing copy index, consistently throughout.
Tag each contract currently held in original DA as reserved or open according to its school’s two-stage choice. We claim that an original school update can be simulated by expanded DA, with these tags indicating which version is held.
Suppose a school receives new original proposals. Let \(B\) comprise these proposals and its previous holdings.
The following invariant holds before the update:
Submit each new proposal first to its reserve version. Reserve proposals are considered before all open proposals. Moreover,
\(\sum_t p_{c,t}\le q_c,\)
so total school capacity never prevents a reserve selection that satisfies all label reserve bounds.
It follows that the new reserve holdings are precisely the highest-priority \(p_{c,t}\) proposals of each label in \(B\), or all such proposals if fewer exist. Indeed, previous open holdings cannot improve this reserve selection: whenever such holdings exist, the previous reserve was already full with higher-priority proposals.
Now send every rejected reserve proposal—including displaced reserve holdings—to its immediately following open version. Together with previous open holdings, these are exactly the proposals in \(B\) remaining after reserve selection. Greedy open selection therefore retains their highest-priority members up to
\(q_c-\sum_t z(R_{c,t}).\)
This is exactly the original second stage.
For completeness, intermediate open rejections cause no discrepancy. Reserve holdings never decrease in number: each label retains its highest-priority proposals up to a fixed bound, and reserve choices are unaffected by open proposals. Thus residual open capacity never increases. Adding further open proposals cannot rescue an already rejected open proposal. We may therefore finish all reserve-to-open transitions before advancing any open rejection to its next original contract.
This proves the invariant inductively and simulates every original DA update. A unit advances to its next original contract exactly when its open version is rejected. Hence, if \(d\) is the expanded DA allocation, the original scaled outcome satisfies
\(D x_{\theta,c,t}=d_{e^R}+d_{e^O}.\)
The same argument applies to block batches: the aggregate choice depends only on their counts. It therefore also applies directly to the rational-mass DA in the question.
3. The expanded constraints are two polymatroids
For a normalized, nondecreasing, submodular function \(g:2^E\to\mathbb R_{\ge0}\), write
\(P(g)=\{z\in\mathbb R_{\ge0}^E:z(A)\le g(A)\text{ for every }A\subseteq E\}.\)
Define the applicant rank function by
\(h(A)=\sum_{\theta:\,A\cap E_\theta\ne\varnothing}m_\theta.\)
This is a weighted coverage function, hence normalized, nondecreasing, and submodular. Its polymatroid is exactly
\(P(h)=\{z\ge0:z(E_\theta)\le m_\theta\text{ for every }\theta\}.\)
For each school, define
\(f_c(A)=\min\!\left\{q_c,\ q_c\mathbf 1_{\{A\cap O_c\ne\varnothing\}}+\sum_t p_{c,t}\mathbf 1_{\{A\cap R_{c,t}\ne\varnothing\}}\right\},\qquad A\subseteq E_c.\)
The expression inside the minimum is another weighted coverage function. Truncation at \(q_c\) preserves monotonicity and submodularity. In this particular formula, this can be checked directly: adding a coordinate contributes zero if its class is already represented; otherwise it contributes the smaller of its class weight and the remaining distance to \(q_c\). This marginal contribution cannot increase when the starting set grows.
We claim that
\(P(f_c)=\{z\ge0:z(E_c)\le q_c,\ z(R_{c,t})\le p_{c,t}\text{ for every }t\}.\)
The forward implication follows by applying the rank inequalities to \(E_c\) and each nonempty \(R_{c,t}\). For the reverse implication, consider any \(A\subseteq E_c\).
Taking the direct sum,
\(f(A)=\sum_c f_c(A\cap E_c),\)
gives precisely all expanded school constraints.
Finally, choose a total order \(\succ_H\) on \(E\) by concatenating the expanded applicant lists, and choose a total order \(\succ_F\) consistent with every expanded school order. The instance is now a pair of totally ordered polymatroids,
\((E,h,\succ_H)\quad\text{and}\quad(E,f,\succ_F).\)
4. The algorithmic theorem and the relevant stability condition
Iwata and Yokoi give an algorithm that computes a stable allocation for two totally ordered polymatroids in \(O(n^3\gamma)\) time, where \(n\) is the ground-set size and \(\gamma\) is the time for a saturation or exchange-capacity calculation. For integer-valued rank functions its output is integral. Their output \(y\) also dominates every stable allocation \(z\) in every prefix of the first order:
\(y(\{a:a\succeq_H b\})\ge z(\{a:a\succeq_H b\})\quad(b\in E).\)
See the algorithmic bound and Theorem 7.7 in [Iwata–Yokoi, *Finding a Stable Allocation in Polymatroid Intersection*](https://www.keisu.t.u-tokyo.ac.jp/data/2017/METR17-02.pdf).
It remains essential to identify this output with expanded DA.
In the ordered-polymatroid definition, a side is willing to increase coordinate \(e\) if it can either increase that coordinate alone or increase it while decreasing a strictly worse coordinate. Stability means that no coordinate has both sides willing.
For our constraints, unwillingness has a useful explicit certificate:
A side is unwilling to increase \(e\) if and only if some displayed capacity set \(S\) containing \(e\) is tight and every positive coordinate in \(S\) is ranked at least as high as \(e\).
Here the applicant capacity sets are \(E_\theta\); the school capacity sets are \(E_c\) and \(R_{c,t}\).
To prove the characterization, note that all capacity sets containing a fixed coordinate form a chain. If none is tight, a sufficiently small increase is feasible. Otherwise let \(S\) be the smallest tight set containing \(e\). If \(S\) contains a positive, strictly worse coordinate \(v\), increasing \(e\) and decreasing \(v\) by a sufficiently small common amount preserves every tight constraint. It also preserves all initially slack constraints when the amount is small enough. Conversely, a tight set containing only coordinates ranked at least as high as \(e\) prevents both kinds of improvement.
This proves the characterization, including boundary cases involving zero capacities.
5. Why the computed optimum is exactly expanded DA
We supply the finite-to-compressed identification to avoid assuming that an arbitrary stable allocation suffices.
First, consider the finite expanded instance from Section 2. Each school’s feasible sets form a matroid: take the direct sum of uniform matroids on the reserve classes and the free matroid on open contracts, then truncate at \(q_c\).
We use the following finite DA fact, with its proof.
Finite DA lemma. With unit-demand applicants and greedy ordered-matroid choices on the receiving side, applicant-proposing DA is stable and gives every applicant its best contract among all stable outcomes.
For a greedy matroid choice \(G\), a contract is rejected from a set exactly when that set contains a circuit in which the contract has lowest priority. Thus rejection persists as the offered set grows. Also, deleting rejected contracts does not change a greedy scan. Consequently,
\(G(G(A)\cup B)=G(A\cup B).\)
DA holdings therefore equal the choice from cumulative proposals. At termination every contract an applicant prefers to its assignment has been rejected, which proves stability.
To prove optimality, fix a stable outcome \(M\). At each school, let \(B\) contain its contracts in \(M\) and every contract applicants prefer to their assignments in \(M\). Stability and the displayed identity imply \(G(B)=M_c\): adding any one of these desired contracts leaves \(M_c\) unchanged, and hence so does adding all of them.
Suppose a contract belonging to \(M\) is rejected for the first time. Before that rejection, every proposal belongs to \(B\), since an applicant cannot reach a contract worse than its assignment in \(M\) without first having that assignment rejected. Rejection persistence would then reject the same contract from \(B\), contradicting \(G(B)=M_c\). No contract of \(M\) is ever rejected. Each applicant’s DA assignment is therefore at least as good as its assignment in \(M\). This proves the lemma.
This argument does not require a school’s choice on hypothetical proposal sets to enforce applicant unit demand; actual DA holdings satisfy unit demand because only unheld applicants propose.
We next relate finite stable outcomes to compressed stable allocations.
Aggregation. The aggregate vector of any stable finite expanded outcome is stable for the two compressed polymatroids.
Otherwise some coordinate \(e\) would have both sides willing. Applicant willingness supplies a copy assigned below \(e\), or unmatched. School willingness permits adding one unit at \(e\), possibly removing a contract from a strictly lower-priority block. The amount can be one because all capacities and allocations are integral. This produces a blocking contract in the finite instance, a contradiction.
Lifting. Every integral compressed stable allocation \(z\) can be realized as a stable finite expanded outcome.
For each type, assign copies in increasing index order to its expanded contracts in decreasing preference order, using the prescribed counts \(z_e\); leave remaining copies unmatched.
Suppose copy \(i\) wants a contract in block \(e\). The applicant side is then willing to increase \(e\) at \(z\). Compressed stability supplies a school certificate \(S\) from Section 4: \(S\) is full and all its occupied blocks rank at least as high as \(e\).
Every copy actually assigned to block \(e\) has smaller index than \(i\), by the construction. Thus all contracts filling \(S\) have strictly higher finite priority than the proposed contract of copy \(i\). The school rejects that proposal. No blocking contract exists, proving the lifting claim.
Now let \(d\) be the aggregate expanded DA outcome, and let \(y\) be the Iwata–Yokoi output.
The vector \(d\) is compressed stable by aggregation. Therefore the algorithm’s optimality gives, for every prefix \(P\) of \(\succ_H\),
\(y(P)\ge d(P).\)
The vector \(y\) is integral, so lift it to a finite stable outcome. The finite DA lemma says that each copy weakly prefers its DA assignment to its assignment in this lift. Consequently, for every prefix of every expanded applicant list, the DA count is at least the count under \(y\).
Because \(\succ_H\) concatenates those lists, summing these inequalities gives
\(d(P)\ge y(P)\)
for every prefix \(P\) of \(\succ_H\). Thus all prefix sums coincide. Taking differences of consecutive prefix sums yields
\(d=y.\)
Combined with Section 2, this proves that the required output is exactly
\(x_{\theta,c,t}=\dfrac{y_{e^R}+y_{e^O}}{D}.\)
6. Polynomial complexity on the compressed input
No finite population expansion is performed by the algorithm.
For either constructed polymatroid, write its explicit constraints as \(z(S)\le b_S\). Saturation capacity at coordinate \(u\) is
\(\widehat c(z,u)=\min_{S:\,u\in S}(b_S-z(S)).\)
For distinct coordinates \(u,v\), feasible exchange capacity is
\(\overline c(z,u,v)=\min\!\left\{z_v,\ \min_{S:\,u\in S,\ v\notin S}(b_S-z(S))\right\},\)
where an empty inner minimum is \(+\infty\).
These formulas follow directly by substituting \(z+\alpha\mathbf 1_u\) and \(z+\alpha(\mathbf 1_u-\mathbf 1_v)\) into the explicit inequalities and nonnegativity constraints.
After discarding empty sets, there are \(O(|E|)\) constraints with \(O(|E|)\) total incidences. Each oracle calculation therefore takes \(O(|E|)\) arithmetic operations by direct summation. The cited algorithm consequently uses \(O(|E|^4)\) arithmetic operations with this straightforward implementation.
The scaled integer data have polynomial binary length, and these are explicit polynomial-bit capacity oracles for a strongly polynomial algorithm. Hence the computation has polynomial bit complexity as well. Division by \(D\) gives the exact rational output.
The finite-applicant runtime alone would not establish this conclusion: its population expansion can be exponentially large. The ordered-polymatroid reduction supplies the required algorithm on compressed blocks.
⟨structured verdict parsed — rendered above⟩
The prover’s argument establishes polynomial-time exact computation of the specified DA-OT outcome from the compressed rational input. I found no major or minor mathematical issue requiring repair. Crucially, the proof identifies the algorithm’s output with the DA outcome, rather than merely producing an arbitrary stable allocation.
A common denominator obtained by multiplying the input denominators has polynomial binary length. The scaled masses, capacities, and reserves consequently also have polynomial binary length. Multiplication by this denominator commutes with the comparisons, additions, and quota truncations in the school choice rule.
The applicant constraint counts reserve and open coordinates together, so the construction does not duplicate mass. Placing the two versions consecutively in each preference list is essential: rejection from the reserve version leads to the open version before any less preferred original contract.
The inequality \(\sum_t p_{c,t}\leq q_c\) ensures that total capacity cannot obstruct reserve selection within the individual label bounds. Ranking all reserve coordinates before all open coordinates therefore implements the first stage of the original rule.
The invariant concerning previous open holdings justifies omitting those holdings from new reserve proposals: whenever an open holding of a label exists, that label’s reserve is already full of higher-priority holdings. Adding proposals can improve the reserve selection but cannot make a previous open holding newly eligible for it.
Reserve rejections and displaced reserve holdings subsequently enter the open stage. The remaining capacity and priority order agree with the original second stage.
The treatment of intermediate rejections is also valid. Reserve occupancy cannot decrease, and therefore open capacity cannot increase. Together with the addition of competing open proposals, this prevents an intermediate open rejection from being reversed. Deferring its next original proposal until the reserve-to-open transitions finish is consequently legitimate.
The argument operates on counts within strictly ordered blocks. The finite-copy interpretation therefore agrees with the rational batch operations after scaling; it is not being used as a polynomial-size implementation.
The applicant rank function is a nonnegative weighted coverage function. Its inequalities give exactly the displayed per-type capacity constraints.
The school rank function is a truncated weighted coverage function. The supplied marginal-contribution argument verifies submodularity, including zero weights and the truncation boundary.
Both directions of the asserted school-polytope equality are valid. Sets containing an open coordinate receive rank \(q_c\); reserve-only sets are bounded by the applicable label capacities and total capacity. Empty reserve classes impose only vacuous inequalities.
Direct sums preserve the required rank-function properties. The proposed total orders exist because the applicant lists are disjoint across types and the school lists are disjoint across schools.
I checked the cited paper. Theorem 6.6 supplies the stated capacity-oracle running time; the paper states integrality for integer-valued ranks; and Theorem 7.7 gives dominance over every stable allocation in every prefix of the first order. Its Definition 1.1 agrees with the willingness condition used here. These are the properties needed by the reduction. [Iwata–Yokoi, *Finding a Stable Allocation in Polymatroid Intersection*](https://www.keisu.t.u-tokyo.ac.jp/data/2017/METR17-02.pdf)
The constructed functions are normalized, nondecreasing, submodular, and integer-valued after scaling. Both orders are total, and Section 6 supplies the relevant oracles. Thus the application has no missing hypothesis.
For a fixed coordinate, the displayed capacity sets containing it form a chain. If none is tight, a sufficiently small increase is feasible.
Otherwise, the smallest tight containing set controls whether an exchange with a worse occupied coordinate is possible. The exchange described in the proof preserves every tight containing constraint; constraints containing only the decreased coordinate become weaker. Finitely many initially slack constraints permit a sufficiently small positive exchange.
Conversely, a tight containing set with no worse occupied coordinate prevents either permitted improvement. This includes zero-capacity sets, whose lack of positive coordinates makes the certificate vacuously valid.
The receiving-side feasibility system is a matroid: the reserve classes and open class form the stated direct sum, followed by truncation.
The circuit characterization of greedy rejection is valid, including loops caused by zero capacities. It establishes rejection persistence. Removing rejected elements leaves the greedy choice unchanged, supporting the displayed identity for cumulative proposals.
The stability argument correctly uses cumulative rejections. The optimality argument also closes: stability of the comparison outcome makes each individually desired additional contract rejected; the choice identity permits combining those additions. A first rejection of a contract in that outcome would then contradict rejection persistence.
The observation about applicant unit demand is appropriate. The proof does not mistakenly require the school’s matroid to impose that constraint on hypothetical proposal sets.
In aggregation, applicant willingness supplies an actual copy that prefers the proposed coordinate. School willingness supplies a feasible addition or exchange against a strictly worse block. Integrality permits a unit move. Strict block priorities ensure that the selected applicant copy would generate a blocking finite contract.
In lifting, assigning smaller-index copies to better contracts is the necessary compatibility condition with the fixed priority refinement. Whenever a copy wants a block, all copies already assigned to that block have smaller indices. The school’s tight-set certificate therefore consists entirely of contracts strictly above the proposed finite contract, including occupants of the same block. This validates rejection and establishes finite stability.
Aggregation makes the finite expanded DA vector \(d\) eligible for the algorithm’s prefix-dominance guarantee, giving \(y(P)\geq d(P)\).
Integrality permits lifting \(y\). The finite DA lemma then gives applicant-by-applicant dominance of DA over that lift, hence dominance on every individual preference prefix.
A prefix of the concatenated applicant order consists of complete earlier lists and a prefix of one further list. The stated summation therefore yields \(d(P)\geq y(P)\). Equality of all prefix sums determines every coordinate, proving \(d=y\).
The final projection and division by \(D\) consequently recover the requested original assignment masses.
The saturation formula accounts for precisely the constraints tightened by increasing a coordinate. The exchange formula additionally includes the nonnegativity bound on the decreased coordinate and only those capacity sets containing the increased coordinate but not the decreased one.
Each coordinate belongs to only a constant number of displayed constraints. Thus the asserted linear total incidence count and linear arithmetic cost per oracle call are valid, yielding the stated \(O(|E|^4)\) arithmetic bound.
Polynomial-length scaling and the strongly polynomial algorithm with these explicit capacity oracles support polynomial bit complexity. No exponentially large finite population is constructed.
Zero masses, zero capacities, zero reserves, empty eligible classes, and unmatched mass do not invalidate the argument. It does not assume that aggregate school capacity alone guarantees every applicant can be assigned.
No additional mathematical clarification is needed to make the conclusion verifiable.
⟨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.