CS Paper Radar

Rules, Choice, and Chance: A Welfare Evaluation Framework for Student-School Matching

Reetahan Mukhopadhyay, Clara Strasser Ceballos, Augustin Plantureux, Christoph Kern, Julia Stoyanovich

cs.CY ·submitted 2026-11-08 17:40 UTC · v1
code/data

Abstract

Centralized student-school matching systems, adopted in the United States, Chile, the Netherlands, and the United Kingdom, assign students to schools based on their submitted preference rankings and schools' priority policies. Yet welfare in these systems is typically measured through a narrow lens: a few aggregate statistics published by education authorities, such as the share of students unmatched or assigned to a top-ranked choice. A single aggregate cannot reveal how outcomes vary across students, or why. Welfare depends on three interacting forces: the rules policymakers set (algorithm, tie-breaking, list length limits); the choices students make (which and how many schools to rank); and chance (lottery draws and students' residential location). A rule that reduces unmatched rates may simultaneously lower top-ranked assignment rates for specific groups, and evaluating such trade-offs in advance is challenging because individual-level preference data are rarely available. We present Trace (Trade-offs in Rules, Agency, Chance, and Equity), an open-source framework that synthesizes individual-level preference profiles from aggregate data using mixtures of Mallows models and evaluates alternative rules across multiple welfare metrics, disaggregating outcomes by choice and chance. We apply Trace to two real-world systems: NYC high school matching, where we study minimum list length requirements, and Chilean school assignment, where we compare the current multiple tie-breaking rule with a counterfactual single tie-breaking rule. Both reveal substantial, heterogeneous welfare trade-offs, underscoring the value of simulation-based evaluation before implementing school choice reforms.

Comment
42 pages, 26 figures, with 14 page main section

Closest papers

Nearest neighbours by meaning across the whole index.

The Double-Edged Sword of Information: Revealed versus Hidden Lotteries in School Choice

cs.GT cs.LGecon.TH ·2026-09-28 ·Parinaz Naghizadeh, Jingyan Wang
unusual similarity 0.70
Abstract

In school choice, a lottery number is often used by the matching mechanism to break ties when there are more students who prefer the same school than the number of seats available. There has been growing theoretical and empirical interest in understanding the impact of revealing the lottery number to students. In practice, in recent years, the NYC Public Schools started revealing the lottery number to students to improve transparency. Theoretical findings from prior literature also suggest that revealing the lottery number strictly improves the number of matches under the deferred acceptance algorithm. However, these theoretical results are based on the over-simplifying assumption that all students share the same preference ranking for schools. In this work, we relax this assumption and allow students to have heterogeneous preference rankings. Under a game-theoretic model where student strategies form a Bayesian Nash equilibrium, we characterize scenarios where revealing the lottery number can either improve or worsen the matching outcome, measured by two metrics of match rate and social welfare. We further consider revealing partial information about the lottery, and demonstrate non-monotonic effects in the amount of information available to students. These results together illustrate complex tradeoffs induced by the lottery revealing policy.

0.28

Personalized Recommendations Without Inducing Congestion: Mitigating Disparities in the NYC High School Match

cs.CY econ.GN ·2026-10-06 ·Erica Chiang, Kenny Peng, Rebecca Lichtenstein, Brielle McDaniel, Kristen O'Neil +5 more
similarity 0.67
Abstract · Preliminary version in ACM EC 2026

Algorithmic recommendations can help participants navigate large matching markets. For example, recommendations for school and college choices may reduce information frictions and disparities in access to high-performing programs. At scale, however, recommenders in capacity-constrained settings can be self-defeating: if they steer too many users toward the same items, then even users who were originally predicted to have a high chance of matching to an item may not, due to increased competition. In this paper, we formalize this phenomenon of recommendation-induced congestion; motivated by the NYC high school match, we show that naive recommendations can cause sharp decreases in program acceptance rates, most affecting applicants with the fewest nearby options. Next, we propose and theoretically analyze a congestion-aware, bilevel optimize-and-simulate approach to allocate recommendations and improve match outcomes safely, in equilibrium. Finally, we deploy this approach in the 2025-26 admissions cycle of the NYC high school match, aiming to reduce disparities by highlighting personalized lists of nearby, high-performing programs where an applicant has a high predicted offer likelihood. In a randomized controlled trial, we find that 16.4% of treatment applicants ranked a recommended program, versus 10.5% of control applicants who ranked a program they would have been recommended (57% relative increase; $p$=0.011); 5.6% of treatment applicants matched to such a program, versus 3.3% of control applicants (71% relative increase; $p$=0.071); further, no treatment applicant was rejected from a recommended program. Our findings suggest that recommenders should be analyzed and designed as market-shaping interventions.

