Welfare Direction under Short School Lists: Preference Information, Complexity, and Exact Bounds

This paper studies the number of strict gainers minus strict losers when student-proposing deferred acceptance expands from one acceptable school per list to two. Students, capacities, school priorities and the realized lottery are fixed, and reports are truthful acceptable prefixes of one common preference completion. The same first-choice record and known individual acceptable sets can support opposite welfare directions with the gainer count and enrollment increase fixed. A protected-entry construction relates attainable values to simple directed paths. Certifying nonnegative or positive direction for every completion is coNP-complete, and detecting opposite strict signs is NP-complete, already with unit school capacities. Under a common strict priority order, unit capacities and independently available stopping choices, exact extrema are computable by minimum-cost circulation. The paper also gives a conservative certificate for general capacities and an elicitation procedure along realized rejection chains. The results are finite-market theorems and analytic constructions. AI tools assisted with candidate derivations, internal mathematical review, and manuscript preparation.