Answer: The promise guarantees a unique core allocation, and exact core search is polynomial-time solvable.
Theorem 15 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf a college-admissions problem satisfies the weak top- coalition property, then it has a unique core matching µ. Moreover, µ is the largest fixed point of T 2, and if k is the cardinality of the partition in Definition 3, then the algorithm finds µ in at most k steps.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many colleges \(C\), student types \(T\), rational masses \(\mu_t\), and rational affine type and college utilities over school and cohort composition, find a core allocation \(x\), where \(x_{tc}\geq 0\), \(\sum_c x_{tc}\leq\mu_t\), and each college's cohort vector is \(z_c=(x_{tc})_{t\in T}\). A block is a one-college deviation in which the college retains some current student mass and recruits available mass, forming a new cohort; each participating unit weakly prefers its new school and cohort to its current outcome, the college weakly prefers the new cohort, and the college or a positive mass of participants strictly prefers the deviation. Assume the colleges and the unit mass admit a finite ordered decomposition into top-coalition layers, with type mass divisible across layers, as in the continuous analogue of the paper's weak top-coalition property. Does this promise guarantee a unique core allocation, and can an algorithm find it?
Let \(C\) contain \(m\geq1\) colleges. A society is given by its support: the list of \(\tau\) student types with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length.
Type utilities are \(u_t(c,z)=a_{tc}+b_{tc}^{\mathsf T}z\), and college utilities are \(v_c(z)=d_c^{\mathsf T}z\), with arbitrary signed rational coefficients. Unmatched students have utility \(0\). Numerical utility comparisons define preferences, including indifference; there is no tie-breaking. Cohort coordinates are absolute masses, and there are no capacities.
An allocation has real entries \(x_{tc}\geq0\), with \(\sum_cx_{tc}\leq\mu_t\). Write \(z_c=(x_{tc})_t\), \(x_{t0}=\mu_t-\sum_cx_{tc}\), and \(u_t(0)=0\). Individual rationality requires \(u_t(c,z_c)\geq0\) whenever \(x_{tc}>0\), and \(v_c(z_c)\geq v_c(y)\) for every \(0\leq y\leq z_c\).
A one-college block chooses \(c\) and real masses \(0\leq y_{td}\leq x_{td}\) from origins \(d\in C\cup\{0\}\), forming \(q_t=\sum_dy_{td}\). For every \(y_{td}>0\), require \(u_t(c,q)\geq u_t(d,z_d)\), interpreting origin \(0\) as unmatched; also require \(v_c(q)\geq v_c(z_c)\). At least one comparison is strict, either for the college or for positive participant mass. Origin \(c\) supplies retained mass; other origins supply recruits. Expelled students and colleges losing recruits need not consent, and \(q=0\) is allowed. A core allocation is individually rational and has no such block.
The layer promise is defined on residual colleges \(D\subseteq C\) and residual masses \(r\). A college layer chooses \(c\in D\) and \(0\leq q\leq r\): \(q\) uniquely maximizes \(v_c\) over that box, and, for each \(q_t>0\), \((c,q)\) is the unique best outcome among unmatched status and all \((d,z)\) with \(d\in D\), \(0\leq z\leq r\), \(z_t>0\). Remove \(c\) and subtract \(q\) from \(r\).
An unmatched layer removes a nonzero vector \(0\leq q\leq r\) whose positive-mass types uniquely prefer unmatched status to every residual school outcome just described. Starting from \((C,\mu)\), some finite sequence of these layers exhausts all colleges and mass. College layers may have \(q=0\); types may be divided across layers. The sequence is promised to exist but is not supplied.
Does this promise guarantee a unique core allocation?
Is exact core search on these promised inputs, allowing an emptiness report, polynomial-time in \(m,\tau,L\), or NP-hard?
For finite students with strict preferences, ordered residual top-coalition layers guarantee a unique core matching, found in at most \(k\) iterations when there are \(k\) layers; this is an iteration bound rather than a bit-complexity bound for affine inputs. [Discrete result](https://feem-media.s3.eu-central-1.amazonaws.com/wp-content/uploads/NDL2005-120.pdf)
No result settling this exact continuous promise problem was identified in the literature search.
The promise guarantees exactly one core allocation, and exact core search is polynomial-time in \(m,\tau,L\). On promised inputs, the core is therefore never empty.
Moreover, in that unique allocation, every type is either entirely assigned to one college or entirely unmatched. The proof below gives an algorithm that discovers the layers without being supplied their sequence.
Write \(d_{ct}\) for coordinate \(t\) of the college vector \(d_c\). At a residual state \((D,r)\), let \(I=\{t:r_t>0\}\).
Because \(v_c(q)=\sum_t d_{ct}q_t\), its maximizer over \(0\leq q\leq r\) is unique if and only if \(d_{ct}\neq0\) for every \(t\in I\). When it is unique, it is necessarily
\[ q^c_t= \begin{cases} r_t,&d_{ct}>0,\\ 0,&d_{ct}<0, \end{cases} \qquad t\in I, \]
with \(q^c_t=0\) outside \(I\).
Indeed, each coordinate is optimized independently. A positive coefficient forces its upper endpoint, a negative coefficient forces zero, and a zero coefficient on a nondegenerate interval prevents uniqueness.
Consequently, a college layer removes all residual mass of every type it includes.
Call an unmatched layer *saturated* if it removes all residual mass of one type. Whenever a type satisfies the unmatched-layer preference condition, such a saturated layer is permitted.
We next show that greedily choosing these layers preserves the promise.
Throughout this section, “eligible” means satisfying precisely the layer conditions in the question.
Suppose \((D,r)\) admits an exhausting layer sequence, and \((c,q)\) is any eligible college layer at this state. Then an exhausting sequence exists whose first layer is \((c,q)\).
Proof. Let \(S=\{t:q_t>0\}\). Consider an exhausting sequence, and its layer removing \(c\).
Before that layer, no mass of any type in \(S\) can be removed. To prove this, suppose there were a first earlier layer removing positive mass of some \(t\in S\). Immediately before this first removal, \(c\) remains available and \(q\) remains feasible.
If the earlier layer is an unmatched layer, its condition gives \(0>u_t(c,q)\). But eligibility of \((c,q)\) gives \(u_t(c,q)>0\), a contradiction.
If it is a college layer \((e,p)\), then \(e\neq c\). Eligibility of the original layer gives \(u_t(c,q)>u_t(e,p)\), because \(p\leq r\) and \(p_t>0\). Eligibility of the earlier layer, with \((c,q)\) still available, gives the reverse strict inequality. This is again a contradiction.
Thus \(q\) remains feasible until \(c\) is removed. Since it uniquely maximizes \(v_c\) over the original box, it also uniquely maximizes over this smaller box. The layer removing \(c\) therefore uses exactly \(q\).
Move this layer to the beginning. Every layer formerly preceding it removes only types outside \(S\), so its cohort remains feasible. Its residual box and set of alternative colleges only shrink. A unique college maximum remains unique when the feasible set shrinks while retaining its maximizer; likewise, a unique best student outcome remains unique when alternatives are removed. Hence all those earlier layers remain valid.
After these reordered layers, the residual state is exactly the state following the original removal of \(c\). The remaining sequence is unchanged. This argument also covers \(q=0\), when \(S\) is empty. ∎
Suppose \((D,r)\) admits an exhausting sequence, and an active type \(t\) uniquely prefers unmatched status to every residual school outcome. Then an exhausting sequence exists beginning with removal of all \(r_t\) mass of type \(t\).
Proof. Every later residual school outcome is among the school outcomes available at \((D,r)\). Thus, whenever it contains type \(t\), its utility for that type is strictly negative.
No college layer in the exhausting sequence can include \(t\): its included types must strictly prefer its outcome to unmatched status. Therefore all mass of \(t\) is eventually removed through unmatched layers.
Remove all \(r_t\) first. In the original sequence, replace coordinate \(t\) of every unmatched removal vector by zero, omitting any resulting zero unmatched layer. Every college cohort is unchanged, because none included \(t\).
At every remaining layer, its cohort stays feasible, its residual box only shrinks, and its preference conditions remain valid. The modified sequence exhausts the residual problem. ∎
At each residual state:
On a promised state, some next layer exists. If that layer is unmatched, any positive-mass type in it is eligible for a saturated unmatched removal. Thus the algorithm always has a choice.
Lemmas 1 and 2 show inductively that every chosen layer leaves a promised residual state.
Each iteration removes a college or eliminates an active type. Hence there are at most \(m+\tau\) iterations. Furthermore, at every state, each residual coordinate is either \(\mu_t\) or zero.
Let \(X^*\) be the allocation constructed by this saturated sequence.
Fix any core allocation \(X\). We prove, in sequence order, that \(X\) must implement every layer of the greedy construction.
The induction invariant is that every previously removed college has its constructed cohort, and every previously removed type has all its mass at its constructed college or unmatched.
Consequently, each remaining college’s cohort in \(X\) lies in the current residual box \(0\leq z\leq r\). All mass of an active type originates at remaining colleges or unmatched status.
Consider the next college layer \((c,q)\). If its actual cohort \(z_c\) differs from \(q\), unique maximization gives \(v_c(q)>v_c(z_c)\).
For every \(t\) with \(q_t>0\), we have \(q_t=r_t=\mu_t\). Collect all mass of these types from their current origins, retaining any mass already at \(c\). This forms exactly \(q\).
Every positive participant strictly prefers \((c,q)\) to their current outcome: unmatched status is strictly worse, and any current school outcome is an available residual outcome distinct from \((c,q)\). The college also strictly improves. Thus this is an allowed block.
If \(q=0\), the same strict college improvement produces the permitted empty block.
Therefore \(z_c=q\). Every included type is entirely at \(c\), establishing the induction invariant for this layer.
Suppose the next layer removes all residual mass of type \(t\). Any remaining-school outcome containing \(t\) gives that type strictly negative utility.
If \(X\) assigned positive mass of \(t\) to a remaining college, that college’s cohort would lie in the residual box and contain \(t\), contradicting student individual rationality. Previously removed colleges have already been fixed and contain no active type.
Hence all mass of \(t\) is unmatched in \(X\).
The induction exhausts all colleges and types. Thus there is at most one core allocation, namely \(X^*\).
Every type assigned by a college layer strictly prefers its assigned outcome to unmatched status, so its utility is positive.
For a college layer \((c,q)\), every subcohort \(0\leq y\leq q\) also lies in that layer’s residual box. Maximization therefore gives \(v_c(q)\geq v_c(y)\). This is exactly college individual rationality.
Suppose a proposed block targets college \(c\), whose college layer has index \(k\), and forms cohort \(q\).
We first show that \(q\) cannot contain any type removed before layer \(k\).
Otherwise, choose a type in \(q\) whose removal layer has the smallest index, say \(j<k\). Because no type in \(q\) was removed before \(j\), the entire cohort \(q\) lies in the residual box at layer \(j\). College \(c\) is still present there.
If that type was removed by an unmatched layer, it strictly prefers its current unmatched status to \((c,q)\).
If it was assigned by a college layer, it strictly prefers its current layer outcome to \((c,q)\), since that earlier layer’s college differs from \(c\).
Either case violates the participant comparison required for a block.
Thus \(q\) lies in the residual box at college \(c\)’s own layer. Write \(q^c\) for its constructed cohort. The blocking college comparison requires \(v_c(q)\geq v_c(q^c)\). Unique maximization over that box forces \(q=q^c\).
Every type in \(q^c\) has all its mass already at \(c\). Hence positive participants can only be retained students, and their outcome is unchanged. The college’s utility is also unchanged. No required comparison is strict, so this is not a block.
This argument includes \(q=0\). Therefore \(X^*\) is a core allocation. Together with Section 3, it proves uniqueness.
It remains to justify that eligibility can be tested without quantifying computationally over a continuum.
Write \(b_{td,s}\) for coordinate \(s\) of \(b_{td}\). For an active type \(t\) and residual college \(d\), define
\[ M_{td}(r)=a_{td}+\sum_{\substack{s\in I\\ b_{td,s}>0}}b_{td,s}r_s. \]
This is the supremum of \(u_t(d,z)\) over \(0\leq z\leq r\), \(z_t>0\).
To verify this, maximizing over the closed box selects the upper endpoint of each positive-coefficient coordinate and zero for each negative-coefficient coordinate. The restricted domain \(z_t>0\) is dense in that box, so it has the same supremum.
The supremum is attained in the restricted domain if and only if \(b_{td,t}\geq0\):
Consequently, for any rational threshold \(H\), all these school outcomes have utility strictly below \(H\) exactly when
\[ M_{td}(r)<H \quad\text{or}\quad \bigl(M_{td}(r)=H\ \text{and}\ b_{td,t}<0\bigr). \]
If the supremum exceeds \(H\), some feasible outcome exceeds \(H\); if it equals \(H\), strict inequality everywhere holds precisely when the supremum is unattained.
An active type \(t\) is eligible exactly when, for every \(d\in D\),
\[ M_{td}(r)<0 \quad\text{or}\quad \bigl(M_{td}(r)=0\ \text{and}\ b_{td,t}<0\bigr). \]
When \(D\) is empty, this condition is vacuous.
First require \(d_{cs}\neq0\) for all active \(s\), and form the uniquely maximizing endpoint vector \(q^c\) from Section 1.
For every included type \(t\), set \(U_t=u_t(c,q^c)\). Check:
\[ M_{td}(r)<U_t \quad\text{or}\quad \bigl(M_{td}(r)=U_t\ \text{and}\ b_{td,t}<0\bigr). \]
Condition 2 is exactly the requirement that \(q^c\) uniquely maximize this student’s utility among outcomes at \(c\) containing type \(t\). If a coefficient has the wrong sign, moving that coordinate inward improves utility; if it is zero, such a movement gives a distinct tied outcome. When the varied coordinate is \(t\), the movement can be chosen small enough to keep it positive.
Conversely, the stated strict signs make every coordinate movement away from \(q^c\) weakly decrease utility, with a strict decrease for at least one changed coordinate. Hence every distinct feasible outcome at \(c\) is strictly worse.
Conditions 1 and 3 handle unmatched status and the other colleges. Therefore these tests are necessary and sufficient for college-layer eligibility. When \(q^c=0\), the student tests are vacuous.
Every residual mass is either its original input value \(\mu_t\) or zero. Each computed utility or supremum is a sum of at most \(\tau\) products of input rationals. These numbers therefore have polynomial bit length in \(\tau,L\), and all comparisons, including equality, can be performed exactly in polynomial time.
Testing all colleges and unmatched types at one state uses a polynomial number of rational operations; a loose bound is \(O(m^2\tau^2)\). There are at most \(m+\tau\) states requiring a choice. The total bit complexity is consequently polynomial in \(m,\tau,L\).
The output entries are all zero or original masses \(\mu_t\). No approximation or real-number oracle is needed.
Thus the stated promise yields a unique, nonempty core and a polynomial-time exact search algorithm.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes existence and uniqueness of the core allocation and gives an exact polynomial-time algorithm on promised inputs. I found no mathematical errors or gaps requiring repair.
The characterization of a unique college maximizer is correct.
For each active coordinate \(t\), the feasible interval is \([0,r_t]\) with \(r_t>0\). A positive coefficient \(d_{ct}\) uniquely selects \(r_t\), a negative coefficient uniquely selects zero, and a zero coefficient permits multiple maximizing values. Inactive coordinates are fixed at zero and impose no sign condition.
Thus every college layer takes all residual mass of each included type. This does not itself exclude partial unmatched removals in the promised sequence; the subsequent saturation argument correctly addresses that distinction.
The first-removal argument is valid.
Before the first earlier removal of any type in \(S=\{t:q_t>0\}\), all coordinates needed by \(q\) remain available, so \(q\) is feasible. The two possible earlier layers yield the stated contradictions:
Consequently, the original sequence retains \(q\) until it removes \(c\). Restricting the original box while retaining its unique maximizer preserves that maximizer, so the original removal of \(c\) indeed uses exactly \(q\).
Moving this layer first leaves every preceding cohort feasible because those cohorts contain no types in \(S\). Their alternative sets shrink, and their chosen outcomes remain available. Both college uniqueness and student unique-best conditions therefore persist.
The residual state after the reordered prefix agrees with the original state after removing \(c\). The argument also correctly covers \(q=0\).
This argument is also valid.
Every later school outcome containing the eligible type \(t\) belongs to its original residual comparison domain and has strictly negative utility. Hence no later college layer can include \(t\), since inclusion requires strict preference over unmatched status.
Removing all of \(t\) first therefore leaves every college cohort unchanged. Deleting the \(t\)-coordinate from subsequent unmatched removals preserves their conditions for every remaining participant. Omitting a resulting zero unmatched layer respects the requirement that unmatched removals be nonzero.
The modified residual boxes only shrink and retain each chosen cohort, so the remaining layer conditions persist.
The promise supplies an eligible next layer at every promised residual state. If an available layer is unmatched, each type appearing positively in it is eligible for saturated removal.
The two lemmas therefore justify arbitrary greedy choices. Each iteration removes either one college or all remaining mass of an active type, giving at most \(m+\tau\) iterations.
The assertion that every residual coordinate is either \(\mu_t\) or zero follows inductively from the endpoint form of college layers and the saturated unmatched removals.
The induction invariant is sufficient and correctly maintained.
Previously fixed types have all their mass at their prescribed college or unmatched. Previously fixed colleges have their entire prescribed cohort. Thus remaining colleges’ cohorts lie in the current residual box, and active types have no mass at previously removed colleges.
If a core allocation has \(z_c\neq q\), unique college maximization gives \(v_c(q)>v_c(z_c)\).
Every included type has \(q_t=r_t=\mu_t\). Collecting all its mass from its current origins therefore forms exactly \(q\), with recruitment and retention masses satisfying the block’s origin constraints.
For every positive participant:
The student comparisons are consequently strict, and the college comparison is strict as well. This is a valid block under the stated definition; expelled students need not consent.
When \(q=0\), the strict college improvement alone suffices for the explicitly permitted empty block.
Therefore every core allocation must have \(z_c=q\).
An eligible unmatched type receives strictly negative utility at every remaining-school outcome containing it. Any positive assignment of that type would violate student individual rationality. Previously fixed colleges cannot contain it.
Thus its entire mass must be unmatched.
The induction proves that every core allocation equals the constructed allocation. This establishes at most one core allocation without assuming existence.
Assigned types strictly prefer their prescribed layer outcomes to unmatched status, so student individual rationality holds.
For a constructed college cohort, every subcohort belongs to the residual box over which that cohort maximized college utility. Therefore the required inequality against every subcohort holds.
The earliest-removal argument is correct.
If a proposed blocking cohort contains any type removed before the target college’s layer, choose a participating type with the earliest removal index. Every type in that cohort was still fully available at that earlier state, so the entire proposed cohort lies in that state’s residual box. The target college was also still available.
The chosen type strictly prefers its current outcome to the proposed target outcome, whether its earlier removal was an unmatched layer or a different college layer. Its entire mass has that current origin in the constructed allocation. Positive participation therefore violates the required weak preference comparison.
Consequently, any blocking cohort must lie in the target college’s own residual box. The college’s weak improvement requirement and the uniqueness of its maximizer force that cohort to equal its constructed cohort.
All types in this cohort already have their entire mass at the target college. Participants can only be retained students, and all student and college comparisons are equalities. The required strict comparison is absent.
This also covers the empty cohort. Hence the constructed allocation is in the core.
Together with the preceding uniqueness argument, this establishes exactly one core allocation.
The formula for \(M_{td}(r)\) correctly gives the maximum over the closed residual box.
For an active type \(t\), the domain additionally requiring \(z_t>0\) is dense in that box. Affine utility is continuous, so the restricted domain has the same supremum.
The attainment criterion is correct:
Thus strict inequality below a threshold \(H\) holds everywhere precisely when the supremum is below \(H\), or equals \(H\) without being attained. The unmatched-type test correctly applies this with \(H=0\), including the vacuous case of no residual colleges.
The college coefficient test correctly determines whether its maximizer is unique and constructs its endpoint cohort.
For each included type, the strict sign agreement condition is necessary and sufficient for that endpoint cohort to be its unique best outcome at the same college:
The positivity test handles unmatched status, and the supremum tests handle every other residual college, including unattained equality cases.
When the college’s maximizing cohort is zero, no student conditions are required. This matches the promise exactly.
The bit-complexity argument is sufficient.
Residual masses remain original input masses or zero. Each utility or supremum is a sum of at most \(\tau\) products of input rationals, so its exact rational representation has polynomial bit length. Exact sign and equality comparisons therefore take polynomial time.
The stated loose bound of \(O(m^2\tau^2)\) rational operations per state accommodates testing all college candidates and unmatched types. Combining this with at most \(m+\tau\) iterations yields polynomial total bit complexity.
Output coordinates are zero or original masses, so the output itself has polynomial size.
The algorithm is justified on the promised input class. Since existence is proved throughout that class, it never needs an emptiness report there. No behavior outside the promise is needed to resolve the task.
No additional clarification or repair is required.
⟨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.