Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
55,553 characters · 20 sections · 51 citation commands
Rank-heterogeneous preference models for school choice
\email{[email removed]} \email{[email removed]} \email{[email removed]} \email{[email removed]} \email{[email removed]}
\ccsdesc[500]{Information systems Rank aggregation} \ccsdesc[300]{Applied computing Economics}
Large school districts around the world employ school choice mechanisms to assign students to K--12 schools. In many of these systems, families submit ranked preference lists over school programs to their district, and the district in turn assigns children to schools via a centralized mechanism. School choice researchers employ discrete choice models, statistical models of choices made from slates of discrete options, to describe the preference-generation process by breaking a ranking into a sequence of choices from dwindling choice sets.
Such models are useful for explanation, indirectly identifying the most influential school characteristics in the decision-making of families, saving time and resources in surveying families. They can also be used for forecasting and planning potential changes in the district offerings. Finally, these models are also central to evaluating changes in school choice mechanisms themselves, as policymakers propose changes to assignment mechanisms with the hope of improving district outcomes. In the latter contexts, these models play a role in simulating preferences and assignments, and/or evaluating the resulting welfare of assignment under the proposed mechanism. Put simply, better preference models lead to better school choice analyses, and better analysis lead to better childhood educational outcomes.
The widely-used ranked preference models in this space, including the Plackett--Luce “exploded logit” model Plackett1968,Luce1977, model the process of constructing a preference ranking as a series of independent discrete choices (conditional multinomial logit (MNL) in the case of Plackett-Luce) based on school, program, and household attributes. While many such models are simple and interpretable, there is long-standing evidence in the discrete choice literature for ranking behavior that is {\it rank-heterogeneous}, meaning that the sequence of choices are driven by different considerations as individuals work down a preference list Chapman1982, Hausman1987, Fok2012. The criteria an agent uses for selecting top-ranked alternatives may differ from those at lower ranks, either due to true preference shifts or behavioral mechanisms such as decision fatigue.
In this work, we present and evaluate two strategies for incorporating rank-heterogeneity in choice models for school choice. One strategy achieves heterogeneity through a sequential dependence using context effects, while the other relies on regularized model stratification.
Context effects describe the influence of a particular decision context, including the available or previously-chosen options, on a individual's relative preferences between alternatives. We adapt a previous model of context effects, the context-dependent random utility model (CDM) Seshadri2019, to the school ranking setting. The CDM has been used to study ranked preferences Seshadri2020 by decomposing the ranking process as a series of choices in the context of the dwindling set of items yet to be chosen. We consider a variation of the CDM more natural to the school choice setting: modeling the ranking instead as a series of choices in the context of the already chosen items. Surprisingly, we show that the two modeling approaches (respectively, forward-dependence and backwards-dependence) are equivalent, and opt to use the latter variation when interpreting our results.
An alternative approach to inducing rank-heterogeneity is stratifying the modeling problem by rank position. Simply learning a series of independent models for each rank position, however, can split the data too finely and result in poor generalization. To avoid this pitfall, we apply Laplacian regularization Tuck2021 to the independent models, with carefully tuned regularization graphs that bring models of adjacent choices close together.
Incorporating context effects and model stratification are not mutually exclusive, and we also evaluate the combination of both approaches in our analysis. Moreover, we perform a series of ablation studies to demonstrate the independent contributions of each approach. We evaluate these new tools by modeling the preferences for the San Francisco Unified School District (SFUSD) kindergarten programs during the 2017-18 and 2018-19 assignment years. We find that the first strategy (context effects) dramatically lowers out-of-sample negative log likelihood, particularly on down-rank choices, when compared to rank-homogeneous models. The second strategy (model stratification) delivers more accurate prediction in top choices than a rank-homogeneous model---essentially, by modelling them separately---but otherwise does not appear to produce any significant improvements over the non-stratified baseline. Furthermore, we evaluate the performance of our context effect model against a nested MNL model and demonstrate sizable advantages in the school choice setting.
Section (ref) introduces notation and definitions used throughout the work. Section (ref) explains the SFUSD assignment system, its inputs and outputs, and summarizes the data we use for training and evaluation. In Section (ref), we describe the choice models studied in this work, presenting the backwards-dependent context-dependent model (CDM) and the stratified approach with Laplacian regularization. Section (ref) addresses identifiability of the models and details our model optimization framework. In Section (ref), we present and discuss the performance of our models; Section (ref) concludes.
The present work closely relates to various prior works that develop or apply preference models in school choice. Laverde Laverde2022 uses an MNL choice model to simulate counterfactual assignments in Boston in 2010--2013, quantifying the role of distance and unequal access on stated preferences. Agarwal & Somaini Agarwal2018 develop a procedure for estimating an MNL model in the presence of strategic reporting. Abdulkadiro\u{g}lu et al. Pathak2020 use MNL models to find links between preferences, school effectiveness and peer quality in New York City in 2003--2013. For an in-depth review of prior applications of preference models in school choice, see Agarwal & Somaini Agarwal2020.
Meanwhile, many works have studied the relative suitability of different choice models in school choice, evaluating accuracy and prediction errors of preference models. For example, Pathak & Shi Pathak2017 examine out-of-sample estimates for three models after a large-scale policy change in Boston. They develop several model evaluation metrics, and we adapt one to our work. Calsamiglia et al. Calsamiglia2020 similarly estimate a full choice system and evaluate it out-of-sample using administrative data from 2006 and 2007 school years in Barcelona.
Several prior efforts aim to understand preference heterogeneity between various demographic groups. For example, Laverde Laverde2022 estimates MNL models for White, Black, and Hispanic families by including indicator variables for these features in the chosen MNL utility. Hastings et al. Hastings2008 apply mixed-logit models McFadden2000 to data from Charlotte-Mecklenburg, North Carolina, learning separate model coefficients by race and SES status. In contrast to these examples of heterogeneity between groups, the present work focuses instead on preference heterogeneity within participants as they assemble their rankings.
Our idea is inspired by prior works in psychology, economics and marketing research, all of which cite inconsistent agent behavior in the assembly of rankings. Under the observation that individuals are generally more careful in reporting their top choices than lower ranked ones, Hausman & Ruud Hausman1987 model structured rank-heterogeniety through a common choice model with increasing variance as choosers proceed down the ranks, Chapman & Staelin Chapman1982 drop ranked alternatives after a threshold, and Allison & Christakis Allison1994 interact model covariates with indicators for early (top-4) or late (5+) rank choices. Our work extends this last idea by fully stratifying models by rank position of choice, interacting all model parameters with indicators for the first $k$ ranks. More on our stratification (and regularization) framework in Section (ref).
Finally, our work applies recent advances from the discrete choice and preference learning literatures to the school choice domain. The MNL model satisfies the axiom of independence of irrelevant alternatives (IIA), that the relative probability of selecting any item $j$ over another item $k$ from choice set $S$ is independent of the other items in $S$. However, this axiom is highly restrictive and often not representative of the true choice process Tversky1969, Tversky1993. We adopt strategies for going beyond the independence of irrelevant alternatives (IIA) assumption from Seshadri et al. Seshadri2019, in turn adapted from Batsell & Polking Batsell1985, extending that framework from a previously-studied forward-dependent model of ranking Seshadri2020 to backwards-dependent ranking. Other recent work extending the CDM include studies of salient features bower2020preference and feature-based context effects tomlinson2021learning; we leave the evaluation of such model extensions as future work. Further, we benchmark the performance of our approaches against the nested MNL model mcfadden1978modelling, which also goes beyond the restrictive IIA assumption, in Section (ref).
We begin by introducing our notation for viewing school choice through the lens of discrete choice. For a specific school year, let $\mathcal{U} \coloneqq [m] = \{ 1,...,m \}$ denote the universe set of all offerings, or alternatives, in the district, labeled 1 through $m$, and let $n$ be the number of students seeking assignment in the choice system. Throughout this work, we use “household” and “student” interchangeably to represent the decision-maker, as enrollment pertains to the student but rankings are often submitted by caretakers. Further, let $\text{PO}(\mathcal{U})$ denote the set of all partial orders on the alternatives in $\mathcal{U}$. A preference list $R_i\in \text{PO}(\mathcal{U})$ is household $i$'s partial ranking of the alternatives in $\mathcal{U}$, and we denote by $k_i\leq m$ the length of that ranking. The vector of observable covariates on student $i$ and offering $j\in\mathcal{U}$ are given by $x_{ij}$, containing demographic, socioeconomic, geographic, and performance-related information on the pair. Then, a school choice dataset, $(\mathcal{D}, X)$, is defined as the collection of all participating-household's partial rankings submitted to the district, $\mathcal{D}=\{R_1, ..., R_{n}\}$, and observed student-program covariates, $X\in\mathbb{R}^{n\times m \times d}$, where $x_{ij}$ is a length-$d$ vector of attributes pertaining to student $i$ and alternative $j$.
To learn a model of rank data, researchers typically transform rankings to choices and then apply discrete choice models such as the MNL, resulting in what is known (equivalently) as the rank-ordered logit Hausman1987, exploded-logit Punj1983, Chapman1982, or Plackett-Luce Plackett1968,Luce1977 model for rankings, which we present in Section (ref). The generality of converting rankings to choice is non-obvious, but the most powerful and widespread transformation is motivated by the theory of L-decomposable ranking distributions Critchlow1991,Luce1959 (L as in Left). A ranking distribution is said to be L-decomposable if the probability of observing ranking $R=(r_1,...,r_k)$ can be decomposed into probabilities of choices from dwindling choice sets, from most to least preferred: \[ P(R) = P(r_1|\{r_1,...,r_k\})P(r_2|\{r_2,...,r_k\})...P(r_{k-1}|\{r_{k-1}, r_k\}). \] This unraveling-from-the-left decomposition is sometimes also referred to as repeated selection Seshadri2020. In the present work, we apply repeated selection to ranking data throughout, simplifying the name of the ranking model to just the enlisted choice model employed after unraveling.
Encoding the unraveled choices as (agent, choice, choice set) triples, the rank data $\mathcal{D}$ then becomes a choice dataset, $D$:
where $r_{ij}$ is represents the $j$-{th} selection by agent $i$ on ranking $R_i$, and $S_{ij}\subseteq \mathcal{U}$ is the slate of available alternatives, or choice set, when choosing position $j$ of ranking $R_i$. The size of the resulting dataset is $|D| = \sum_{i\in[n]}k_i$.
To concretely illustrate the decomposition at the level of a data point, given a universe of alternatives $\mathcal{U}=\{a,b,c,d\}$, consider a dataset made up of one ranking, by agent $1$, $\mathcal{D}=\{R_1\}$, where $R_1=(b,d,c)$. Following Eq. (ref), the choice dataset becomes
In this section, we present the assignment process implemented within the San Francisco Unified School District (SFUSD) from 2014 to the present. SFUSD is made up of 130 schools with 150+ unique program offerings. Students enroll in these programs via an annual assignment lottery where families submit ranked preferences over available offerings to the district, and the district tries to honor family choices while satisfying capacity constraints. The algorithm performing this constrained assignment is the student-proposing deferred acceptance algorithm Gale1962. Participation may occur across all grade levels, but kindergarten enrollment is by far the largest participating group each year, making up over a third of all annual participants. As such, and following suit with many other studies of school choice, we focus solely on kindergarten assignment.
In the face of overly-demanded program seats, the district uses the following priority hierarchy to make assignments:
For each program, a student is considered in the highest priority category for which they qualify. Within each priority tier, ties are broken by next highest tier if applicable, or by a random number, $v_{ij}$, drawn uniformly at random for each student-school pair\footnote{This lottery design is known as the multiple tie-breaking rule (MTB) as students receive multiple values, one for each ranked school. By contrast, the single tie-breaking rule (STB) assigns a single lottery value to each student, used across desired schools. For more on the analysis of tie-breaking rules, see Abdulkadiroğlu2009,Haan2015,Ashlagi2019,Ashlagi2020.}.
Once all submitted preference lists have been exhausted by the matching algorithm, there may be students left without any assignment, for which the district administratively assigns these students to a program not on their list. In this work, as we are solely interested in modeling the preferences submitted by families in the first stage, such assignments fall outside the scope of our analysis.
To understand families stated preferences, we study data from both the 2017--18 and 2018--19 school years, principally training models on the 2017--18 data and evaluating out-of-sample on the 2018--19 data. We opted for this train--test split, following other work in school choice Calsamiglia2020, Pathak2017, to prevent data leakage. This split also mimics real use cases of school choice preference models, where models are used to simulate future years' outcomes.
Within each year, we collapse all three rounds of stated preference elicitation (instead of focusing only on the first and largest round), to better capture the full district demographics. We exclude programs that are newly offered the 18-19 school year, dropping 804 households from the test dataset, as our model's fixed effects do not extrapolate to never-before-seen alternatives. Handling these out-of-distribution preferences is a known limitation of the MNL class of models and an area of future work. Summary statistics for each school year's data are found in Table (ref).
The student-program covariates $X$ used in this work were selected by domain experts at SFUSD:
We consider the following school-specific features as well, modeled as interacting with the CTIP1-status of the student.
We acknowledge that additional attention to feature engineering can likely yield measurable performance improvements, but we consider the above features adequate and realistic for our purposes, namely evaluating the value of modeling rank-heterogeneity.
A choice model models probability distributions over subsets of a collection. More formally, let $\mathcal{S} = \{S : S\subseteq\mathcal{U}, |S|\geq2\}$ denote the set of all subsets of size at least two of a collection $\mathcal{U}$. Let $P(j|i,S)$ describe, for each agent $i\in[n]$ and each set $S\in \mathcal{S}$, the probability of agent $i$ selecting item $j$ from set $S$. Recall from Section (ref) that in the SFUSD school choice mechanism, $n$ households submit partial rankings $R_1, R_2, ..., R_{n}$ with student-program covariates $X$. Each partial ranking $R_i$ is decomposed into choices per Equation (ref), obtaining a dataset $D$ of choices.
We begin by considering a random utility model (RUM) of choice. The utility to agent $i$ of alternative $j$ in choice set $S$ is given by $$U(j|i,S) = V(j|i,S) +\epsilon_{ij},$$ decomposed into a part labeled $V$ that is known by the researcher up to some parameters, the representative utility, and an unknown part $\epsilon$ that is treated as random Train09. Under the assumption of independent Gumbel noise $\epsilon$, agent $i$'s probability of choosing alternative $j$ from choice set $S$ is given in closed form by
deriving the most ubiquitous RUM---especially in school choice---the conditional multinomial logit (MNL) Luce1959.
Taking the noise instead to be jointly Gumbel distributed with correlation yields variations on a mixed MNL McFadden2000 or nested MNL Train09 model, the latter featuring correlations across pre-specified clusters of alternatives. We benchmark our performance against a nested MNL model in Section (ref). Mixed MNL models have performed comparably to ordinary MNL in several prior school choice studies Hastings2008, Pathak2014, so we do not benchmark against it in this work.
Under the MNL model, the task of the researcher is to define a representative utility function, typically a parametric model, denoted $V_\theta$. We select our model from the chosen model class using regularized maximum likelihood, selecting parameters $\theta$ to minimize
where $\ell(D;\theta)$ is the negative log-likelihood (NLL) loss,
$r(\theta) = \lambda||\theta||_2$ is the $\ell_2$ penalty, and $\lambda$ is the regularization gain.
At this point, our task is to define the representative utility, $V$. Assigning inherent utilities to each alternative,
reduces the model to the basic Plackett-Luce model Luce1959. Here, $\delta\in\mathbb{R}^{\tilde m}$ where $\tilde{m} < m$ is defined as the number of unique schools plus the number of unique program-types offered in the district\footnote{Each alternative in the choice universe $j\in\mathcal{U}$ has an associated school, $s(j)$, and program type, $p(j)$. Example program types are general education, special education, and language program offerings. As such, our fixed effect $\delta_j$ is actually shorthand for $\delta_{s(j)}+\delta_{p(j)}$, reducing degrees of freedom while allowing our models to better generalize to new offerings at existing schools. We refer the interested reader to our code for the exact implementation.}, $\tilde{m} = n_s+n_p$. See Table (ref) for district summary statistics. We will refer to this model as the fixed-effect MNL.
Adding user-alternative specific covariates yields a linear MNL,
the most common utility structure in the school choice literature. Note that covariates contained in $x_{ij}$, detailed in the previous section, are indexed both by student and alternative; school- or program-specific features (only indexed by $j$) are absorbed into the fixed effects $\delta_j$, and student-specific features (only indexed by $i$) cancel out in the expression of the MNL choice probability, Eq. (ref).
As as auxiliary benchmark, we implement a nested MNL model, using the same expression of representative utility as the linear MNL in Eq. (ref), for benchmarking in Section (ref). In the nested MNL, alternatives are explicitly assigned to one of $K$ nests (non-overlapping subsets of $\mathcal{U}$), and choice probabilities are defined to be correlated within nests. See Appendix (ref) for full discussion and presentation of the nested MNL choice probabilities. The nests we implement in this work are ‘Chinese Language’, ‘Filipino Language’, ‘General Education’, ‘Japanese Language’, ‘Korean Language’, ‘Spanish Language’, and ‘Special Education’ offerings. Each nest is associated with a number of unique program offerings ---see Table (ref) for more details.
The fixed-effect and linear MNL models presented in this section satisfy IIA (see Section (ref)). As a result, they are rank-homogeneous, relying on a constant representative utility $V(j|i,S;\theta)$ for each alternative regardless of when the choice is being made in the ranking process. The contextual choice model that follows does not satisfy IIA and thus leads to rank-heterogeneous choice distributions.
The context-dependent model (CDM) Seshadri2020 is our first strategy for incorporating rank-heterogeneity into the traditional MNL models above. The CDM relaxes the strict IIA assumption, initially crafted to model “choice set effects” trueblood2013not whereby the slate of alternatives under consideration impacts the choice probabilities of the agent. We modify this modeling framework to suit the school choice sequential ranking problem. Specifically, under the standard CDM, each choice $j$ from choice set $S$ occurs within the context of the choice set $S$. For our purposes, we generalize this framework to consider the choices as occurring within the context of a generic and possibly different context set of alternatives, $A$.
The representative utility of this generalized CDM models context effects as a linear dependence between items, interpretable as “push” and “pull” factors, with items in $A$ pushing and pulling on each alternative in the choice set $S$, \[ V_\theta(j|i,A,S) = \delta_j + \beta^Tx_{ij} + \frac{1}{|A|}\sum_{k\in A}u_{jk}, \forall j \in S. \] When $A=S \setminus j$ we recover the standard CDM. The parameters $u_{ij}$ are defined for all $i,j\in\mathcal{U}$ where $i\neq j$. The generalized CDM has the same parameter complexity as standard CDM, requiring $m(m-1)$ parameters beyond the linear model, arranged in a matrix-like structure $U\in\mathbb{R}^{m\times m}$, with undefined diagonal. To reduce the parametric complexity of the model, $U$ can be factorized as the product of two low-rank matrices, $U=TC^T$ with $T,C\in\mathbb{R}^{m\times r}$ serving as target and context embeddings, respectively, analogous to word2vec-type methods mikolov2013. The low-rank CDM representative utility is then written as
We proceed with the factorized form of the CDM in this work. The low-rank CDM introduces a hyperparameter, in the form of the embedding dimension $r$; see Section (ref) for a discussion of hyperparameter tuning.
To accompany this change in model, the structure of the data described in Eq. (ref) must be generalized to include a generic context set for each choice, resulting in the following choice dataset
where $A_{ij}$ is the context set when agent $i$ chose item $j$. Table (ref) summarizes the representative utilities of the three models---the fixed-effect MNL, linear MNL, and CDM---and their parameters.
In the original formulation of the CDM for rankings Seshadri2020, the context set was assumed to be the choice set itself, $A=S\setminus j$, a formulation we refer to as the forward-dependent contextual ranking model.
Considering the generalized CDM above, we consider instead a model where the context set $A$ is the set of already-chosen alternatives. Equivalently, let $A=\mathcal{U}\setminus S$, the complement of the current choice set. We introduce this model as the backward-dependent contextual ranking model. Rather than modeling context effects between alternatives in the choice set, it measures how well each alternative fits with the choices already made. This conceptual shift is better suited to the psychology of the school choice selection process than the former framing, and yields a more interpretable model in ranking settings where choice sets are large, such as in school choice.
Considering these two different approaches to modeling rankings as a sequence of contextual choices, it seems as though these formulations constitute different model classes. However, we find that the forwards- and backwards-dependent CDM ranking model classes are in fact equivalent, and provide a bijection between the spaces of parameters for both the unfactorized and factorized models. See Appendix (ref) for proofs of Theorems (ref) and (ref).
In Section (ref), as a supplemental analysis, we consider results for truncated top-$k$-dependent context sets, $A_{ij}=\{r_{i1}, ..., r_{il}\}$ for $l=\min(k, j)$, to evaluate whether a more limited dependence (and thus, simpler model) performs as well as full backward-dependence. We find that even the truncated top-1 CDM---with knowledge only of the agent's first choice---makes considerable gains over the linear MNL model, but the full (top-$m$) backwards-dependent CDM exhibits the best performance.
It has been generically noted Chapman1982, Hausman1987, Fok2012 that the criteria individuals use for selecting top-ranked alternatives differs from those for lower-ranked alternatives, either due to decision fatigue or a true preference shift. As such, we consider the possibility of within-agent preference shift by stratifying the choice model by rank, and learning independent choice models at each rank position. A possible concern with this approach is that we end up with considerably less data for each model in this stratification, compared to estimating a single common model. To address this concern, we encourage models at neighboring ranks to be close to one another via Laplacian regularization, resulting in a Laplacian-regularized stratified model Tuck2021. The methods of Laplacian-regularized stratification are closely related to popular methods for smoothing ($\ell_2$) and trend filtering ($\ell_1$) in temporal kim2009ell1 and general graphical smola2003kernels,wang2015trend domains, where the underlying idea of parameter fusion dates back to at least the work of Land and Friedman land1997variable,tibshirani2005sparsity.
The stratification builds upon a base choice model---in this work, one of the three models summarized in Table (ref). Taking the number of strata to be $K$, a stratified choice model is then the composition of $K$ sub-models with parameters $\theta = \{\theta_1,...,\theta_K\}\in \mathbb{R}^{K\times N}$, where $N$ is the number of parameters in the chosen base model.
The $K$ models are regularized towards each other as dictated by an accompanying regularization graph Tuck2021. In our case, rank-based stratification lends itself well to a common “path graph” for regularization, where models of adjacent ranks are connected by edges and thus regularized towards each other. Laplacian regularization here is then defined as: $$ r_\mathcal{L}(\theta) = \lambda_\mathcal{L} \sum_{i=2}^K||\theta_{i}-\theta_{i-1}||_2^2, $$ where $\lambda_\mathcal{L}$ is a chosen Laplacian regularization strength, and $r_\mathcal{L}$ is convex in $\theta$. Compared to the non-stratified objective in Eq. (ref), the regularized, stratified objective function is the sum of $K$ decoupled model losses (each with a local $\ell_2$ regularization) and the Laplacian regularization term:
Regularized stratified models feature two additional hyperparameters over their base models, the number of strata $K$ and the Laplacian regularization gain $\lambda_\mathcal{L}$; see Section (ref) for a discussion of hyperparameter tuning.
We briefly discuss the identifiability of the presented models, alongside details about hyperparameter tuning and optimization. A model is identifiable if no two distinct sets of parameters, $\theta$ and $\theta'$, produce the same probability distributions over all choice sets $S\in\mathcal{S}$. Identifiability is crucial in settings where decisions are made based on interpreting parameter estimates. If the goal is solely to make decisions based on the resulting distributions only, e.g., from predictions or simulations, identifiability is not strictly necessary.
The traditional MNL family of ranking distributions are non-identifiable due to their shift-invariance. In this case, strategies for achieving identifiability are to fix one of the parameters, constrain their sum, or to apply regularization and obtain the minimum-norm parameter estimates Xia2019. In our work, we employ the latter strategy for the MNL and all other models, applying non-zero $\ell_2$ regularization, $r(\theta)$, in the objective function and achieving identifiability by obtaining the minimum norm solution.
The models in this work introduce additional hyperparameters; the low-rank CDM requires the selection of the embedding dimension $r$, and a stratified model is specified by $K$ and $\lambda_{\mathcal{L}}$; the number of strata and amount of Laplacian regularization, respectively. We tune these hyperparameters via 5-fold cross validation within our training dataset, selecting the values that minimize validation loss. Figures illustrating our search over these hyperparameters are found in Appendix (ref), with Table (ref) summarizing the chosen values. With hyperparameter values selected and regularization in place, the models are fully specified and we proceed to train our models on the full 2017--18 dataset for testing on the 2018--19 dataset.
We run Adam Kingma2014, implemented in PyTorch, with default parameters, $\text{lr} = 0.001$, $\beta = (0.9, 0.999)$, $\epsilon= 1e-8$, adding $\ell_2$ regularization with weight $\lambda= 1e-5$ in accordance with our hyperparameter selection for $\lambda$. Model parameters are updated over batches of training data until reaching $\texttt{max\_epoch}=1000$ or convergence, i.e., when the absolute difference in losses is less than $\epsilon=1e-4$. See Appendix (ref) for a discussion on the learned model parameters.
In this section, we evaluate and examine eight models---non-stratified and stratified versions of the fixed-effect MNL, linear MNL, CDM, and nested MNL models---trained on 2017--18 preference data and evaluated out-of-sample on 2018--19 data. We observe unique advantages of the context effects modeled by the CDM when benchmarked against the other models, and find that stratifying any model results in strictly (but marginally) better predictions, mostly for top (first) choices.
Figure (ref) depicts train and test negative log likelihood (NLL) losses on the left, and test losses disaggregated by rank on the right. We include a “null” model in the plots, representing uniform choices over programs, as a baseline reference point. We see that the CDM models, stratified or not, result in considerably lower test losses than the fixed-effect, linear, and nested MNL models overall. Stratifying provides modest decreases in overall test loss across all models.
On top choices, many families have priority access to one school in the district (e.g., sibling or PreK/TK priorities), and in most cases, rank these schools first. The linear and CDM models incorporate these priorities into the model, and therefore model top choices better than the fixed-effect model. The CDM leverages no additional information in the first choice as the context set is empty (i.e., no choices have been made). As such, there is negligible difference between the linear MNL and CDM models at position 1. However, after the relatively easy task of predicting top-choices, the CDM is able to leverage the choices made and separates itself from the lower-fidelity models. Stratifying yields a lower test loss for top choice across all three models, but quickly loses its advantage at lower ranks, likely due to diminishing training data at those positions (Cf.\ Table (ref), households rank fewer than 10 programs on average).
Recall from Eq. (ref) that the CDM utility differs from the linear MNL model via a sum of pairwise interactions between alternatives and a context set, $A$. Throughout this work, the context set is taken to be the set of all previously-chosen alternatives, which has a powerful equivalence in expressivity (Theorems (ref) and (ref)) to the standard CDM. As a robustness check, it is reasonable to ask which prior choices are most relevant to the context set. We evaluate several variations on the CDM model with the context being defined as the set of $k$ top alternatives. Specifically, the utility is given by Eq. (ref) with $A_{ij}=\{r_{i1},...,r_{il}\}$ for agent $i$'s $j$-th choice, where $l=\min(j,k)$. In other words, for choices made after position $k$, only the first $k$ choices constitute the context.
Figure (ref) presents the losses for these top-$k$-dependent CDM models. When $k=0$, the context set is always empty and the model is equivalent to the linear MNL. When $k=m$, the number of offered programs, we recover the backwards-dependent CDM considered everywhere else in this work. We find that even a minimal context set, e.g., the top-choice only ($k=1$), provides considerable improvement compared to the no-context linear model. That is, the information of what an agent chose first supplies the model with meaningful signal in making all down-rank predictions. That said, letting the context effect be linear in the full set of prior choices ($k=m$) has measurable advantages.
In Figure (ref), we show the pairwise interactions $U=TC^T$ estimated for the (non-stratified) backwards-dependent CDM. Element $u_{ij} = t_j^T c_i$ is the utility boost that program $j$ receives from chosen program $i$ being in the context set. In the heatmap, programs on the $x$- and $y$-axes were arranged first by program type and then by (descending) popularity within each. From top/left to bottom/right, the program types are General Education (65), Spanish Language (32), Special Education (27), Chinese Language (24), and Miscellaneous Language (6) programs.
We see significant block structure in the matrix, suggesting that the CDM primarily (but not only) uses the context set to learn program type affinities. For example, the third block along the diagonal corresponds to Special Education programs, where we see a strong positive context effect. That is, once a family has ranked a special education program, it becomes much more likely that the family will rank other special education programs. This model behavior is highly intuitive, and is also beyond the behavior of an MNL model or any other model assuming independence. Put simply, the CDM's use of context effects enables it to pick up on household signals, from the second choice and onward, that are otherwise not available a priori at the household level.
The block structure of $U$ may seem to suggest good performance from a nested MNL model, as the latter explicitly clusters similar programs. Instead, in Figure (ref) we find that the nested MNL shows only marginal gains over the linear MNL model and is not competitive with the CDM. This result sounds surprising, but is fairly intuitive; in models obeying IIA (such as the fixed-effect and linear MNL models), when an item is removed from the choice set, that item's probability is proportionally redistributed to the remaining alternatives for follow-up choices. The nested model instead allows the removed alternative’s probability to be non-proportionally distributed to the remaining items, specifically by favoring the alternatives in its nest (see Appendix (ref) for details). However, in this setting, the choice universe and nests are relatively large, so the impact of redistributing already-small choice probabilities is marginal.
To illustrate how choice probabilities are redistributed in different models, Figure (ref) showcases first- and second-choice probabilities by the non-stratified linear MNL, nested MNL, and CDM models over the special education subset for an example household in the district who first chose a special education program. We see that the CDM drastically alters its second-choice distribution, (correctly) boosting the likelihood of this household choosing another special education program, while the nested model's top- and second-choice distributions are almost indistinguishable. Special education programs are low-probability selections in the data at large, and the nested paradigm can only marginally influence future predictions when one such item is removed from the choice set. The CDM has a far greater ability to update its future distributions in the context of rare chosen items.
Beyond in- and out-of-sample goodness of fit, we now consider the prediction quality of the models on the test dataset. Specifically, we task the models with making a prediction at rank position $k$, conditional on the first $k-1$ choices made, resulting in an “accuracy in $k$th Prediction” evaluation metric.
Recall that $R_i$ denotes the true ranking of household $i$, where $r_{ij}$ is the $j$th item in the ranking for $j\leq k_i$. Let $R_{ik}$ be the set of their true top-$k$ choices, $R_{ik} = \{r_{i1}, r_{i2}, ..., r_{ik}\}$. Denote by $I_k=\{i : k_i\geq k\}$ the set of households who have ranked at least $k$ alternatives. Then, given a choice model, denote by $y_{ik}$ the modal prediction by the model at position $k$, i.e., the highest probability alternative over remaining programs, in the context of the previous $k-1$ choices, $A_{ik} = R_{i,k-1}$, $$ y_{ik}=\arg\max_{j\in S_{ik}}~V_\theta(j|i, A_{ik}, S_{ik}), $$ where the representative utilities $V(\cdot)$ are defined in Section (ref). The metric is then given by \[ \textbf{Accuracy in $k$th Prediction} = \frac{1}{|I_k|}\sum_{i\in I_k} 1(y_{ik}=r_{ik}). \]
Figure (ref) summarizes model performances on this metric. The CDM models are significantly more accurate in making down-rank predictions when given earlier choices, which is precisely the use-case of the contextual model. Stratification leads to improvements in down-rank predictions made by the fixed-effect MNL model, but has limited effect on the linear, nested and CDM models. It appears to learn that if a household has not already ranked the most popular programs, they wont be adding them later, as seen in Figure (ref) of Appendix (ref). Doing so, it outperforms its non-stratified counterpart beyond position 5.
We can also disaggregate these accuracies by sub-populations of interest, see Appendix (ref). We find that the groups receiving sibling and PreK/TK priorities have top choices that are relatively easy to predict, as their preferences are concentrated on their (typically singular) priority schools. All models generally under-perform on CTIP1, Hispanic/Latino, and Black student populations, relative the broader population, for one of two reasons: either the subgroups demonstrate more varied preferences than other subgroups, or the training data was relatively small. Lastly, we see in Figure (ref) that the CDM specializes in predicting down-rank choices for households with non-mainstream initial preferences.
In this work, we introduce rank-heterogeneous preference modeling for school choice and present two strategies, discrete choice context effects via a backwards-dependent CDM, and model stratification by rank position. Rank-heterogeneous models have the potential to leverage already-chosen alternatives when making down-rank predictions, or to broadly capture evolving household values down a ranking. We define and evaluate several metrics, finding that incorporating context terms in the utility dramatically decreases test loss over the linear and nested MNL models, capturing signals not present in covariates alone while also seeing particular improvements in modeling rare choices. The contextual model also generates more accurate predictions for list-completion tasks. Stratifying by rank yields improvements in top-choice accuracy across all models, but otherwise does not result in significant improvements or additional predictive power down-rank.
While rank-heterogeneous models enable school choice researchers to improve predictions and perform counterfactual analysis, our methods do not come without limitations. For one, the increased parametric complexity of the CDM and regularized stratification strategies raises, albeit mildly, model training times and data requirements relative to the MNL. Recent developments to the CDM tomlinson2021learning mitigates this problem by leveraging the model's block structure and learning interactions between program attributes rather than the programs themselves. Applying this work to the school choice setting would reduce complexity while uncovering context effects, a promising direction for future work. Another limitation stems from our model failing to generalize to new program offerings with undefined fixed-effects. Here, applying strategies for out-of-distribution prediction---such as establishing a prior on the fixed-effects of new program offerings based on the values for similar offerings---provide further directions for future work. Despite these limitations, we strongly encourage school choice researchers to consider rank-heterogeneous models in their preference modeling tasks for improved down-rank and rare-event prediction.
{{\bf Reproducibility.}} The SFUSD data used in this work is not public, but implementations of all models as well as notebooks used to generate plots in this paper are available at: \url{https://github.com/ameloa/rankingmodels}.