Gabrielle Fack
email: gabrielle.fack@dauphine.fr

Julien Grenet
email: julien.grenet@ens.fr

Yinghua He
email: yinghua.he@gmail.com

Nikhil Agarwal

Peter Arcidi- Acono

Eduardo Azevedo

Estelle Cantillon

Yeon-Koo Che

Jeremy Fox

Guillaume Haeringer

Yu-Wei Hsieh

Adam Kapor

Fuhito Kojima

Jacob Leshno

Thierry Magnac

Ariel Pakes

Mar Reguant

Al Roth

Bernard Salanié

Orie Shelef

Xiaoxia Shi

Matt Shum

Xun Tang

Olivier Tercieux

Beyond Truth-Telling: Preference Estimation with Centralized School Choice and College Admissions

Keywords: Gale-Shapley Deferred Acceptance Mechanism, School Choice, College Admissions, Stable Matching, Student C78, D47, D50, D61, I21 Gale-Shapley Deferred Acceptance Mechanism, School Choice, College Admissions, Stable Matching, Student

We propose novel approaches to estimating student preferences with data from matching mechanisms, especially the Gale-Shapley Deferred Acceptance. Even if the mechanism is strategy-proof, assuming that students truthfully rank schools in applications may be restrictive. We show that when students are ranked strictly by some ex-ante known priority index (e.g., test scores), stability is a plausible and weaker assumption, implying that every student is matched with her favorite school/college among those she qualifies for ex post. The methods are illustrated in simulations and applied to school choice in Paris. We discuss when each approach is more appropriate in real-life settings.

The past decade has seen the Gale-Shapley Deferred Acceptance (DA) becoming the leading centralized mechanism for the placement of students to public schools at every education level, and it is now used by many education systems around the world, including Amsterdam, Boston, Hungary, New York, Paris, and Taiwan.

One of the reasons for the growing popularity of DA is its strategy-proofness (Abdulkadiroglu and Sönmez, 2003). When applying for admission, students are asked to submit rank-order lists (ROLs) of schools, and it is in their best interest to rank schools truthfully.

Students and their parents are thus released from strategic considerations. Consequently, DA also provides policymakers "with more credible data about school choices, or parent 'demand' for particular schools," as argued by Thomas Payzant (former Boston Public Schools superintendent). Indeed, such rank-ordered data contain rich information on student preferences over schools, and are increasingly used in the empirical literature.

Due to the strategy-proofness of DA, one may be tempted to assume that the submitted ROLs reveal students' true preferences over schools. However, this truth-telling assumption can be restrictive in settings where students face only limited uncertainty about their admission outcomes. One such environment is the "strict-priority" setting in which schools rank students by some priority index, e.g., a test score, which is known to students when submitting their ROL. Consider a student who likes a highly selective school but has a low test score. The student may "skip the impossible" and choose not to apply to this school, as she rationally expects a zero admission probability based on available information such as past admission outcomes. This implies that not all students have strong incentives to rank all schools truthfully in their ROLs. 1 Based on theoretical investigations of student incentive and behavior, we aim to provide empirical approaches to estimating student preferences in the strict-priority setting, which remains largely unexplored in the empirical literature on school choice and college admissions. Our proposed approaches can potentially be applied in many real-life systems, such as those in Table 1, including school choice in Finland, Paris, and Turkey (Panel A) as well as college admissions in Chile, Norway, and Taiwan (Panel B). The paper's first contribution is to clarify the implications of the truth-telling assumption, which hypothesizes that students always report true preferences. Given the Notes: a For exam schools in Boston, selective enrollment high schools in Chicago, and specialized high schools in NYC, strict priority indices are used in the admission. In contrast, admissions to other schools often do not use strict priority indices. b In Hungary, students may apply for any number of programs but they are charged a fee (of approximately 10 euros) for every program after the third application. c In all of the countries/cities listed in this table, students' priorities are based on various combinations of grades, entrance/exit exams, and other criteria (aptitude tests, interviews, etc.). When priority indices are not school-specific, i.e., schools/universities rank students in the same way, DA, whether student-proposing or school/college-proposing, is equivalent to serial dictatorship, under which students, in the order of their priority indices, are allowed to choose among the remaining schools or universities.

flourishing empirical literature on the setting in which schools rank students with postapplication lotteries (Pathak and Shi, 2014; Abdulkadiroglu et al., 2017), it is natural to extend those truth-telling-based approaches to the strict-priority setting. Unfortunately, strategy-proofness implies that truth-telling is a weakly dominant strategy, leaving open the issue of multiple equilibria because a student may obtain the same outcome by opting for non-truth-telling strategies-as shown in the "skipping the impossible" example above. Making truth-telling even less likely, many applications of DA restrict the length of submittable ROLs, which destroys strategy-proofness (Haeringer and Klijn, 2009).

These arguments are formalized in a theoretical model. Deviating from the literature, we introduce an application cost that students incur when submitting ROLs, and the model therefore has the common real-life applications of DA as special cases. Conditional on both preferences and priorities being private information, we show that for truth-telling to be the unique equilibrium, two conditions are needed: no application cost and large uncertainty in admission outcomes. Neither is easily satisfied in the strict-priority setting.

Even without limits on the length of submittable ROLs, students may find it costly to rank a long list of schools. As students know their own priority indices, uncertainty about admission outcomes can also be limited.

Going beyond truth-telling, the paper's second contribution is to propose a set of novel empirical approaches that are theoretically founded. We consider a weaker assumption implied by truth-telling: stability, or justified-envy-freeness, of the matching (Abdulkadiroglu and Sönmez, 2003), meaning that every student is matched with her favorite feasible school. A school is feasible for a student if its ex post cutoff is below the student's priority index. These cutoffs are well-defined and often observable to the researcher: given the admission outcome, each school's cutoff is the lowest priority index of the students accepted there. Conditional on the cutoffs, stability therefore defines a discrete choice model with personalized choice sets, which is straightforward to analyze empirically.

We show that stability is a plausible assumption, as there exists an equilibrium outcome that is asymptotically stable under certain conditions. When school capacities and the number of students increase proportionally while the number of schools is fixed, the fraction of students not matched with their favorite feasible school tends to zero. Although stability, as an ex post optimality condition, is not guaranteed when students' information is incomplete, we provide numerical evidence suggesting that typical real-life markets are sufficiently large for stability to be almost exactly satisfied.

Based on the theoretical results, we propose a menu of approaches for preference estimation. We start by formalizing the truth-telling assumption under which one can apply rank-ordered models on submitted ROLs. In practice, students rarely rank all available schools, and, therefore, the truth-telling assumption often imposes the exogeneity of the length of a submitted ROL. 2 Stability, but not asymptotic stability, leads to a discrete choice model with personalized choice sets, so the nonparametric identification in the discrete-choice literature can be applied (e.g., Matzkin, 1993), under the assumption that priority indices and unobserved preference heterogeneity are independent conditional on observables. An advantage of this approach is that it enables estimation with data on admission outcomes only, although ignoring the information in ROLs entails some efficiency loss in the estimation.

We also provide a solution if neither truth-telling nor stability is satisfied: as long as students do not play dominated strategies, the submitted ROLs reveal true partial preference orders of schools (Haeringer and Klijn, 2009), 3 allowing us to derive probability bounds for one school being preferred to another. The corresponding moment inequalities can be used for inference (for a survey, see Tamer, 2010). When stability is satisfied and identifies student preferences, these inequalities provide over-identifying information that can improve estimation efficiency ( Moon and Schorfheide, 2009).

To guide the choice between these identifying assumptions, we consider several statistical tests, provided that the model is correctly specified and identified. Truth-telling, leading to more restrictions than stability, can be tested against stability using a Hausmantype test (Hausman, 1978) or a test of over-identifying restrictions (Hansen, 1982). Similarly, stability can be tested against undominated strategies: if the outcome is unstable, the stability restrictions are incompatible with the moment inequalities implied by undominated strategies, allowing us to use tests such as Bugni et al. (2015).

Our third contribution is to evaluate the performance of each approach based on simulated and real-life data. Having illustrated the main theoretical results with Monte Carlo simulations, we apply the empirical approaches to school choice data from Paris.

There are 1,590 middle school students applying for admissions to 11 academic-track high schools in Paris' Southern District through a version of DA. Schools rank applicants by their academic grades but give priority to low-income students. The findings are more consistent with stability than truth-telling. Our proposed statistical tests reject truthtelling in favor of stability but fail to reject stability against undominated strategies.

The tests, however, do not provide definitive proof against truth-telling, since they are conditional on the model's parametric assumptions. Additionally, we provide reducedform evidence on students' ranking behavior suggesting that some students may have omitted the most selective schools from their ROLs because of low admission probabilities.

Moreover, the truth-telling-based estimator is outperformed by the stability-based one when it comes to predicting admission outcomes and student preferences.

To highlight the differences between the proposed approaches and their underlying behavioral assumptions, we summarize the theoretical results and describe the nesting structure of the assumptions in Section 5. We also emphasize the key features of school choice and college admissions in practice that can help researchers to choose the most 3 An ROL is a true partial preference order if the listed schools are ranked according to true preferences.

appropriate empirical approach to preference estimation.

Other Related Literature. Since the seminal work of Abdulkadiroglu and Sönmez (2003), the theoretical study of student behavior and matching properties under DA has been extensive, and large-market asymptotics are a common analytical tool (see the survey by Kojima, 2015). Closely related to our study is Azevedo and Leshno (2016), who show the asymptotics of stable matchings. Our paper extends theirs to outcomes of Bayesian Nash equilibrium, whereas they assume that students are always truth-telling.

There is a burgeoning literature on preference estimation using centralized school choice data. One strand of this literature uses data from settings in which researchers argue that truth-telling behavior by students is plausible. For example, Hastings et al. (2008) use data from Charlotte-Mecklenburg public school district, and Abdulkadiroglu et al. (2017) study school choice data from New York City, which is a "lottery" setting. 4 Both papers estimate student preferences under the assumption that students truthfully report their preferences. In the same spirit, assuming students report their true preferences in surveys, Budish and Cantillon (2012) and De Haan et al. (2015) use reported student ordinal preferences to conduct analysis without estimating preferences.

The second strand of the empirical literature explicitly considers students' strategic behavior when estimating student preferences, especially if the mechanism is not strategyproof, e.g., the (Boston) immediate-acceptance mechanism (Calsamiglia et al., 2014; He, 2015; Hwang, 2014; Kapor et al., 2016; Agarwal and Somaini, 2018). In those settings, observed ROLs are sometimes considered as solutions to the maximization of students' expected utility. Avoiding some difficulties of this strategy-based approach, we instead propose methods that rely on equilibrium outcome of the school choice game. 5 As to the strict-priority setting, there are only a handful of empirical studies (Burgess et al., 2014; Ajayi, 2017; Akyol and Krishna, 2017). Most of them use ad-hoc solutions to the potential problem of students' non-truth-telling behavior. 6 Akyol and Krishna 4 The authors perform robustness checks, e.g., only considering students' top three submitted choices. 5 With assumptions on students' beliefs, the strategy-based approach formulates a discrete choice problem defined on the set of possible ROLs. It faces some challenges: (i) Degenerate admission probabilities can occur, leading to multiple equilibria (He, 2015). (ii) Application costs, especially those related to cognitive load, are often unobservable, necessitating additional assumptions in the maximization of expected utility. (iii) A given ROL is evaluated against a large number of alternative ROLs, sometimes creating computational burden (e.g., there exist S!{pS ¡ Kq! lists ranking 1 ¤ K ¤ S schools). 6 Analyzing school choice in the U.K., where proximity to schools breaks ties in determining admission to oversubscribed primary schools, Burgess et al. (2014) restrict each student's set of schools to those in close proximity to the student's residence. In the context of admissions to secondary schools in Ghana, where exam scores determine priority, Ajayi (2017) considers a subset of schools with similar selectivity.

(2017) is an exception. Observing the outcome and the cutoffs of high school admissions in Turkey, the authors estimate preferences based on the assumption that every student is assigned to her favorite feasible school, which amounts to assuming stability of the matching. We formalize and clarify this stability assumption, along with other extensions.

Although stability is a rather common identifying assumption in the two-sided matching literature (see the surveys by Fox, 2009; Chiappori and Salanié, 2016),7 it is new in empirical studies of school choice and college admissions.

Lastly, estimation of student preferences with college admissions data is under-explored, often due to the decentralized nature of the admission process. Among centralized admissions, however, there are many applications of the DA mechanism (see Table 1). 8 The specifics of the mechanism have led to numerous studies on the causal effects of education (e.g., Hastings et al., 2015; Kirkebøen et al., 2016), but few on preference estimation.

One exception is Kirkebøen (2012) who uses the truth-telling assumption while excluding from a student's choice set every college program at which the student does not meet the formal requirements or is below its previous-year cutoff. Another is Bucarey (2018) who applies our stability-based estimator to evaluate the crowding-out effects of free college tuition for low-income students in Chile.

Organization of the Paper. Section 1 presents the model and the theoretical foundation. Section 2 formalizes the empirical approaches and tests, which are illustrated in Monte Carlo simulations in Section 3. School choice in Paris and the empirical results are shown in Section 4. Section 5 discusses practical considerations for applying the approaches to data and outlines some extensions. We conclude in Section 6.

The Model

To study student behavior, we extend the model in Azevedo and Leshno (2016). An economy, as a school choice/college admissions problem, consists of a finite set of schools/colleges, S t1, . . . , Su, and a set of students. Student i has a type θ i pu i , e i q Θ r0, 1s S ¢ r0, 1s S , where u i pu i,1 , ¤ ¤ ¤ , u i,S q r0, 1s S is a vector of von Neumann-Morgenstern (vNM) utilities of being assigned to schools, and e i pe i,1 , ¤ ¤ ¤ , e i,S q r0, 1s S is a vector of priority indices at schools, a student with a higher index having a higher priority at a school. To simplify notation, we assume that all schools and students are acceptable. 9

Students are matched with schools through a centralized mechanism.

The continuum economy with a unit mass of students is denoted by E tG, q, Cu, where G is an atomless probability measure over Θ representing the distribution of student types; q pq 1 , ¤ ¤ ¤ , q S q are masses of seats available at each school, where q s p0, 1q for all s; lastly, C is an application cost, to be specified shortly. G being atomless implies a measure-zero set of students with indifference in either utilities or priority indices.