0.32

Fairness and Non-wastefulness in Matching with Siblings and Initial Enrollments: Compatibility and Complexity

cs.GT ·2026-10-01 ·Haris Aziz, Gergely Csáji, Zhaohong Sun, Makoto Yokoo
similarity 0.60
Abstract

We study a two-sided matching problem between families and daycare centers in which a family may have multiple children with joint preferences, and some children may already be enrolled in daycare centers while seeking transfers. Our model combines and generalizes two well-studied matching frameworks: matching with couples and school choice with initial enrollments. The interaction between joint family preferences and initial enrollments creates fundamental challenges for the existence of desirable outcomes and the design of computationally efficient algorithms. Since stable matchings need not exist, we decompose stability into individual rationality, fairness, and non-wastefulness, and study the trade-off between fairness and non-wastefulness from two complementary directions. To preserve non-wastefulness, we first consider master-list-based approaches and show that they are insufficient in the presence of initial enrollments. We then introduce \emph{resettlement}, which protects displaced families by allowing them to return to their initial assignments, and develop a greedy improvement algorithm that establishes the existence of matchings satisfying non-wastefulness together with resettlement-based fairness. To preserve fairness, we first examine a generalized cutoff approach and then develop a fairness-preserving non-wasteful algorithm that guarantees fairness together with a relaxed notion of non-wastefulness. We further characterize the computational complexity of these solution concepts. While several fairness notions can be verified in polynomial time, deciding whether a non-wasteful matching satisfying them exists is NP-complete. Resettlement restores universal existence, but computing resettlement-based outcomes is PLS-hard, and verifying the stronger dominance-based fairness notion is coNP-complete.

0.18

Characterizing Predictive Multiplicity in Ranking and Its Fairness Implications

cs.LG ·2026-11-11 ·Ainhize Barrainkua, Mikel Malagón
similarity 0.54
Abstract · 32 pages, 6 figures

Prediction problems often admit competing models that achieve comparable performance yet produce conflicting outputs, a phenomenon known as predictive multiplicity. While this challenge has been extensively studied in classification tasks, its implications remain largely unexplored in ranking frameworks, which are critical for high-stakes societal decisions such as the allocation of welfare resources and social assistance. This paper investigates the phenomenon of predictive multiplicity in score-based ranking problems. We introduce formal definitions to capture multiplicity in ranking settings, supported by foundational theoretical guarantees. Furthermore, we examine the dual relationship between predictive multiplicity and algorithmic fairness in ranking problems: we analyze how model multiplicity can act as a potential source of unfairness, while demonstrating how exploring this decision space provides a principled avenue for discovering less discriminatory rankings. Finally, we complement our theoretical contributions with insightful empirical evaluations on both synthetic and real-world datasets, validating our analytical findings and illustrating their practical implications. Taken together, this work highlights the real-world relevance of predictive multiplicity in ranking and sheds light on the potential of leveraging this effect to achieve fairer outcomes.

0.16

Fair Stable Matching: A Nash Social Welfare Approach

cs.GT cs.AI ·2026-09-02 ·Parth Desai, Rasheed M, Ganesh Ghalme, Sujit Gujar
similarity 0.53
Abstract

While traditional stable matching algorithms, such as the Gale-Shapley algorithm, prioritize stability, they may fall short of achieving equitable outcomes among participants. We study the role of \emph{Nash social welfare} (NSW) as a fairness objective in the classic \emph{stable marriage problem}. We develop \texttt{SNSW-Alg} that finds a stable matching that maximizes Nash social welfare under rank-induced utilities in $\tilde{\mathcal{O}}(n^4)$ time, where $n$ is the number of men or women. We demonstrate that \texttt{SNSW-Alg} balances equity while preserving stability. We empirically evaluate our methods across diverse preference distributions, demonstrating significant gains in fairness without substantial losses in other key measures such as regret, egalitarian criterion, and sex equality. Our findings suggest that the stable matching produced by \texttt{SNSW-Alg} is statistically Pareto-undominated by stable matchings based on other fairness measures - regret, egalitarian, and sex equality. This study offers compelling insights for designing fair-stable matching.

0.23

Compatibility Matters: A Framework for Token-Level Teacher Selection in On-Policy Distillation

cs.LG ·2026-10-15 ·Stanley Wei, Jiin Woo, Kaan Ozkara, Youngsuk Park
theory similarity 0.53
Abstract

On-policy distillation (OPD) has recently been introduced as a promising paradigm for continual learning, where a student policy can be supervised at the token-level. Typically, OPD is performed using a single teacher per prompt rollout (or even per training run). However, this ignores a whole other axis of flexibility that is available due to the on-policy nature - token-level teacher selection during rollouts. Building on this insight, we theoretically explore what makes a teacher and a student compatible for OPD, and leverage our findings to derive several empirical heuristics for teacher selection. In particular, our framework captures several desiderata for OPD: compatible teacher-student reasoning patterns, teacher competence, and induced student diversity. Theoretically, we categorize several types of teacher routing schemes, and we prove that under different scenarios, different routing schemes are likely to be beneficial for optimization and student diversity. We back up our findings with extensive experimental results in domains such as math, coding, kernel generation, and visual reasoning, where we find upwards of 10 percentage points of improvement on pass@$k$ when compared to vanilla OPD and the teacher experts on certain tasks, indicating both capability improvement and diversity over high-quality responses.

0.13

Actionable Insights from Observational Data: The Case of Advanced Classes in K-12 Education

cs.LG ·2026-09-20 ·Nabit Bajwa, Seth B. Hunter, Sanmay Das
published similarity 0.51
Abstract

A fundamentally challenging question in K-12 education is about the effects of taking more advanced or challenging classes. It is particularly complex because students (and/or their parents) choose whether to enroll in these classes, making causal analysis challenging. In this paper, we begin to tackle this question by taking advantage of a novel dataset from a public school system in the US. This dataset records students' course enrollment decisions, prior academic histories, demographics, and subsequent outcomes around the time of a district-wide change that introduced optional open-enrollment advanced middle-school courses in subject areas. This is a rich observational dataset, but enrollment in advanced classes is driven by student characteristics and choices rather than random assignment. This creates a core identification challenge: the same factors that influence enrollment in advanced courses are also predictive of academic outcomes. As a result, simple comparisons between enrolled and non-enrolled students are confounded, and naive estimates may reflect underlying differences in student ability, motivation, or support rather than the impact of coursework itself. Our analysis shows that enrolling in advanced English courses has a net positive but modest effect on student achievement outcomes. However, these benefits are unevenly distributed: some students with relatively large predicted gains ("middle achievers" in prior years) are less likely to enroll than others. Some other groups (e.g. Black students and those with lower socio-economic status) also demonstrate significantly lower propensity to enroll. This gap between predicted benefit and observed enrollment illustrates how careful data analysis can extract actionable insights from large observational datasets, including identifying students who appear well-positioned to benefit but do not select into advanced options.

0.40

Top Trading Cycles with Indifferences under Matroid Constraints

cs.GT econ.TH ·2026-09-26 ·Yasushi Kawase
theory similarity 0.50
Abstract

We study the reallocation of indivisible objects among agents who may hold initial endowments and may be indifferent between objects. Each agent has her own set of admissible objects, and a matroid constraint specifies which combinations of assigned objects are feasible. The model contains the housing market, house allocation with newcomers who hold no endowment, and the assignment of students to schools under matroidal constraints at each school. For this model, we introduce the top-class trading cycles mechanism (TCTC), which extends the top trading cycles mechanism (TTC) to matroid constraints and weak preferences. When a trading cycle is selected, TCTC fixes each agent's top indifference class rather than a specific object and postpones the choice within the class to the end. TCTC is individually rational, Pareto efficient, and weakly group-strategy-proof on the full domain of weak preferences, and it runs in polynomial time. When preferences and reports are strict, TCTC is strongly group-strategy-proof. Together with a known impossibility result, our theorem establishes a maximal domain of school-by-school constraints for individual rationality, Pareto efficiency, and strategy-proofness.

0.07