A random finite economy of size I is denoted by F pIq tG pIq , q pIq , Cu. F pIq is constructed by independently drawing I students, indexed by i t1, ¤ ¤ ¤ , Iu, from the distribution G and adjusting the numbers of seats to integers. Specifically, G pIq is the random empirical distribution of types for a sample of I students;10 q pIq rq¤Is{I is the supply of seats per student, where rxs is the vector of integers nearest to x (with a rounding down in case of a tie). We use F pIq t ĜpIq , q pIq , Cu to denote a realization of F pIq .

In the following, we start with F pIq to specify the matching process and to analyze student behavior, because empirical studies deal with finite economies; the extension to the continuum economy E is deferred to Section 1.4.

In a realization of the random economy, F pIq , schools first announce their capacities, and every student then submits a rank-order list (ROL) of 1 ¤ K i ¤ S schools, denoted by L i l 1 i , . . . , l k i , . . . , l K i i ¨, where l k i S is i's kth choice. L i also represents the set of schools being ranked in L i . We define ¡ L i such that s ¡ L i s I if and only if school s is ranked above school s I in L i . The set of all possible ROLs is L, which includes all ROLs ranking at least one school. Student i's true ordinal preference induced by her vNM utilities u i is denoted by rpu i q r 1 i , . . . , r S i ¨ L.

When submitting an ROL, a student incurs a cost C p|L|q, which depends on the number of schools being ranked in L, |L|. Furthermore, C p|L|q r0, Vs for all L and is weakly increasing in |L|. To simplify students' participation decisions, we set C p1q 0. Such a cost function flexibly captures many common applications of school choice mechanisms. If C p|L|q 0 for all L, we are in the traditional setting without costs (e.g., Abdulkadiroglu and Sönmez, 2003); if C p|L|q V for |L| greater than a constant K, it 9 Assuming acceptability of all schools justifies the normalization of u r0, 1s S . Although we could extend the preference domain to allow for negative values, this would create the possibility that students avoid being assigned to schools with negative vNM utilities when maximizing expected utility.

corresponds to the constrained school choice where students cannot rank more than K schools (e.g., Haeringer and Klijn, 2009); when C p|L|q maxt0, p|L| ¡ Kqcu, students pay a constant marginal cost c for each choice beyond the first K choices, as in Hungarian college admissions (Biró, 2011); lastly, the monotonic cost function may simply reflect that it is cognitively burdensome to rank too many schools.

The student-school match is then solved by a mechanism that takes into account students' ROLs and schools' rankings over students. Our main analysis focuses on the student-proposing Gale-Shapley Deferred Acceptance (DA), leaving the discussion of other variants to Section 5.2. As a computerized algorithm, DA works as follows:

Round 1. Every student applies to her first choice. Each school rejects the lowestranked students in excess of its capacity and temporarily holds the other students.

Generally, in:

Round k. Every student who is rejected in Round pk ¡ 1q applies to the next choice on her list. Each school, pooling together new applicants and those it holds from Round pk ¡ 1q, rejects the lowest-ranked students in excess of its capacity. Those who are not rejected are temporarily held by the schools.

The process terminates after any Round k when no rejections are issued. Each school is then matched with the students it is currently holding.

Information Structure and Decision-Making

In a realization of the finite economy, F pIq , given its construction, every student's prefer- ences and priority indices are private information, and are i.i.d. draws from G, which is common knowledge (but ĜpIq , the realization of G pIq , remains unknown). We start by taking student i's point of view. Conditional on others' submitted ROLs and priority indices (L ¡i , e ¡i ), as well as student i's (L i , e i ), her admission outcome is deterministic, given the algorithm. Specifically, i's admission outcome at school s is:

a s pL i , e i ; L ¡i , e ¡i q 6 8 7 1 i is rejected by l 1 i , . . . , l k i and accepted by l k 1 i s | L i , e i ; L ¡i , e ¡i 0 if s L i if s L i
where 1p¤ | L i , e i ; L ¡i , e ¡i q is an indicator function. Moreover, due to the centralized mechanism, a student can receive at most one offer, so °S s1 a s pL i , e i ; L ¡i , e ¡i q 0 or 1.

Of course, L ¡i and e ¡i are unknown to i at the time of submitting her ROL, so i takes into account the uncertainty when choosing an action. A pure strategy is σ : Θ Ñ L.

Given σ, the (ex ante) admission probabilities are ³ a s pσpθ i q, e i ; σ ¡i pθ ¡i q, e ¡i q dGpθ ¡i q for all i and s, where σ ¡i pθ ¡i q tσpθ j qu j$i . We consider a (type-)symmetric equilibrium σ ¦ in pure strategies such that σ ¦ solves the following maximization problem for every θ i : 11 σ ¦ pθ i q arg max σpθ i qL 5 şS u i,s » a s σpθ i q, e i ; σ ¦ ¡i pθ ¡i q, e ¡i ¨dGpθ ¡i q ¡ C p|σpθ i q|q C

.

(1)

The existence of pure-strategy Bayesian Nash equilibrium can be established by applying Theorem 4 (Purification Theorem) in Milgrom and Weber (1985), although there can be multiple equilibria. For ease of exposition, the following analysis focuses on pure-strategy equilibrium. We note that while economy F pIq is random, a strategy σ is "deterministic"

in the sense that it only depends on pG, I, Cq but not on the realization of F pIq . We define a realized matching μ as a mapping from Θ to Stru such that: (i) μ pθ i q s if student i is matched with s; (ii) μ pθ i q r if student i is unmatched; and (iii) μ¡1 psq is the set of students matched with s, while |μ ¡1 psq| is the number of students matched with s and does not exceed s's capacity. F pIq and σ together lead to an ROL profile as inputs into the DA mechanism and result in a matching, µ p F pIq ,σq , which is uniquely determined by the mechanism. Note that µ pF pIq ,σq is a random matching because F pIq is a random economy.

Moreover, the (random) cutoff of school s in random matching µ pF pIq ,σq is defined as:

P s ¡ µ pF pIq ,σq © 6 8 7 min 3 e i,s | µ pF pIq ,σq pθ i q s A 0 if |µ ¡1 pF pIq ,σq psq | q pIq s if |µ ¡1 pF pIq ,σq psq | q pIq s That is, P s ¡ µ pF pIq ,σq

Truth-Telling Behavior in Equilibrium

To assess the plausibility of the truth-telling assumption in empirical studies, we begin by investigating students' truth-telling behavior in equilibrium. A clarification of the concepts is in order. Student i is weakly truth-telling (WTT, hereafter) if σpθ i q pr 1 i , r 2 i , . . . , r K i i q for K i ¤ S. That is, i ranks her K i most-preferred schools by her true preference order but may not rank all schools. If a WTT strategy always truthfully ranks all S schools and thus σpθ i q rpu i q, i is strictly truth-telling (STT, hereafter). 12 We emphasize the difference between WTT and STT because strategy-proofness concerns the latter. However, WTT is often considered in empirical studies because in practice, students rarely rank all available schools, as we shall revisit in Section 2.2.

It is known that DA is strategy-proof when there is no application cost (Dubins and Freedman, 1981; Roth, 1982). That is, when C p|L|q 0 for all L L, STT is a weaklydominant strategy for all students. However, strategy-proofness, or weak dominance of STT, leaves open the possibility of multiple equilibria. Even when all others play STT, there may exist multiple best responses for a given student. 13 It is therefore useful to clarify the conditions under which STT is the unique equilibrium. The following example highlights two sources of equilibrium multiplicity in a complete-information environment.

Example 1 (Multiple Equilibria under DA without Application Cost). Consider a finite economy that has two students (i 1 , i 2 ), three one-seat schools (s 1 , s 2 , s 3 ), but no application cost. As common knowledge, all schools rank i 1 above i 2 ; student i 1 's preference order is ps 1 , s 2 , s 3 q, but i 2 's is ps 2 , s 1 , s 3 q. There are many equilibria in addition to STT, stemming from two sources: "irrelevance at the bottom" and "skipping the impossible." Both arise when some admission probabilities are zero.

For i 1 , the bottom part of her submitted ROL is irrelevant as long as s 1 is top-ranked.

In fact, any ROL (s 1 , s I , s P ), for s I , s P ts 2 , s 3 u tru, is weakly dominant for i 1 , as she is always accepted by s 1 . For student i 2 , "skipping the impossible" comes into play. She can omit s 1 from her submitted ROL without affecting her outcome, because s 1 is always taken by i 1 in any equilibrium. Making things worse, how she ranks s 1 is payoff-irrelevant.

One may conjecture that STT might survive as the unique equilibrium when information is incomplete. Indeed, specifying the incompleteness of information, the following proposition provides sufficient conditions and a necessary condition.

Proposition 1. (i) Sufficiency: STT is the unique Bayesian Nash equilibrium under DA if (i) there is no application cost: C p|L|q 0, dL L; and (ii) the joint distribution of preferences and priorities G has full support.

(ii) Necessity: For any non-zero application cost, there always exist student types for whom STT is not an equilibrium strategy.

All proofs can be found in Appendix A. The no-cost condition is violated if students cannot rank as many schools as they wish, or if they suffer a cognitive burden when ranking too many schools. It should also be emphasized that the cost need not be large to make students deviate from STT, because the marginal benefit of ranking an additional school can be close to zero. When a student considers her admission probability at her kth choice, she may face a close-to-one probability of being accepted by at least one of her earlier choices. This is in the same spirit as the "irrelevance at the bottom" in Example 1.

When the marginal application cost exceeds marginal benefits, STT is no longer a best response, which implies the necessity of the zero-cost condition.

The full-support condition, also considered in Chen and Pereyra (2017), makes all admission probabilities non-zero by introducing uncertainties, and therefore any deviation from STT is costly. This is more plausible when the priority index is determined by an ex post lottery and when the information on others' preferences over schools is less precise.

Remark 1. Proposition 1 specifies when students have incentives to rank all schools truthfully, but this result does not extend to WTT. Although it is sometimes used for identification and estimation, the WTT assumption is not supported as an equilibrium.14

We may take one step back and focus on whether students have incentives to order the ranked schools truthfully. We call L i , |L i | ¤ S, a partial preference order of schools if L i respects the true preference order among those ranked in L i . That is, L i ranks s above s I , only if u i,s ¡ u i,s I; when s is not ranked in L i , there is no information on how s is ranked relative to any other school according to i's true preferences.

Proposition 2. Under DA with application cost, if students do not play weakly dominated strategies, a student's submitted ROL is a partial order of her true preferences.

Proposition 2 can be considered as a corollary of Proposition 4.2 in Haeringer and Klijn (2009), and thus we omit its proof. The key is that a non-partial-preference-order ROL is weakly dominated by the ROL that ranks the same schools according to their true preference order. This result is useful for empirical analysis, as it specifies students' revealed preferences. Section 2.5 formulates how to use this information in estimation.

Matching Outcome: Stability

The above results speak to the plausibility of the truth-telling assumptions, WTT and STT, in empirical studies. In particular, WTT is not theoretically supported as a weaklydominant strategy even in DA with no application cost; whenever there is any form of application cost, STT is no longer a dominant strategy.

Taking a different perspective, we note that all equilibria lead to the same matching in Example 1. This motivates us to investigate the properties of equilibrium outcomes of DA. Intuitively, the degree of multiplicity in equilibrium outcomes must be smaller than that in equilibrium strategies. In the two-sided matching literature, stability is the leading concept for equilibrium outcome and the main identifying assumption (Chiappori and Salanié, 2016). We investigate whether stability can also be satisfied in all equilibrium outcomes of school choice and college admissions.

Unfortunately, we shall demonstrate that having stability satisfied in all equilibrium outcomes requires similar conditions to those for STT being the unique equilibrium. In fact, whenever there is application cost, stability is not guaranteed in equilibrium either. This is because Bayesian Nash equilibrium implies ex ante optimality of student strategy, while stability requires ex post optimality.

As we study a matching's ex post properties, let us consider μ, a realization of the random matching. pi, sq form a blocking pair if (i) i prefers s over her matched school μpθ i q while s has an empty seat (|μ ¡1 psq| I ¢ q pIq s ), or if (ii) i prefers s over μpθ i q while s has no empty seats (|μ ¡1 psq| I ¢ q pIq s ) but i's priority index is higher than its cutoff, e i,s ¡ min tj:μpθ j qsu te j,s u. μ is stable if there is no blocking pair. Stability is also known as elimination of justified envy in school choice ( Abdulkadiroglu and Sönmez, 2003).

Given a realized matching μ, school s is ex post feasible for i if i's priority index at s is above s's cutoff, e i,s ¥ P s pμq. Let Spe i , P pμqq be the set of feasible schools for i.

With these definitions, combining Lemmata 1 and 2 in Balinski and Sönmez (1999), we reach an important result: a realized matching μ is stable if and only if every student is matched with her favorite feasible school (i.e., μpθ i q arg max sSpe i ,P pμqq u i,s , di). As the cutoffs of a matching are observed ex post by the researcher, we can define every student's set of feasible schools; stability therefore implies a discrete choice model with observable, personalized choice sets. We further formalize this in Section 2.3.

We are interested in stability being satisfied in an outcome of dominant-strategy equilibrium, which would free us from specifying the information structure and from imposing additional equilibrium conditions. The following lemma provides necessary and sufficient conditions, which are similar to those for STT to be the unique equilibrium.

Lemma 1. Under DA, a Bayesian Nash equilibrium in dominant strategy always leads to a stable matching if and only if C p|L|q 0 for all L. It is the unique equilibrium outcome if additionally G has full support.

The "if and only if" statement of the lemma is implied by strategy-proofness of DA without application cost, while the uniqueness statement is a result of Proposition 1.

DA is known to produce a stable matching when students are STT (Gale and Shapley, 1962), but not when students are only WTT. The following results, clarifying the relationship between WTT and stability, have implications for our empirical approaches.

Proposition 3. Suppose that every student is WTT under DA, which may not be an equilibrium. Given a realized matching:

(i) whenever a student is assigned, she is matched with her favorite feasible school;

(ii) if everyone who has at least one feasible school is assigned, the matching is stable.

The above results describe the nesting structure of the two assumptions, WTT and stability, although they do not speak to the plausibility of either of them being an equilibrium strategy/outcome. Specifically, WTT is more restrictive, as it implies the noblocking property among assigned students. We use these results to formulate statistical tests for the choice between WTT and stability in Section 2.4.

Asymptotic Stability in Bayesian Nash Equilibrium

So far, we have shown that neither truth-telling (STT and WTT) nor stability can emerge in equilibrium without some potentially restrictive assumptions. Following the literature on large markets, we study whether stability can be asymptotically satisfied.

We now revisit the continuum economy, E, and additionally introduce a sequence of random finite economies tF pIq u IN that are constructed from E as before.

The definitions of matching, DA, and stability can be naturally extended to continuum economies as in Abdulkadiroglu et al. (2015) and Azevedo and Leshno (2016), which are discussed in Appendix A.2.1. These definitions are similar to their counterparts in finite economies. For example, a matching in E when everyone adopts σ is µ pE,σq : Θ Ñ Stru, which satisfies (i) µ pE,σq pθ i q s when type θ i is matched with s and (ii) Gpµ ¡1 pE,σq psqq ¤ q s . It is known that, generically, there exists a unique stable matching in the continuum economy (Azevedo and Leshno, 2016); 15 we impose the conditions for the uniqueness and denote this stable matching in E as µ V and the corresponding cutoffs as P V . To continue our exploration, we make the following assumption: Assumption 1. Every Bayesian Nash equilibrium of the continuum economy E results in the unique stable matching, µ V .

A sufficient condition for Assumption 1 is Cp2q ¡ 0 (i.e., it is costly to apply to more than one school), and when Cp2q 0, a sufficient and necessary condition is Ergin acyclicity (Proposition A3 in Appendix A.2.5). An economy is acyclical if no student can block a potential settlement between any other two students without affecting her own match (Ergin, 2002). Appendix A.2.5 gives its formal definition in continuum economies. This condition is satisfied when all schools rank every student by a single priority index.

Because we are interested in equilibrium outcomes, we augment the sequence of economies with equilibrium strategies, tF pIq , σ pIq u IN , where σ pIq is a pure-strategy Bayesian Nash equilibrium in F pIq and satisfies the following assumption.

15 A sufficient condition for the uniqueness of stable outcome in E is that G has full support. Even when G does not have full support, the uniqueness can be achieved when °S s1 q s 1. Let σ ST T be the STT strategy. We define the demand for each school in pE, σ ST T q as a function of cutoffs, D s pP | E, σ ST T q ³ 1pu i,s max s 1 Spei,Pq u i,s 1 qdGpθ i q. Let DpP | E, σ ST T q rD s pP | E, σqs sS . E admits a unique stable matching if the image under DpP | E, σ ST T q of the closure of the set 2 P p0, 1q S : DpP | E, σ ST T q is not continuously differentiable at P @ has Lebesgue measure zero.

Assumption 2. There exists σ V such that lim IÑV G 2 θ i Θ | σ pIq pθ i q σ V pθ i q @¨ 1.

A sufficient condition for Assumption 2 is Cp2q ¡ 0 (Lemma A5 in Appendix A.2.4). 16 Although F pIq is a random economy, σ pIq is fixed given the size of the economy. In other words, σ pIq remains as an equilibrium strategy in any realization of F pIq . Assumption 2 regulates how the equilibria evolve with economy size, which is necessary as there are multiple equilibria. By this assumption, in the sequence tσ pIq u IN , fewer and fewer student types need to adjust their optimal actions when the economy enlarges. Moreover, given Assumption 1, the limit strategy σ V leads to µ V in E (Proposition A1).

Asymptotic Stability: Definition and Results

Let the random matching µ pF pIq ,σ pIq q be µ pIq , and the associated random cutoffs P µ pIq be P pIq . The following definition formalizes the concept of asymptotic stability. 17 Definition 1. A sequence of random matchings, tµ pIq u IN , associated with the sequence of random economies and equilibrium strategies, tF pIq , σ pIq u IN , is asymptotically stable if the fraction of students who are matched with their favorite feasible school in a random finite economy (F pIq ) converges to one, almost surely, or, equivalently, lim IÑV G pIq £ tθ i Θ | µ pIq pθ i q arg max sSpe i ,P pIq q u i,s u 1, almost surely.

We are now ready to introduce our main result.

Proposition 4. In the sequence of random economies and equilibrium strategies, tF pIq , σ pIq u IN , if Assumptions 1 and 2 are satisfied, then (i) the random cutoffs converge to those of the stable matching in the continuum economy: lim IÑV P pIq P V , almost surely;

(ii) the sequence of random matchings, tµ pIq u IN , is asymptotically stable.

16 Allowing Cp2q 0, Appendix A.2.4 investigates the properties of equilibrium strategies. The results, Lemmata A2-A4, imply strong restrictions on the sequence of Bayesian Nash equilibria in the direction of satisfying Assumption 2. Specifically, it is shown that a strategy that does not lead to µ V in the continuum economy cannot survive as an equilibrium when I Ñ V. This immediately implies that in sufficiently large economies, every student includes in her ROL the school prescribed by µ V . Moreover, students do not pay a cost to rank more schools in large economies.

Part (ii) implies that the fraction of students who are matched with their favorite feasible school, or not in any blocking pair, converges to one almost surely, as the economy grows. This provides justifications for the stability assumption in large markets. (i) Let σ pIq pθ i q L pIq ; then L pIq is a partial order of i's ordinal preferences. If ex post i forms a blocking pair with s, s must not be included in L pIq , s L pIq .

The probability that i is in a blocking pair with any school in the random matching µ pIq , denoted by B pIq i Prphs S, u i,s ¡ u i,µ pIq pθ i q , and e i,s ¥ P pIq s q, satisfies: Because in equilibrium student i reports a partial order of her true preferences, she can only form a blocking pair with a school that she did not rank (part i). Therefore, the probability that i is in a blocking pair decreases whenever it is less costly to rank more schools (part ii). Together, Proposition 5 shows that stability is more plausible when the cost of ranking more schools is lower and/or the economy is large. Moreover, in the case of constrained/truncated DA where there is a limit on the length of ROLs, the higher the number of schools that can be ranked, the more likely stability is to be satisfied.

(ii) B pIq i is bounded above: B pIq i ¤ |SzL pIq | Cp|L pIq | 1q¡Cp|L pIq |q

Empirical Approaches

Building on the theoretical results, we formalize the estimation of student preferences under different sets of assumptions and propose a series of tests to guide the selection of the appropriate approach. To be more concrete, we consider a logit-type random utility model, although our approaches can be extended to other specifications.

This section focuses on a random finite economy F pIq in which I students compete for admissions to S schools. Each school has a positive capacity, and students are assigned through a version of the student-proposing DA. Besides submitted ROLs and admission outcomes, the researcher observes priority indices, student characteristics, and school attributes. Given these observables, we discuss the probability of a student submitting a

given ROL or being matched with a given school from the researcher's perspective.

Model Setting and Revealed Preferences

As is traditional and more convenient in empirical analysis, we let the student utility functions take any value on the real line. 19 With some abuse, we still use the same notation for utility functions. To facilitate the analysis, student i's utility from attending schools s is parameterized:

u i,s V i,s i,s V pZ i,s , βq i,s , (2)
where V p¤, ¤q is a known function, taking as arguments Z i,s , a vector of observable studentschool characteristics, and β, a vector of unknown parameters to be estimated; i,s is the unobservable student heterogeneity.

We further define Z i tZ i,s u S s1 , and i t i,s u S s1 . It is assumed that i u Z i and that i,s is i.i.d. over i and s with the type-I extreme value (Gumbel) distribution. Such a formulation rules out outside options, although this assumption can be relaxed.

We also assume that a student's preferences are not affected by other students' school assignments (no peer effects) and that statistics associated with the realized matching, such as cutoffs, do not enter the utility function. This is consistent with the theoretical model in Section 1 and implies that Z i does not include variables that depend on the ex-post observed matching.

The estimation relies on revealed student preferences in the data, and what information is revealed crucially depends on the imposed assumption-WTT, stability, or undominated stategies. Figure 1

Truth-Telling

In the literature on school choice with lotteries, some empirical approaches are based on the truth-telling assumption (Hastings et al., 2008; Abdulkadiroglu et al., 2017). As similar mechanisms are commonly used in our strict-priority setting, we extend these approaches to our setting and clarify the assumptions embedded within.

We start with WTT instead of STT because in practice students in school choice and college admissions rarely rank the same number of choices (Abdulkadiroglu et al., 2017; He, 2015; Artemov et al., 2017). Under the assumption of truth-telling without outside option, this can only be consistent with WTT but not STT, because STT requires everyone to rank all schools. We discuss STT with outside options in Appendix A.4.

For notational convenience, we make it explicit that student i's type θ i is described by pu i , e i q. Let σ W : R S ¢ r0, 1s S Ñ L be a WTT pure strategy.20 More precisely, the WTT assumption amounts to the following: Assumption (Characterization of Weak Truth-Telling).

WTT1. Suppose σ W pu i , e i q L pl 1 , . . . , l K i q. L ranks i's top K i preferred schools according to her true preferences: u i,l 1 ¡ ¤ ¤ ¤ ¡ u i,l K i ¡ u i,s I for all s I not ranked in L; WTT2. The number of schools ranked by a student is exogenous: u i u |σ W pu i , e i q|, di.

We are interested in the choice probability of L conditional on observables, where the uncertainty from the researcher's perspective is due to the utility shocks ( i ). Note that:

Pr σ W pu i , e i q L § § Z i ; β Pr σ W pu i , e i q Lq § § Z i ; β; |σ W pu i , e i q| K ¨¢ Pr |σ W pu i , e i q| K § § Z i ; β ¨,
which are calculated by integrating out the unobservables ( i ) in u i . Assumption WTT2 implies that Pr |σ W pu i , e i q| K § § Z i ; β ¨does not depend on preferences. Thus, in the estimation, it suffices to focus on the following conditional probability:

Pr σ W pu i , e i q L § § Z i ; β; |σ W pu i , e i q| K Pr u i,l 1 ¡ ¤ ¤ ¤ ¡ u i,l K ¡ u i,s I d s I SzL § § Z i ; β; |σ W pu i , e i q| K ¹ sL £ exppV i,s q °sI £ L s exppV i,s Iq
, where s I £ L s indicates that s I is not ranked before s in L, including s itself and those excluded from L. This rank-ordered (or "exploded") logit model can be seen as a series of conditional logits: one for the top-ranked school (l 1 ) being the most preferred, another for the second-ranked school (l 2 ) being preferred to all schools except l 1 , and so on.

Let |σ W | be the vector of lengths of all submitted ROLs. The model can be estimated by maximum likelihood estimation (MLE) with the log-likelihood function:

ln L T T β § § Z, |σ W | ¨ I i1 şσ W pu i ,e i q V i,s ¡ I i1 şσ W pu i ,e i q ln ¡ şI £ σ W pu i ,e i q s exppV i,s Iq © .
The estimator is denoted by βTT . Alternatively, the generalized method of moment (GMM) can be employed, for which the moment conditions are derived as in Section 2.5.

WTT implies additional restrictions beyond standard discrete choice models (see details in Section 2.4). Thus, the discrete-choice literature (e.g., Matzkin, 1993) implies that student preferences are nonparametrically identified (also see Agarwal and Somaini, 2018).

Stability

We now assume that the matching is stable, which is different from, but in large samples justified by, asymptotic stability. The following analysis abstracts away from the matching mechanism and ignores how stability is obtained. We formulate a stable matching as the outcome of a discrete choice model and clarify the conditions that are needed for identification and estimation.

Consider the matching µ and the associated cutoffs P pµq, which are random variables determined by the unobserved utility shocks ( ). µ is the outcome of a discrete choice model with personalized choice set, Spe i , P pµqq (i.e., the set of i's feasible schools). The probability that i is matched with s, or chooses s in Spe i , P pµqq, is:

Pr £ s µpu i , e i q arg max sSpe i ,P pµqq u i,s § § § Z i , e i , Spe i , P pµqq; β .
To proceed, we impose the following assumptions:

Assumption (Exogeneity of Priority Index and Feasible Set).

EXO1. For all i, e i u i |Z i : Conditional on observables Z i , student preferences and priority indices are independent.

EXO2. For all i and s, 1pe i,s P s pµqqu i |Z i , or Spe i , P pµqqu i |Z i : Conditional on observables Z i , a student's preferences and her set of feasible schools are independent.

Assumption EXO1 implies that, when priority indices (e i ) are determined by test scores, no student intentionally under-performs or over-performs in exams.

Assumption EXO2 deserves some discussion. Most importantly, it does not require that cutoffs P pµq are conditionally independent of preferences shocks i . Instead, it only assumes that the personalized choice set, Spe i , P pµqq, is exogenously given, which is necessary for identification in a discrete choice model with personalized choice sets. For instance, if instead Spe i , P pµqq is endogenous and only includes school s when s is i's most preferred school, we lose the identification of i's preferences, because there is no variation in i's choice whenever s is in Spe i , P pµqq. Appendix A.5 details such an example, along with a discussion and an example in which the assumption is satisfied.

One may argue that, in a finite market, a student can affect some cutoffs by applying to a school or not, and thus can change the feasibility of some schools. Another concern is that given student preferences, there can be multiple stable matchings. If a single student can select among the stable matchings, Assumption EXO2 is also violated.

These concerns diminish as the economy grows large, because the potential influence on cutoffs by any student decreases and there tends to be a unique stable matching.

For instance, Part (i) of Proposition 4 implies that a single student's impact on cutoffs diminishes to zero, almost surely. Moreover, even in small markets, Assumption EXO2 can be satisfied, because the assumption does not require P pµqu i |Z i . An example is when every school ranks students in the same way, or e i,s e i for all s and i.21

Given the parametric assumptions on utility functions, the corresponding (conditional) log-likelihood function is:

ln L ST pβ | Z, e, Spe i , P pµqqq I i1 S ş1 V i,s ¢ 1pµpu i , e i q sq ¡ I i1 ln ¡ ş1
Spei,Ppµqq

exppV i,s 1 q © . ( 3
)
This estimator is denoted by βST . Similarly, GMM can be applied, as in Section 2.5.

Identification. The above discussion transforms the matching game into a discrete choice model. 22 Therefore, the nonparametric identification arguments for discrete choice models still apply (Matzkin, 1993). An important feature in the stability-based estimation is that students face personalized choice sets. As long as the choice sets are determined exogenously (Assumption EXO2), the identification goes through.

Another concern is that a student's priority index may enter her utility functions directly, when, for example, priority indices are determined by test score or student ability.

In this case, the stability assumption does not reveal information about low-scoring students' preferences over popular schools, because such schools are often infeasible to them.

This may lead to a failure of identifying how test scores determine student preferences.

This problem is mitigated if we have another measure of student ability, as in our empirical exercise. We assume that conditional on student ability, priority indices do not determine preferences and only affect school feasibility. If, additionally, priority indices have full support (i.e., can take any possible value) at each given level of student ability, we can observe some low-ability students having all schools feasible. This restores nonparametric identification in discrete choice models as in Matzkin (1993).

Relative to WTT, the stability assumption uses unambiguously less information from the data (see Figure 1 for an example). WTT utilizes all information implied by the submitted ROLs, while stability only imposes restrictions on admission outcome. One by the students with higher priority indices. Because preferences are independent across students by assumption, we have Spe i , P pµqqu i |Z i , or 1pe i,s P s pµqqu i |Z i for all s.

It should be noted that P pµqw i |Z i even in this case. For example, when i chooses s among the feasible schools, the cutoff of s will possibly increase; similarly, i may decrease s's cutoff by choosing a different school. However, we always have 1pe i,s P s pµqqu i |Z i , because s will remain feasible to i either way. 22 A simplification is that we ignore the restrictions implied by the cutoffs P pµq, which may lead to efficiency loss in estimation. That is, even when the sets of feasible schools are exogenous to every single student's preferences, P pµq is endogenously determined by the model's parameters. However, the additional information in these restrictions may be negligible, since we use the information on the whole matching already. An earlier version of the paper relaxes this assumption and uses the restrictions implied by the cutoffs. Our estimation results from simulated data and school choice data from Paris show that using the cutoff restrictions makes a negligible difference in the estimation results.

may expect that the stability-based approach leads to a loss of information; in particular, we may lose some precision in estimating the substitution patterns when we allow for more flexible random utility models (Berry et al., 2004; Abdulkadiroglu et al., 2017). Indeed, as we shall see in our Monte Carlo simulations and the analysis of the school choice data from Paris, there is a clear bias-variance tradeoff: stability tolerates non-truth-telling behavior at the cost of yielding less precise estimates.

Estimation with Asymptotic Stability. When taking the above results to real-life data, one may be concerned that the matching may not be exactly stable. Indeed, our theoretical results only prove asymptotic stability. This raises the question of whether the estimator is still consistent. In Appendix A.3, we show that the MLE with asymptotic stability is consistent (Proposition A4). In a finite economy, the stability-based estimation is incorrectly specified, because some students may not be assigned to their favorite feasible school and their reveal preferences are mis-classified when stability is imposed.

However, the fraction of students who are not assigned to their favorite feasible school converges to zero at an exponential rate (part iii of Proposition A2), implying that the mis-classification in revealed preferences vanishes with economy size. By verifying the conditions in Theorem 2.1 of Newey and McFadden (1994), we show that the stabilitybased estimator is consistent even when the matching is only asymptotically stable.

Testing Truth-Telling against Stability

Having two distinct estimators, βTT and βST , makes it possible to test the truth-telling assumption against stability. Maintaining the assumption of identification given stability, we shall see shortly that WTT provides over-identifying restrictions.

Before we present the tests, a few caveats are in order. First, one should check that the conditions for identification (for example, those in Matzkin, 1993) are satisfied before conducting the tests. Second, because the tests are essentially about joint restrictions on the parametric assumptions and the behavioral assumptions, one should be aware of the consequence of model misspecification. Rejecting truth-telling in favor of stability may not provide definitive proof against truth-telling, since the proposed tests are conditional on the model's parametric assumptions. In light of these limitations, it is often useful to provide additional empirical results, such as reduced-form results on student behavior (see, e.g., Section 4.2) and goodness of fit of the estimates (see, e.g., Section 4.4).

Over-identifying Restrictions. As summarized in Proposition 3, if every student is WTT and is assigned to a school, the matching is stable. Stability, however, does not imply that students are WTT and is therefore a less restrictive assumption.

To see the additional restrictions from WTT, let us consider student i who submits a K-choice list L and is matched with school s. Therefore, s must be ranked in L. WTT implies the following conditions on the choice probability:

Pr ¡ σ W pu i , e i q L § § § Z i ; β; |σ W pu i , e i q| K © Pr £ u i,l 1 ¡ ¤ ¤ ¤ ¡ u i,l K ¡ u i,s I, ds I SzL § § § Z i ; β; |σ W pu i , e i q| K; s arg max sSpe i ,P pµqq u i,s ¢ Pr £ s µpu i , e i q arg max sSpe i ,P pµqq u i,s § § § Z i ; β; Spe i , P pµqq (4)
This equality uses the fact that the event,

u i,l 1 ¡ ¤ ¤ ¤ ¡ u i,l K i ¡ u i,s I, ds I SzL ¨, implies
s arg max sSpe i ,P pµqq u i,s ¨but not the reverse. 23 This is because i's feasible schools are either ranked below s in L or are omitted from L; in either case, WTT requires that s is preferred to any other feasible school. Therefore, the first conditional probability on the right-hand side of the equality cannot always be one. As the restrictions implied by stability are just Pr s µpu i , e i q arg max sSpe i ,P pµqq u i,s | Z i ; β; Spe i , P pµqq ¨, the additional restrictions from WTT are summarized in the first term. When the model is identified under stability, Equation ( 4) summarizes the over-identifying restrictions.

Hausman Test. Our estimator βTT uses all the restrictions implied by WTT. Therefore, under the null hypothesis that students are WTT, both estimators βTT and βST are consistent but only βTT is asymptotically efficient. Under the alternative that the matching is stable but not all students are WTT, only βST is consistent.

In this setting, the general specification test developed by Hausman (1978) can be 23 We also make use of the exogeneity of the set of feasible schools (Assumption EXO2) and the exogeneity of the length of submitted ROL (Assumption WTT2). Therefore, Pr £ s µpu i , e i q arg max sSpei,P pµqq

u i,s § § § Z i ; β; Spe i , P pµqq Pr £ s arg max sSpei,P pµqq u i,s § § § Z i ; β; |σ W pu i , e i q| K .
applied by computing the following test statistic:

T H p βST ¡ βTT q I p VST ¡ VTT q ¡1 p βST ¡ βTT q,
where p VST ¡ VTT q ¡1 is the inverse of the difference between the asymptotic covariance matrices of βST and βTT .24 Under the null hypothesis, T H χ 2 pd β q, where d β is the dimension of β. If the model is correctly specified and the matching is stable, the rejection of the null hypothesis implies that WTT is violated in the data.

Testing Over-identifying Restrictions. The above Hausman test requires that we have a consistent and efficient estimator, βTT . When relying on MLE or GMM, this calls for strong parametric assumptions. An alternative is to construct a test for overidentifying restrictions (Hansen, 1982), which is made feasible because of the nesting structure of WTT and stability due to Proposition 3. Instead of requiring βTT to be asymptotically efficient, the test for over-identifying restrictions only requires that βTT utilizes more restrictions than βST . With Equation ( 4), we can separate out the additional restrictions and test whether they are satisfied based on Hansen (1982).

No-blocking among Assigned Students. The above estimation and tests can be applied even if stability is violated. Part (i) of Proposition 3 states that whenever a WTT student is assigned, she is matched with her favorite feasible school and thus is not in any blocking pair. However, this no-blocking condition can be violated among unassigned students, implying the violation of stability. We can thus re-formulate the above tests as WTT against "no-blocking among assigned students." The estimation based on "noblocking among assigned students" will exclude unassigned students; it does not create selection bias under the null hypothesis, because the length of every submitted ROL, which determines the probability of being unassigned, is exogenous under WTT.

Undominated Strategies and Stability

The stability-based approach described above is only valid when the matching is stable.

However, as we have shown theoretically, stability can fail. Without stability, one may consider the undominated-strategies assumption, under which observed ROLs are students' true partial preference orders. That is, a submitted ROL, L i , respects i's true preference order among the schools ranked in L i (see, for an example, Figure 1).

These partial orders provide information that can be used to identify student preferences, but only partially, because the econometric structure is now incomplete (Tamer, 2003). In other words, for a student with type pu i , e i q, the assumption of undominated strategies does not predict a unique ROL for the student. As we shall see, undominated strategies lead to a set of inequality restrictions that can be satisfied by a set of β's, instead of a unique vector of β. Therefore, we lose point identification.

Moment Inequalities. Students' submitted ROLs can be used to form conditional moment inequalities. Without loss of generality, consider two schools s 1 and s 2 . Since not everyone ranks both schools, the probability of i, who adopts the strategy σpu i , e i q, ranking s 1 before s 2 , i.e., s 1 ¡ σpu i ,e i q s 2 , is:

Pr s 1 ¡ σpu i ,e i q s 2 | Z i ; β ¨ Pr pu i,s 1 ¡ u i,s 2 and s 1 , s 2 σpu i , e i q | Z i ; βq ¤ Pr pu i,s 1 ¡ u i,s 2 | Z i ; βq (5)
The first equality is due to undominated strategies, and the inequality defines a lower bound for the conditional probability of u i,s 1 ¡ u i,s 2 . Similarly, an upper bound is:

Pr pu i,s 1 ¡ u i,s 2 | Z i ; βq ¤ 1 ¡ Pr s 2 ¡ σpu i ,e i q s 1 | Z i ; β ¨. (6)
Inequalities ( 5) and ( 6) yield the following conditional moment inequalities:

Prpu i,s 1 ¡ u i,s 2 | Z i ; βq ¡ E 1ps 1 ¡ σpu i ,e i q s 2 q | Z i ; β $ ¥ 0; 1 ¡ E 1ps 2 ¡ σpu i ,e i q s 1 q | Z i ; β $ ¡ Pr pu i,s 1 ¡ u i,s 2 | Z i ; βq ¥ 0.
Similar inequalities can be computed for any school pair and can be generalized to any n schools in S, for 2 ¤ n ¤ S. In the simulations and empirical analysis, we focus on inequalities for pairs. The bounds become uninformative if n ¥ 3, because not many schools are simultaneously ranked by the majority of students. We interact Z i with the conditional inequalities and obtain M 1 unconditional moment inequalities, pm 1 , . . . , m M 1 q.

Estimation with Moment Inequalities. For estimation with moment inequalities, one can follow the approach of Andrews and Shi (2013), which is valid for both point and partial identifications. The objective function is a test statistic, T M I pβq, of the Cramer-von Mises type with the modified method of moments (or sum function). With the unconditional moment inequalities, it is constructed as follows:

T M I pβq M 1 j1 mj pβq σj pβq & 2 ¡ (7)
where mj pβq and σj pβq are the sample mean and standard deviation of the jth moment, m j pβq, respectively; and r s ¡ is such that ras ¡ mint0, au. One can then follow Bugni et al. (2017) to construct marginal confidence intervals. For a given coordinate β k of β, the authors test the hypothesis H 0 : β k β 0 , for a given β 0 R. The confidence interval for β k 's true value is the convex hull of all β 0 's at which H 0 is not rejected.

While the assumption of undominated strategies seems plausible, it should be noted that the above approach often leads to uninformative confidence intervals of parameters of interest, constrained by the available econometric techniques. However, one can integrate the inequalities with the restrictions implied by stability, when stability is also plausible.

Integrating Stability with Undominated Strategies

An important advantage of the stability-based approach is that it only requires data on the admission outcomes. However, submitted ROLs are often observed and can be used to improve estimation efficiency. Under the assumption that stability provides point identification of student preferences, these ROLs provide over-identifying information that can be used together with stability in estimation.

The potential benefits can be illustrated in a simple example. Consider a constrained/truncated DA where students are only allowed to rank up to three schools out of four. With personalized sets of feasible schools under the stability assumption, the preferences over two schools, say s 1 and s 2 , are estimated mainly from the sub-sample of students who are assigned to either of these schools while having priority indices above the cutoffs of both. Yet it is possible that all students include s 1 and s 2 in their ROLs, even if these schools are not ex post feasible for some students. In such a situation, all students could be used to estimate the preference order of s 1 and s 2 , rather than just a sub-sample. As shown below, this argument can be extended to the case where two or more schools are observed being ranked by a subset of students.

Moment Equalities. To integrate the above over-identifying information in ROLs with that from stability, we reformulate the likelihood function described in Equation ( 3) into moment equalities. The choice probability of the matched school can be rewritten as a moment condition by equating theoretical and empirical probabilities:

I i1 Pr ¡ s arg max s I Spe i ,P q pu i,s Iq | Z i , P pµq; β © ¡ E ¡ I i1 1pµpu i , e i q sq © 0, ds S,
where 1pµpu i , e i q sq is an indicator function taking the value of one if and only if µpu i , e i q s. We again interact the variables in Z with the above conditions, leading to

M 2 moment equalities, pm M 1 1 , . . . , m M 1 M 2 q.
Estimation with Moment (In)equalities. To obtain consistent point estimates with both equality and inequality moments (henceforth, moment (in)equalities), we augment the test statistic in Equation ( 7) to incorporate the M 2 unconditional moment equalities:

T M EI pβq M 1 j1 mj pβq σj pβq & 2 ¡ M 1 M 2 jM 1 1 mj pβq σj pβq & 2 . ( 8
)
We denote the point estimate βMEI , which minimizes T M EI pβq, and we can take the same approach as in Bugni et al. (2017) to construct marginal confidence intervals for β.

Testing Stability against Undominated Strategies

Given the identification of student preferences under stability, the moment inequalities add over-identifying information. This constitutes a test of stability, provided that students do not play dominated strategies. More precisely, if both assumptions are satisfied, the moment (in)equalities in Section 2.5.1 should yield a point estimate that fits the data relatively well; otherwise, there should not exist a point β that satisfies all moment (in)equalities. Formally, we follow the specification test in Bugni et al. (2015).

It should be noted that, for the above test, we maintain the undominated-strategies assumption, which may raise concerns, because students could make mistakes as documented in several real-life contexts; moreover, untrue partial preference ordering is not dominated under the school-proposing DA. We revisit these issues in Section 5.2.

The discussion in Section 2.5 provides another test of the undominated-strategies assumption, which also relies on the non-emptyness of the identified set under the null hypothesis (Bugni et al., 2015). That is, if there is no value of β satisfying the moment inequalities, the undominated-strategies assumption is not satisfied. Unfortunately, the available methods of moment (in)equalities tend to result in conservative confidence sets of parameters, which implies that this test may lack power.

Results from Monte Carlo Simulations

To illustrate the proposed estimation approaches and tests, we carry out Monte Carlo simulations, the details of which are consigned to Appendix C.

Bayesian Nash equilibrium of the school choice problem is simulated in two settings where I students compete for admission to 6 schools with per capita capacities tq s u 6 s1 t0.1, 0.1, 0.05, 0.1, 0.3, 0.3u. 25 The first is the constrained/truncated DA where students are allowed to rank up to K schools (K 6). The second setting, labelled as DA with cost, allows students to rank as many schools as they wish but imposes a constant marginal cost c per additional school in the list after the first choice.

Student preferences over schools follow a random utility model:

u i,s α s ¡ d i,s 3pa i ¤ ās q i,s , (9)
where α s is school s's fixed effect; d i,s is the distance from student i's residence to s; a i is i's ability; ās is school s's quality; and i,s is randomly drawn from the type-I extreme value distribution. Student priority indices are constructed such that (a) i's priority index at each school is correlated with her ability a i (correlation coefficient 0.7) and (b) i's priority indices at any two schools s and s I are also correlated (correlation coefficient 0.7).

Several lessons can be drawn from these simulations. The first is that in both settings, 25 Appendix C.2 describes the details on solving equilibrium. In general, there are multiple equilibria. We focus on the one that is found by an algorithm iterating over the following steps: (i) for each candidate ROL (a true partial preference order of the schools), every student calculates the admission probability at each school by comparing her priority indices to the cutoff distribution; (ii) each student selects the ROL that maximizes her expected utility; (iii) the matchings across M simulation samples jointly lead to an updated cutoff distribution; (iv) students update the admission probabilities based on the updated distribution. The initial cutoff distribution is the empirical cutoff distribution with strictly truth-telling students, and steps (i)-(iv) are repeated until a fixed point in the cutoff distribution is found. the distribution of school cutoffs is close to jointly normal and degenerates as school capacities and the number of students increase proportionally while holding constant the number of schools (Figure 2); the matching is almost stable (i.e., almost every student is assigned to her favorite feasible school) even in moderately-sized economies. By contrast, WTT is often violated among the majority of the students, even when they can rank 4 out of 6 schools (constrained DA) or when the cost of including an extra school is negligibly small (DA with cost). 26 When the application cost increases, equilibrium strategies may prescribe that many students rank fewer than 6 schools even though they are allowed to rank all of them. Based on these results, observing that only a few students make full use of their ranking opportunities may not be viewed as a compelling argument in favor of truth-telling when the application cost is a legitimate concern.

The second insight is that stability leads to estimates much closer to the true values than WTT. Table 2 reports the results from estimation under each of the following assumptions: (i) weak truth-telling (columns 2-4); (ii) stability (columns 5-7); and (iii) stability and undominated strategies (columns 8-10). Panel A is for the constrained/truncated DA where students are allowed to rank up to 4 schools; Panel B is for the DA with a marginal application cost equal to 10 ¡6 . an unconstrained DA where students can rank as many schools as they wish, but incur a constant marginal cost c 10 ¡6

for including an extra school in their ROL beyond the first choice (Panel B). Under assumptions (i) and (ii), student preferences are estimated using maximum likelihood estimation. Under assumption (iii), they are estimated using Andrews and Shi (2013)'s method of moment (in)equalities. Column 1 reports the true values of the parameters. The mean and standard deviation (SD) of point estimates across the Monte Carlo samples are reported in columns 2, 5 and 8, and in columns 3, 6 and 9, respectively. Columns 4, 7 and 10 report the coverage probabilities (CP) for the 95 percent confidence intervals. The confidence intervals in models (i) and (ii) are the Wald-type confidence intervals obtained from the inverse of the Hessian matrix. The marginal confidence intervals in model (iii) are computed using the method proposed by Bugni et al. (2017). Truth-telling is tested against stability by constructing a Hausman-type test statistic from the estimates of both approaches. Stability is tested against undominated strategies by checking if the identified set of the moment (in)equality model is empty, using the test proposed by Bugni et al. (2015). See Appendix C for details on the Monte Carlo simulations.

The WTT-based estimator ( βTT ) is severely biased (column 2). Particularly in Panel A, we note that low-ability students' valuation of the most popular schools (e.g., School 6) tends to be underestimated, because such schools are more likely to be omitted from these students' ROLs due to their low admission probabilities. This bias is also present among small schools (e.g., Schools 3 and 4), which are often left out of ROLs because their cutoffs tend to be higher than those of equally desirable but larger schools.

By contrast, the average of the stability-based estimates ( βST ) is reasonably close to the true values. Its standard deviations, however, are larger than those obtained under WTT. This efficiency loss is a direct consequence of ignoring the information content of ROLs. 27 The Hausman test strongly rejects WTT in favor of stability.

The estimator based on moment (in)equalities ( βMEI ), which integrates stability with information in ROLs, is also consistent (column 8). Moreover, the test based on moment (in)equalities never rejects the null hypothesis that stability is consistent with undominated strategies. A limitation of this approach, however, is that the currently available methods for conducting inference based on moment (in)equalities are typically conservative. As a result, the 95 percent marginal confidence intervals based on moment (in)equalities cover the true values too often (coverage probability, or CP, is close to one).

School Choice in Paris

Since 2008, the Paris Education Authority (Rectorat de Paris) assigns students to public high schools based on a version of the school-proposing DA called AFFELNET (Hiller and Tercieux, 2014). At the district level, student priority indices are not school-specific (as detailed below) and the mechanism is equivalent to a serial dictatorship.

Towards the end of the Spring term, final-year middle school students who are admitted to the upper secondary academic track (Seconde Générale et Technologique)28

are requested to submit an ROL of up to 8 public high schools to the Paris Education Authority. Students' priority indices are determined as follows:

(i) Students' academic performance during the last year of middle school is graded on a scale of 400 to 600 points.

(ii) Paris is divided into four districts. Students receive a "district" bonus of 600 points at each school located in their home district. Thus, students applying to a withindistrict school have full priority over out-of-district applicants to the same school.

(iii) Low-income students are awarded a bonus of 300 points. 29 As a result, these students are given full priority over all other students from the same district.

The DA algorithm is run at the end of the academic year to determine school assignment for the following academic year. Unassigned students can participate in a supplementary round of admissions by submitting a new ROL of schools among those with remaining seats, the assignment mechanism being the same as for the main round.

Note that the mechanism would be strategy-proof if there were no constraints on the length of ROLs, because it is equivalent to serial dictatorship. Nonetheless, under the current mechanism, it is still a dominated strategy to submit an ROL that is not a partial order of true preferences (Proposition 2).

Data

For our empirical analysis, we use data from Paris' Southern District (Sud ) and study the behaviors of 1,590 within-district middle school students who applied for admission to the district's 11 public high schools for the academic year 2013-14. Owing to the 600-point "district" bonus, this district is essentially an independent market.30

Along with socio-demographic characteristics and home addresses, our data contain all the relevant variables to replicate the matching algorithm, including the school capacities, the submitted ROLs, and the priority indices (converted into percentiles between Enrollment data further reveals a high level of compliance with the assignment outcome. Among the assigned students, 96 percent attend the school they were matched with (Appendix Table E1), about 1 percent attend a public high school different from their assignment school, and less than 3 percent opt out to enroll in a private school.

Evaluating the Assumptions: Reduced-Form Evidence

To evaluate the WTT and stability assumptions, we investigate if students are less likely to rank schools at which they expect low admission probabilities. Similar to "skipping the impossible" as in Example 1, this behavior would be inconsistent with WTT.

Figure 3 focuses on the district's four most selective schools (as measured by their cutoffs). For each school, we separately plot the fraction of students who rank it in their ROL as a function of their distance to the school cutoff, measured by the difference (using the original scale in points) between the student's priority index and the cutoff. 32

31 See Appendix B for a description of the data sources and Appendix Figure E1 for a map. 32 We restrict the sample for a school to students whose score is no more than 50 points away from its cutoff. Due to the low-income bonus of 300 points, low-income students' priority indices are always well above the cutoffs. They are therefore not considered in the analysis. Each plot shows that almost all students with a priority index above a school's cutoff include that school in their ROL, whereas the fraction of students ranking the school decreases rapidly when the priority index falls below the cutoff. Irrespective of strategic considerations, one might expect high priority students to have a stronger preference for the most selective schools-since priorities are positively correlated with academic performance-and hence to rank them more often. However, the kink around the cutoffs is consistent with students omitting the most selective schools from their ROL because of the low admission probabilities. In Appendix D.1, we show that the kink-shaped relationship between student priority index and their ranking behavior is robust to controlling for potential determinants of preferences, including distance to school and the student's DNB exam scores in French and math. Recall that DNB scores are not used to calculate the priority indices. These results cannot be easily reconciled with truth-telling behavior.

The evidence in Figure 3 suggests the potential influence of expected admission probabilities on student ranking behavior. At the time of application, students know their academic grades and low-income status but not their priority ranking nor the ex post cutoffs. 33 They can, however, gather information on past cutoffs to assess admission probabilities. While we do not have direct information on students' beliefs, Figure 4 shows that the current year (2013) cutoffs are similar to those from the previous year (2012). 34 This lends support to the assumption that students have some ability to predict their admission probabilities. Although not a necessary condition for the matching to be stable, this feature makes the stability assumption more likely to be satisfied.

Estimation and Test Results

We parameterize student i's utility of being matched with school s as follows:

u i,s α s ¡ d i,s Z I i,s γ λ i,s
, s 1, . . . , 11;

(10) 33 This uncertainty in both priority ranking and cutoffs may explain why some students find it optimal to rank multiple schools, given that the cost of ranking up to 8 choices is arguably negligible. 34 The comparison could not be performed for earlier years due to the modifications in the computation of the priority index and the small changes in the set of available schools.

where α s is the school fixed effect, d i,s is the distance to s from i's residence, and Z i,s is a vector of student-school-specific observables. As observed heterogeneity, Z i,s includes two variables that capture potential non-linearities in the disutility of distance and control for potential behavioral biases towards certain schools: "closest school" is a dummy variable equal to one if s is the closest to student i among all 11 schools; "high school co-located with middle school" is another dummy that equals one if high school s and the student's middle school are co-located at the same address. 35 To account for students' heterogeneous valuation of school quality, interactions between student scores and school scores are introduced separately for French and math, as well as an interaction between own SES and the fraction of high SES students in the school. These school attributes are measured among the entering class of 2012, whereas our focus is on students applying for admission in 2013. We normalize the variables in Z i,s so that each school's fixed effect can be interpreted as the mean valuation, relative to School 1, of a non-high-SES student who has median scores in both French and math, whose middle school is not co-located with that high school, and for whom the high school is not the closest to her residence.

The error term i,s is assumed to be an i.i.d. type-I extreme value, and the variance of unobserved heterogeneity is λ 2 multiplied by the variance of i,s . The effect of distance is normalized to ¡1, and, therefore, the fixed effects and γ are all measured in terms of willingness to travel. As a usual position normalization, α 1 0. We do not consider outside options because of students' almost perfect compliance with the assignment outcome.

Using the same procedures as in the Monte Carlo simulations (described in Appendix C), we obtain the results summarized in Table 5, where each column reports estimates under a given set of identifying assumptions: (i) weak truth-telling (column 1);

(ii) stability (column 2); and (iii) stability with undominated strategies (column 3). 36 The results provide clear evidence that the WTT-based estimates (column 1) are rather different from the others. Specifically, a downward bias is apparent for popular 35 There are five such high schools in the district. 36 For the estimates in column 3, we use the method of moment (in)equalities where inequalities are constructed as described in Section 2.5. Determined by Z i,s , we interact French score, math score, and distances to Schools 1 and 2 with the conditional moments. Although one could use more variables, e.g., SES status and distance to other schools, they provide little additional variation. In principle, the assumption of undominated strategies alone implies partial identification (Section 2.5). Because stability is not rejected by our test, we do not present results based on this approach (available upon request). We note that the marginal confidence intervals from moment inequalities only turn out to be wide in our empirical setting, and hence are relatively uninformative. The possible reasons are that the empirical bounds for the probability of a preference ordering over a pair of schools are fairly wide, and that the available methods to conduct inference based on moment inequalities are typically conservative. 2), rejects WTT in favor of stability (p-value 0.01); a test based on moment equalities and inequalities does not reject the null hypothesis that stability is consistent with undominated strategies at the 5 percent significance level. schools that are not ranked by many students, such as Schools 8 and 11. School 8, which is omitted by 61 percent of students, is deemed by WTT to be less desirable than all the schools included in the ROL, which leads to a low estimated fixed effect. Similarly, the fixed effect estimate of School 11, one of the most popular schools, varies substantially across the identifying assumptions. The under-estimation is mitigated when the model is estimated under a different assumption (columns 2 and 3). Provided that the model is correctly specified, the Hausman test rejects WTT in favor of stability (p-value 0.01); the test based on moment (in)equalities does not reject the null hypothesis that stability is consistent with undominated strategies at the 5 percent significance level.

The results show that "closest school" has no significant effect, but students significantly prefer co-located schools. Compared with low-score students, those with high French (math) scores have a stronger preference for schools with higher French (math) scores. Moreover, high SES students prefer schools that have admitted a larger fraction of high SES students in the previous year (2012).

Although the WTT-based estimates of the coefficients of covariates (Panel B) are not markedly different from the stability-based estimates, one cannot conclude that the WTT assumption produces reasonable results, as shown by the estimates of fixed effects. To provide a better evaluation, we now compare the estimators by their model fit.

Goodness of Fit

In three dimensions (cutoffs, assignment, and revealed preferences), we compare the observed values to those predicted by the estimates from Table 5. This comparison reveals that the stability-based estimates fit the data well, as opposed to those based on WTT (see Appendix D.2 for computational details). Specifically, Figure 5 and Appendix Table D2 show that the stability-based estimates (with or without undominated strategies) predict cutoffs close to the observed ones.37 By contrast, WTT substantially under-predicts the cutoffs of the most popular schools.

Panel A of Table 6 compares each student's predicted assignment to the observed one.

The stability-based estimates have 33-38 percent success rates, whereas the WTT-based estimates accurately predict only 22 percent of the assignments. In Panel B, we take as 5. The simulated cutoffs are averaged over 300 simulated samples. See Appendix D.2 for details.

given the schools that a student has included in her submitted ROL, and compute the probability of observing this particular preference order among the ranked schools. The observed order of students' top two choices has a mean predicted probability of 60 or 62 percent based on the stability-based estimates, higher than the 55 percent achieved by the WTT-based estimates. We next consider the observed order of a student's full list of choices. Again, the stability-based estimates outperform those based on WTT, with an average predicted probability between 2.2 and 2.5 percent for the former versus 1.2 percent for the latter. The predictive power of the stability-based estimates along the two measures in Panel B is noteworthy because the prediction is partly out of sample.38

Summary and Discussion

As a summary of the results, we clarify when each approach is more appropriate for empirical analysis. We also discuss whether the results can be extended to the schoolproposing DA, the case with non-equilibrium behavior, and settings beyond school choice.

Choosing among the Approaches: A Summary

In the preference estimation with real-life data from centralized school choice and college admissions, some practical considerations should be taken into account. Recall that we Notes: This table reports two sets of goodness-of-fit measures comparing the observed outcomes to those predicted under the different sets of identifying assumptions as in Table 5, for the high school assignment of students in the Southern District of Paris. Panel A compares students' observed assignment with their predicted assignment in 300 simulated samples. In all simulations, we vary only the utility shocks, which are kept common across columns 1-3 (see Appendix D.2 for details). Predicted and observed assignments are compared by computing the average predicted fraction of students who are assigned to their observed assignment school, with standard deviations across the simulation samples reported in parentheses; in other words, this is the average fraction of times each student is assigned to her observed assignment in the 300 simulated samples. Panel B uses two measures to compare students' observed partial preference order of given schools (revealed in their submitted ROL) with the prediction, among students who rank at least two schools: (i) mean predicted probability that a student prefers the top-ranked school to the 2nd-ranked in her submitted ROL, which is averaged across students; and (ii) mean predicted probability that a student's partial preference order among the schools in her ROL coincides with the submitted rank order. Due to the logit specification, those probabilities can be calculated without simulation.

focus on the strict-priority setting in which students are ranked based on strict priority indices that are ex ante known privately. Building on the results from our theoretical and empirical analyses, this section emphasizes some of the key market features that deserve careful examination when one decides which approach to use in a given context.

The Nesting Structure of Identifying Assumptions. Our results imply that the identifying assumptions follow a nesting structure, as depicted in Figure 6.

Truth-telling is a natural candidate identifying assumption because of DA's strategyproofness. However, strict truth-telling (i.e., students truthfully rank all schools) is not an equilibrium, if students cannot rank all schools at no cost (Proposition 1). In real-life data, students seldom rank all schools, which calls for a weaker version of the truth-telling assumption. As clarified in the theoretical analysis, weak truth-telling (i.e., students truthfully rank their most preferred schools and omit some least preferred ones) does not follow directly from strategy-proofness, as it requires additional assumptions such as the length of ROLs being independent of preferences.

Stability is an even weaker assumption on student behavior, while still allowing for the Notes: This figure shows the nesting structure of the identifying assumptions that can be used to analyze data generated by DA and its variants in the strict-priority setting. The numbered areas correspond to different combinations of identifying assumptions: 1 strict truth-telling; 2 weak truth-telling and stability; 3 weak truth-telling without stability; 4 stability and undominated strategies; 5 stability without undominated strategies; 6 undominated strategies without stability. identification of preferences. It states that every student is assigned to her favorite ex post feasible school, and is always satisfied when students are strictly truth-telling. Although stability is not guaranteed in all Bayesian Nash equilibria, even when students are weakly truth-telling, it is asymptotically satisfied when the economy grows large (Proposition 4).

The third candidate identifying assumption is that students do not play dominated strategies (Proposition 2), so that submitted ROLs reveal students' partial preference orders of schools. Weak truth-telling is a special case of this more general assumption, whereas stability may hold even if students play dominated strategies.

The Choice of Empirical Approaches. When choosing among the candidate identifying assumptions, consideration should be given to the features of the problem under study, as well as the available data. For each assumption, Table 7 summarizes the features making it more plausible, the required data, and some discussion about identification and estimation. Truth-telling is more likely to be satisfied when students can rank as many schools as they wish at no cost, and face large uncertainty about each school's exact ranking of students. Conditional on students' submitted ROLs being observed, preferences can be estimated using either MLE or GMM. The choice between weak truth-telling and strict truth-telling depends on whether students rank all schools (Section 2.2) and on the importance of outside options (Appendix A.4).

When students face some cost of ranking more schools (e.g., if the length of submittable ROLs is restricted), stability can be a more plausible assumption than truth-telling. Notes: This table describes the empirical approaches to analyses of data generated by DA and its variants in the strictpriority setting. In addition, there are two tests available: (i) weak truth-telling can be tested against stability (H 0 : both weak truth-telling and stability are satisfied; H 1 : only stability is satisfied), e.g., using the Hausman (1978) or Hansen (1982) tests; (ii) stability can be tested against undominated strategies (H 0 : both stability and undominated strategies are satisfied; H 1 : only the undominated-strategies assumption is satisfied) using the approach in Bugni et al. (2015).

This assumption is more likely to hold when the market is larger (i.e., many students and many seats per school), when students are less constrained in applying to multiple schools (e.g., longer ROLs), when they are less uncertain about each school's ranking of all students at the time of application, when they know more about others' preferences, or when it is easier for them to predict school cutoffs (Proposition 5). Our Monte Carlo simulations additionally provide numerical evidence suggesting that stability is a plausible assumption even when students face non-negligible application costs (Appendix C.3).

Estimating preferences based on stability uses information on the admission outcome, the school capacities, and the priority indices, but has the advantage of not requiring data on submitted ROLs. However, it is necessary to assume the conditional independence between priority index and unobserved preference heterogeneity. Compared to truthtelling, the main cost of the stability-based approach is its limited power to identify rich substitution patterns, because the information content of ROLs is discarded.

Weak truth-telling does not always imply stability, but it does imply no-blocking among all assigned students (Proposition 3). Therefore, weak truth-telling can be tested against stability (or no-blocking among assigned students) using the Hausman (1978) and Hansen (1982) tests. It should be emphasized that these tests do not provide definitive proof against truth-telling unless the model is correctly specified and identified.

If it is believed that neither truth-telling nor stability is likely to be satisfied, preferences can still be partially identified under the assumption that students do not play dominated strategies. This assumption is more plausible when no school is either "safe"

or "impossible" for students, making it less likely that students rank some schools in an arbitrary manner. Submitted ROLs can then be used to form conditional moment inequalities that partially identify preferences.

When the conditions for both stability and undominated-strategies assumptions are jointly satisfied, the moment inequalities from the latter assumption provide over-identifying information that can be integrated with the stability assumption to estimate preferences based on all of the available data (ROLs, matching outcome, school capacities, and priority indices). Additionally, the stability assumption can be tested against the undominated-strategies assumption using the specification test in Bugni et al. (2015).

Discussion and Extension

The School-Proposing DA. Our main results can be extended to the school-proposing DA, which is also commonly used in practice (see Table 1). Under this mechanism, schools "propose" to students following the order of student priority indices. Proposition 2 no longer holds; that is, students might have incentives not to report a true partial preference order (Haeringer and Klijn, 2009). Nonetheless, the asymptotic stability result (Proposition 4) is still valid, as its proof does not rely on Proposition 2. Indeed, the matching can be stable in equilibrium (Haeringer and Klijn, 2009).

To summarize, if the market under the school-proposing DA has features making the matching stable (see Table 7), we can formulate identification and estimation of student preferences based on stability. However, the truth-telling assumption no longer has theoretical support, as the school-proposing DA is not strategy-proof for students (Roth, 1982). The approach based on undominated strategies does not apply either, since there are no dominated strategies under this mechanism (Haeringer and Klijn, 2009).

Non-Equilibrium Strategies. We have thus far assumed that everyone plays an equilibrium strategy with a common prior. More realistically, some students could have different information and make mistakes when strategizing.

Indeed, a growing number of studies find that strategic mistakes are common even in strategy-proof environments. Laboratory experiments show that a significant fraction of subjects do not report their preferences truthfully in strategy-proof mechanisms (Chen and Sönmez, 2006). More relevantly, mistakes occur in real-world contexts, e.g., the admissions to Israeli graduate programs in psychology (Hassidim et al., 2016), the medical resident match in the U.S. (Rees-Jones, 2018), and the Australian university admissions (Artemov et al., 2017). Without estimating preferences, these studies show that a nonnegligible fraction of participants make unambiguous mistakes in their ROLs.

However, the vast majority of these mistakes are not payoff relevant. In other words, although some students play dominated strategies, the matching is still close to stable, corresponding to area 5 in Figure 6. Based on these observations, the results in Artemov et al. (2017) imply that, as identifying restrictions, assuming stability can be more robust and more plausible than the assumption of undominated strategies.

Beyond School Choice and College Admissions. Although the analysis has focused on school choice and college admissions, our results can apply to certain assignment procedures based on DA. Let us call agents on the two sides "applicants" and "recruiters," respectively. The key requirement is that when applying, applicants have sufficiently precise information on how recruiters rank them and that researchers observe how recruiters exactly rank applicants. 39 Examples include the assignment of teachers to schools in France (Combe et al., 2016) and the Scottish Foundation Allocation Scheme matching medical school graduates with training programs (Irving, 2011). The estimation approaches discussed in Section 2 could be implemented in these settings.

Conclusion

We present novel approaches to estimating student preferences with school choice or college admissions data generated by the popular Deferred Acceptance mechanism when applicants are ranked strictly by some ex-ante known priority index. We provide theoretical and empirical evidence showing that, in this commonly observed setting, it can be rather restrictive to assume that students truthfully rank schools when applying for 39 Without information on how either side ranks the other, it becomes the classical two-sided matching, and additional assumptions are needed for identification and estimation ( Chiappori and Salanié, 2016).

admission. Instead, stability (or justified-envy-freeness) of the matching provides rich identifying information, while being a weaker assumption on student behavior. Assuming that students do not play dominated strategies, we also discuss methods with moment inequalities, which can be useful with or without stability. A series of tests are proposed to guide the selection of the appropriate approach.

The estimation and testing methods are illustrated with Monte Carlo simulations.

When applied to school choice data from Paris, our results are more consistent with stability than with truth-telling. Reduced-form evidence on ranking behavior suggests that some students omit the most selective schools from their list because of low admission probabilities. Provided that the model is correctly specified, our proposed tests reject truth-telling but not stability. Compared with our preferred estimates based on stability (with or without imposing undominated strategies), assuming truth-telling leads to an under-estimation of preferences for popular or small schools. Moreover, the stabilitybased estimators outperform the truth-telling-based estimator in predicting matching outcomes and student preferences.

Our approaches are applicable to many school choice and college admissions systems around the world, as well as to other matching schemes such as teacher assignment in France and medical matching in Scotland.

types are such that: (a) i's priority index is the lowest among all students at school r 1 i ; (b) i's priority index is the highest among all students at all other schools; and (c) all other students have r 1 i as their most preferred school. In this event, by Claim 1, all students rank r 1 i as top choice. Therefore, i is rejected by r 1 i , but she is definitely accepted by her second choice. Because STT means she is accepted by r 2 i , Equation (A.1) implies that σpθ i q must also rank r 2 i as the second choice. This proves the claim.

We can continue proving a series of similar claims that σpθ i q and rpu i q must agree on top S choices. In other words, σpθ i q rpu i q. This proves that there is no non-STT equilibrium, and, therefore, STT is the unique Bayesian Nash equilibrium.

(ii) Necessity. The following shows that the zero-application-cost condition is necessary for STT to be an equilibrium strategy for every student type.

Without loss of generality, suppose that CpSq ¡ CpS ¡ 1q ¡ 0 , which implies that applying to the Sth choice is costly. Let σ ST T be the STT strategy. Let us consider students whose Sth choice in terms of true preferences, r S i , has a low cardinal value. More specifically, u i,r S i CpSq ¡ CpS ¡ 1q. For such students, σ ST T is a dominated strategy, dominated by dropping r S i and submitting pr 1 i , . . . , r S i q. In other words, σ ST T is not an equilibrium strategy for these students.

In fact, σ ST T is not an equilibrium strategy for more student types, given others playing σ ST T . If a student drops an arbitrary school s and submits a partial true preference order L i of length pS ¡ 1q, the saved cost of is CpSq ¡ CpS ¡ 1q, while the associated foregone benefit is at most u i,s ³ a s L i , e i ; σ ST T ¡i pθ ¡i q, e ¡i ¨dGpθ ¡i q. The saved cost can exceed the forgone benefit because the latter can be close to zero when s tends to have cutoff much higher than e i,s or when i can be almost certainly accepted by more desirable schools, given that everyone else plays STT. When it is the case, i deviates from STT.

The above arguments can be extended to any non-zero application cost.

Proof of Lemma 1.

The sufficiency of the first statement is implied by the strategy-proofness of DA and by DA producing a stable matching when everyone is STT. That is, STT is a dominant strategy if C p|L|q 0 for all L, which always leads to stability.

To prove its necessity, it suffices to show that there is no dominant strategy when C p|L|q ¡ 0 for some L L.

If C p|L|q V for some L, we are in the case of the constrained/truncated DA, and it is well known that there is no dominant strategy (see, e.g., Haeringer and Klijn, 2009). Now suppose that 0 C p|L|q V for some L L. If a strategy ranks fewer than S schools with a positive probability, we know that it cannot be a dominant strategy for the same reason as in the contrained/truncated DA. If a strategy does always rank all schools, then it is weakly dominated by STT. We therefore need to show that STT is not a dominant strategy for all student types, for which we can construct an example where it is profitable for a student to drop some schools from her ROL to save application costs for some profiles of ROLs submitted by other students.

Therefore, there is no dominant strategy when C p|L|q ¡ 0 for some L L, and hence stability cannot be an equilibrium outcome in dominant strategy.

The second statement is implied by Proposition 1 and that DA produces a stable matching when everyone is STT.

Proof of Proposition 3.

(i) Suppose that given a realized matching μ, there is a student-school pair pi, sq such that μpθ i q $ r, u i,s ¡ u i,μpθ i q , and e i,s ¥ P s pμq. That is, i is not matched with her favorite feasible school.

Since i is weakly truth-telling, she must have ranked all schools that are more preferred to μpθ i q, including s. The DA algorithm implies that i must have been rejected by s at some round given that she is accepted by a lower-ranked school μpθ i q. As i is rejected by s in some round, the cutoff of s must be higher than e i,s . This contradiction rules out the existence of such matchings.

(ii) Given the result in part (i), when every student who has at least one feasible school is matched, everyone must be assigned to her favorite feasible school. Moreover, unmatched students have no feasible school. Therefore, the matching is stable.

A.2 Asymptotics: Proofs and Additional Results

We now present the proofs of results in the main text as well as some additional results on the asymptotics and the continuum economy.

A-4

A.2.1 Matching and the DA Mechanism in the Continuum Economy

We follow Abdulkadiroglu et al. (2015) and Azevedo and Leshno (2016) to extend the definitions of matching and DA to the continuum economy, E.

Similar to that in finite economies, a matching in E is a function µ : Θ Ñ S tru, such that (i) µ pθ i q s if student i is matched with s; (ii) µ pθ i q r if student i is unmatched; (iii) µ ¡1 psq is measurable and is the set of students matched with s, while Gpµ ¡1 psqq ¤ q s ; and (iv) for any s S, the set tθ Θ :

u i,µpθq ¤ u i,s u is open.
The last condition is imposed because in the continuum model it is always possible to add a measure-zero set of students to a school without exceeding its capacity. This would generate multiplicities of stable matchings that differ only in sets of measure zero.

Condition (iv) rules out such multiplicities. The intuition is that the condition implies that a stable matching always allows an extra measure zero set of students into a school when this can be done without compromising stability.

The DA algorithm works almost the same as in a finite economy. Abdulkadiroglu et al. (2015) formally define the algorithm, and prove that it converges. A sketch of the mechanism is as follows. At the first step, each student applies to her most preferred school. Every school tentatively admits up to its capacity from its applicants according to its priority order, and rejects the rest if there are any. In general, each student who was rejected in the previous step applies to her next preferred school. Each school considers the set of students it has tentatively admitted and the new applicants. It tentatively admits up to its capacity from these students in the order of its priority, and rejects the rest. The process converges when the set of students that are rejected has zero measure. Although this process might not complete in finite time, it converges in the limit (Abdulkadiroglu et al., 2015).

A.2.2 Proofs of Propositions 4 and 5

We start with some intermediate results. Similar to Azevedo and Leshno (2016), we define the convergence of tF pIq u IN to E if q pIq converges to q and if G pIq converges to G in the weak-* topology. A.1 We similarly define the convergence of tF pIq , σ pIq u IN to A.1 The weak-* convergence of measures is defined as ³ Xd ĜpIq Ñ ³ XdG for every bounded continuous function X : r0, 1s 2S Ñ R, given a sequence of realized empirical distributions t ĜpIq u IN . This is also known as narrow convergence or weak convergence.

A-5 pE, σ V q, additionally requiring the empirical distributions of ROLs prescribed by σ pIq in finite economies to converge to those in E prescribed by σ V . Lemma A1. For a sequence of random economies and equilibrium strategies tF pIq , σ pIq u IN satisfying Assumption 2, P pIq , the random cutoff associated with pF pIq , σ pIq q, converges to P pµ pE,σ V q q almost surely.

Proof of Lemma A1.

First, we note that the sequence of random economies tF pIq u IN converges to E almost surely. By construction, q pIq converges to q. Moreover, by the Glivenko-Cantelli Theorem, the empirical distribution functions G pIq converge to G in the weak-* topology almost surely. Therefore, we have that tF pIq u IN converges to E almost surely.

Second, we show that tF pIq , σ pIq u IN converges to pE, σ V q almost surely. As σ pIq and σ V map student types to ROLs, tF pIq , σ pIq u IN is a sequence of random economies that are defined with ROLs. A student's "type" is now characterized by pL i , e i q L ¢ r0, 1s S . Let M V be the probability measure on the modified student types in pE, σ V q. That is, for any Λ L ¢ r0, 1s S , M V pΛq Gptθ i Θ | pσ V pθ i q, e i q Λuq. Similarly, M pIq is the empirical distribution of the modified types in the random economy tF pIq , σ pIq u. We shall show that M pIq converges to M V in the weak-* topology almost surely.

Let X : L ¢ r0, 1s S Ñ rx, xs R be a bounded continuous function. We also define M pIq σ V the random probability measure on L ¢ r0, 1s S when students play σ V in random economy F pIq . Because the strategy is fixed at σ V for all I, by the same arguments as above (i.e., the convergence of q pIq to q and the Glivenko-Cantelli Theorem), M pIq σ V converges to M V almost surely.

Let Θ pIq tθ i Θ | σ pIq pθ i q $ σ V pθ i qu. We have the following results:

§ § § § » XdM pIq ¡ » XdM V § § § § ¤ § § § § » XdM pIq ¡ » XdM pIq σ V § § § § § § § § » XdM pIq σ V ¡ » XdM V § § § § § § § § » Xpσ pIq pθ i q, e i qdG pIq ¡ » Xpσ V pθ i q, e i qdG pIq § § § § § § § § » XdM pIq σ V ¡ » XdM V § § § § § § § § » θ i Θ pIq Xpσ pIq pθ i q, e i q ¡ Xpσ pVq pθ i q, e i q $ dG pIq § § § § § § § § » XdM pIq σ V ¡ » XdM V § § § § ¤px ¡ xqG pIq pΘ pIq q § § § § » XdM pIq σ V ¡ » XdM V § § § § , A-6
where the first inequality is due to the triangle inequality; the equalities are because of the definitions of M pIq and M pIq σ V and because Xpσ pIq pθ i q, e i q Xpσ V pθ i q, e i q whenever θ i Θ pIq ; the last inequality comes from the boundedness of X.

Because lim IÑV GpΘ pIq q 0 by Assumption 1 and G pIq converges to G almost surely, lim IÑV G pIq pΘ pIq q 0 almost surely. Moreover, M pIq σ V converges to M V almost surely, and thus the above inequalities implies This proves tF pIq , σ pIq u IN converges to pE, σ V q almost surely. By Proposition 3 of Azevedo and Leshno (2016), P pIq converges to P pµ pE,σ V q q almost surely.

Proposition A1. Given Assumption 1, in a sequence of random economies and equilibrium strategies tF pIq , σ pIq u IN satisfying Assumption 2, µpE, σ V q µ V and thus σ V pθ i q ranks µ V pθ i q for all θ i Θ except a measure-zero set of student types.

Proof of Proposition A1.

Suppose that the first statement in the proposition is not true, Gptθ i Θ | µ pE,σ V q pθ i q $ µ V pθ i quq ¡ 0 and therefore P pE, σ V q $ P V . Because there is a unique stable matching in E, which is the unique equilibrium outcome, by Assumption 1, µ pE,σ V q is not stable and thus is not an equilibrium outcome.

Recall that P pE, σ V q, P V , µ pE,σ V q , and µ V are constants, although their counterparts in finite economies are random variables. Moreover, σ pIq and σ V are not random either.

For some η, ξ ¡ 0, we define: Θ pη,ξq 6 9 9 9 9 9 9 8 9 9 9 9 9 9 7

θ i Θ § § § § § § § § § § § §
e i,µ V pθ i q ¡ P V µ V pθ i q ¡ η, e i,µ pE,σ V q pθ i q ¡ P µ pE,σ V qpθ i q pµ pE,σ V q q ¡ η, e i,s ¡ P s pµ pE,σ V q q ¡η, for all s ranked above µ pE,σ V q pθ i q by σ V pθ i q;

u i,µ V pθ i q ¡ u i,µ pE,σ V q pθ i q ¡ ξ.

D G G G G G G F G G G G G G E
, Θ pη,ξq must have a positive measure for some η, ξ ¡ 0 and is a subset of students who can form a blocking pair in µ pE,σ V q . Clearly, σ V pθ i q ranks µ pE,σ V q pθ i q but not µ V pθ i q for all θ i Θ pη,ξq . We further define: Θ pIq pη,ξq Θ pη,ξq tθ i Θ | σ pIq pθ i q ranks µ pE,σ V q pθ i q but not µ V pθ i qu.

By Assumption 2, σ pIq converges to σ V , and thus Θ pIq pη,ξq converges to Θ pη,ξq and has a positive measure when I is sufficiently large.

A-7

We show below that tσ pIq u IN is not a sequence of equilibrium strategies. Consider a unilateral deviation for θ i Θ pIq pη,ξq from σ pIq pθ i q to L i such that the only difference between the two actions is that µ pE,σ V q pθ i q, ranked in σ pIq pθ i q, is replaced by µ V pθ i q in L i while L i is kept as a partial order of i's true preferences.

By Lemma A1, for 0 φ ξ{p1 ξq there exists n N such that, in all F pIq with I ¡ n, i is matched with µ pE,σ V q pθ i q with probability at least p1¡φq if submitting σ pIq pθ i q but would have been matched with µ V pθ i q if instead L i had been submitted.

Let EUpσ pIq pθ i qq be the expected utility when submitting σ pIq pθ i q. Then EUpσ pIq pθ i qq ¤ p1¡φqu i,µ pE,σ V q pθ i q φ because max s tu i,s u ¤ 1 by assumption, and EUpL i q ¥ p1¡φqu i,µ V pθ i q .

The difference between the two actions is:

EUpL i q ¡ EUpσ pIq pθ i qq ¥p1 ¡ φqu i,µ V pθ i q ¡ p1 ¡ φqu i,µ pE,σ V q pθ i q ¡ φ ¥p1 ¡ φqξ ¡ φ ¡ 0,
which proves that tσ pIq u IN is not a sequence of equilibrium strategies. This contradiction further shows that Gptθ i Θ | µ pE,σ V q pθ i q $ µ V pθ i quq 0 and that σ V pθ i q ranks µ V pθ i q for all θ i Θ except a measure-zero set of student types.

We are now ready to prove Proposition 4.

Proof of Proposition 4.

Part (i) is implied by Lemma A1 and Proposition A1. Because F pIq converges to E almost surely and σ pIq converges to σ V , P pIq converges to P pµ pE,σ V q q almost surely. Moreover, µ pE,σ V q µ V except a measure-zero set of students implies that P pµ pE,σ V q q P V . Therefore, lim IÑV P pIq P V almost surely.

To show part (ii), we first define Θ pIq tθ i Θ | σ pIq pθ i q $ σ V pθ i qu. By Assumption 1, G pIq pΘ pIq q converges to zero almost surely. We have the following inequalities:

G pIq £5 θ i Θ : µ pIq pθ i q arg max sSpe i ,P pIq q u i,s C ¤ § § § § § G pIq £5 θ i Θ : µ pIq pθ i q arg max sSpe i ,P pIq q u i,s C ¡ G pIq £5 θ i Θ : µ pIq pθ i q arg max sSpe i ,P V q u i,s C § § § § § G pIq £5 θ i Θ : µ pIq pθ i q arg max sSpe i ,P V q u i,s C ¤G pIq 2 θ i Θ | Spe i , P V q $ Spe i , P pIq q @¨ G pIq 2 θ i Θ | µ pIq pθ i q $ µ V pθ i q @¨, A-8
where the first inequality is due to the triangle inequality; the second inequality is because 2 θ i Θ : µ pIq pθ i q arg max sSpe i ,P pIq q u i,s @ and 2 θ i Θ : µ pIq pθ i q arg max sSpe i ,P V q u i,s @ can possibly differ only when Spe i , P V q $ Spe i , P pIq q and because:

5 θ i Θ : µ pIq pθ i q arg max sSpe i ,P V q u i,s C 2 θ i Θ | µ pIq pθ i q $ µ V pθ i q @ . Furthermore, G pIq 2 θ i Θ | Spe i , P V q $ Spe i , P pIq q @ G pIq tθ i Θ | minpP V s , P pIq s q ¤ e i,s maxpP V s , P pIq s q, hs Su ¨.
The right hand side converges to zero almost surely, because almost surely G pIq converges to G, which is atomless, and lim nÑV P pIq P V almost surely. Therefore,

lim IÑV G pIq 2 θ i Θ | Spe i , P V q $ Spe i , P pIq q @¨ 0 almost surely. (A.2) Moreover, G pIq 2 θ i Θ | µ pIq pθ i q $ µ V pθ i q @¤
G pIq pΘ pIq q G pIq 2 θ i ΘzΘ pIq | µ pIq pθ i q $ µ V pθ i q @¤ G pIq pΘ pIq q G pIq ¡3 θ i ΘzΘ pIq | u i,µ pIq pθ i q ¡ u i,µ V pθ i q & e i,µ pIq pθ i q ¥ P pIq µ pIq pθ i q A© G pIq ¡3 θ i ΘzΘ pIq | u i,µ pIq pθ i q u i,µ V pθ i q , e i,µ V pθ i q P pIq µ V pθ i q , & e i,µ pIq pθ i q ¥ P pIq µ pIq pθ i q A©

In the first inequality, we decompose the student type space into two, Θ pIq and ΘzΘ pIq . In the former, students do not adopt σ V , while those in the latter set do and thus rank the school prescribed by µ V . The second inequality consider the events when µ pIq pθ i q $ µ V pθ i q can possibly happen.

The almost-sure convergence of G pIq to G and that of P pIq to P V implies that:

lim IÑV G pIq ¡3 θ i ΘzΘ pIq | u i,µ pIq pθ i q ¡ u i,µ V pθ i q & e i,µ
pIq pθ i q ¥ P pIq µ pIq pθ i q A© 0 almost surely, because for any s such that u i,s ¡ u i,µ V pθ i q , we must have e i,s P V s . Similarly, almost surely, lim IÑV G pIq ¡3 θ i ΘzΘ pIq | u i,µ pIq pθ i q u i,µ V pθ i q , e i,µ V pθ i q P pIq µ V pθ i q , & e i,µ pIq pθ i q ¥ P pIq µ pIq pθ i q A© 0.

Therefore, G pIq 2 θ i Θ | µ pIq pθ i q $ µ V pθ i q @¨ 0 almost surely. Together with (A.2),

A-9 it implies that G pIq 2 θ i Θ : µ pIq pθ i q arg max sSpe i ,P pIq q u i,s @¨c onverges to zero almost surely. In other words, tµ pIq u IN is asymptotically stable.

Proof of Proposition 5.

The first statement in part (i) is implied by Proposition 2. Suppose that i is in a blocking pair with some school s. It means that the ex post cutoff of s is lower than i's priority index at s. Therefore, if s L pIq i , the stability of DA (with respect to ROLs) implies that i must be accepted by s or by schools ranked above and thus preferred to s. Therefore, i and s cannot form a blocking pair if s L pIq i , which proves the second statement in part (i).

Part (iii) is implied by Proposition 4 (part (i)).

To show part (ii), we let S pIq 0 SzL pIq i and therefore:

B pIq i Prphs S 0 , u i,s ¡ u i,µ pIq pθ i q and e i,s ¥ P pIq s q ¤ şS pIq 0 Pr ¡ e i,t P pIq t , dt L pIq i , s.t., u i,t ¡ u i,s ; e i,s ¥ P pIq s © . Let B pIq i,s be Pr ¡ e i,t P pIq t , dt L pIq i , s.t., u i,t ¡ u i,s ; e i,s ¥ P pIq s ©
for s S pIq 0 . Since s S 0 and L pIq i is ex ante optimal for i in F pIq , σ pIq , it implies:

şS u i,s » a s ¡ L pIq i , e i ; σ pIq pθ ¡i q, e ¡i © dGpθ ¡i q ¡ C ¡ § § §L pIq i § § § © ¥ şS u i,s » a s L, e i ; σ pIq pθ ¡i q, e ¡i ¨dGpθ ¡i q ¡ C ¡ § § §L pIq i § § § 1 ©
where L ranks all schools in L pIq i and s while respecting their true preference rankings, i.e., adding s to the true partial preference order L pIq i while keeping the new list a true partial preference order.

For notational convenience, we relabel the schools such that school k is the kth choice in L and that s is k ¦ th school in L. Those not ranked in L are labeled as

|L pIq i | 2, ¤ ¤ ¤ , S.
It then follows that:

C ¡ § § §L pIq i § § § 1 © ¡ C ¡ § § §L pIq i § § § © ¥ k ¦ ¡1 ţ1 0 B pIq i,s u i,s A-10 |L pIq i | 1 ţk ¦ 1 u i,t ¤ ¤ ¥ Pr ¡ e i,t ¥ P pIq t ; e i,τ P pIq τ , τ 1, . . . , t ¡ 1 © ¡ Pr ¡ e i,t ¥ P pIq t ; e i,τ P pIq τ , τ 1, . . . , k ¦ ¡ 1, k ¦ 1, ¤ ¤ ¤ , t ¡ 1 © , k ¦ ¡1 ţ1 0 B pIq i,s u i,s ¡ |L pIq i | 1 ţk ¦ 1 u i,t ¤ Pr ¡ e i,t ¥ P pIq t ; e i,s ¥ P pIq s ; e i,τ P pIq τ , τ 1, . . . , k ¦ ¡ 1, k ¦ 1, ¤ ¤ ¤ , t ¡ 1 © ,
where the zeros in the first term on the right come from the upper invariance of DA. That is, the admission probability at any school ranked above s is the same when i submits either L pIq i or L.

Also note that u i,s ¡ u i,t for all t ¥ k ¦ 1 and that:

|L pIq i | 1 ţk ¦ 1
Pr ¡ e i,t ¥ P pIq t ; e i,s ¥ P pIq

s ; e i,τ P pIq

τ , τ 1, . . . , k ¦ ¡ 1, k ¦ 1, ¤ ¤ ¤ , t ¡ 1 © ¤ B pIq i,s . Besides, u i,k ¦ 1 ¥ u i,t for all t k ¦ 2, ¤ ¤ ¤ , |L i | 1. Therefore, for all s S pIq 0 , C ¡ § § §L pIq i § § § 1 © ¡ C ¡ § § §L pIq i § § § © ¥ B pIq i,s u i,s ¡ B pIq i,s u i,k ¦ 1
This leads to:

B pIq i,s ¤ C ¡ § § §L pIq i § § § 1 © ¡ C ¡ § § §L pIq i § § § © u i,s ¡ u i,k ¦ 1 ¤ C ¡ § § §L pIq i § § § 1 © ¡ C ¡ § § §L pIq i § § § © u i,s . Finally, B pIq i ¤ °sS pIq 0 B pIq i,s ¤ |SzL i | Cp|L i | 1q¡Cp|L i |q max sSzL pIq i u i,s .

A.2.3 Asymptotic Distribution of Cutoffs and Convergence Rates

For the next result, we define the demand for each school in pE, σq as a function of the cutoffs:

D s pP | E, σq » 1pu i,s max
s I Spe i ,P q σpθ i q u i,s IqdGpθ i q, where σpθ i q also denotes the set of schools ranked by i; 1pq is an indicator function. Let DpP | E, σq rD s pP | E, σqs sS .

Assumption A1.

(i) There exists n N such that σ pIq σ V for all I ¡ n;

(ii) Dp¤ | E, σ V q is C 1 and fDpP V | E, σ V q is invertible; (iii) °S s1 q s 1.
Part (i) says that σ V maintains as an equilibrium strategy in any economy of a size that is above a threshold. This is supported partially by the discussion in Section A.2.4.

In particular, when Cp2q ¡ 0, part (i) is satisfied. Dp¤ | E, σ V q being C 1 (in part ii) holds when G admits a continuous density. In this case, the fraction of students whose demand is affected by changes in P is continuous. Part (iii) guarantees that every school has a positive cutoff in the stable matching of E.

Because of Assumption A1, our setting with cardinal preferences can be transformed into one defined by students' ROLs that is identical to that in Azevedo and Leshno (2016).

Therefore, some of their results are also satisfied in our setting.

Proposition A2. In a sequence of matchings, tµ pIq u IN , of the sequence of random economies and equilibrium strategies, tF pIq , σ pIq u IN , satisfying Assumption A1, we have the following results:

(i) The distribution of cutoffs in pF pIq , σ pIq q satisfies: c

I P pIq ¡ P V ¨d Ý Ñ N p0, V pσ V qq
where V pσ V q fDpP V | E, σ V q ¡1 Σ pfDpP V | E, σ V q ¡1 q I , and

Σ ¤ ¦ ¦ ¦ ¦ ¦ ¦ ¥
q 1 p1 ¡ q 1 q ¡q 1 q 2 ¤ ¤ ¤ ¡q 1 q S ¡q 2 q 1 q 2 p1 ¡ q 2 q ¤ ¤ ¤ . . . . . . . . . . . . ¡q S¡1 q S ¡q S q 1 ¤ ¤ ¤ ¡q S q S¡1 q S p1 ¡ q S q .

(ii) For any η ¡ 0 and I ¡ n, there exist constants γ 1 and γ 2 such that the probability that the matching µ pIq has cutoffs ||P pIq ¡ P V || ¡ η is bounded by γ 1 e ¡γ 2 I :

Pr ||P pIq ¡ P V || ¡ η ¨ γ 1 e ¡γ 2 I .
(iii) Moreover, suppose that G admits a continuous density. For any η ¡ 0 and I ¡ n, there exist constants γ I 1 and γ I 2 such that, in matching µ pIq , the probability of the fraction of students who can form a blocking pair being greater than η is bounded by γ I 1 e ¡γ I Parts (i) and (ii) are from Azevedo and Leshno (2016) (Proposition G1 and part 2 of Proposition 3), although our part (iii) is new and extends their part 3 of Proposition 3.

A-12

Proposition A2 describes convergence rates and thus has implications for empirical approaches based on stability (see Section 2.3).

Proof of Proposition A2 (part iii).

To show part (iii), we use similar techniques as in the proof for Proposition 3 (part 3) in Azevedo and Leshno (2016). We first derive the following results.

G pIq ptθ i Θ | µ pIq pθ i q arg max sSpe i ,P pIq q u i,s uq G pIq ptθ i Θ | e i,s rminpP V s , P pIq s q, maxpP V s , P pIq s qq, ds S; µ pIq pθ i q arg max sSpe i ,P V q

u i,s u G pIq ptθ i Θ | e i,s rminpP V s , P pIq s q, maxpP V
s , P pIq s qq, hs S; µ pIq pθ i q arg max sSpe i ,P pIq q u i,s uq ¤G pIq ptθ i Θ | µ pIq pθ i q $ µ V pθ i qu G pIq ptθ i Θ | e i,s rminpP V s , P pIq s q, maxpP V s , P pIq s qq, hs Suq

In the first equality, whenever e i,s rminpP V s , P pImq s q, maxpP V s , P pImq s qs, ds S, i faces the same set of feasible schools given either P pIq or P V , Spe i , P pIq q Spe i , P V q. Because µ V is stable, µ V pθ i q is i's favorite school in Spe i , P V q; together with the relaxation of the conditions in the second term, it leads to the inequality.

By Azevedo and Leshno (2016) Proposition 3 (part 3), we can find γ I 1 and γ I 2 such that:

Pr G pIq ptθ i Θ | µ pIq pθ i q $ µ V pθ i quq ¡ η{2 ¨ γ I 1 e ¡γ I 2 I {2. (A.3)
Let g be the supremum of the marginal probability density of e i,s across all s. Denote the set of student types with priority indices which have at least one coordinate close to P V by distance η 1 {p2Sgq (where η 1 η{4):

Θ η 1 tθ i Θ | hs S, |e i,s ¡ P V s | ¤ η 1 {p2Sgqu.
Then GpΘ η 1 q ¤ 2Sg ¤ η 1 {p2Sgq η 1 . The fraction of students in F pIq that have types in Θ η 1 is then G pIq pΘ η 1 q. Note that G pIq pΘ η 1 q is a random variable with mean GpΘ η 1 q. By A-13 the Vapnik-Chervonenkis Theorem, A.2 PrpG pIq pΘ η 1 q ¡ 2η 1 q Prp|G pIq pΘ η 1 q ¡ GpΘ η 1 q| ¡ η 1 q γ I 1 e ¡γ I 2 I {4.

(A.4) Moreover, by part (ii), we know that:

Pr ||P pIq ¡ P V || ¡ η 1 {p2Sgq ¨ γ I 1 e ¡γ I 2 I {4. (A.5)
We can choose γ I 1 and γ I 2 appropriately, so that (A.3), (A.4), and (A.5) are all satisfied.

When the event, ||P pIq ¡ P V || ¡ η 1 {p2Sgq, does not happen, tθ i Θ | e i,s rminpP V s , P pIq s q, maxpP V s , P pIq s qq, hs Su Θ η 1 .

When neither ||P pIq ¡ P V || ¡ η 1 {p2Sgq nor G pIq pΘ η 1 q ¡ 2η 1 happens, G pIq ptθ i Θ | e i,s rminpP V s , P pIq s q, maxpP V s , P pIq s qq, hs Suq ¤ 2η 1 η{2;

the probability that neither of these two events happens is at least 1 ¡ γ I 1 e ¡γ I G pIq ptθ i Θ | µ pIq pθ i q arg max sSpe i ,P pIq q

u i,s uq ¤G pIq ptθ i Θ | µ pIq pθ i q $ µ V pθ i qu G pIq ptθ i Θ | e i,s rminpP V s , P pIq s q, maxpP V
s , P pIq s qq, hs Suq ¤η.

Therefore, Pr £ G pIq ptθ i Θ | µ pIq pθ i q arg max sSpe i ,P pIq q u i,s uq ¡ η γ I 1 e ¡γ I 2 I .

A.2 See Azevedo and Leshno (2016) and the references therein for more details on the theorem for its application in our context.

A-14

A.2.4 Properties of Equilibrium Strategies in Large Economies

We now discuss the properties of Bayesian Nash equilibria in a sequence of random economies and thus provide some justifications to Assumptions 2 and A1.

We start with Lemma A2 showing that a strategy, which does not result in the stable matching in the continuum economy when being adopted by students in the continuum economy, cannot survive as an equilibrium strategy in sufficiently large economies. This immediately implies that, in finite large economies, every student always includes in her ROL the matched school in the continuum-economy stable matching (Lemma A3). Moreover, students do not pay a cost to rank more schools in large economies (Lemma A4).

Lastly, when it is costly to rank more than one school (Cp2q ¡ 0), in sufficiently large economies, it is an equilibrium strategy for every students to only rank the matched school prescribed by the continuum-economy stable matching.

Lemma A2. If a strategy σ results in a matching µ pE,σq in the continuum economy such that Gptθ i Θ | µ pE,σq pθ i q $ µ V pθ i quq ¡ 0, then there must exist n N such that σ is not an equilibrium in F pIq for all I ¡ n.

Proof of Lemma A2.

Suppose instead that there is a subsequence of finite random economies tF pInq u nN such that σ is always an equilibrium. Note that we still have F pInq Ñ E almost surely, and therefore tF pInq , σu converges to tE, σu almost surely.

Given the student-proposing DA, we focus on the student-optimal stable matching (SOSM) in pF pIq , σq. By Proposition 3 of Azevedo and Leshno (2016), it must be that P pInq ÑP σ almost surely, where P pInq P pµ pF pInq ,σq q and P σ P pµ pE,σq q.

Because there is a unique equilibrium outcome in E, which is also the unique stable matching in E by assumption, Gptθ i Θ i | µ pE,σq pθ i q $ µ V pθ i quq ¡ 0 in the continuum economy implies that P σ is not the cutoffs of µ V (E's stable matching), P σ $ P V . Because there is a unique stable matching in E by assumption, µ pE,σ V q is not stable and thus is not an equilibrium outcome in E. There exist some η, ξ ¡ 0, such that: Θ pη,ξq 6 9 9 9 9 9 9 8 9 9 9 9 9 9 7

θ i Θ § § § § § § § § § § § §
e i,µ V pθ i q ¡ P V µ V pθ i q ¡ η, e i,µ pE,σq pθ i q ¡ P σ µ pE,σqpθ i q ¡ η, e i,s ¡ P σ s ¡η, for all s ranked above µ pE,σq pθ i q by σpθ i q;

u i,µ V pθ i q ¡ u i,µ pE,σq pθ i q ¡ ξ.

D G G G G G G F G G G G G G E
student priority indices at all schools satisfy the so-called Ergin acyclicity condition (Ergin, 2002). We extend this result to the continuum economy and to a more general class of DA mechanisms where application costs, Cp|L|q, are flexible.

Definition A1. In a continuum economy, we fix a vector of capacities, tq s u S s1 , and a distribution of priority indices, H. An Ergin cycle is constituted of distinct schools ps 1 , s 2 q and subsets of students tΘ 1 , Θ 2 , Θ 3 u (of equal measure q 0 ¡ 0 ), whose elements are denoted by θ 1 , θ 2 , and θ 3 , respectively, and whose "identities" are i 1 , i 2 , and i 3 , such that the following conditions are satisfied:

(i) Cycle condition: e i 1 ,s 1 ¡ e i 2 ,s 1 ¡ e i 3 ,s 1 , and e i 3 ,s 2 ¡ e i 1 ,s 2 , for all i 1 , i 2 , and i 3 . (ii) Scarcity condition: there exist (possibly empty) disjoint sets of agents Θ s 1 , Θ s 2 Θz tΘ 1 , Θ 2 , Θ 3 u such that e i,s 1 ¡ e i 2 ,s 1 for all θ i Θ s 1 , |Θ s 1 | q s 1 ¡ q 0 ; e i,s 2 ¡ e i 1 ,s 2 for all i Θ s 1 , and |Θ s 2 | q s 2 ¡ q 0 . A priority index distribution H is Ergin-acyclic if it allows no Ergin cycles. This acyclicity condition is satisfied if all schools rank students in the same way. With this, we extend Theorem 6.3 in Haeringer and Klijn (2009) to the continuum economy.

Proposition A3. In the continuum economy E:

(i) If Cp2q 0, every (pure-strategy) Bayesian Nash equilibrium results in a stable matching if and only if the economy satisfies Ergin-acyclicity (Haeringer and Klijn, 2009).

(ii) If Cp2q ¡ 0, all (pure-strategy) Bayesian Nash equilibrium outcomes are stable.

Proof. To prove parts (i) and (ii), we use the proof of Theorem 6.3 in Haeringer and Klijn (2009) and, therefore, that of Theorem 1 in Ergin (2002). They can be directly extended to the continuum economy under more general DA mechanisms. We notice the following:

(a) The continuum economy can be "discretized" such that each subset of students can be treated as a single student. When doing so, we do not impose restrictions on the sizes of the subsets, as long as they have a positive measure. This allows us to use the derivations in the aforementioned proofs.

(b) The flexibility in the cost function of ranking more schools does not impose additional restrictions. As we focus on equilibrium, for any strategy with more than one school listed, we can find a one-school list that has the same or higher payoff. Indeed, many steps in the aforementioned proofs involve such a trick.

A-18

A.3 Consistency of the Preference Estimator under the Assumption of Asymptotic Stability

We provide a proof of the consistency of MLE under the assumption of asymptotic stability. The same proof can be extended to the corresponding GMM estimator.

Let us consider a sequence of random economies and strategies that satisfies Assumptions 1 and 2. The associated matchings and cutoffs are tµ pIq , P pIq u IN . We further assume that lim IÑV P pIq P V , almost surely, and that tµ pIq u IN is asymptotically stable. A.3 In this section, we follow the notation in Newey and McFadden (1994) and define:

Q 0 pβ|P V q E tZ,eu £ ln Pr £ µ V pu i , e i q arg max sSpe i ,P V q u i,s | Z i , e i , Spe i , P V q; β ' ,
where the expectation is taken over Z i , e i . Recall that both µ V and P V are deterministic.

We also define the following regularity conditions. Assumption A2. Suppose that the data are i.i.d., that β 0 is the true parameter value, and that the sequence tµ pIq , P pIq u IN has lim IÑV P pIq P V , almost surely, and tµ pIq u IN being asymptotically stable. We impose the following regularity conditions: (i) Q 0 pβ|P V q is continuous in β and uniquely maximized at β 0 . (ii) β B, which is compact. (iii) At any β B for almost all Z i and e i , Pr £ µ V pu i , e i q arg max sSpe i ,P V q u i,s | Z i , e i , Spe i , P V q; β is bounded away from zero and continuous.

(iv) E tZ,eu £ sup βB § § § § § ln Pr £ µ V pu i , e i q arg max sSpe i ,P V q u i,s | Z i , e i , Spe i , P V q; β ' § § § § § V. (v) GpΘ δ qE pZ,eq ¤ ¦ ¥ sup βB,sS,P Ppe i ,sq § § § § § § § ln Pr £ s arg max sSpe i ,P q u i,s |Z i ,e i ,Spe i ,P q;β Pr £ µ V pu i ,e i q arg max sSpe i ,P V q u i,s |Z i ,e i ,Spe i ,P V q;β § § § § § § § | pu i , e i q Θ δ
converges to zero as δ Ñ 0, where Θ δ tpu i , e i q Θ : e i,s pP V s ¡δ, P V s δq, hs Su for δ ¡ 0 and Ppe i , sq tP r0, 1s S : s Spe i , P qu is the set of all possible cutoffs making s feasible to i.

Conditions (i) and (ii) are standard for identification of the model; conditions (iii) A.3 Recall that under the stability assumption, only students who have at least two feasible schools contribute to the estimation. If one has zero or one feasible school, her match (or her choice) does not reveal any information about her preferences. To simplify the notations below, we implicitly assume that a student's probability of being matched with the school prescribed by the match in a finite economy or the continuum economy is one, whenever she has no feasible school. and (iv) are satisfied in common applications of discrete choice models, including logit and probit models with or without random coefficients. Condition (v) extends condition (iv). Without loss in our setting, we assume G admits a marginal density of e i , and thus GpΘ δ q Ñ 0 as δ Ñ 0. Condition (v) is then satisfied if the conditional expectation in (v) is either bounded or grows to infinity at a slower rate than 1{GpΘ δ q when δ Ñ 0. This is satisfied in the aforementioned discrete choice models that have full-support utility shocks, as choice probabilities are bounded away from zero almost surely given that β B. A.4 To proceed, we define p Q I pβ|P pIq q as the average of log-likelihood based on stability when the economy is of size I. That is,

p Q I pβ|P pIq q 1 I I i1 S ş1
1pµ pIq pu i , e i q sq ln Pr £ s arg max s I Spe i ,P pIq q u i,s I | Z i , e i , Spe i , P pIq q; β ' . p Q I pβ|P pIq q is possibly incorrectly specified because µ pIq may not be exactly stable. That is, some students may not be matched with their favorite feasible school in µ pIq . Correspondingly, we also define:

p Q I pβ|P V q 1 I I i1 ln Pr £ µ V pu i , e i q arg max sSpe i ,P V q u i,s | Z i , e i , Spe i , P V q; β ' .
In this definition, with the same economy as used in p Q I pβ|P pIq q, we construct the hypothetical matching µ V and cutoff P V . Recall that both µ V and P V are deterministic. p Q I pβ|P V q is then the average of the log-likelihood function of this hypothetical dataset. p Q I pβ|P V q is correctly specified because in matching µ V , every student is matched with her favorite feasible school given P V .

The following lemma shows that the MLE estimator would be consistent if we could have access to the hypothetical dataset and use p

Q I pβ|P V q. Lemma A6. When conditions (i)-(iv) in Assumption A2 are satisfied, (i) sup βB | p Q I pβ|P V q ¡ Q 0 pβ|P V q| p Ñ 0, and
(ii) βI is consistent (i.e., βI p Ñ β 0 ), where βI arg max βB p Q I pβ|P V q.

A .4 Equivalently, this requires that a choice probability is strictly positive for almost all Z. This is also true in the usual models with random coefficients; random coefficients often have full support on the real line and therefore lead to strictly positive choice probabilities.

A-20

Proof. Note that § § § § § ln Pr £ µ V pu i , e i q arg max sSpe i ,P V q u i,s | Z i , e i , Spe i , P V q; β ' § § § § § ¤ sup βB § § § § § ln Pr £ µ V pu i , e i q arg max sSpe i ,P V q u i,s | Z i , e i , Spe i , P V q; β ' § § § § §
.

Implied by condition (iv) of Assumption A2, the right-hand-side of the inequality has a finite first moment. Together with conditions (ii) and (iii), this implies that the conditions in Lemma 2.4 of Newey and McFadden (1994) are satisfied, leading to part (i) of the above lemma. By Theorem 2.1 of Newey and McFadden (1994), part (ii) is also satisfied.

Lemma A7. Given Assumption A2, sup βB | p Q I pβ|P pIq q ¡ p Q I pβ|P V q| p Ñ 0.
Proof. Lemma A3 shows that in sufficiently large economies, every student except a measure-zero set includes in her ROL the school prescribed by µ V . For each student, whenever Spe i , P pIq q Spe i , P V q, µ pIq pu i , e i q µ V pu i , e i q.

Therefore, for any β B, in sufficiently large economies, § § § p

Q I pβ|P pIq q ¡ p Q I pβ|P V q § § § § § § § § § § § § § 1 I
i:Spei,P pIq q$Spei,P 8 q S ş1 1pµ pIq pu i , e i q sq ln Pr £ s arg max s 1 Spei,P pIq q u i,s 1 | Z i , e i , Spe i , P pIq q; β Pr £ µ V pu i , e i q arg max sSpei,P 8 q

u i,s | Z i , e i , Spe i , P V q; β § § § § § § § § § § ¤ 1 I i:Spei,P pIq q$Spei,P 8 q S ş1 1pµ pIq pu i , e i q sq § § § § § § § § § § ln Pr £ s arg max s 1 Spei,P pIq q u i,s 1 | Z i , e i , Spe i , P pIq q; β Pr £ µ V pu i , e i q arg max sSpei,P 8 q u i,s | Z i , e i , Spe i , P V q; β § § § § § § § § § § ¤ 1 I i:Spei,P pIq q$Spei,P 8 q sup βB,sS,P Ppei,sq § § § § § § § § § § ln Pr £ s arg max s 1 Spei,Pq u i,s 1 | Z i , e i , Spe i , P q; β Pr £ µ V pu i , e i q arg max sSpei,P 8 q u i,s | Z i , e i , Spe i , P V q; β § § § § § § § § § § ¤ 1 I pui,eiqΘ δ sup βB,sS,P Ppei,sq § § § § § § § § § § ln Pr £ s arg max s 1 Spei,Pq u i,s 1 | Z i , e i , Spe i , P q; β Pr £ µ V pu i , e i q arg max sSpei,P 8 q u i,s | Z i , e i , Spe i , P V q; β § § § § § § § § § § loooooooooooooooooooooooooooooooooooooooooooooooooooooooooomoooooooooooooooooooooooooooooooooooooooooooooooooooooooooon p¦q A-21 1 I
pui,eiqΘzΘ δ :

Spei,P pIq q$Spei,P 8 q sup βB,sS,P Ppei,sq §

§ § § § § § § § § ln Pr £ s arg max s 1 Spei,Pq u i,s 1 | Z i , e i , Spe i , P q; β Pr £ µ V pu i , e i q arg max sSpei,P 8 q u i,s | Z i , e i , Spe i , P V q; β § § § § § § § § § § looooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooomooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooon p¦¦q (A.7)
Since the above results apply to all β B, inequality (A.7) is also satisfied if we replace the first line with sup βB § § § p

Q I pβ|P pIq q ¡ p Q I pβ|P V q § § §.
By the law of large numbers, as I Ñ V, (¦) in inequality (A.7) converges almost surely to GpΘ δ qE pZ,eq ¤ ¦ ¦

¥ sup βB,sS,

P Ppe i ,sq § § § § § § § § ln Pr ¤ ¥ s arg max
s I Spe i ,P pIq q u i,s I|Zi,ei,Spei,P pIq q;β Pr £ µ V pu i ,e i q arg max sSpe i ,P V q

u i,s |Z i ,e i ,Spe i ,P V q;β § § § § § § § § | pu i , e i q Θ δ ,
which, as a function of δ, converges to zero if δ Ñ 0 (condition v of Assumption A2). This implies that, for η 1 ¡ 0, there exists δ η 1 such that for all δ δ η 1 , we have

GpΘ δ qE pZ,eq ¤ ¦ ¦ ¥ sup βB,sS, P Ppe i ,sq § § § § § § § § ln Pr ¤ ¥ s arg max s I Spe i ,P pIq q u i,s I|Zi,ei,Spei,P pIq q;β Pr £ µ V pu i ,e i q arg max sSpe i ,P V q u i,s |Z i ,e i ,Spe i ,P V q;β § § § § § § § § | pu i , e i q Θ δ η 1 {2. By inequality (A.7
) and the law of large numbers, we can choose n 1 such that for any

I ¡ n 1 , sup βB § § § p Q I pβ|P pIq q ¡ p Q I pβ|P V q § § § η 1 {2 η 1 {2 p¦¦q| δ δη 1 η 1 p¦¦q| δ δη 1 almost
surely, where p¦¦q| δ δη 1 indicates the last term in inequality (A.7) evaluated at δ δ η 1 .

Moreover, by assumption, lim IÑV P pIq P V , almost surely. Given δ δ η 1 and for any η 2 , there exists n 2 such that for I ¡ n 2 , Pr P pIq ¡ P V ¤ δ ¨¡ 1 ¡ η 2 . When this happens (i.e., P pIq ¡ P V ¤ δ), p¦¦q in inequality (A.7) evaluated at δ is zero because tpu i , e i q ΘzΘ δ : Spe i , P pIq q $ Spe i , P V qu is empty.

Therefore, for any η 1 and η 2 , there exist n 1 and n 2 such that whenever I ¡ maxtn 1 , n 2 u,

Pr ¡ sup βB § § § p Q I pβ|P pIq q ¡ p Q I pβ|P V q § § § ¡ η 1 © η 2 , which proves the lemma. Proposition A4. When Assumption A2 is satisfied, p β I is consistent (i.e., p β I p Ñ β 0 ),
where p β I arg max βB p Q I pβ|P pIq q.

Proof. Assumption A2, Lemma A6 (part i), and Lemma A7 imply that p Q I pβ|P pIq q satisfies the conditions in Theorem 2.1 of Newey and McFadden (1994) Adding the common value of 10 for every school ensures that all schools are acceptable in the simulated samples.

Students' abilities ta i u I i1 are randomly drawn from a uniform distribution on the interval r0, 1s. School qualities tā s u S s1 are exogenous to students' idiosyncratic preferences i,s . The procedure followed to ascribe values to the schools' qualities is discussed at the end of this section.

The positive coefficient γ on the interaction term a i ¤ ās reflects the assumption that high-ability students value school quality more than low-ability students. In the simulations, we set γ 3.

Priority Indices. Students are ranked separately by each school based on a schoolspecific index e i,s . The vector of student priority indices at a given school s, te i,s u I i1 is constructed as correlated random draws with marginal uniform distributions on the interval [0,1], such that: (i) student i's index at each school is correlated with her ability a i with a correlation coefficient of ρ; (ii) i's indices at any two schools s 1 and s 2 are also correlated with correlation coefficient ρ. When ρ is set equal to 1, a student has the same priority at all schools. When ρ is set equal to zero, her priority indices at the different schools are uncorrelated. For the simulations presented in this appendix, we choose ρ 0.7. It is assumed that student know their priority indices but not their A-28 priority ranking at each school.

School Quality. To ensure that school qualities tā s u S s1 are exogenous to students' idiosyncratic preferences, while being close to those observed in Bayesian Nash equilibrium of the school choice game, we adopt the following procedure: we consider the unconstrained student-proposing DA where students rank all schools truthfully; students' preferences are constructed using random draws of errors and a common prior about the average quality of each school; students rank schools truthfully and are assigned through the DA mechanism; each school's quality is computed as the average ability of students assigned to that school; a fixed-point vector of school qualities, denoted by tā ¦ s u S s1 , is found; the value of each school's quality is set equal to mean value of ā¦ s across the samples.

The resulting vector of school qualities is: tā s u 6 s1 t0.28, 0.39, 0.68, 0.65, 0.47, 0.61u

C.2 Data Generating Processes

The simulated data are constructed under two distinct data generating processes (DGPs).

DGP 1: Constrained/Truncated DA. This DGP considers a situation where the student-proposing DA is used to assign students to schools but where the number of schools that students are allowed to rank, K, is strictly smaller than the total number of available schools, S. For expositional simplicity, students are assumed to incur no cost when ranking exactly K schools. Hence:

C p|L|q 6 8 7 0 if |L| ¤ K V if |L| ¡ K
In the simulations, we set K 4 (students are allowed to rank up to 4 schools out of 6).

DGP 2: Unconstrained DA with Cost. This DGP considers the case where students are not formally constrained in the number of schools they can rank but nevertheless incur a constant marginal cost, denoted by cp¡ 0q, each time they increase the length of their ROL by one, if this list contains more than one school. Hence:

C p|L|q c ¤ p|L| ¡ 1q ,
where the marginal cost c is strictly positive. In the simulations, we set c 10 ¡6 .

For each DGP, we adopt a two-stage procedure to solve for a Bayesian Nash equilibrium of the school choice game. (v) The cutoffs tP pmq u M m1 are used to derive the empirical distribution of school cutoffs under the unconstrained DA, which is denoted by F 0 p¤ | tP pmq u M m1 q. In the simulations, we set M 500.

C.3 Summary Statistics of Simulated Data

We now present some descriptive analysis on the equilibrium cutoff distributions and the 500 Monte Carlo samples of school choice data that are simulated for each DGP.

Equilibrium Distribution of Cutoffs. The equilibrium distribution of school cutoffs is displayed in Figure C2 separately for each DGP. In line with the theoretical predictions

A .8 This is without loss of generality, because in equilibrium the admission probability is non-degenerate and it is, therefore, in students' best interest to rank exactly 4 schools.

A-31 (Proposition A2), the marginal distribution of cutoffs is approximately normal. Because both DGPs involve the same profiles of preferences and produce almost identical matchings, the empirical distribution of cutoffs under the constrained/truncated DA (left panel) is very similar to that observed under the unconstrained DA with cost (right panel). School cutoffs are not strictly aligned with the school fixed effects, since cutoffs are also influenced by school size. In the simulations, small schools (e.g., Schools 3 and 4) tend to have higher cutoffs than larger schools (e.g., Schools 5 and 6) because, in spite of being less popular, they can be matched only with a small number of students, which pushes their cutoffs upward. A.9 Comparative Statics. To explore how the cost of ranking more schools affects weak truth-telling and ex post stability in equilibrium, we simulated data for DGP 2 (DA with cost) using different values of the cost parameter c, while keeping the other parameters at their baseline values. A.10 For each value of the cost parameter, we simulated 500 samples of school choice data and computed the following statistics by averaging across samples: (i) average length of submitted ROLs; (ii) average fraction of weakly truth-telling students; and (iii) average fraction of students assigned to their favorite feasible school.

The results of this comparative statics exercise are displayed in Figure C4. They confirm that, in our simulations, stability is a weaker assumption than WTT whenever students face a cost of ranking more schools: the share of students assigned to their favorite feasible school (blue line) is always larger than the share of WTT students (red .10 We performed a similar exercise for DGP 1 (constrained/truncated DA) by varying the number of schools that students are allowed to rank. The results (available upon request) yield conclusions similar to those based on DGP 2 (DA with cost).

A
A-34 matched school is the chosen alternative. A.11 Finally, estimates under assumption (iii) are based on Andrews and Shi (2013)'s method of moment (in)equalities, using the approach proposed by Bugni et al. (2017) to construct the marginal confidence intervals for the point estimates. A.12 The results from 500 Monte Carlo samples are reported and discussed in the main text (Table 2). They are consistent with the theoretical predictions for both the con- C2, show that while both truth-telling-based and stability-based estimates are close to the true parameters values, the latter are much more imprecisely estimated than the former (column 6 vs. column 3): the stability-based estimates have standard deviations 2.5 to 3.8 times larger than the TT-based estimates. Note, however, that the efficiency loss induced by the stability assumption is considerably reduced when combing stability and undominated strategies (column 9 vs. column 3): the standard deviations of estimates based on the moment (in)equality approach are only 1.3 to 1.9 larger than their truth-telling counterparts.

Reassuringly, the Hausman test rejects truth-telling against stability in exactly 5 percent of samples, which is the intended type-I error rate. This test can therefore serve as a useful tool to select the efficient truth-telling-based estimates over the less efficient stability-based estimates when both assumptions are satisfied.

A .11 Our stability-based estimator is obtained using maximum likelihood. It can be equivalently obtained using a GMM estimation with moment equalities defined by the first-order conditions of the log-likelihood function.

A .12 The conditional moment inequalities are derived from students' observed orderings of all 15 possible pairs of schools (see Section 2.5). The variables that are used to interact with these conditional moment inequalities and thus to obtain the unconditional ones are student ability (a i ), distance to School 1 (d i,1 ) and distance to School 2 (d i,2 ), which brings the total number of moment inequalities to 120. Notes: Results are calculated with administrative data from the Paris Education Authority (Rectorat de Paris) for students from the Southern District who applied for admission to public high schools for the academic year starting in 2013.

Columns 1-3 report estimates from of a linear probability model describing the probability that a student ranks the school with the highest cutoff (School 11) as a function of her priority index, her test scores in French and math, and additional student-specific characteristics. Columns 4-6 report estimates for the probability of ranking the school with the second highest cutoff (school 9). The empirical specification allows for the effect of the priority index to vary depending on whether the student is above or below the school's cutoff, and allows for a discontinuous jump in the ranking probability at the cutoff.

Figure 1 :

 1 Figure 1: Revealed Preferences under Different Assumptions-An Example

Figure 2 :

 2 Figure 2: Monte Carlo Simulations: Impact of Economy Size on the Equilibrium Distribution of Cutoffs (Constrained/Truncated DA)Notes: This figure shows the marginal distribution of school cutoffs in equilibrium under the constrained/truncated DA (ranking 4 out of 6 schools) when varying the number of students, I, who compete for admission to 6 schools with a total enrollment capacity of I ¢ 0.95 seats. Using 500 simulated samples, the line fits are from a Gaussian kernel with optimal bandwidth using MATLAB's ksdensity command. See Appendix C for details on the Monte Carlo simulations.

0

  and 1). Individual examination results for the Diplôme national du brevet (DNB)-a national exam that all students take at the end of middle school-are used to construct different measures of academic ability (French, math, and composite score), which are normalized as percentiles between 0 and 1. Note that the DNB exam scores are not used in the computation of the student priority index, which is based on the grades obtained throughout the final year of middle school. The DNB scores therefore provide additional measures of student ability. 31 Table3reports students' characteristics, choices, and admission outcomes. Almost half of the students are of high socioeconomic status (SES), while 15 percent receive the low-income bonus. 99 percent are assigned to a within-district school in the main admission round, but only half obtain their first choice. Table 4 presents summary statistics for the 11 high schools. Columns 1-4 show a high degree of stratification among the schools, both in terms of the average ability of students enrolled in 2012 and of their social background (measured by the fraction of high SES students). Columns 5-8 describe school choice in 2013. The district's total capacity (1,692 seats) is unevenly distributed across schools: the smallest school has 62 seats while the largest has 251. School cutoffs in 2013 are strongly correlated with school quality. The last column shows the fraction of submitted ROLs in which each school is ranked. The least popular three schools are each ranked by less than 24 percent of students, and two of them remain under-subscribed (Schools 1 and 3) and thus have a zero cutoff. Consistent with our Monte Carlo results, smaller schools are omitted by more students, even if they are of high quality. Likewise, a sizeable fraction of students (20 percent) do not rank the best-performing school (School 11) in their ROLs.

Figure 3 :

 3 Figure 3: Fraction of Students Ranking Each of the Four Most Selective Schools in the Southern District of Paris, by Distance to School Cutoff Notes: The results are calculated with data from the Paris Education Authority on students who applied to the 11 high schools of the Southern District in 2013. The figure shows the ranking behavior of students as a function of the distance (using the original scale in points) between each school's cutoff and students' priority index. For each school, the sample only includes students with a priority index within ¡50 and +50 points of the cutoff, and students are grouped into bins of 10-point width. Bins with less than 10 observations are excluded. Each point represents the fraction of students in a given bin who rank the school in their list. The dotted lines show the 95 percent confidence interval. Low-income students are not included because the low-income bonus of 300 points places them well above the cutoffs.

Figure 4 :

 4 Figure 4: School Cutoffs in 2012 and 2013Notes: The results are calculated with administrative data from the Paris Education Authority. Each dot represents a school, with its cutoff in 2013 on the Y-axis and the one in 2012 on the X-axis. The dashed line denotes the 45-degree line.

Figure 5 :

 5 Figure 5: Goodness of Fit: Observed vs. Simulated Cutoffs Notes: This figure compares the cutoffs observed for the 11 high schools of Paris' Southern District in 2013 to those simulated with the three sets of estimates in Table5. The simulated cutoffs are averaged over 300 simulated samples. See Appendix D.2 for details.

Figure 6 :

 6 Figure 6: Nesting Structure of Identifying Assumptions

³

  XdM pIq converges to ³ XdM V almost surely. By the Portmanteau theorem, M pIq converge to M V in the weak-* topology almost surely.

G

  pIq ptθ i Θ | µ pIq pθ i q arg max sSpe i ,P pIq q u i,s uq ¡ η γ I 1 e ¡γ I 2 I .

2 I

 2 {4 1 ¡ γ I 1 e ¡γ I 2 I {2. This implies, PrpG pIq ptθ i Θ | e i,s rminpP V s , P pIq s q, maxpP V s , P pIq s qq, hs Suq ¡ η{2q γ I 1 e ¡γ I 2 I {2.(A.6) The events in (A.3) and (A.6) do not happen with probability at least 1 ¡γ I 1 e ¡γ I 2 I {2¡ γ I 1 e ¡γ I 2 I {2 1 ¡ γ I 1 e ¡γ I 2 I ; and when they do not happen,

Stage 1 :

 1 Distribution of Cutoffs Under Unconstrained DA. Students' "initial" beliefs about the distribution of school cutoffs are based on the distribution of cutoffs that arises when students submit unrestricted truthful rankings of schools under the standard DA. Specifically: (i) For m 1, ¤ ¤ ¤ , M , we independently generate sample m by drawing students' geographic coordinates, ability a pmq i , school-specific priority indices e pmq i,s , and idiosyncratic preferences pmq i,s over the S schools for all I students. We then calculate u pmq i,s for all i 1, ¤ ¤ ¤ , I, s 1, ¤ ¤ ¤ , S, and m 1, ¤ ¤ ¤ , M . (ii) Student i in sample m submits a complete and truthful ranking rpu pmq i q of the schools; i.e., i is strictly truth-telling. (iii) After collecting trpu pmq i qu I i1 , the DA mechanism assigns students to schools taking into account their priority indices in sample m. (iv) Each matching µ pmq in sample m determines a vector of school cutoffs P pmq tP pmq s u S s1 .

Stage 2 :

 2 Bayesian Nash Equilibrium. For each DGP, the M Monte Carlo samples generated in Stage 1 are used to solve the Bayesian Nash equilibrium of the school choice game. Specifically: (i) Each student i in each sample m determines all possible true partial preference orders tL pmq i,n u N n1 over the schools, i.e., all potential ROLs of length between 1 and K that respect i's true preference ordering R i,m of schools among those ranked in L pmq i,n ; for each student, there are N °K k1 S!{rk!pS ¡ kq!s such partial orders. Under the constrained/truncated DA (DGP 1), students consider only true partial preference orderings of length K ( S), i.e., 15 candidate ROLs when they rank A-30 exactly 4 schools out of 6; A.8 under the unconstrained DA with cost (DGP 2), students consider all true partial orders of length up to S, i.e., 63 candidate ROLs when they can rank up to 6 schools. (ii) For each candidate ROL L pmq i,n , student i estimates the (unconditional) probabilities of being admitted to each school by comparing her indices e i,s to the distribution of cutoffs. Initial beliefs on the cutoff distribution are based on F 0 p¤ | tP pmq u M m1 q, i.e., the empirical distribution of cutoffs under unconstrained DA with strictly truthtelling students. (iii) Each student selects the ROL L pmq¦ i that maximizes her expected utility, where the utilities of each school are weighted by the probabilities of admission according to her beliefs. (iv) After collecting tL pmq¦ i u I i1 , the DA mechanism is run in sample m. (v) The matchings across the M samples jointly determine the "posterior" empirical distribution of school cutoffs, F 1 p¤ | ¤q. (vi) Students use F 1 p¤ | ¤q as their beliefs, and steps (ii) to (v) are repeated until a fixed point is found, which occurs when the posterior distribution of cutoffs ( F t p¤ | ¤q) is consistent with students' beliefs F t¡1 p¤ | ¤q. The equilibrium beliefs are denoted by F ¦ p¤ | ¤q. The simulated school choice data are then constructed based on a new set of M Monte Carlo samples, which are distinct from the samples used to find the equilibrium distribution of cutoffs. In each of these new Monte Carlo samples, submitted ROLs are students' best response to the equilibrium distribution of cutoffs ( F ¦ p¤ | ¤q). The school choice data consist of students' priority indices, their submitted ROLs, the student-school matching, and the realized cutoffs in each sample.

Figure C2 :

 C2 Figure C2: Monte Carlo Simulations: Equilibrium Distribution of School Cutoffs (6 schools, 500 students)Notes: This figure shows the equilibrium marginal distribution of school cutoffs under the constrained/truncated DA (left panel) and the DA with cost (right panel) in a setting where 500 students compete for admission to 6 schools. With 500 simulated samples, the line fits are from a Gaussian kernel with optimal bandwidth using MATLAB's ksdensity command.

Figure

  Figure C3 reports the marginal distribution of cutoffs in the constrained/truncated DA for various economy sizes. The simulations show that as the number of seats and the number of students increase proportionally while holding the number of schools constant, the distribution of school cutoffs degenerates and becomes closer to a normal distribution.

Figure C3 :

 C3 Figure C3: Monte Carlo Simulations: Impact of Economy Size on the Equilibrium Distribution of Cutoffs (Constrained/Truncated DA)Notes: This figure shows the equilibrium marginal distribution of school cutoffs under the constrained/truncated DA (ranking 4 out of 6 schools) when varying the number of students, I, who compete for admission into 6 schools with a total enrollment capacity of I ¢ 0.95 seats. Using 500 simulated samples, the line fits are from a Gaussian kernel with optimal bandwidth using MATLAB's ksdensity command.

  Figure C4: Monte Carlo Simulations: Impact of the Marginal Cost of Applying to Schools on Equilibrium Outcomes (500 Students, 6 Schools) Notes: This figure presents summary statistics of simulated data under unconstrained DA with cost (DGP 2), in which students can rank as many schools as they like, but incur a constant marginal cost c per extra school included in their ROL beyond the first. The data are simulated using different values of the marginal cost parameter c, while maintaining the other parameters at their baseline values. For each value of the cost parameter, 500 samples of school choice data are simulated. The following statistics are computed by averaging across samples: (i) average length of submitted ROLs; (ii) average fraction of weakly truth-telling students; (iii) average fraction of students matched with favorite feasible school.

  strained/truncated DA (Panel A) and the unconstrained DA with cost (Panel B). Efficiency Loss from Stability-Based Estimates. The efficiency loss from estimating the model under stability is further explored by comparing the truth-telling-based and stability-based estimates in a setting where students are strictly truth-telling. To that end, we generate a new set of 500 Monte Carlo samples using the unconstrained DA DGP, after setting the marginal application cost c to zero. In this setting, all students submit truthful ROLs that rank all 6 schools. The estimation results, which are reported in Table

Figure E1 :

 E1 Figure E1: The Southern District of Paris for Public High School Admissions Notes: The Southern District of Paris covers four of the city's 20 arrondissements (administrative divisions): 5th, 6th, 13th and 14th. The large red circles show the location of the district's 11 public high schools (lycées). The small blue circles show the home addresses of the 1,590 students in the data.

Notes:

  The summary statistics are based on administrative data from the Paris Education Authority (Rectorat de Paris), for students who applied to the 11 high schools of Paris's Southern District for the academic year starting in 2013. All scores are from the exams of the Diplôme national du brevet (DNB) in middle school and are measured in percentiles and normalized to be in r0, 1s. Enrollment shares are computed for students who are still enrolled in the Paris school system at the beginning of the 2013-2014 academic year (97 percent of the initial sample). Students unassigned after the main round have the possibility of participating in a supplementary round, but with choices restricted to schools with remaining seats.

Table 1 :

 1 Centralized School Choice and College Admissions based on the Deferred Acceptance Mechanism with Strict Priority Indices: Examples

  Suppose student i exists in all economies in the sequence tF pIq u IN which is associated with a sequence of Bayesian Nash equilibria in pure strategies tσ pIq u IN .

	18
	1.4.2 Probability of Being in a Blocking Pair for a Given Student
	To assess if a matching is likely to be stable, we investigate how the probability that
	a given student is in a blocking pair changes with economy attributes. The following
	proposition shows how economy size, application cost, and other factors play a role.
	Proposition 5.

  Student i's priority indices: e i,s 0.5, ds Submitted ROL of i: ps 1 , s 3 q : u i,s1 ¡ u i,s3 ¡ u i,s , for s s 2 , s 4 Stability: u i,s3 ¡ u i,s4 Undominated u i,s1 ¡ u i,s3

	Data	Revealed preferences
	Available schools: s 1 , . . . , s 4
	ùñ
	Admission outcome of i: s 3 Cutoffs: P p0.8, 0.9, 0.4, 0.2q
	shows an example. WTT takes the submitted ranking
	as truthful and assumes unranked schools being the least preferable. Stability dictates
	that a student is matched with her favorable feasible school. Lastly, a submitted ROL

WTTstrategies:

Table 2 :

 2 Monte Carlo Results (500 Students, 6 Schools, 500 Samples)

					Identifying assumptions
			Weak Truth-telling		Stability of the matching	Stability and undominated strategies
		True value	Mean	SD	CP	Mean SD	CP	Mean SD	CP
		(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)	(9)	(10)
	Panel A. Constrained/Truncated DA (ranking up to 4 out of 6 schools)
	Parameters School 2 School 3 School 4	0.50 1.00 1.50	¡0.13 ¡2.08 ¡1.29	0.06 0.14 0.12	0.00 0.00 0.00	0.51 1.05 1.54	0.29 0.58 0.52	0.94 0.96 0.96	0.50 1.02 1.52	0.28 0.57 0.50	1.00 1.00 1.00
	School 5	2.00	0.56	0.07	0.00	2.02	0.31	0.96	2.01	0.29	1.00
	School 6 Own ability ¢ school quality Distance	2.50 3.00 ¡1.00	0.23 9.40 ¡0.71	0.12 0.64 0.08	0.00 0.00 0.08	2.53 2.97 ¡1.01 0.20 0.95 ¡1.01 0.20 1.00 0.45 0.96 2.51 0.43 1.00 2.29 0.96 3.05 2.26 1.00
	Summary statistics (averaged across Monte Carlo samples)
	Average length of submitted ROLs		4.00
	Fraction of weakly truth-telling students		0.39
	Fraction of students assigned to favorite feasible school 1.00
	Model selection tests
	Truth-Telling (H Parameters
	School 2	0.50	0.41	0.09	0.88	0.51	0.29	0.94	0.49	0.28	1.00
	School 3	1.00	0.57	0.16	0.23	1.05	0.58	0.96	1.00	0.53	1.00
	School 4	1.50	1.17	0.15	0.37	1.54	0.52	0.96	1.49	0.48	1.00
	School 5	2.00	1.74	0.11	0.32	2.02	0.30	0.96	1.99	0.29	1.00
	School 6 Own ability ¢ school quality Distance	2.50 3.00 ¡1.00	2.24 2.19 ¡0.93	0.14 0.72 0.09	0.50 0.77 0.88	2.54 2.96 ¡1.01 0.20 0.95 ¡1.00 0.20 1.00 0.45 0.96 2.48 0.41 1.00 2.29 0.96 3.16 2.29 1.00
	Summary statistics (averaged across Monte Carlo samples)
	Average length of submitted ROLs		4.60
	Fraction of weakly truth-telling students		0.79
	Fraction of students assigned to favorite feasible school 1.00
	Model selection tests
	Truth-Telling (H 0 ) vs. Stability (H 1 ):		H 0 rejected in 37% of samples (at 5% significance level).
	Stability (H 0 ) vs. Undominated strategies (H 1 ):	H 0 rejected in 0% of samples (at 5% significance level).

0 ) vs. Stability (H 1 ): H 0 rejected in 100% of samples (at 5% significance level). Stability (H 0 ) vs. Undominated strategies (H 1 ): H 0 rejected in 0% of samples (at 5% significance level). Panel B. DA with application cost (constant marginal cost c 10 ¡6 ) Notes: This table reports Monte Carlo results from estimating students' preferences under different set of identifying assumptions: (i) weak truth-telling; (ii) stability; (iii) stability and undominated strategies. 500 Monte Carlo samples of school choice data are simulated under two data generating processes for an economy in which 500 students compete for admission to 6 schools: a constrained/truncated DA where students are allowed to rank up to 4 schools out of 6 (Panel A);

Table 3 :

 3 High School Applicants in the Southern District of Paris: Summary Statistics

	Variable	Mean	SD	Min	Max	N
		Panel A. Student characteristics
	Age	15.0	0.4	13	17	1,590
	Female	0.51	0.50	0	1	1,590
	French score	0.56	0.25	0.00	1.00	1,590
	Math score	0.54	0.24	0.01	1.00	1,590
	Composite score	0.55	0.21	0.02	0.99	1,590
	High SES	0.48	0.50	0	1	1,590
	With low-income bonus	0.15	0.36	0	1	1,590
		Panel B. Choices and outcomes
	Number of choices within district	6.6	1.3	1	8	1,590
	Assigned to a within-district school	0.99	0.12	0	1	1,590
	Assigned to first choice school	0.56	0.50	0	1	1,590
	Panel C. Attributes of first-choice school
	Distance (km)	1.52	0.93	0.01	6.94	1,590
	Mean student French score	0.62	0.11	0.32	0.75	1,590
	Mean student math score	0.61	0.13	0.27	0.78	1,590
	Mean student composite score	0.61	0.12	0.31	0.77	1,590
	Fraction high SES in school	0.53	0.15	0.15	0.71	1,590
		Panel D. Attributes of assigned school
	Distance (km)	1.55	0.89	0.06	6.94	1,568
	Mean student French score	0.56	0.12	0.32	0.75	1,568
	Mean student math score	0.54	0.14	0.27	0.78	1,568
	Mean student composite score	0.55	0.13	0.31	0.77	1,568
	Fraction high SES in school	0.48	0.15	0.15	0.71	1,568

Notes: This table provides summary statistics on the choices of middle school students from the Southern District of Paris who applied for admission to the district's 11 public high schools for the academic year starting in 2013, based on administrative data from the Paris Education Authority (Rectorat de Paris). All scores are from the exams of the Diplôme national du brevet (DNB) in middle school and are measured in percentiles and normalized to be in r0, 1s. The composite score is the average of the scores in French and math. The correlation coefficient between French and math scores is 0.50. School attributes, except distance, are measured by the average characteristics of students enrolled in each school in the previous year (2012).

Table 4 :

 4 High Schools in the Southern District of Paris: Summary Statistics

			School attributes (2012)			Assignment outcomes (2013)
	School	Mean French score	Mean math score	Mean composite score	Fraction high SES students	Capacity	Count	Admission cutoffs	Fraction ranking it ROLs
		(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)
	School 1	0.32	0.31	0.31	0.15	72	19	0.000	0.22
	School 2	0.36	0.27	0.32	0.17	62	62	0.015	0.23
	School 3	0.37	0.34	0.35	0.16	67	36	0.000	0.14
	School 4	0.44	0.35	0.39	0.46	140	140	0.001	0.59
	School 5	0.47	0.44	0.46	0.47	240	240	0.042	0.83
	School 6	0.47	0.46	0.46	0.32	171	171	0.069	0.71
	School 7	0.58	0.54	0.56	0.56	251	251	0.373	0.91
	School 8	0.58	0.66	0.62	0.30	91	91	0.239	0.39
	School 9	0.65	0.62	0.63	0.66	148	148	0.563	0.83
	School 10	0.68	0.66	0.67	0.49	237	237	0.505	0.92
	School 11	0.75	0.78	0.77	0.71	173	173	0.705	0.80

Notes: This tables provides summary statistics on the attributes of high schools in the Southern District of Paris and on the outcomes of the 2013 assignment round, based on administrative data from the Paris Education Authority (Rectorat de Paris). School attributes in 2012 are measured by the average characteristics of the schools' enrolled students in 2012-2013. All scores are from the exams of the Diplôme national du brevet (DNB) in middle school and are measured in percentiles and normalized to be in r0, 1s. The composite score is the average of the scores in French and math. The correlation coefficient between school-average math and French scores is 0.97.

Table 5 :

 5 Estimation Results under Different Sets of Identifying Assumptions This table reports the estimates of the parameters in Equation (10) for the Southern District of Paris, with the coefficient on distance being normalized to ¡1. The point estimates in columns 1 and 2 are based on maximum likelihood, whereas those in column 3 are based on moment equalities and inequalities, with 95 percent confidence intervals in brackets.

		Identifying assumptions
		Weak Truth-telling	Stability of the matching	Stability and undominated strategies
		(1)	(2)	(3)
		Panel A. School fixed effects
	School 2	¡0.71 [¡1.17, ¡0.24]	1.46 [0.64, 2.28]	1.21 [0.14, 2.29]
	School 3	¡2.12 [¡2.66, ¡1.58]	1.03 [0.19, 1.86]	0.84 [¡0.56, 2.01]
	School 4	3.31	2.91	2.90
		[2.75, 3.86]	[2.07, 3.76]	[2.36, 3.39]
	School 5	5.13	4.16	4.16
		[4.41, 5.84]	[3.22, 5.10]	[3.71, 4.49]
	School 6	4.87	4.24	4.30
		[4.21, 5.54]	[3.29, 5.18]	[3.73, 4.82]
	School 7	7.33	6.81	6.24
		[6.47, 8.18]	[5.65, 7.98]	[5.76, 7.28]
	School 8	1.59	4.46	4.27
		[1.10, 2.08]	[3.46, 5.47]	[2.98, 5.26]
	School 9	6.84	7.77	6.57
		[6.07, 7.61]	[6.55, 8.99]	[5.84, 7.26]
	School 10	7.84	7.25	6.44
		[6.94, 8.75]	[6.01, 8.49]	[5.87, 7.05]
	School 11	5.35	7.28	5.61
		[4.62, 6.08]	[6.06, 8.51]	[4.98, 7.33]
		Panel B. Covariates
	Closest school	¡0.37 [¡0.63, ¡0.11]	¡0.19 [¡0.47, 0.10]	¡0.15 [¡0.75, 0.57]
	High school co-located	2.54	1.76	1.54
	with middle school	[2.02, 3.07]	[1.19, 2.32]	[0.17, 3.12]
	Student French score [¢10] ¢ school French score [¢10]	0.20 [0.16, 0.23]	0.18 [0.13, 0.24]	0.23 [0.10, 0.35]
	Student math score [¢10] ¢ school math score [¢10]	0.30 [0.26, 0.34]	0.27 [0.21, 0.32]	0.30 [0.18, 0.40]
	High SES ¢ fraction high SES in school	6.79 [5.62, 7.97]	4.92 [3.31, 6.54]	8.12 [4.18, 12.55]
	Scaling parameter	3.09	1.33	1.50
		[2.79, 3.38]	[1.16, 1.50]	[1.20, 1.64]
	Number of students	1,590	1,568	1,590

Notes: Model selection tests: A Hausman test, testing (1) against (

Table 6 :

 6 Goodness-of-Fit Measures Based on Different Sets of Identifying Assumptions

			Estimates from
		Weak Truth-telling	Stability of the matching	Stability and undominated strategies
		(1)	(2)	(3)
	Panel A. Simulated vs. observed assignment (300 simulated samples)
	Mean predicted fraction of students	0.220	0.383	0.326
	assigned to observed assignment	(0.011)	(0.010)	(0.012)
	Panel B. Predicted vs. observed partial preference order of given schools
	Mean predicted probability that a student
	prefers the top-ranked school to the	0.553	0.615	0.595
	2nd-ranked in her submitted ROL
	Mean predicted probability that a student's partial
	preference order among the schools in her ROL	0.012	0.025	0.022
	coincides with the submitted rank order

Table 7 :

 7 Summary of Empirical Approaches

	Identifying assumption	What makes the assumption more plausible?	Required data	Identification and estimation
	Weak Truth-Telling: Schools in a submitted ROL are ranked in true preference order and omitted ones are less preferred.	(1) No cost of ranking more schools, e.g., no restriction on the length of submittable ROLs and choice set not being too large. (2) At the time of application, each student knows her own priority priority indices has a large variance. index but not others', and the distribution of	Submitted ROLs	Point identification Estimation by, e.g., MLE/GMM
		Stability is satisfied if truth-telling holds and
	Stability of the matching: Every student is assigned to her favorite feasible school. Priority indices and unobserved preference heterogeneity are conditionally independent.	(almost) everyone is assigned. Otherwise, it is more likely to be true when (1) market is large (many students, big schools); (2) students are less (4) students know more about others' preferences; constrained when applying to more schools; (3) students face limited uncertainty about how schools rank them at the time of application;	Admission outcome, school capacities, priority indices	Point identification Estimation by, e.g., MLE/GMM
		or (5) cutoffs are easy to predict.
	Undominated strategies: Submitted ROLs are true partial preference orders.	(1) No "safety school" so that "irrelevance at the bottom" of one's ROL is less likely. (2) No "impossible school" so that students do not rank impossible school arbitrarily.	Submitted ROLs	Partial identification Estimation using moment inequalities
	Stability and Undominated strategies: See the conditions laid out separately for stability and undominated strategies.	See the conditions laid out separately for stability and undominated strategies.	Submitted ROLs, admission outcome, school capacities, priority indices	Point identification Estimation using moment equalities and moment inequalities

  Monte Carlo Simulations: Spatial Distribution of Students and SchoolsNotes: This figure shows the spatial configuration of the school district considered in one of the Monte Carlo samples, for the case with 500 students and 6 schools. The school district is represented as a disc of radius 1. The small blue and large red circles show the location of students and of schools, respectively.

	1
	0.8
	0.6
	0.4
	0.2
	0										Students
	-0.2										Schools
	-0.4
	-0.6
	-0.8
	-1
	-1	-0.8	-0.6	-0.4	-0.2	0	0.2	0.4	0.6	0.8	1
	Figure C1:
											. Hence, p β I	p Ñ β 0 .

A.4 Estimation with Strict Truth-Telling and Outside Option

The following discussion supplements Section 2.2 in which we present how weak truthtelling (WTT) can be applied to data on school choice and college admissions and what

Table C1 :

 C1 Monte Carlo Simulations: Summary Statistics This table presents summary statistics of simulated data under two DGPs: (i) constrained/truncated DA (column 1): students are only allowed to rank 4 schools out of 6; and (ii) unconstrained DA with cost (column 2): students can rank as many schools as they like, but incur a constant marginal cost of c 10 ¡6 per extra school included in their ROL beyond the first choice. Standard deviations across the 500 simulation samples are in parentheses.

		Data generating process
		Constrained/truncated DA	Unconstrained DA with cost
		(1)	(2)
		Panel A. Outcomes
	Average length of submitted ROLs	4.00	4.60
		(0.000)	(0.054)
	Assigned to a school	0.950	0.950
		(0.000)	(0.000)
	Weakly truth-telling	0.391	0.792
		(0.022)	(0.018)
	Assigned to favorite feasible school	1.000	1.000
		(0.001)	(0.000)
		Panel B. Parameters
	Number of students	500	500
	Number of schools	6	6
	Number of simulated samples	500	500
	Maximum possible length of ROL Marginal application cost (c)	4 0	6 10 ¡6

Notes:

Table D1 :

 D1 Correlation between Student Priority Index and Probability of Ranking the Most Selective Schools in the Southern District of Paris

			Dependent variable: School s is ranked by student
			s School 11			s School 9
		(school with the highest cutoff)	(school with second highest cutoff)
		(1)	(2)	(3)	(4)	(5)	(6)
	Priority index (original scale in points { 100)
	(Priority index ¡ school cutoff)¢1tpriority index cutoffu	0.549***	0.428***	0.430***	0.381***	0.213***	0.236***
		(0.052)	(0.064)	(0.064)	(0.073)	(0.078)	(0.078)
	(Priority index ¡ school cutoff)¢1tpriority index ¥ cutoffu	0.083	¡0.074	0.074	0.043	¡0.156*	0.061
		(0.077)	(0.079)	(0.102)	(0.077)	(0.085)	(0.089)
	1tpriority index ¥ cutoffu	¡0.022	¡0.025	¡0.015	0.068**	0.058**	0.045*
		(0.022)	(0.022)	(0.023)	(0.026)	(0.026)	(0.026)
	Student test scores
	French score		0.054	0.124		0.153***	0.524***
			(0.050)	(0.209)		(0.049)	(0.202)
	Math score		0.179***	0.370*		0.196***	0.375*
			(0.053)	(0.214)		(0.051)	(0.211)
	French score (squared)			¡0.100			¡0.388**
				(0.167)			(0.160)
	Math score (squared)			¡0.254			¡0.268
				(0.173)			(0.171)
	Other covariates
	High SES student			0.094***			0.092***
				(0.020)			(0.019)
	Distance to School (in km)			¡0.051***			¡0.069***
				(0.014)			(0.010)
	Closest school			0.010			¡0.090***
				(0.036)			(0.030)
	School co-located with student's middle school			0.014			-
				(0.028)			-
	Number of students	1,344	1,344	1,344	1,344	1,344	1,344
	Adjusted R-squared	0.123	0.132	0.164	0.086	0.108	0.164
	F -Test: joint significance of the three coefficients on priority index
	F -stat	79.04	18.14	21.48	51.61	10.62	13.32
	p-value	0.001	0.001	0.001	0.001	0.001	0.001

Table E1 :

 E1 Assigned and Unassigned Students in the Southern District of Paris

		Assigned students Unassigned students
	Panel A. Student characteristics
	Age	15.0	15.0
	Female	0.51	0.45
	French score	0.56	0.45
	Math score	0.54	0.47
	Composite score	0.55	0.46
	High SES	0.48	0.73
	With low-income bonus	0.16	0.00
	Panel B. Enrolment outcomes
	Enrolled in assignment school	0.96
	Enrolled in another public school	0.01	0.65
	Enrolled in a private school	0.03	0.35
	Number of students	1,568	22

In contrast, students can be more uncertain about their admission outcomes if (i) schools use lotteries to break ties ex post, or (ii) schools rank students by test scores that are ex ante unknown. In these cases, the aforementioned student may choose to apply to the highly selective school, since uncertainty in priority indices implies that admission probabilities are rarely zero ex ante.

Hence, we distinguish strict from weak truth-telling. The former assumes that every student ranks all schools truthfully, while the latter requires students to rank their most-preferred schools truthfully and allows them to omit the least-preferred schools.

This literature usually considers decentralized matching markets;[START_REF] Agarwal | An Empirical Model of the Medical Match[END_REF] is an exception.

Some centralized college admissions do not use DA, e.g., Brazil[START_REF] Carvalho | College Choice Allocation Mechanisms: Structural Estimates and Counterfactuals[END_REF].

For a realized economy with realized student types pθ 1 , ¤ ¤ ¤ , θ I q, the realized empirical distribution ĜpIq is defined as ĜpIq pθq 1 I °I i1 1pθ i ¤ θq, dθ R 2S , where 1p¤q is an indicator function.

Related to the distinction between STT and WTT, the literature on lab experiments on school choice sometimes also defines truth-telling as being different from STT. For example,[START_REF] Chen | School Choice: An Experimental Study[END_REF] call a student truth-telling under the DA mechanism if she ranks her most-preferred schools up to her district school, at which she has guaranteed admission.

Unfortunately, it is impossible to make STT a strictly-dominant strategy, because it would require STT to be strictly better than all other strategies against all possible action profiles of other students.

The equilibrium condition, Equation (1), implies that a student may "skip the impossible" by omitting her most-preferred school if the admission probability is close to zero, thus violating WTT.

We define the probability space, pΩ, F, Pq. Specifically, Ω ± IN Θ I , and an element in Ω is denoted by ω pω 1 , ω 2 , ¤ ¤ ¤ q, where ω I is a possible realization of student types in the random economy F pIq . F is a Borel σ-algebra of Ω, and P is a probability measure from F to r0, 1s.

This result, however, does not mean that the probability of a matching being stable converges to one as the market grows. As long as there is at least one blocking pair, a matching is not stable.

In the theoretical discussion, the utility functions are restricted to be in r0, 1s. One can use the inverse of standard normal distribution, Φ ¡1 , to transform them to be on the real line. Note that the expected utility theory cannot be applied to the transformed utility functions; indeed, we do not.

Because the preference space is transformed from r0, 1s S to R S , a strategy is now defined on the transformed type space. Moreover, it will be clear that σ W does not depend on priority indices, e i .

In this case, DA is equivalent to serial dictatorship in which students choose the remaining schools one by one in the order determined by their priority indices. There is a unique stable matching for each realization of student types. Moreover, the set of feasible schools for student i is determined

Since exact stability is assumed, the calculation of VST does not take into account the sampling variance of cutoffs in a finite economy.

Consistent with Proposition 5, our simulations show that the fraction of students who are matched with their favorite feasible school decreases with the application cost. However, students with justified envy are rare unless students face very large application costs (see FigureC4in the Appendix C.3).

Appendix C.4 further quantifies the efficiency loss in simulations with strictly truth-telling students.

In the French educational system, students are tracked at the end of the final year of collège (equivalent to middle school), at the age of 15, into vocational or academic upper secondary education.

The low-income status is conditional on a student applying for and being granted the means-tested low-income financial aid in the last year of middle school. A family with two children would be eligible in 2013 if its taxable income was below 17,155 euros. The aid ranges from 135 to 665 euros per year.

Out-of-district applicants could affect the availability of school seats in the supplementary round, but this is of little concern since, in the district, only 22 students were unassigned at the end of the main round (for the comparison between assigned and unassigned students, see Appendix TableE1).

It should be emphasized that the stability-based estimation does not try to fit cutoffs directly, neither does it restrict a student's preferences over infeasible schools. The difference in predicted cutoffs between stability and WTT is solely due to their differences in predicting preferences.

In the data, 54 percent of students ranked at least one infeasible school among their top two choices (34 percent ranked one infeasible school, while 20 percent ranked two). The average fraction of infeasible schools among all submitted choices is 30 percent.

A.9 Note that this phenomenon is also observed if one sets γ 0, i.e., when students' preferences over schools do not depend on the interaction term a i ¤ ās .

The authors are grateful to the staff at the French Ministry of Education (Ministère de l' Éducation Nationale, Direction de l' Évaluation, de la Prospective et de la Performance) and the Paris Education Authority (Rectorat de l'Académie de Paris) for their invaluable assistance in collecting the data. Financial support from the French National Research Agency (l'Agence Nationale de la Recherche) through Projects DesignEdu (ANR-14-CE30-0004) and FDA (ANR-14-FRAL-0005), from the European Union's Seventh Framework Programme (FP7/2007-2013) under the Grant agreement no. 295298 (DYSMOIA), from the Labex OSE, and from the National Science Foundation (award # 1730636) is gratefully acknowledged. Country/city Assignment mechanism Choice restrictions Sources Panel A. Secondary Education Boston (selective schools) a Student-proposing DA Unrestricted Abdulkadiroglu et al. (2014) Chicago (selective schools) a DA (Serial dictatorship) c Up to 6 choices Pathak and Sönmez (2013) NYC (selective schools) a DA (Serial dictatorship) c Unrestricted Abdulkadiroglu et al. (2014) Finland School-proposing DA Up to 5 choices Salonen (2014) Ghana DA (Serial dictatorship) c

Appendix A Proofs and Additional Results

Section A.1 collects the proofs and additional results for a finite economy, while those related to asymptotics and the continuum economy are presented in Section A.2.

A.1 Finite Economy: Proofs from Sections 1.2 and 1.3

Proof of Proposition 1.

(i) Sufficiency. Without application cost, STT is a dominant strategy (Dubins and Freedman, 1981; Roth, 1982), so we only need to prove it is the unique equilibrium.

Suppose that a non-STT strategy, σ, is another equilibrium. Without loss of generality, let us assume σ is in pure strategy.

Since STT is a weakly dominant strategy, it implies that, for any i and any θ ¡i Θ I¡1 , S ş1 u i,s a s prpu i q, e i ; σpθ ¡i q, e ¡i q ¥ S ş1 u i,s a s pσpθ i q, e i ; σpθ ¡i q, e ¡i q , in which both terms are non-negative given the assumptions on G. Moreover, σ being an equilibrium means that, for any i:

» a s prpu i q, e i ; σpθ ¡i q, e ¡i q dGpθ ¡i q ¤ S ş1 u i,s » a s pσpθ i q, e i ; σpθ ¡i q, e ¡i q dGpθ ¡i q.

It therefore must be that, for any i and any θ ¡i Θ I¡1 except a measure-zero set of θ ¡i , S ş1 u i,s a s prpu i q, e i ; σpθ ¡i q, e ¡i q S ş1 u i,s a s pσpθ i q, e i ; σpθ ¡i q, e ¡i q .

(A.1)

Through the following claims, we then show that σ must be STT, i.e., σpθ i q rpu i q.

Claim 1 : σpθ i q and rpu i q have the same top choice.

Proof of Claim 1 : Given the full support of G, there is a positive probability that i's priority indices at all schools are the highest among all students. In this event, i is accepted by r 1 i (her most preferred school) when submitting rpu i q and accepted by the top choice in σpθ i q when submitting σpθ i q. As preferences are strict, σpθ i q must have r 1 i as the top choice to have Equation (A.1) satisfied.

Claim 2 : σpθ i q and rpu i q have the same top two choices. Proof of Claim 2 : From Claim 1, we know that σpθ i q and rpu i q agree on their top choices. Given G's full support, there is a positive probability that i's type and others' Θ pη,ξq must have a positive measure for some η, ξ ¡ 0 and is a subset of students who can form a blocking pair in µ pE,σq . Clearly, σpθ i q ranks µ pE,σq pθ i q but not µ V pθ i q for all θ i Θ pη,ξq . We show below that σ is not an equilibrium strategy in sufficiently large economies.

Consider a unilateral deviation for θ i Θ pη,ξq from σpθ i q to L i such that the only difference between the two actions is that µ pE,σq pθ i q, ranked in σpθ i q, is replaced by µ V pθ i q in L i while L i is kept as a partial order of i's true preferences.

Because P pInq ÑP σ almost surely, for 0 φ ξ{p1 ξq there exists n 1 N such that, in all F pInq with I n ¡ n 1 , i is matched with µ pE,σq pθ i q with probability at least p1 ¡ φq if submitting σpθ i q, but would have been matched with µ V pθ i q if instead L i had been submitted.

Let EUpσpθ i qq be the expected utility when submitting σpθ i q. Then EUpσpθ i qq ¤ p1¡φqu i,µ pE,σq pθ i q φ, because max s tu i,s u ¤ 1 by assumption, and EUpL i q ¥ p1¡φqu i,µ V pθ i q .

The difference between the two actions is:

implying that σ is not an equilibrium strategy in F pInq for I n ¡ n 1 . This contradiction further implies that there exist n N such that σ is not an equilibrium strategy in all F pIq with I ¡ n.

Lemma A3. If a strategy σ is such that Gptθ i Θ | σpθ i q does not rank µ V pθ i quq ¡ 0, then there must exist n N such that σ is not an equilibrium in F pIq for all I ¡ n.

Proof of Lemma A3.

Note that Gptθ i Θ | σpθ i q does not rank µ V pθ i quq ¡ 0 implies Gptθ i Θ | µ pE,σq pθ i q $ µ V pθ i quq ¡ 0, because i cannot be matched with µ V pθ i q if σpθ i q does not rank µ V pθ i q.

Lemma A2 therefore implies the statement in this lemma.

Lemmata A2 and A3 imply that, in large enough economies, there exist equilibrium strategies with which every student ranks her matched school prescribed by µ V . The following lemma further bounds the number of choices that a student ranks.

Lemma A4. Suppose CpKq 0 and CpK 1q ¡ 0 for 1 ¤ K ¤ pS ¡ 1q. Consider a strategy σ such that σpθ i q ranks at least K 1 schools for all θ i Θ I Θ and GpΘ I q ¡ 0.

In the sequence of random economies, tF pIq u IN , there exists n N such that σ is not an equilibrium strategy in any economy F pIq for I ¡ n.

Proof of Lemma A4.

By Lemma A3, we only need to consider all σ that rank µ V pθ i q for θ i . Otherwise, the statement is satisfied already.

Let CpK 1q ξ. By Proposition 3 of Azevedo and Leshno (2016), it must be that P pIq ÑP σ almost surely in the sequence tF pIq , σu IN , where P pIq P pµ pF pIq ,σq q and P σ P pµ pE,σq q. For 0 φ 2ξ, there must exit n N such that i is matched with µ V pθ i q with probability at least 1 ¡ φ in F pIq for all I ¡ n.

Let EUpσpθ i qq be the expected utility when submitting σpθ i q. We compare this strategy with any unilateral deviation L i that keeps ranking µ V pθ i q but drops one of the other ranked schools in σpθ i q.

Then EUpσpθ i qq ¤ p1 ¡ φqu i,µ V pθ i q φ ¡ ξ, where the right side assumes that i obtains the highest possible utility (equal to one) whenever not being matched with µ V pθ i q. Moreover, EUpL i q ¥ p1 ¡ φqu i,µ V pθ i q ξ. The difference between the two actions is:

which proves that σ is an equilibrium strategy in F pIq for I ¡ n.

Moreover, when Cp2q ¡ 0, we can obtain even sharper results: Lemma A5. Suppose Cp2q ¡ 0 (i.e., it is costly to rank more than one school), and σpθ i q pµ V pθ i qq (i.e., only ranking the school prescribed by µ V ) for all student types. In a sequence of random economies tF pIq u IN , there exists n N such that σ is a Bayesian Nash equilibrium in F pIq for all I ¡ n.

Proof of Lemma A5. This is implied by Lemmata A3 and A4 (when K 1).

A.2.5 Equilibrium and Stable Matching

In a finite economy with complete information, it is known that a matching in equilibrium can be unstable (Haeringer and Klijn, 2009). They further show that, in finite economies, DA with constraints implements stable matchings in Nash equilibria if and only if the assumptions it entails. However, assuming the length of submitted ROL is exogenous (Assumption WTT2) may seem restrictive. An alternative way to relax this assumption is to introduce an outside option and to make some school unacceptable to some students.

Suppose that i's utility for her outside option is denoted by u i,0 V i,0 i,0 , where i,0 is a type I extreme value. We then augment the type space of each student with the outside option and let σ S : R pS 1q ¢ r0, 1s S Ñ L be an STT pure strategy defined on the augmented preference space. More precisely, one version of the STT assumption contains the following two assumptions:

Assumption (Strict Truth-Telling with Outside Option). STT1. σ S pu i , u i,0 , e i q ranks all i's acceptable schools according to her true preferences. STT2. Students do not rank unacceptable schools: u i,0 ¡ u i,s I for all s I not ranked by σ S pu i , u i,0 , e i q.

Given these two assumptions, similar to the case with WTT, either MLE or GMM can be applied based on the following choice probabilities: A.5 Pr

Recall that s I £ L s indicates that s I is not ranked before s in L, which includes s itself and the schools not ranked in L.

Assumptions STT1 and STT2 can be justified as an equilibrium outcome when there is no application cost. However, there may be an issue of multiple equilibria created by unacceptable schools. Namely, if a student can always decline to enroll at an unacceptable school, she may not mind including or excluding that school in her ROL and being assigned to it (He, 2015).

A.5 Assumption EXO2 for the Stability-Based Estimator

The necessity of Assumption EXO2 can be seen in a following modified utility function: A.5 For an example imposing the STT assumption, see He and Magnac (2016) in which the authors observe students ranking all available options and have information on the acceptability of each option.

A-23

where ¡V ¢ 1pte i,s P s pµqq is zero for feasible schools but equal to ¡V for infeasible ones, thus making them always less desirable. With 1pe i,s P s pµqq being personalized "prices," a stable matching is then equivalent to discrete choice based on the modified utility functions (He et al., 2015, 2018). That is, a realized matching μ is stable if and only if μpθ i q μpu i , e i q arg max sS u i,s . Although utility shocks can depend on Z i for identification in usual discrete choice models (Matzkin, 1993), 1pe i,s P s pµqq is special. Conditional on 1pe i,s P s pµqq and Z i , i's ordinal preferences and thus i's choice may lack variation without Assumption EXO2. This is shown in the following example.

An example with Assumption EXO2 violated. Let I 3 and S 3, each with one seat. Students have the same preferences, pu i,1 , u i,2 , u i,3 q p0.9, 0.6, 0.3q for i t1, 2, 3u; the priority index vectors pe i,1 , e i,2 , e i,3 q are p0.8, 0.5, 0.8q for i 1, p0.5, 0.8, 0.3q for i 2, and p0.3, 0.3, 0.5q for i 3.

Suppose students are strictly truth-telling. Therefore, the matching is stable. The cutoffs are P p0.8, 0.8, 0.5q, which leads to Spe 1 , P q t1, 3u. However, if pu i,1 , u i,2 , u i,3 q p0.6, 0.9, 0.3q for i 1, then P I p0.5, 0.5, 0.5q and Spe 1 , P I q t1, 2, 3u. Therefore, for i 1, Spe i , P pµqqw i |Z i . If the data generating process is as such, conditional on student 1's set of feasible schools, we never observe u 1,1 ¡ u 1,2 , or school 1 being chosen over school 2 when both are feasible.

An example with Assumption EXO2 satisfied. Let us consider the following example with Ergin cyclicity where each school has one seat.

School priority ranking (high to low)

Student ordinal preferences (more to less preferred)

When everyone is strictly truth-telling, i 1 's set feasible schools Spe i 1 , P q ts 1 , s 3 u.

No matter how i 1 's ordinal preferences change, i 1 's feasible schools do not change, as long as the matching is stable. A.6 Therefore, given others' preferences, Assumption EXO2 is satisfied for i 1 .

A .6 In any stable matching, i 2 is assigned to s 2 ; otherwise, either i 3 or i 2 would have justified envy. Therefore, s 2 is not feasible to i 1 . Both s 1 and s 3 are feasible to i 1 in any stable matching, because i 1 has a higher priority at both schools than i 3 , while i 2 's assignment is fixed at s 2 .

Appendix B Data B.1 Data Sources

For the empirical analysis, we use three administrative data sets on Parisian students, which are linked using an encrypted version of the French national student identifer (Identifiant National Élève).

B.2 Definition of Variables

Priority Indices. Students' priority indices at every school are recorded as the sum of three main components: (i) students receive a "district" bonus of 600 points on each of the schools in their list which are located in their home district; (ii) students' academic performance during the last year of middle school is graded on a scale of 400 to 600 points; (iii) students from low-income families are awarded an additional bonus of 300 A-25 points. We convert these priority indices into percentiles between 0 and 1.

Student Scores. Based on the DNB exam data set, we compute several measures of student academic performance, which are normalized as percentiles between 0 and 1 among all Parisian students who took the exam in the same year. Both French and math scores are used, and we also construct the students' composite score, which is the average of the French and math scores. Note that students' DNB scores are different from the academic performance measure used to calculate student priority indices as an input into the DA mechanism. Recall that the latter is based on the grades obtained by students throughout their final year of middle school.

Socio-Economic Status. Students' socio-economic status is based on their parents' occupation. We use the French Ministry of Education's official classification of occupations to define "high SES": if the occupation of the student's legal guardian (usually one of the parents) belongs to the "very high SES" category (company managers, executives, liberal professions, engineers, academic and art professions), the student is coded as high SES, otherwise she is coded as low SES. A.7

B.3 Construction of the Main Data Set for Analyses

In our empirical analysis, we use data from the Southern District of Paris (District Sud ).

We focus on public middle school students who are allowed to continue their studies in the academic track of upper secondary education and whose official residence is in the Southern District. We exclude those with disabilities, those who are repeating the first year of high school, and those who were admitted to specific selective tracks offered by certain public high schools in Paris (e.g., music majors, bilingual courses, etc.), as these students are given absolute priority in the assignment over other students. This leads to the exclusion of 350 students, or 18 percent of the total, the majority of whom are grade repeaters. Our data thus include 1,590 students from 57 different public middle schools, with 96 percent of students coming from one of the district's 24 middle schools. A.7 There are four official categories: low SES, medium SES, high SES, and very high SES.

Appendix C Monte Carlo Simulations

This appendix provides details on the Monte Carlo simulations that we perform to assess our empirical approaches and model selection tests. Section C.1 specifies the model, Section C.2 describes the data generating processes, Section C.3 reports a number of summary statistics for the simulated data, and Section C.4 discusses the main results.

C.1 Model Specification

Economy Size. We consider an economy where I 500 students compete for admission to S 6 schools. The vector of school capacities is specified as follows: I ¤ tq s u 6 s1 t50, 50, 25, 50, 150, 150u.

Setting the total capacity of schools (475 seats) to be strictly smaller than the number of students (500) simplifies the analysis by ensuring that each school has a strictly positive cutoff in equilibrium.

Spatial Configuration. The school district is stylized as a disc of radius 1 (Figure C1). Student Preferences. To represent student preferences over schools, we adopt a parsimonious version of the random utility model described in Section 2.1. Student i's utility from attending school s is specified as follows:

where 10 α s is school s's fixed effects; d i,s is the walking distance from student i's residence to school s; a i is student i's ability; ās is school s's quality; and i,s is an error term that is drawn from a type-I extreme value distribution. Setting the effect of distance to ¡1 ensures that other coefficients can be interpreted in terms of willingness to travel.

The school fixed effects above the common factor, 10, are specified as follows:

tα s u 6 s1 t0, 0.5, 1.0, 1.5, 2.0, 2.5u H 0 rejected in 0% of samples (at 5% significance level).

Notes: This table reports Monte Carlo results from estimating students' preferences under different sets of identifying assumptions: (i) weak truth-telling; (ii) stability; (iii) stability and undominated strategies. 500 Monte Carlo samples of school choice data are simulated under the following data generating process for an economy in which 500 students compete for admission to 6 schools: an unconstrained DA where students can rank as many schools as they wish, with no cost for including an extra school in their ROL. Under assumption (iii), the model is estimated using Andrews and Shi (2013)'s method of moment (in)equalities. Column 1 reports the true values of the parameters. The mean and standard deviation (SD) of point estimates across the Monte Carlo samples are reported in columns 2, 5 and 8, and in columns 3, 6 and 9, respectively. Columns 4, 7 and 10 report the coverage probabilities (CP) for the 95 percent confidence intervals. The confidence intervals in models (i) and (ii) are the Wald-type confidence intervals obtained from the inverse of the Hessian matrix. The marginal confidence intervals in model (iii) are computed using the method proposed by Bugni et al. (2017). Truth-telling is tested against stability by constructing a Hausman-type test statistic from the estimates of both approaches. Stability is tested against undominated strategies by checking if the identified set of the moment(in)equality model is empty, using the test proposed by Bugni et al. (2015).

Appendix D Additional Results and Goodness of Fit

Section D.1 of this appendix presents additional results on students' ranking behavior (extending Section 4.2 in the main text). Section D.2 describes the goodness-of-fit statistics that we use to compare the estimates of student preferences under different sets of identifying assumptions (Section 4.4 in the main text).

D.1 Additional Results on Students' Ranking Behavior

The reduced-form evidence presented in Section 4.2 of the main text suggests that students' ranking behavior could be influenced by their expected admission probabilities, as the fraction of students ranking a selective school is shown to be close to one for students with a priority index above the school cutoff, while decreasing rapidly when the priority index falls below the cutoff.

We extend this analysis by evaluating whether the pattern in Figure 3 is robust to controlling for potential determinants of student preferences. In particular, since the decision to rank a selective school might be influenced by the student's ability, we investigate whether the correlation between the priority index and the probability of ranking a selective school is still present once we control for the student's DNB scores in French and math. A.13 Specifically, we estimate the following linear probability model separately for each of the four schools with the highest cutoffs in the Southern District of Paris: y i,s δ 0 δ 1 ¤1te i,s P s u¢pe i,s ¡P s q δ 2 ¤1te i,s ¥ P s u¢pe i,s ¡P s q δ 3 ¤1te i,s ¥ P s u Z I i,s π i,s , (A.9)

where y i,s is an indicator function that takes the value of one if student i included school s in her ROL, and zero otherwise; the coefficients δ 1 and δ 2 allow the linear relationship between student i's priority index at school s (e i,s ) and the probability of ranking that school to differ on either side of the school cutoff (P s ), while the coefficient δ 3 allows for a discontinuous jump in the ranking probability at the cutoff; Z i,s is a vector of studentschool-specific characteristics, which includes the student's DNB exam scores in French and math, an indicator for having a high SES background, the distance to school s from i's place of residence, an indicator for school s being co-located with the student's middle school, and an indicator for school s being the closest to her residence.

A .13 Note that students' DNB scores are different from the academic performance measure that is used to calculate student priority indices as an input into the DA mechanism (see Appendix B).

For reasons of space, Table D1 only reports the OLS estimates of model (A.9) for the two schools with the highest cutoffs, i.e., School 11 (columns 1-3) and School 9

(columns 4-6). The results for the third and fourth most selective schools (Schools 10 and 7, respectively) yield similar conclusions and are available upon request. Overall, these reduced-form results suggest that students' submitted choices are influenced by their priority index, in ways that seem uncorrelated with their underlying preferences. This type of behavior cannot be easily reconciled with weak truth-telling.

D.2 Goodness of Fit

The goodness-of-fit statistics reported in Panel A of Table 5 in the main text are based on simulation techniques (Panel A), whereas those reported in Panel B use closed-form expressions for the choice probabilities (due to the logit specification). We use these goodness-of-fit measures to compare the predictive performance of the preference estimates obtained under different sets of identifying assumptions.

D.2.1 Simulation-Based Goodness-of-Fit Measures

To compare different estimators' ability to predict school cutoffs and students' assignment, we use several simulation-based goodness-of-fit statistics. We keep fixed the estimated A-40 coefficients and Z i,s , and draw utility shocks as type-I extreme values. This leads to the simulated utilities for every student in 300 simulation samples. When studying the WTTbased estimates, we let students submit their top 8 schools according to their simulated preferences; the matching is obtained by running DA. For the other sets of estimates, because stability is assumed, we focus on the unique stable matching in each sample, which is calculated using students' priority indices and simulated ordinal preferences.

Predicted Cutoffs. Observed school cutoffs are compared to those simulated using the different estimates. The results, which are averaged over the 300 simulated samples, are reported in Table D2, with standard deviations across the samples in parentheses (see Figure 5 in the main text for a graphical representation).

Predicted Assignment. Students' observed assignment is compared to their simulated assignment by computing the average predicted fraction of students who are assigned to their observed assignment school; in other words, this is the average fraction of times each student is assigned to her observed assignment in the 300 simulated samples, with standard deviations across the simulation samples reported in parentheses. The results are reported in Panel A of Table 6 in the main text.

D.2.2 Predicted vs. Observed Partial Preference Order

Our second set of goodness of fit measures involves comparing students' observed partial preference order (revealed by their ROL) with the predictions based on different sets of identifying assumptions. We use two distinct measures: (i) the mean predicted probability that a student prefers the top-ranked school to the 2nd-ranked in her submitted ROL, which is averaged across students; and (ii) the mean predicted probability that a student's partial preference order among the schools in her ROL coincides with the submitted rank order. Because of the type-I extreme values, we can exactly calculate these probabilities.

The results are reported in Panel B of Table 6 in the main text.

A-41 Notes: This table compares the cutoffs, observed for the 11 high schools of the Southern District of Paris in 2013, to the average cutoffs simulated under various identifying assumptions as in Table 5. The reported values for the simulated cutoffs are averaged over 300 simulated samples, and the standard deviations across the samples are reported in parentheses. In all simulations, we vary only the utility shocks, which are kept common across columns 2-4.