Department of Policy and Planning Sciences
Discussion Paper Series

No.1342Do outside options matter in matching?
A new perspective on the trade-offs in student
assignmentby
Onur KESTEN and Morimitsu KURINO

Mar 2016

UNIVERSITY OF TSUKUBA
Tsukuba, Ibaraki 305-8573
JAPANDo outside options matter in matching? A new perspectiveon the trade-oﬀs in student assignment∗
Onur Kesten†

Morimitsu Kurino‡
March 5, 2016

Abstract
This paper studies a general one-sided matching problem in which outside options do
not necessarily exist. An important debate centers around whether it is possible to improveupon the Gale-Shapley student-proposing deferred acceptance mechanism (DA) via alternative
strategy-proof mechanisms. In the current paper we introduce a new perspective on this debate
by investigating the role of outside options in school choice and college admissions. We showthat on a general domain of preferences where all students are able to credibly rank theirexogenous or endogenous outside options, no strategy-proof mechanism improving upon DA
exists. It is, however, possible to construct natural subdomains allowing for positive results,
where some students’ preferences are in part induced by an exogenous hierarchy of quality
tiers. We then identify maximal domains on which it is possible to improve upon DA without
sacrificing strategy-proofness. This result may help better assess the underpinnings of thethree-way tension among eﬃciency, individual rationality/stability, and strategy-proofness inmatching.
JEL Classification: C78; D47; D78; I21
Keywords: student-proposing deferred acceptance mechanism, strategy-proofness, Pareto dominance, outside options

We thank Hidekazu Anno, Gadi Barlevy, Caterina Calsamiglia, Estelle Cantillon, Daisuke Hirata, Shuhei Morimoto, Parag Pathak, Al Roth, and participants at Aarhus, Keio, Lund, Osaka, Osaka Prefecture U, Ozyegin U,
Syracuse, Tsukuba, Waseda, Yokohama National U, the WZB Berlin, the Asian meeting of the Econometric Society
2013, and the “Frontiers in Market Design” conference in Switzerland for helpful comments and suggestions. Mostof the paper was written when the second author was aﬃliated with the WZB Berlin Social Science Center, fromwhich he acknowledges the financial support. All remaining errors are our own.
†
Tepper School of Business, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213, USA; e-mail:okesten@andrew.cmu.edu.
‡
Faculty of Engineering, Information and Systems, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki
305-8573, Japan; email: kurino@sk.tsukuba.ac.jp.
∗

1

1

Introduction

In many economic contexts, canonical results implied by standard theory are overturned in the
shadow of outside options. Examples abound. In auction theory, when buyers have outside options, the seller can exploit these so as to increase either revenue (Jehiel et al., 1996) or bothrevenue and eﬃciency (Figueroa and Skreta, 2009). The bargaining literature has long recognized
the fundamental roles played by outside options (e.g., Nash, 1950, 1953) as they do not merely
represent disagreement points, but can lead to inevitable ineﬃciencies (Compte and Jehiel, 2009)
and constitute an additional source of learning a party’s private information (Lee and Liu, 2013).
In contract theory, standard properties of the optimal contract are invalidated when agents havetype-dependent outside options (see, e.g., Jullien, 2000).1
In this paper we explore the role of outside options in one-sided matching problems within
the context of school choice and college admissions. The past two decades have witnessed a rapid
spread in the implementation of school choice, both within the US and globally, as countless school
districts have replaced existing residence-based assignment plans with choice programs. Meanwhile,large centralized college admissions systems have been put in place in many countries including
China, Russia, Turkey, Greece, India, and South Korea, where students are prioritized in various
categories based on a standardized test.
In the context of school choice, outside options may be limited only to a subset of students.
Many if not all families are unable to aﬀord private schools; nor do they have the time or the means
for supervising their children’s education at home. Therefore, outside options such as private
education and home schooling are fundamentally diﬀerent from standard schooling options, which
are accessible to all families within the public education system. Hence, an outside option, if one
exists, can be family-specific and can in turn alter the student’s strategy set. For example, itis easy to see the eﬀect of outside options when implementing a mechanism, such as the muchdebated Boston mechanism,2 that incentivizes strategic play. A family that is able to aﬀord private
education can take a higher risk by aiming at a popular school when choosing its first choice, as
opposed to another family without an outside option, which will cautiously stick to its safety school
as first choice.3 In the context of college admissions, exercising the outside option simply implies
1

In principal-agent models of adverse selection, agents’ outside options equip the principal with an additional
screening tool, which in turn enhances the eﬃciency of the optimal contract (Rasul and Sonderegger, 2010). In
monopoly pricing theory, the famous Coase conjecture fails when buyers are assumed to have private outside options
they can choose to exercise (Board and Pycia, 2014).
2
The Boston mechanism assigns students lexicographically according to first choice and then priority. Accordingly, the emphasis of the mechanism on first choices incentivizes students to be highly strategic when deciding
which school to rank first. For an in-depth game-theoretic and axiomatic analysis of this assignment procedure, see
Ergin and Sönmez (2006), Pathak and Sönmez (2008), and Kojima and Ünver (2014).
3
Indeed, in a recent empirical study of student assignment in Barcelona where the Boston mechanism is in use,
Calsamiglia and Güell (2014) report that 14% of students who fail to get into their first-ranked schools go to private
school, although only 4% of schools in Barcelona are private. They argue that the availability of outside options for
some, but not all, families leads to important inequalities and may significantly diminish any possible gains fromschool choice. In the US, available data indicate that only a small percentage of participants in NYC and Boston

2remaining unassigned to a college (even to a private one) and its cost can be formidably high. In
Chinese college admissions, for example, being unassigned often entails repeating the senior year,
re-taking the exam the following year, or foregoing higher education altogether (c.f. Chen and
Kesten, 2015).
An ongoing debate in the market design literature concerns how to choose the “right” student
assignment mechanism based on the three-way tension among incentives, stability, and welfare. In
matching problems, if outside options are allowed, the stability requirement encompasses individual
rationality along with the no-blocking condition, i.e., that no student would prefer to be assigned
to a school where he has higher priority than at least one student currently assigned to that school.
In two-sided matching, however, strategy-proofness and stability are incompatible (Roth, 1982).
Moreover, there is no strategy-proof, eﬃcient, and individually rational mechanism (Alcalde andBarbera, 1994). School-choice problems, often referred to as one-sided matching problems for lackof schools’ preferences,4 provide a new framework where individual rationality could matter bothconceptually and technically.
Dominant-strategy implementation responds to the famous Wilson critique, articulated in Wilson (1987), by imposing the robustness requirement that each agent’s strategy be optimal, notonly against the actual (or equilibrium) strategies of other agents, but against all possible strategies of other agents. In this sense, a dominant-strategy incentive compatible, or strategy-proof
mechanism is “detail free” and satisfies this strong form of robustness (Bergemann and Morris,2005). A strategy-proof mechanism provides strategic simplicity by inducing the straightforward
behavior of market participants while also oﬀering a sense of fairness by leveling the playing fieldamong sophisticated and naïve participants (Abdulkadiroğlu et al., 2006; Pathak and Sönmez,
2008). Much in line with these considerations, strategy-proofness has played a critical role inrecent school-choice reforms in the US.
In their pioneering work, Abdulkadiroğlu and Sönmez (2003) unearthed an important incentiverelated shortcoming of what has come to be known as the Boston mechanism and discussed alternative strategy-proof proposals that make truth-telling a dominant strategy for students. One ofthese proposals,5 the Gale-Shapley student-proposing deferred acceptance mechanism (DA), hassince become a central student assignment method for school choice both in theory and in practice.6
have reported singleton preference lists in recent years.
4
Mathematically, school priorities are isomorphic to school preferences. However, economically, priorities do
not represent schools’ preferences over students since they are mandated by law based on families’ residence area,
sibling status, or other socioeconomic status. Therefore, priorities preclude welfare and incentive analysis on theschool side.
5
Their second proposal, the top trading cycles mechanism, which is also strategy-proof, is currently being
implemented in New Orleans. See Kesten (2006) for a theoretical comparison of top trading cycles with respect todeferred acceptance.
6
DA has long played a prominent role in two-sided matching markets well before it gained much acclaim inschool choice. Probably the most well-known of these markets, the U.S. National Residency Matching Program, isgenerally considered the earliest account of the use of this assignment method in practice (see Roth 1984; Roth andSotomayor 1990). Balinski and Sönmez (1999) and Guillen and Kesten (2012) show that equivalent versions of DA3

In contrast to the Boston mechanism, DA assigns students tentatively based on preferences while
using priorities to settle all shortages irrespective of preference rankings. This subtle but crucial
diﬀerence endows DA with the superior incentive property. Thanks to the collaborative eﬀorts ofeconomists and oﬃcials, the New York City Department of Education as well as the Boston Public
School system transitioned to new designs implementing DA for student assignment beginning in
2004 and 2006, respectively (Abdulkadiroğlu et al., 2005a,b). Abandoning its residence-based system because of major concerns about social diversity, France has also been implementing DA in allof its thirty districts since 2007 (Hiller and Tercieux, 2014). In the context of college admissions,
Turkey and China have been implementing variants of DA within the last decade.
DA is not only strategy-proof (Dubins and Freedman, 1981; Roth, 1982) but also implements
a stable matching. Given a strict priority structure, the outcome of DA is the most favorable toeach student within the set of stable matchings, in the sense that each student’s assignment at thismatching is at least as good as that at any other stable matching (Gale and Shapley, 1962), i.e., itis the student-optimal stable matching. Because of this theoretical appeal, DA has remained as thecornerstone of the important debate concerning the trade-oﬀs faced in school-choice mechanisms.
DA, however, is eﬃcient only when constrained to the stable set. In general, its outcome
may be ineﬃcient even when school priorities are strict.7 When priorities are coarse, it faces anadditional welfare loss due to breaking ties in priorities, since DA operates on strict priorities only.8
To overcome this shortcoming, mechanisms that Pareto improve upon DA have been proposed in
the recent literature (see Erdil and Ergin, 2008; Kesten, 2010; Abdulkadiroğlu et al., 2015; Kesten
and Ünver, 2015). Nevertheless, none of these mechanisms is strategy-proof. Diﬀerently put, thesemechanisms Pareto dominate DA at the expense of its fundamental incentive property.9 Then anatural question is whether or not strategy-proof mechanisms that improve upon DA exist, or,alternatively, whether or not DA is second-best incentive compatible? We show that the answer
to this question may depend crucially on the role played by a student’s outside option, should hehave one.
Departing from the existing literature, where little attention has been paid to the availabilityof outside options, we argue in this paper that the extent to which students can exercise theiroutside options may significantly impact the three-way tension among incentives, eﬃciency, andindividual rationality/stability in the school-choice setting. We study a general model of school
choice possibly with coarse priority structures where outside options may or may not exist. We
show that even when outside options are completely eliminated, if students are unconstrained inare currently in use respectively for college admissions in Turkey and on-campus dormitory assignments at MIT.
7
Kesten (2010) provides worst-case scenarios where DA assigns each student to either his worst choice or his
second-worst choice in problems of arbitrary size.
8
Working with the NYC data after the transition to DA, Erdil and Ergin (2008) quantify this second sourceof welfare loss and show that it is possible to strictly improve the assignment of around 5% of students without
hurting any others.
9
Erdil and Ergin (2008) and Kesten (2010) show that their proposals gain strategic immunity in low-information
environments, whereas Kesten and Ünver (2015) establish that their proposal is strategy-proof in a large market.

4their strategic rankings of schools, then one must necessarily forgo strategy-proofness to dominate
DA (Theorem 1). In establishing this result, we generalize and unify two independent impossibility
results by Kesten (2010) and Abdulkadiroğlu et al. (2009), while also correcting an erroneous claimin the latter paper.10,11
The rest of the paper is organized as follows: Section 2 gives the formal model and the description of the DA algorithm. Section 3 provides the impossibility result on the full domain andSection 4 the possibility result on a specific subdomain. Section 6 concludes. The technical proofs
are relegated to the Appendix.

2

The Model

We consider a general school-choice model with or without outside options. A school-choice problem, or a problem for short, is a five-tuple (I, S, (qs )s∈S , (Pi )i∈I , (�s )s∈S ). I is a finite set ofstudents and S is a finite set of schools. Each school s ∈ S has qs available seats, or capacity,where qs ≥ 1. We assume throughout the paper that the total number of seats is no fewer than�the number of students, i.e., |I| ≤s∈S qs . If qs is large enough, say qs = |I|, then school s
represents an outside option such as private or home schooling. We call such a school the outside
option and denote it by o. We do not necessarily assume the existence of the outside option.12
Each student i ∈ I has a strict preference relation Pi on S. Let Ri denote the at-least-as-good-as
relation associated with Pi . We denote by P the set of all strict preference relations on S. Given a
student i ∈ I, a set Di ⊆ P denotes the set of all admissible preferences on S. A preference profile
P := (Pi )i∈I ∈ P I specifies a strict preference for each student i ∈ I. A (preference) domain is a
set D := ×i∈I Di ⊆ P I . We say that D is the full domain if D = P I . For each P ∈ D, each i ∈ I,
and each Pi� ∈ Di , we denote P−i := (Pj )j∈I\{j} , and by (Pi� , P−i ) the profile obtained by replacing
10

In a model where schools have strict priorities and students do not necessarily have outside options, Kesten(2010) showed that no eﬃcient and strategy-proof mechanism dominates DA. In a two-sided matching model allowing for weak priorities, Abdulkadiroğlu et al. (2009) (henceforth APR) showed that no strategy-proof mechanism
dominates DA. APR claimed that the latter result is tighter than the former. We note that this claim does not holdbecause Kesten’s model cannot be embedded into the APR framework, nor is the proof technique used by APR
applicable in this setting. More specifically, contrary to Kesten, APR assume that every student has some outside
option and is able to submit singleton preference lists that declare only a single school as acceptable.
11
For an assignment model that also assumes outside options, Erdil (2014) shows that no strategy-proof mechanism dominating a non-wasteful and strategy-proof mechanism exists. We note, however, that that result also nolonger holds once outside options are ruled out. Consider, for example, a simple assignment setting with n agentsand n objects. Clearly, any constant assignment mechanism is non-wasteful and strategy-proof. However, such amechanism is dominated by the corresponding core mechanism, which is also strategy-proof. See also Anno andKurino (2014) for an extension of this impossibility result to multiple-type markets with outside options.
12
The school-choice model concerns the allocation of indivisible goods and the existence of outside options is
not necessarily assumed in this literature (see Sönmez and Ünver, 2011, for a recent survey). On the other hand,
the literature on the two-sided matching model typically assumes outside options, which are represented as being
assigned with oneself (see Roth and Sotomayor, 1990, for a survey). Because under strict priorities a school-choiceproblem is isomorphic to a two-sided matching problem, it inherits much in modeling and results. This might be areason for the modeling diﬀerences in outside options.

5

Pj with Pj� in P . We assume that each school s has a weak priority �s on I that is a complete
and transitive binary relation on I. We say that a priority �s is strict if it is an antisymmetricweak priority. Let �s represent the asymmetric part of �s . We denote by A the set of all weakpriorities on I. A priority profile �:= (�s )s∈S ∈ AS specifies a weak priority for each school s ∈ S.
For convenience we fix I, S, (qs )s∈S throughout the paper and denote a problem by a pair (P, �).
A matching is a correspondence µ : I ∪ S → S ∪ I such that each student is assigned only one
school and each school is assigned students up to its capacity, i.e., for each i ∈ I and each s ∈ S,µ(i) ⊆ S, µ(s) ⊆ I, |µ(i)| = 1, |µ(s)| ≤ qs , and i ∈ µ(s) ⇔ s ∈ µ(i). Since µ(i) is a singleton, we
denote µ(i) = s instead of µ(i) = {s}. Let M be the set of all matchings.
Let a problem (P, �) be given. A matching is non-wasteful at P if for each i ∈ I and eachs ∈ S, s Pi µ(i) implies |µ(s)| = qs . A matching µ dominates matching ν at P if for each i ∈ I,µ(i) Ri ν(i), and for some i ∈ I, µ(i) Pi ν(i). A matching is Pareto eﬃcient at P if it is not
dominated by any other matching at P . A pair (i, s) ∈ I × S blocks a matching µ at (P, �) if��
s Pi µ(i) and either |µ(s)| < qs or for some j ∈ µ(s), i �s j . A matching is stable at (P, �) if
it is not blocked by any pair at (P, �). Note that a stable matching at (P, �) is non-wasteful at
P . A stable matching is a student-optimal stable matching at (P, �) if it is not dominated at
P by any other matching that is stable at (P, �).
A mechanism is a function ϕ : D × AS → M that maps each problem to a matching. Denoteby ϕi (P, �) the school that is matched to i by ϕ at problem (P, �). Similarly, denote by ϕs (P, �)
the set of students that are matched to s by ϕ. For notational simplicity, given j1 , . . . , jm ∈ I and
s1 , . . . , sm ∈ S, we denote ϕ(j1 ,...,jm ) (P, �) = (s1 , . . . , sm ) when ϕj1 (P, �) = s1 , ..., ϕjm (P, �) = sm .
Similarly, given J1 , . . . , Jm ⊆ I, ϕJ1 ,...,Jm (P, �) = (s1 , . . . , sm ) when ϕ(j1 ,...,jm ) (P, �) = (s1 , . . . , sm )for all (j1 , . . . , jm ) ∈ J1 ×. . .×Jm . Mechanism ϕ : D×AS → M is strategy-proof (on domain D)
if for each (P, �) ∈ D ×AS , each i ∈ I, and each Pi� ∈ Di , ϕi (P, �) Ri ϕi (Pi� , P−i , �). A mechanism
ϕ dominates another mechanism ζ if (i) for each problem (P, �) ∈ D × AS , ϕi (P, �) Ri ζi (P, �),and (ii) for some problem (P, �) ∈ D × AS , ϕ(P, �) dominates ζ(P, �) at P . A mechanism ϕ
is Pareto eﬃcient (non-wasteful) if for each (P, �) ∈ D × AS , matching ϕ(P, �) is Paretoeﬃcient (non-wasteful) at P .
Abdulkadiroğlu and Sönmez (2003) advocated the use of Gale and Shapley’s (1962) studentproposing deferred acceptance (DA) algorithm as a plausible assignment method in school
choice. For a strict priority profile � and a preference profile P , the DA algorithm works as follows:
Step 1: Each student applies to her favorite school. Each school s tentatively assigns its seats to
its applicants following the priority order �s . Any unassigned student is rejected.
In general,
Step k: Each student who was rejected at the previous step applies to her next favorite school.
Each school s considers the students it has been holding together with its new applicants andtentatively assigns its seats following the priority order �s . Any unassigned student is rejected.
6

The algorithm terminates when no student remains unassigned. At this point all current
assignments are final.
A tie-breaker for school s is an injective function τs : I → N associating �s with a strict priority �τs as follows: i �τs j ⇔ [(i �s j) or (i �s j, j �s i, and τs (i) < τs (j))]. A tie-breaking
rule is a profile τ := (τs )s∈S of all schools’ tie-breakers.
The student-proposing deferred acceptance mechanism with a tie-breaking rule τ ,which is denoted by DAτ , is the mechanism obtained by the student-proposing deferred acceptancealgorithm acting on (P, �τS ) ∈ D × AS , where �τs is obtained from �s by breaking ties using τs .
It is well known that if � is not strict, there might be multiple student-optimal stable matchings(cf. Erdil and Ergin 2008). But if it is strict, such a matching is unique and dominates any otherstable matching (Gale and Shapley, 1962; Balinski and Sönmez, 1999). More precisely, when � isnot strict, DAτ (P, �) is the unique student-optimal stable matching at (P, �τ ) and dominates at
P any other matching that is stable at (P, �τ ). Furthermore, DAτ is strategy-proof (Dubins andFreedman, 1981; Roth, 1982) and non-wasteful on P and thus on any domain D.13

3

Impossibility on the Full Domain

We start our quest of understanding the role of outside options by searching for a strategy-proof
mechanism that dominates the student-proposing deferred acceptance (DA) mechanism. The critical question we ask is “Is it possible to improve upon DA without losing its compelling incentive
property, if students’ outside options taken away?” We give a negative answer to this questionand provide an impossibility result on the full preference domain, which generalizes two logicallyindependent impossibilities obtained by Abdulkadiroğlu et al. (2009) [henceforth APR] and Kesten(2010).
Theorem 1. (Impossibility on the full domain) No strategy-proof mechanism dominates thestudent-proposing deferred acceptance mechanism with any tie-breaking rule on the full domain P I
whether an outside option exists or not.
Corollary 1. (Kesten, 2010) When priorities are strict, no strategy-proof and eﬃcient mechanism dominates the student-proposing deferred acceptance mechanism on the full domain P I
whether an outside option exists or not.
Corollary 2. (Abdulkadiroğlu et al., 2009) When the outside option exists, nostrategy-proof mechanism dominates the student-proposing deferred acceptance mechanism withany tie-breaking rule on the full domain P I .
13

We note, however, that irrespective of the assumption of the existence of the outside option, the strategyproofness of DA is lost when a quota is imposed on the length of students’ preference lists. See Haeringer and Klijn(2009) for an equilibrium analysis of DA when students’ choices are constrained in this manner.

7

Table 1: Preferences and matchings in Example 1
Pj 1

Pj 2

Pi

Pj�1

Pj 2

Pi

�τt1

�τt2

t2

t1

t2

t2

t1

t2

j1

j2

t1

t2

t1

o

t1

t1

i

i

o

o

o

t1

o

o

j2

j1

Two preference profiles and a priority profile after breaking a tie are shown for Example 1. The underlined (overlined)schools in the preference profiles are assigned to the corresponding students under DA (dominating mechanism ϕ).

To illustrate the diﬀerence between the setups of the two corollaries, consider, for example,
a poor neighborhood where the total capacity is suﬃcient to serve the student body within the�neighborhood ( s∈S\{o} qs > |I| ), but students have no outside options.14 Notice that Corollary
2 is not applicable in this case. Moreover, Theorem 1 implies that the eﬃciency requirement inCorollary 1 can also be dropped.
It is worth emphasizing that Theorem 1 and Corollary 1 are not implied by the APR impossibility, i.e., Corollary 2. In their proof, APR, whose model assumes the existence of an outside
option for each student, critically rely on the assumption that each student is able to submit asingleton preference list where exactly one school can be listed above the outside option. Before
proving Theorem 1, we illustrate this point in the following example to help better understand therole of the presence of outside options as well as gain insight into some of the main ideas behind
our proof.
Example 1. Let I = {i, j1 , j2 } and S = {t1 , t2 , o} with qt1 = qt2 = 1 where o stands for theoutside option. Consider the preference profile P and the priority profile � shown in Table 1.
The DA assignment of each student for this problem is indicated as the underlined school in thecorresponding preference ranking in Table 1, e.g., student j1 is assigned to school t1 , etc.
Note that this matching is not Pareto eﬃcient at P , as students j1 and j2 can both be betteroﬀ by swapping their DA assignments.15 Consider the following mechanism ϕ which we call a DA
mechanism with ex-post swapping:ˆ =ϕ(j1 ,j2 ,i) (P̂ , �)14(t , t , o)
2

1

DAτ

ˆ

(j1 ,j2 ,i) (P̂ , �)

ˆ =�,if P̂ = P and �otherwise.

Another example of an assignment problem with no outside options is the assignment of senior students tolaboratories in engineering faculties in many universities. In this case, while students can declare preference overlaboratories, each student must be assigned to work in one of the available labs as a prerequisite for graduation.
15
As shown in this construction, the DA outcome can be ineﬃcient. Ergin (2002) identifies restrictions on priority
structures to ensure the eﬃciency of DA. See also Kesten (2006) and Ehlers and Erdil (2010).

8

This exchanges the assignments between students j1 and j2 at (P, �) and coincides with DAτ at
any other problem. Each student’s assignment under ϕ is indicated as the overlined school at thecorresponding preference ranking in Table 1.
Now consider the student j1 ’s preference Pj�1 that upgrades the outside option o above her
DA assignment, t1 , at P . In other words, Pj�1 is the singleton preference that declares only t2
above o (Table 1). At (Pj�1 , P−j1 , �), the DA assignment is Pareto eﬃcient and coincides with theassignment by the dominating mechanism ϕ.
Under ϕ, student j1 is assigned the outside option by reporting Pj�1 , whereas she is assigned
to school t2 by reporting Pj1 . Thus, when she has Pj�1 as her true preferences, student j1 getsa better assignment by misreporting her preference. Thus the dominating mechanism ϕ is not
strategy-proof.
♦
Although simple, Example 1 gives us much insight into the failure of any dominating mechanism
to be strategy-proof. The point is that when a mechanism such as ϕ dominates DAτ , a student,such as j1 in the example, who can get a better school under the dominating mechanism, has theability to upgrade the outside option above her DA assignment and declare only a single school as
acceptable. However, such a strategy is not available in a general setting, which may not allow for
the outside option. Recent student assignment data from Boston and New York City, for instance,
also highlight that singleton preference lists are generally used by only a small fraction of students(Abdulkadiroğlu et al., 2006).16
To prove Theorem 1 we introduce several notions. The first is a notion of a “weakly underdemanded school,” which can be seen as a counterpart to the outside option in the general setting
where an outside option may not exist.17
Definition 1. A school s is overdemanded at (P, �) under a matching µ if there is a studenti ∈ I such that s Pi µ(i). A school s is weakly underdemanded at (P, �) under a matchingµ if it is not overdemanded at (P, �) under µ, i.e., for each student i ∈ I, µ(i) Ri s.
Note that in the DA algorithm, an overdemanded school rejects at least one applicant and thus
must be at its full capacity at the DA assignment; on the other hand, a weakly underdemanded
school accepts all its applicants and thus need not necessarily be at full capacity.
�
A set of schools T p ⊆ S is called potentially overdemanded if t∈T p qt < |I|. Moreover, a
set of schools T mp ⊆ S is called maximally potentially overdemanded with respect to T if
16
Since the mechanism in use in both cities is DA, one cannot necessarily infer that these students are being
strategic. Rather, we interpret these fractions as lower bound on the proportion of families with outside options.
17
Put diﬀerently, in our general model, a weakly underdemanded school is the analogue of the outside option (or,the option of being unassigned) in the APR model. Therefore, here too a student need not rank any schools below
a weakly underdemanded school, as she would not need to rank any schools below the outside option in the APR
model.

9

T mp ∈ arg max
�
T ⊇T

��
t∈T �

qt |

�

t∈T �

�
qt < |I| .

Intuitively, for any potentially overdemanded set, it is possible to construct problems where
all schools in that set are overdemanded, e.g., when each student specifies only those schools fromsuch a set as acceptable. Note that the outside option is never in T p or T mp if it exists. We
continue with a series of observations.
Lemma 1. Let τ be a tie-breaking rule, and (P, �) ∈ P I × AS .
1. When it is available, the outside option is weakly underdemanded at (P, �) under any nonwasteful matching, including DAτ (P, �).
2. Let T mp be a maximally potentially overdemanded set with respect to any potentiall overdemanded set T , and ∅ �= S � ⊆ S \ T mp . Then, at least one school among those in T mp ∪ S � isweakly underdemanded at (P, �) under DAτ (P, �).
3. There is a weakly underdemanded school at (P, �) under DAτ (P, �).
The proofs of all lemmas in this section are given in Appendix A. There might not be a weakly
underdemanded school under a non-wasteful matching at some problem,18 but there always exists a weakly underdemanded school under the DA matching. Since we focus on over(weakly
under)demanded schools under the DA matching, we say that a school is over(weakly under)demanded at (P, �; τ ) if it is over(weakly under)demanded at (P, �) under DAτ (P, �).
The following lemma says that if the DA matching is dominated by another matching and somestudent i is assigned a weakly underdemanded school under the DA matching, then she is assigned
the same school under both of the matchings.
Lemma 2. Let (P, �) be a problem and τ a tie-breaking rule. Suppose that a matching ν dominatesDAτ (P, �) at P ∈ P. For each i ∈ I, if school DAτi (P, �) is weakly underdemanded at (P, �; τ )then ν(i) = DAτi (P, �).
In what follows we focus on a specific preference manipulation. To this end, we define some
useful notions: For any S � ⊆ S, define a strict preference relation Pi |S � on S � if for all s, s� ∈ S � ,s� Pi |S � s ⇔ s� Pi s. Given preference Pi of student i and schools s∗ , su with s∗ Pi su , preferencePi� upgrades su above s∗ in Pi if Pi� ranks su right above s∗ and the relative ranking of theother schools stays the same, i.e., (i) s∗ Pi su and su Pi� s∗ , (ii) there is no s ∈ S with su Pi� s Pi� s∗ ,and (iii) Pi |S\{su ,s∗ } = Pi� |S\{su ,s∗ } .
18Consider the following problem where �
S = {s, t},� qs = qt = 1, I = {1, 2}, and � is arbitrarily fixed. Preferences
1 2
are s P1 t and t P2 s. Then matching µ =is clearly non-wasteful at P . All schools are overdemanded att s(P, �) under µ.

10Lemma 3. Suppose that under DA, student i is assigned school s∗ that is overdemanded at (P, �; τ ). Then there exist Pi�� ∈ P and a weakly underdemanded school su at (P, �; τ ) such that Pi��
upgrades su above s∗ in Pi , DAτi (Pi�� , P−i , �) = su , and su is weakly underdemanded at (Pi�� , P−i , �; τ ).
We are now ready to prove Theorem 1.
Proof of Theorem 1. Fix a tie-breaking rule τ . Suppose that a mechanism ϕ dominates DAτ
on the full domain P I . Then, there is a problem (P, �) ∈ P I × AS such that for each i ∈ I,
ϕi (P, �) Ri DAτi (P, �) and for some j ∈ I, ϕj (P, �) Pj DAτj (P, �). As ϕj (P, �) �= DAτj (P, �), by
Lemma 2, school DAτj (P, �) is overdemanded at (P, �; τ ). Thus, by Lemma 3, there exist Pj�� ∈ P
and a weakly underdemanded school su at (P, �; τ ) such that Pj�� upgrades su above DAτj (P, �)in Pj , and su = DAτj (Pj�� , P−j , �) is weakly underdemanded at (Pj�� , P−j , �; τ ). Then, since su
is weakly underdemanded at (Pj�� , P−j , �; τ ), Lemma 2 implies ϕj (Pj�� , P−j , �) = DAτj (Pj�� , P−j , �) = su . Moreover, since ϕj (P, �) Pj DAτj (P, �) and Pj�� upgrades su above DAτj (P, �), we haveϕj (P, �) Pj�� su . Therefore, ϕj (P, �) Pj�� ϕj (Pj�� , P−j , �). That is, ϕ is not strategy-proof.
�
Theorem 1 maintains that even if outside options are completely eliminated from the exogenous
specification, we still cannot overcome the impossibility to improve upon DA. An important insightthat emerges from the proof of Theorem 1 is that although outside options are commonly assumed
to be exogenously specified in many matching models, we find that their strategic role may also
be overtaken by underdemanded schools that emerge endogenously at a given problem. Given
its key role in Theorem 1, however, such an endogenous outside option in this sense,19 could be
more diﬃcult to identify than a readily available exogenous outside option, since it depends on
the information about the joint preference profile, i.e., whether a school is weakly underdemanded
or not depends on the particular problem. Hence, our analysis indicates that manipulating a
Pareto-superior mechanism to DA crucially hinges on the students’ ability to identify and upgrade
weakly underdemanded schools, and even in cases when profitable manipulation is possible, thismay require students to devise rather sophisticated strategies despite holding complete information
about the environment. This in turn provides partial and cautious support for the trends in recent
theory to try to improve upon DA via nonstrategy-proof mechanisms.

4

Possibility Results on a Restricted Domain

The impossibility result on the full domain follows crucially from the requirement that each student is fully capable of finding and upgrading a weakly underdemanded school anywhere in her
preferences. Consider Example 1. We have demonstrated that preference Pj�1 , which upgrades
19

Whereas the critical role of endogenous outside options has been much emphasized in mechanism design andsearch literatures (cf. Lauermann and Virág, 2012 and Atakan and Ekmekci, 2014, for recent applications), we are
not aware of any prior exploration of this notion in the matching context.

11

the outside option above school t1 — the DA assignment of j1 under P — causes the dominating
mechanism ϕ to be manipulable. Under the preference profile P , student j1 is assigned school t1
but is assigned the outside option by reporting Pj�1 . Thus, it may be costly for her to report Pj�1
when her true preference is Pj1 . In practice, students face similar risks when deciding whether
or not to truncate their preferences. After all, an unsuccessful manipulation attempt may cause
the student to end up at her outside option. Therefore, a student who actually has no outside
option may not be able to credibly misrepresent her preference in this manner. This motivates us
to consider restrictions on students’ strategy sets that may arise naturally in real-life situations.
Example 2. We revisit Example 1. Suppose that students j1 and j2 always have the outside
option as the worst. More formally, let T := {t1 , t2 } ⊆ S and P(T ) be the set of all preferences
under which the first and the second top choices are t1 or t2 . In the domain D where Di = P
and Dj1 = Dj2 = P(T ), we can show that the DA mechanism with ex-post swapping that weconstructed in Example 1 becomes strategy-proof. This is because students j1 or j2 can no longer
upgrade the outside option above their DA assignments.
♦
Example 2 shows that under a restricted domain, we might be able to improve on DA while stillpreserving strategy-proofness. We first develop a general procedure of achieving such a mechanism
under an arbitrary preference domain. Then we provide a natural preference domain — tiered
preference domain — under which we can improve DA without sacrificing strategy-proofness.
We first introduce notions of cycles: Let ϕ and ζ be mechanisms. A cycle for ζ at a problem(P, �) is a list C = (i1 , i2 , . . . , , iK ) of distinct students such that K ≥ 1; and if K ≥ 2, for eachk ∈ {1, . . . , K}, student ik prefers the assignment of her neighbor ik+1 to that of her own under ζ,i.e., ζik+1 (P, �) Pik ζik (P, �) where iK+1 = i1 . We say that such a cycle is trivial if K = 1. Notethat we do not impose any condition for a trivial cycle. We say that a school s∗ is the target
school of student ik in cycle C if for a nontrivial cycle, s∗ is school ζik+1 (P, �) — the school
assigned to the neighbor ik+1 ; for a trivial cycle, s∗ is the school assigned to herself. Furthermore,a cycle for (ϕ, ζ) at (P, �) is a cycle for ζ at (P, �), C = (i1 , i2 , . . . , iK ), such that for eachk ∈ {1, . . . , K}, the target school of student ik under ζ is assigned to her under ϕ, i.e., for a
nontrivial cycle, ϕik (P, �) = ζik+1 (P, �); and for a trivial cycle, ϕi1 (P, �) = ζi1 (P, �). We denoteby I(C) the set of students that are involved in a cycle C, i..e, I(C) = {i1 , . . . , iK }.
Remark 1. The conclusion of Lemma 2 is equivalent to the following statement: i is in a trivial
cycle for (ϕ, DAτ ) at (P, �).
To construct a dominating mechanism from a given ineﬃcient mechanism, we need additional
notions on cycles: We define a cycle selection for ζ to be a function C that maps a problem(P, �) ∈ D × AS to a collection C(P, �) of cycles such that for each (P, �) ∈ D × A, eachC ∈ C(P, �) is a cycle for ζ at (P, �) and {I(C)}C∈C(P,�) partitions I. We denote Ci (P, �) by theunique cycle C in C(P, �) such that i ∈ I(C). Moreover, a cycle selection for (ϕ, ζ) is a cycle
12selection C for ζ such that for each (P, �) ∈ D × AS , each C ∈ C(P, �) is a cycle for (ϕ, ζ) at(P, �). A cycle selection C for ζ is trivial if for each (P, �) ∈ D × AS , each C ∈ C(P, �) is trivial.
A mechanism ϕ is the ζ-mechanism with ex-post swapping by a cycle selection C if C isa cycle selection for ζ; and if for each (P, �) ∈ D × AS and each i ∈ I, ϕi (P, �) is the target schoolof i in Ci (P, �). Note that when Ci (P, �) is trivial, ϕi (P, �) = ζi (P, �). Moreover, we say thata mechanism is the ζ-mechanism with ex-post swapping if for some cycle selection C for ζ,
it is the ζ-mechanism with ex-post swapping by C. The next lemma characterizes the mechanism
domination by cycle selections.
Lemma 4.
1. If a mechanism ϕ dominates a non-wasteful mechanism ζ, then there is a nontrivial cycle selection for (ϕ, ζ) and ϕ is non-wasteful.
2. Conversely, if there is a nontrivial cycle selection C for a mechanism ζ, and a mechanism ϕ
is the ζ-mechanism with ex-post swapping by C, then ϕ dominates ζ.
The proofs of all lemmas in this section are in Appendix A. Given a strategy-proof but ineﬃcientmechanism ζ, we aim to construct a new strategy-proof mechanism ϕ that dominates ζ. Lemma
4 is our starting point: a dominating mechanism can be found by identifying a nontrivial cycle
selection as the ζ-mechanism with ex-post swapping by it. An important issue, however, is that theζ-mechanism with ex-post swapping might not be strategy-proof. To maintain strategy-proofness,
we will additionally require a cycle selection to be qualified: The qualified cycle selection is therobustness of target schools when an agent manipulates the mechanism such that she values her
target school higher in her manipulating preferences. We formalize this notion by using the upper
contour set of agent i at s, U (Pi , s) := {s� ∈ S | s� Ri s}.
Definition 2.
1. A cycle selection C for a mechanism ζ is qualified if it is nontrivial; and foreach (P, �) ∈ D × AS , each i ∈ I, and each Pi� ∈ Di if U (Pi� , s∗ ) ⊆ U (Pi , s∗ ), where s∗
is the target school of i in Ci (P, �), then school s∗ is still the target school of i in cycle
Ci (Pi� , P−i , �).
2. A mechanism is the ζ-mechanism with qualified ex-post swapping if it is the ζmechanism with ex-post swapping by some qualified cycle selection for ζ.
The next lemma suggests that the notion of qualified cycle selections is appropriate, as it
characterizes the domination of strategy-proof mechanisms by qualified cycle selections.
Lemma 5.
1. If a mechanism ϕ is strategy-proof and ϕ dominates a non-wasteful mechanism
ζ, then there is a qualified cycle-selection for (ϕ, ζ) and ϕ is non-wasteful.
2. Conversely, if there is a qualified cycle-selection C for a strategy-proof mechanism ζ, and amechanism ϕ is the ζ-mechanism with ex-post swapping by C, then ϕ is strategy-proof anddominates ζ.
13

Now we turn to restricted domains in school-choice programs. One possible student-type that
may be observed in real-life assignment settings includes those students who either do not haveany outside options, or who view their outside options (such as homeschooling) as being inferior tothose oﬀered by the public school system. Naturally, these student-types are not likely to truncate
their preferences. Indeed, in all the years of Boston and NYC student assignments, for which data
exist, thousands of students chose to rank-list as many schools as they were allowed to (see Figure
2).
A generalization of the above type leads us to model correlation among student preferences, aprevalent and salient feature observed in real-life. We do this by assuming student types that divide
the set of schools into tiers according to their desirability. In this case, there may be significant
welfare diﬀerences for these students between a school in a given tier and a school in a lower one.
These types, for instance, may then choose to constrain their strategic behavior to within tiers(i.e., may misrepresent their preferences by altering the true rankings of schools that lie within thesame tier but not those that belong to diﬀerent tiers), for otherwise, a miscalculated manipulation
may result in an assignment at the lower tier before exhausting all the options in the higher tier.
We next formalize these ideas.
Given T ⊆ S, a preference Pi ∈ P is called a T −tier preference if under Pi , the top-|T |choices in S are in T .20 We assume that whether they are truthful or nontruthful, students with
T −tier preferences always report schools in T as their top-|T | choices, while they may individuallydiﬀer in their relative rankings of schools within this set.21 We denote by P(T ) the set of all
T −tier preferences. Note that a student with T -tier preferences is no longer able to upgrade a
non-T school into her top |T | choices. As it turns out, when at least two students’ preference
reports are restricted to the tiered domain, the impossibility to improve upon DA disappears.
Theorem 2. (Possibility result) Suppose that T ⊆ S is a potentially overdemanded set with|T | ≥ 2, and J ⊆ I is a set of students with |J| ≥ |T |, such that each student in J has T -tierpreferences. We denote by DAτ the student-proposing deferred acceptance mechanism with a giventie-breaking rule τ . In the restricted domain D = P(T )J × P I\J where any student in J reports
a T -tier preference in P(T ) and any student not in J reports a full preference in P, we have thefollowing:
1. For some I, S, and q, no strategy-proof and Pareto eﬃcient mechanism dominates DAτ .
2. There is a DAτ -mechanism with qualified ex-post swapping.
20

The set T can be interpreted as a group of schools, or top-tier schools, that this type of student is seriously
targeting such that they are not willing to take the risk of ranking a school from set T below a school they actuallydeem to be inferior. This type of restricted domain has also been considered in the literature (Kesten, 2010; Kandori
et al., 2010).
21
For example, suppose T = {x, y}. It is possible that a student top-ranks school x, whereas another student
top-ranks school y.

14

3. There is a maximal DAτ -mechanism with qualified ex-post swapping, which is a maximal
mechanism in the set of strategy-proof mechanisms that dominates DAτ with respect to thepartial order of the dominance of mechanisms.
4. In sum, any maximal DAτ -mechanism with qualified ex-post swapping is strategy-proof anddominates DAτ . Moreover, it is not dominated by any strategy-proof mechanism.
The students whose welfare improves are only those with T -tier preferences under any DAτ mechanism with qualified ex-post swapping. These students swap their assignments but cannot
manipulate this mechanism due to the restriction on their preferences because they cannot upgrade a weakly underdemanded set above their DA assignments. Thus, it follows from Example
1 and Part (2) of Theorem 2 that the more students have tiered preferences, the more students
can become better oﬀ relative to their DA assignments while preserving strategy-proofness. For
example, on the domain of Example 2 where only students j1 and j2 have tiered preferences, both˜ τ , the remaining
can be better oﬀ under the priority profile �τ . But under the priority profile �
student i has no chance of improvement. However, if all students were to have tiered preferences,
˜ Theorem 2 is a rather
it is straightforward to see that student i could also be better oﬀ under �.
optimistic possibility result. It shows that once there are at least two students who cannot strategically exploit their exogenous or endogenous outside options, i.e., weakly underdemanded schools,
then DAτ -mechanisms with qualified ex-post swapping can improve upon DA at no incentive cost.
Proof. Part (1) is an extension of Kesten’s result – Corollary 1 – to the restricted domain whose
proof is in Appendix B. We will show the key in the proof of the other parts – the constructionof a qualified cycle selection for DAτ – by Lemma 5-(2). With this construction, all of statements
except Part (1) follows by definitions.
We denote T := {t1 , . . . , tm } where m ≥ 2. Let T mp be a maximally potentially overdemanded
set with respect to T . We denote T mp \ T = {sm+1 , . . . , sn }.22 Since |J| ≥ |T |, we arbitrarilychoose m students, j1 , . . . , jm , from J. Moreover, let J1 , . . . , Jn , In+1 be a partition of I suchthat |J1 | = qt1 , ..., |Jm | = qtm , |Jm+1 | = qsm+1 , ..., |Jn | = qsn , and j1 ∈ J1 , ..., jm ∈ Jm .
�
Since T mp = {t1 , . . . , tm , sm+1 , . . . , sn } is potentially overdemanded,s∈T mp qs < |I|. Thus, as�mp
and In+1 is not empty. We consider thes∈S qs ≥ |I| by our assumption, there is sn+1 ∈ S \ Tfollowing sets of preferences (see Table 2): For each � ∈ {1, . . . , n},
P� =
τ


{P � ∈ P | t
i

�
�
mp
}
�+1 Pi t� Pi u for each u ∈ S \ T

{P � ∈ P | s is the top choice in P � }i�iif � ∈ {1, . . . , m},if � ∈ {m + 1, . . . , n}.

¯ be the post-tie-breaking priority profile given by the right table in Table 2. We denote
Let �
22

The subsequent argument assumes T mp \ T �= ∅, but we can modify it for the other case in a straightforward
way.

15

t2
..
.

Table 2: Preferences (left) and priorities (right) in Part 2
m+1
m
n
1
¯ τt
¯ τt
Pi∈J
Pi∈J
. . . Pi∈J
Pi∈I
�
... �
...
m
m
n
1
n+1
m+1
..
...
.
sm+1
...
sn
J1
Jm
tm+1
t2
In+1 . . . In+1 . . .
..
..
..
..
..
..
.
.
.
.
.
.

t1
..
.

tm
..
.

1
Pi∈J
1
..
.

...

¯ τs
�
n

Jn
In+1
..
.

¯ τs∈S\T
�
..
.

t1
..
.
τ

¯ , where vertical dots
The left table shows the preference profile. The right table shows the priority profile �represent arbitrary students. For example, the first column means that students in J1 have higher priority fort1 than those in In+1 , who have higher priority than the others, and the priorities of all remaining students arearbitrary.

D∗ := (P 1 )J1 × . . . × (P m )Jm × (P 1 ∩ P(T mp ))Im+1 .
Let a matching µ be such thatµ=�

J1 . . . Jm Jm+1 . . . Jn
In+1τ¯ S\T p |In+1 )t1 . . . tm sm+1 . . . sn DA (PIn+1 , ��,¯ In+1 ) is the DA matching for a smaller problem consisting of In+1 and thewhere DAτ (PIn+1 , �|
¯ In+1 is kept the same as in �.
¯
relative ranking of �|¯ = (t1 , . . . , tm , sm+1 , . . . , sn ) =Step 1: We show that for each P ∈ D∗ , DAτ(J1 ,...,Jm ,Jm+1 ,...,Jn ) (P, �)µ(J1 ,...,Jm ,Jm+1 ,...,Jn ) .
Let P ∈ (PJ11 , . . . , PJnn , PI1n+1 ). It is straightforward to see that¯ = (sm+1 , . . . , sn ).
DAτ(Jm+1 ,...,Jn ) (P, �)(1)Moreover we can show that µ is stable because under µ, for each � ∈ {1, . . . , n}, school t� for� ≤ m (school s� for � > m) is matched with its top-priority students in J� .
¯ �= µ(J1 ,...,Jm ) . Then, since the DA matching is student-optimal stable,
Suppose DAτ(J1 ,...,Jm ) (P, �)
there exist � ∈ {1, . . . , m} and j ∈ J� such that DAτj (P, �) Pj t� . Thus, as Pj ∈ P � , DAτj (P, �) ∈T mp \{t� }. Thus, by (1), DAτj (P, �) ∈ {t1 , . . . , tm }\{t� }. Let tk := DAτj (P, �) where k �= �. Then,for school tk , any student i ∈ Im+1 has higher priority than j (statement *). On the other hand,since the DA matching is student-optimal stable and (PJ1 , . . . , PJm ) ∈ PJ11 × . . . PJmm , it follows
from (1) that under DA, all students in J1 ∪ ... ∪ Jm are matched with schools in {t1 , . . . , tm }, andthus any student i in Im+1 (�= ∅) is matched with a school in S \ T mp . Thus, as Pi ∈ P 1 , i prefers
school tk to school DAτi (P, �) (statement **). Therefore, by statements (*) and (**), pair (i, tk )blocks DAτ (P, �), which contradicts the stability of DAτ . This completes Step 1.
Step 2: We show that given � ∈ {1, . . . , m} and Pj� ∈ Dj� = P(T ) with t�+1 Pj� t� , we have16

Pj� ∈ P � . To this end, we need to show that for each u ∈ S \ T mp , t� Pj� u. Fix u ∈ S \ T mp .
Since, T ⊆ T mp , u ∈ S \ T . Thus, since Pj� ∈ P(T ), we have t� Pj� u.
Step 3: We show that the following cycle selection C for DAτ is qualified.
C(P, �) =
{(j , . . . , j )} ∪ {(i) | i ∈ I \ J}1m

{(i) | i ∈ I}¯
if P ∈ D∗ and �= �,otherwise.

Let (P, �) ∈ D × AS , i ∈ I, and Pi� ∈ Di such that U (Pi� , s∗ ) ⊆ U (Pi , s∗ ) where s∗ is the target
school of i in Ci (P, �). Let s∗ be the target school of i in Ci (Pi� , P−i , �). We need to show s∗ = s∗∗ .
¯ or [i ∈ {j1 , . . . , jm }, �= �,¯ P �∈ D∗ , (Pi� , P−i ) �∈ D∗ ].
Case 1 : [i �∈ {j1 , . . . , jm } and ��= �]
Then Ci (P, �) = Ci (Pi� , P−i , �) = {i} and thus DAτi (P, �) = s∗ and DAτi (Pi� , P−i , �) = s∗∗ . By
strategy-proofness of DAτ , DAτi (Pi� , P−i , �) = s∗ . Hence s∗ = s∗∗ .
¯ and P ∈ D∗ . Let i = j� for some � ∈ {1, . . . , m}. As P ∈ D∗ , byCase 2 : i ∈ {j1 , . . . , jm }, �= �,
Step 1, s∗ = t�+1 . Note that U (Pi� , t�+1 ) ⊆ U (Pi , t�+1 ) , Pi ∈ P � , and t�+1 Pi t� . Thus t�+1 Pi� t� .
Hence, by Step 2, Pi� ∈ P � and thus (Pi� , P−i ) ∈ D∗ . Thus it follows from Step 1 that s∗∗ = t�+1 .
Hence s∗∗ = t�+1 = s∗ .
¯ and P �∈ D∗ . It is suﬃcient to show (Pi� , P−i ) �∈ D∗ , as in thisCase 3 : i ∈ {j1 , . . . , jm }, �= �,case s∗ = s∗∗ by Case 1. Suppose (Pi� , P−i ) ∈ D∗ . Let i = j� for some � ∈ {1, . . . , m}. Notethat as P �∈ D∗ , Ci (P, �) = {i} and DAτi (P, �) = s∗ . Since U (Pi� , s∗ ) ⊆ U (Pi , s∗ ), by strategyproofness of DAτ , DAτi (Pi� , P−i , �) = s∗ . On the other hand, since (Pi� , P−i ) ∈ D∗ , by Step 1,
DAτi (Pi� , P−i , �) = t� . Hence s∗ = t� . Then, since (Pi� , P−i ) ∈ D∗ , t�+1 ∈ U (Pi� , s∗ ) ⊆ U (Pi , s∗ ) andthus t�+1 Pi t� . Then, by Step 2, Pi ∈ P � and thus P ∈ D∗ , a contradiction.
In any case we have s∗ = s∗∗ . Thus cycle selection C is qualified.
An extreme case of the tiered domain is when there is a single tier including all schools but theoutside option. The following corollary pertains to such cases where students always report theoutside option as the least preferred outcome.
Corollary 3. Suppose that the outside option o exists and the set of schools excluding the null ispotentially overdemanded with |S \ {o} | ≥ 2. If the outside option is the last reported choice of atleast |S \ {o}| students, there is a strategy-proof mechanism that dominates the student-proposing
deferred acceptance mechanism with any tie-breaking rule.
Corollary 3 points to a particular way to improve upon DA in practice in places where themechanism is currently used. By merely utilizing potential trades among students who declarethe outside option as the last choice, it may be possible to make some of the students better oﬀ
without imposing any welfare cost on any other students. Figure 1 shows the fraction of students
who submit full-length preference lists in Boston and NYC, i.e., these are the students who list as
many (real) schools as they are allowed. It is not implausible to imagine that a vast majority of
17

(!"#

(!"#
'$"#

&!!1#
&!!/#
&!%!#
&!%%#

'!"#
&$"#

'$"#
'!"#
&$"#

&!"#

&!"#

%$"#

%$"#

%!"#

%!"#

$"#

$"#
!"#

!"#
)*+,-#.#)*+,-#/#)*+,-#0!#)*+,-#0%#)*+,-#0&#&!!'#&!!(#&!!$#&!!)#

Figure 1: Percentage of students who submitted full-length preference lists in Boston (left) and
New York City (right). Data: The above plotted statistics for the Boston Public Schools and NYC Public
School System are reported in Abdulkadiroğlu et al. (2006) and Abdulkadiroğlu et al. (2009) respectively. In theabove calculation of the Boston stats, we consider the percentages of students who submitted six or more schools
in their preference lists since the maximum length reported for some grades are six. For the case of NYC, thepercentages are for students who submitted the cap of twelve schools in their preference lists.

these students are likely to be without any outside options. Using a DAτ -mechanism with qualified
ex-post swapping to implement trades among them may lead to significant welfare gains of thesestudents without harming others. Most notably, no participant will be given perverse incentives
by doing so.

5

A Maximal Domain for Possibility

Thus far, we have seen that while it is impossible to improve upon DA under the full domain ofpreferences, there exist natural domains under which possibility results may be obtained. Thisin turn raises a natural question about whether or not we can identify maximal domains where astrategy-proof mechanism dominating DA exists. We next search for such domains.
Definition 3. A domain D is maximal for the possibility result if for each tie-breaking rule τ ,1. there is a strategy-proof mechanism that dominates DAτ on D;
2. for each D� with D � D� ⊆ P I , no strategy-proof mechanism dominates DAτ on D� .
Given T ⊆ S and x, y ∈ T , we use the type of preferences, P \ P(x, y, T ), for identifying the
maximal domains where18P(x, y, T ) = { Pi ∈ P | for some u ∈ S \ T, x Pi u Pi y, and for each u� ∈ S \ T, x Pi u� } .
A student with a preference relation from the set P(x, y, T ) prefers school x to school y, ranks
some non-T school between them, and ranks any non-T school below school x.
Example 3. Let S = {x, y, o} and T = {x, y}.
P(T )
x y
y x
o o

P(x, y, T )xoyP \ P(x, y, T )x o y y oy x x o yo y o x x♦

Lemma 6. For all T ⊆ T � ⊆ S and all x, y ∈ T with x �= y, P(T ) ⊆ P \P(x, y, T ) ⊆ P \P(x, y, T � ).
Theorem 3. (Maximal domain) Let τ be a tie-breaking rule, T := {t1 , . . . , tm }, and J :={j1 , . . . , jm } ⊆ I with |J| = |T | = m ≥ 2. Let T mp a maximally potentially overdemanded set withrespect to T . Then define the domain Dmax as follows: for each i ∈ I and each � ∈ {1, . . . , m},

Dimax
where tm+1 ≡ t1 .

=P \ P(t�+1 , t� , T

mp

P

)

if i = j� ,otherwise,

1. Domain Dmax is maximal for the possibility result.
2. Suppose that domain D is such that for each i ∈ I, P(T ) ⊆ Di ⊆ Dimax . Then, there is a
strategy-proof mechanism that dominates DAτ on D.
Remark 2. By Lemma 6, the restricted domain P(T )J × P I\J in Theorem 2 is always containedin the maximal domain Dmax .
The proof is in Appendix C. Loosely speaking, the maximal domain Dmax rules out preference
reversals of students in J with respect to schools in T from the maximally potentially overdemanded
set.23 Theorem 3 sheds light on the logic behind the impossibility theorem on the full domain(Theorem 1) and the possibility result on the tier-preference domain (Theorem 2): Consider apreference profile and a priority structure, where student j� prefers school t�+1 to school t� to
23

Ergin (2002) has shown that certain reversals in schools’ priority orderings (coupled with capacity restrictions)are critical for DA to satisfy Pareto eﬃciency as well as other desirable properties. Theorem 3 provides another,conceptually related perspective on DA from the point of view of students’ preferences.

19which she is assigned under DA. On the maximal domain Dmax , we can construct a strategy-proof
mechanism dominating DA by swapping schools assigned under DA between the students in J atsuch profiles. The key idea is that once we allow either student to upgrade a non-T mp school above
her DA assignment but below her assignment under the dominating mechanism (i.e., by reportinga preference outside Djmax), the dominating mechanism is no longer strategy-proof.
�
Example 4. Consider the setting in Example 1 where I = {i, j1 , j2 } and S = {t1 , t2 , o}. The
unique maximally potentially overdemanded set is T mp = {t1 , t2 }. Consequently, we have:P(T mp )
t1 t2
t2 t1
o
o

Djmax =P\P(t2 ,t1 ,T mp )Djmax =P\P(t1 ,t2 ,T mp )

t1
t2
o

t1
t2
o

1

t1
o
t2

o
t1
t2

t2
t1
o

o
t2
t1

2

o
t1
t2

t2
t1
o

t2
o
t1

o
t2
t1
♦

6

Conclusion

The Gale-Shapley deferred acceptance (DA) mechanism has been a focal assignment tool not onlyin theory but also in practical market design. Recent research has shown a surge of interest in
exploring mechanisms that go beyond DA in terms of welfare (either ex-ante or ex-post). We
have shown that whether such attempts come at the cost of strategy-proofness may be sensitive tothe specifics of the environment. We have argued that weakly underdemanded schools, which weinterpret as the endogenously emerging “pseudo outside options,” appear to be the primary cause of
the general impossibility result shown by Theorem 1. This result suggests that it may be possible
to improve upon DA by restricting attention to problems where weakly underdemanded schools do
not arise. In circumstances when students cannot credibly use outside options as strategic choices
or when it may be diﬃcult to identify weakly underdemanded schools, the scope of manipulation
under alternative mechanisms may be diminished. More broadly, our approach puts the three-way
tension among eﬃciency, stability, and strategy-proofness into a new perspective by highlighting
the importance of the strategic role of outside options. It remains an interesting future goal tosearch for new assignment mechanisms in light of this optimistic perspective.

A

Appendix

A.1

Proof of Lemma 1

Part (1): Let µ ∈ M be non-wasteful at P . Suppose, on the contrary, that the outside option,o, is overdemanded at (P, �) under µ. Then, for some i ∈ I, o Pi µ(i). Thus for some t ∈20

S \ {o}, µ(i) = t, and thus |µ(t)| ≥ 1. Moreover, by non-wastefulness of µ, |µ(o)| = |I|. Thus,��s∈S |µ(s)| ≥ |I| + 1, which contradicts the fact that µ is a matching and thuss∈S |µ(s)| = |I|.
Part (2): Let u ∈ S � ⊆ S \ T mp . Suppose on the contrary that all schools in T mp ∪ S � areoverdemanded at (P, �) under DAτ (P, �). We first show�s∈T mp ∪{u}|DAτs (P, �)| = |I|.

(2)

�
mp
By the definition of T mp ,∪ {u}, since ss∈T mp ∪{u} qs ≥ |I|. Now, for each school s ∈ Tττis overdemanded, there is j ∈ I such that s Pj DAj (P, �) and thus |DAs (P, �)| = qs by non��wastefulness of DA. Thus, as s∈T mp ∪{u} qs ≥ |I|, s∈T mp ∪{u} |DAτs (P, �)| ≥ |I|. Hence, since�ττs∈S |DAs (P, �)| = |I| (∵ DA (P, �) is a matching), we obtain Equation (2).
By Equation (2), under DA, each application is made only to T mp ∪ {u}. Note that DA ends inat least two steps. Consider the last step r ≥ 2 of DA at (P, �τ ), where some student k who was
rejected at step r − 1 and applies to some school t ∈ T mp ∪ {u} at step r. Since t is overdemanded,
there is some student k � �= k such that t Pk� DAτk� (P, �). Thus k � must have applied to and been
rejected by t at an earlier step than r. Thus, school t has kept qt applicants at step r − 1. Hence,school t has at least (qt +1) applications at step r and thus rejects one of them. But this contradicts
the assumption that r is the last step of DA.
�Part (3): Note s∈S qs ≥ |I| by our assumption. Thus, by the definition of T mp , T mp �= S. Then,the set S � := S \ T mp is not empty. Part (2) leads to the desired result.
�

A.2

Proof of Lemmas 2 and 4

We first prove Lemma 4 and then Lemma 2.
A.2.1

Lemma 4

Part (2) is straightforward by definition. Before proving Part (1), we show two useful claims. Let
ϕ and ζ be mechanisms, and (P, �) ∈ D × AS a problem.
Claim 1. If ϕ(P, �) dominates ζ(P, �) at P and ζ(P, �) is non-wasteful at P , then there is a
nontrivial cycle for (ϕ, ζ) at (P, �).
Proof. Let ν = ϕ(P, �) and µ = ζ(P, �). We first define a list of students (i1 , . . . , iK ) to be atemporary list of size K ≥ 2 if for each k ∈ {1, . . . , K − 1}, µ(ik+1 ) Pik µ(ik ) and ν(ik ) =µ(ik+1 ); and ν(iK ) PiK µ(iK ).
We first construct a temporary list of size 2. Since ν dominates µ, there is i1 ∈ I such thatν(i1 ) Pi1 µ(i1 ). Let s2 := ν(i1 ) and s1 := µ(i1 ). Note s1 �= s2 . By non-wastefulness of µ, as
s2 Pi1 µ(i1 ), we have |µ(s2 )| = qs2 . Then there is i2 ∈ µ(s2 ) such that ν(i2 ) �= µ(i2 ) (otherwise, as|µ(s2 )| = qs2 , µ(s2 ) = ν(s2 ); then i1 ∈ ν(s2 ) = µ(s2 ) and thus s2 = µ(i1 ) ≡ s1 , which contradicts21

s1 �= s2 .). Thus, as ν dominates µ, ν(i2 ) Pi2 µ(i2 ). Moreover, as i2 ∈ µ(s2 ), ν(i1 ) ≡ s2 = µ(i2 ); andas ν(i1 ) Pi1 µ(i1 ), we have µ(i2 ) Pi1 µ(i1 ). Thus (i1 , i2 ) is a temporary list of size 2. If ν(i1 ) = µ(i1 ),the temporary list is a nontrivial cycle for (ϕ, ζ) at (P, �). If not, we continue as follows.
Suppose that (i1 , . . . , iK−1 ) is a temporary list of size K − 1 where K ≥ 3. We constructa temporary list of size K. Let sk := µ(ik ) for each k ∈ {1, . . . , K − 1}. Since (i1 , . . . , iK−1 )is a temporary list, ν(iK−1 ) PiK−1 µ(iK−1 ). Let sK := ν(iK−1 ). Note sK−1 �= sK . By nonwastefulness of µ, as sK PiK−1 µ(iK−1 ), we have |µ(sK )| = qsK . Then there is iK ∈ µ(sK ) suchthat ν(iK ) �= µ(iK ) (Otherwise, as |µ(sK )| = qsK , µ(sK ) = ν(sK ); then iK−1 ∈ ν(sK ) = µ(sK ) andthus sK = µ(iK−1 ) ≡ sK−1 , which contradicts sK−1 �= sK ). Thus, as ν dominates µ, ν(iK ) PiKµ(iK ). Moreover, as iK ∈ µ(sK ), ν(iK−1 ) ≡ sK = µ(iK ); and as ν(iK−1 ) PiK−1 µ(iK−1 ), we haveµ(iK ) PiK−1 µ(iK−1 ). Thus (i1 , . . . , iK ) is a temporary list of size K. If ν(iK ) = µ(ik ) for somek ∈ {1, . . . , K − 1}, then the list (ik , . . . , iK ) is a nontrivial cycle for (ϕ, ζ) at (P, �). As the set ofstudents is finite, we eventually obtain a nontrivial cycle for (ϕ, ζ) at (P, �).
We say that a mechanism ζ � is induced by a cycle C for (ϕ, ζ) at (P, �) if for eachi ∈ I(C), ζi� (P, �) is the target school of i in C; for each i ∈ I \ I(C), ζ � (P, �) = ζ(P, �); and foreach (P � , �� ) �= (P, �), ζ � (P � , �� ) = ζ(P � , �� ).
Claim 2. Suppose that ϕ(P, �) dominates a non-wasteful matching ζ(P, �) at P and a mechanismζ � is induced by a nontrivial cycle C for (ϕ, ζ) at (P, �). Then, (i) ϕ(P, �) = ζ � (P, �) or ϕ(P, �)dominates ζ � (P, �) at P , and (ii) ζ � (P, �) is non-wasteful at P .
The proof is straightforward and thus is omitted.
Now we prove Part (1). Let ϕ and ζ be such that ϕ dominates ζ and ζ is non-wasteful. Definea cycle selection C for (ϕ, ζ) such that for each problem (P, �) ∈ D × AS , if ϕ(P, �) = ζ(P, �), let
Ci (P, �) = (i) for each i ∈ I; if ϕ(P, �) dominates ζ(P, �) at P (this is true for at least one (P, �)
due to the dominance), we find C(P, �) in the following procedure: For � ≥ 1, letting ζ 0 = ζ,Step 0: Let C 0 = {(i)| ϕi (P, �) = ζi (P, �)} be the set of all trivial cycles.
Step �: From the previous step, ζ �−1 (P, �) �= ϕ(P, �) is non-wasteful and ϕ(P, �) dominatesζ �−1 (P, �) at P . By Claim 1, there is a nontrivial cycle C � for (ϕ, ζ �−1 ) at (P, �). Let ζ � be themechanism induced by C � for (ϕ, ζ �−1 ) at (P, �). By Claim 2-(i), ϕ(P, �) = ζ � (P, �) or ϕ(P, �)dominates ζ � (P, �) at P . If the former happens, the procedure stops. Otherwise, go to the next
step. Note that by Claim 2-(ii), ϕ(P, �) dominates ζ � (P, �) at P and ζ � (P, �) is non-wasteful at
P.
The above procedure stops in a finite step, L, as the number |i ∈ I | ϕi (P, �) �= ζ � (P, �)| (≤ |I|)is strictly decreasing in � and I is finite.
Let C = C 0 ∪ {C 1 , . . . , C L }. By construction, each C � is also a cycle for (ϕ, ζ), and {I(C)}c∈C
partitions I. Moreover, ζ L (P, �) = ϕ(P, �). Thus, since ζ L (P, �) is non-wasteful at P , and thus
ϕ(P, �) is non-wasteful at P . Hence, ϕ is non-wasteful.
�22

A.2.2

Lemma 2We show its contrapositive. Suppose that student i is not in a trivial cycle for (ϕ, DAτ ) at (P, �).
Since ϕ dominates non-wasteful DAτ , there is a nontrivial cycle selection C for (ϕ, DAτ ). Then,by Lemma 4, i is in a nontrivial cycle Ci (P, �) := (i1 , . . . , iK ) for (ϕ, DAτ ) at (P, �) where K = 2.
Let i = i2 without loss of generality. Then, by definition of cycles, DAτi2 (P, �) Pi1 DAτi1 (P, �).
Thus DAτi2 (P, �) is overdemanded at (P, �; τ ).
�

A.3

Proof of Lemma 3

We start with the following useful claim whose straightforward proof is omitted.
Claim 3. Let T be the set of all schools that are weakly underdemanded at (P, �; τ ). For all��T ∈ AT , (i) DAτ (P, �) = DAτ (P, ��T , �−T ), and (ii) if s is weakly underdemanded at (P, �; τ ),then s is also weakly underdemanded at (P, ��T , �−T ; τ ).
Suppose that under DA, student i is assigned school s∗ , which is overdemanded at (P, �; τ ).
Let S u be the set of all schools that are weakly underdemanded at (P, �; τ ). Note that S u �= ∅ byLemma 1-(3), and any weakly underdemanded school s ∈ S u is strictly worse than s∗ in Pi as s∗
is overdemanded. We consider two cases:
Pi

Pi�

Pi��

Pi |U (Pi ,s∗ )\{s∗ }s∗..
.

Pi |U (Pi ,s∗ )\{s∗ }all weakly underdemanded schools at (P, �; τ )Pi |U (Pi ,s∗ )\{s∗ }
su

s∗
..
.

s∗
..
.

Case 1: for some s ∈ S u , |DAτs (P, �)| < qs . Let su ∈ S u be one such school. Consider the
preference Pi�� that upgrades su above s∗ as described in the above table. Let P �� := (Pi�� , P−i ). Letµ�� be a matching such that µ�� (i) = su and for all j �= i, µ�� (j) = DAτj (P, �). Then µ�� is stable at(P �� , �τ ). For problem (P �� , �; τ ), DA works in exactly the same way as it does for (P, �; τ ) untilright before the step i applies to su . Hence DAτi (P �� , �) �∈ U (Pi , s∗ ) \ {s∗ }. Note that matchingDAτ (P �� , �) dominates at P �� any matching that is stable at (P �� , �τ ); µ�� is stable at (P �� , �τ ); andµ�� (i) = su . Thus DAτi (P �� , �) = su . Also, for each student j �= i, DAτj (P �� , �) Rj µ�� (j). Thus, forall j �= i, as su ∈ S u and µ�� (j) = DAτj (P, �), we have DAτj (P �� , �) Rj DAτj (P, �) Rj su . Therefore
su is weakly underdemanded at (P �� , �; τ ).
Case 2: for all s ∈ S u , |DAτs (P, �)| = qs . As s∗ is overdemanded at (P, �; τ ), all schools in
U (Pi , s∗ ) are overdemanded at (P, �; τ ). Thus, since S u �= ∅, all schools in S u are less desirable
than s∗ to student i in Pi . We consider the preference Pi� that upgrades all weakly underdemanded
schools in S u above s∗ as described in the above table. Moreover, for all s ∈ S u , let ��s be thepriority such that i has the lowest priority for s, and the relative rankings of all other students are
the same as in �s . Let P � := (Pi� , P−i ) and �� := (��S u , �−S u ).
23

We first show that DAτi (P � , �� ) ∈ S u . Suppose not. Then, under DA, all schools in S u rejecti at (P � , �� ; τ ). Since i has the lowest priority at all schools in S u and DAτ (P, �) is stable at(P, �τ ), DAτ (P, �) is also stable at (P � , �� ). Then, as the DA matching is student-optimal stable,DAτ (P � , �� ) = DAτ (P, �). Thus, all overdemanded schools at (P, �; τ ) are still overdemanded at(P � , �� ; τ ), and all weakly underdemanded schools at (P, �; τ ) become overdemanded at (P � , �� ; τ ).
Then, all schools are overdemanded at (P � , �� ; τ ), which contradicts Lemma 1-(2).
Now, letting su := DAτi (P � , �� ) ∈ S u , consider the preference Pi�� that upgrades su above s∗ in
Pi as described in the above table. Let P �� := (Pi�� , P−i ). We will show that DAτi (P �� , �� ) = su .
For (P �� , �� ; τ ) DA works in the same way as for (P, �; τ ) until student i applies to su . Thus,
DAτi (P �� , �� ) �∈ U (Pi�� , su ) \ {su }. Then, by strategy-proofness of DAτ , DAτi (P �� , �� ) Ri�� DAτi (P � , ��), i.e., DAτi (P �� , �� ) Ri�� su and thus DAτi (P �� , �� ) = su .
It remains to show that DAτi (P �� , �) = su and su is weakly underdemanded at (P �� , �; τ ). Notethat DAτ (P, �) is stable at (P �� , �� ), since DAτ (P, �) is stable at (P, �τ ) and i has the lowest
priority for su with |DAτsu (P, �)| = qsu . Since matching DAτ (P �� , �� ) is student-optimal stable, wehave for all j �= i and all s ∈ S u , DAτj (P �� , �� ) Rj�� DAτj (P, �) Rj s and DAτi (P �� , �� ) Ri�� su Ri�� s.
��
Since P−i
= P−i , for all j ∈ I and all s ∈ S u , DAτj (P �� , �� ) Rj�� s. That is, all schools in S u , including
su , are weakly underdemanded at (P �� , �� ; τ ). Hence, by Claim 3, DAτi (P �� , �) = DAτi (P �� , �� ) =su , which is weakly underdemanded at (P �� , �; τ ).
�

A.4

Proof of Lemma 5Part (1). Suppose that a strategy-proof mechanism ϕ dominates a non-wasteful mechanism
ζ. Then, by Lemma 4 (1), there is a nontrivial cycle selection C for (ϕ, ζ). We show that C isqualified for (ϕ, ζ). Let (P, �) ∈ D × AS , i ∈ I, and Pi� ∈ Di such that U (Pi� , s∗ ) ⊆ U (Pi , s∗ ),where s∗ is the target school of i in Ci (P, �). Since cycle selection C is for (ϕ, ζ), ϕi (P, �) = s∗ .
Now, since ϕ is strategy-proof, ϕi (Pi� , P−i , �) Ri� ϕi (P, �) = s∗ . Thus, since U (Pi� , s∗ ) ⊆ U (Pi , s∗ ),ϕi (Pi� , P−i , �) Ri ϕi (P, �). On the other hand, since ϕ is strategy-proof, ϕi (P, �) Ri ϕi (Pi� , P−i , �).
Therefore, by strictness of preferences, ϕi (Pi� , P−i , �) = ϕi (P, �) = s∗ , which shows that s∗ is thetarget school of i in Ci (Pi� , P−i , �). Hence, C is qualified for (ϕ, ζ).
�Part (2). Suppose that there is a qualified cycle-selection C for a strategy-proof mechanism ζ.
Let ϕ be the mechanism induced by C. By Lemma 4 (2), ϕ dominates ζ.
It remains to show that ϕ is strategy-proof. Suppose, for a contradiction, that there exist
�∈ AS , i ∈ I, P ∈ D, and Pi� ∈ Di such that ϕi (Pi� , P−i , �) Pi ϕi (P, �). First, since ϕ dominatesζ, ϕi (P, �) Ri ζi (P, �). Moreover, since ζ is strategy-proof, ζi (P, �) Ri ζi (Pi� , P−i , �). Hence, bytransitivity of preferences, ϕi (Pi� , P−i , �) Pi ζi (Pi� , P−i , �).
Let s∗ = ϕi (P, �) and s∗∗ = ϕi (Pi� , P−i , �). Then s∗ is the i’s target school in Ci (P, �) and s∗∗
is the i’s target school in C(Pi� , P−i , �). Note that s∗∗ Pi s∗ and thus s∗ �= s∗∗ .
Now consider the preference Pi�� of student i where s∗∗ is her top choice and s∗ is her second top
24

Table 3: Preferences and matchings in Part 1
˜ τt �˜ τtPj 1 Pj 2 P i
Pj1 Pj2 Pi�
�
1

2

t2

t1

t2

t2

t1

t2

i

j2

t1

t2

t1

t1

t2

o

j1

j1

o

o

o

o

o

t1

j2

i

Two preference profiles and a priority profile after breaking a tie are shown for the proof of Part 1 in Theorem 2.
The underlined (overlined) schools in the preference profiles are assigned to the corresponding students under DA(dominating mechanism ϕ).

choice. Then, since s∗∗ Pi s∗ , we have {s∗ , s∗∗ } = U (Pi�� , s∗ ) ⊆ U (Pi , s∗ ). Note that C is qualified
and s∗ is the i’s target school in Ci (P, �). Thus, s∗ is the i’s target school in Ci (Pi�� , P−i , �)and thus ϕi (Pi�� , P−i , �) = s∗ . On the other hand, {s∗∗ } = U (Pi�� , s∗∗ ) ⊆ U (Pi� , s∗∗ ) and s∗∗ isthe i’s target school in Ci (Pi� , P−i , �). Thus, since C is qualified, s∗∗ is the i’s target school in
Ci (Pi�� , P−i , �) and thus ϕi (Pi�� , P−i , �) = s∗∗ . In sum, we have ϕi (Pi�� , P−i , �) = s∗ = s∗∗ , which
contradicts s∗ �= s∗∗ .
�A.5

Proof of Lemma 6

Let T ⊆ T � ⊆ S and x, y ∈ T be distinct. It is clear that P(T ) ⊆ P \ P(x, y, T ). To show
P \ P(x, y, T ) ⊆ P \ P(x, y, T � ), we prove its equivalent statement where P(x, y, T � ) ⊆ P(x, y, T ).
Let Pi ∈ P(x, y, T � ). Then, by definition, for some u ∈ S \ T � , x Pi u Pi y and for each ū ∈ S \ T � ,x Pi ū. Since S \ T � ⊆ S \ T , we have u ∈ S \ T , x Pi u Pi y and for each ū ∈ S \ T , x Pi ū. Thus,
Pi ∈ P(x, y, T ).
�

B

Proof of Theorem 2 - Part (1)To facilitate the exposition, we take the same setting (I, S, q, P ) as that in Example 1. Let
I = {i, j1 , j2 }, S = {t1 , t2 , o}, J = {j1 , j2 }, T = {t1 , t2 }, and qt1 = qt2 = 1. The only diﬀerence˜ τ where the roles of students i and j1 are switched. Seefrom Example 1 is the priority profile �
Table 3.
Suppose that there is a Pareto eﬃcient mechanism ϕ̃ that dominates DAτ . We show thatstudent i can manipulate ϕ̃, whose proof is very similar to that of Example 1, where student j1
manipulates the dominating mechanism ϕ.
˜ DAτ˜At problem (P, �),(j1 ,j2 ,i) (P, �) = (o, t2 , t1 ), and thus there is a unique Pareto eﬃcient˜ at P (Table 3). Thus, since ϕ̃ is Pareto
matching ν(j1 ,j2 ,i) = (o, t1 , t2 ) that dominates DAτ (P, �)˜ = ν. Consider the singleton preference Pi� of student ieﬃcient and dominates DAτ , ϕ̃(P, �)
25˜ = (t2 , t1 , o), which is Pareto eﬃcient atthat declares only t2 above o. Then DAτ(j1 ,j2 ,i) (Pi� , P−i , �)˜ Thus, since ϕ̃ is Pareto eﬃcient and dominates DAτ , ϕ̃(Pi� , P−i , �)˜ = DAτ (Pi� , P−i , �).
˜(Pi� , P−i , �).
˜ = t2 Pi� o = ϕ̃i (Pi� , P−i , �).
˜ Hence, ϕ̃ is not strategy-proof.
Now ϕ̃i (P, �)�C

Proof of Theorem 3

For the proof of Theorem 3, it suﬃces to show:• (Possibility result — Part 2 in Theorem 3) On any domain D where for each i ∈ I, P(T ) ⊆Di ⊆ Dimax , there is a strategy-proof mechanism that dominates DAτ .
• (Impossibility result) On any domain D where for each D where Dmax � D ⊆ P I , nostrategy-proof mechanism dominates DAτ .

C.1

Proof of the possibility result

We follow the same proof strategy as the one in the proof of Theorem 2-(2). The only diﬀerenceis that our domain varies from P(T ) to Dimax . As in the proof of Theorem 2-(2), we use the same
notations and argument up to Step 1, and will modify Steps 2 and 3 due to the domain change.
Step 2: We show∀� ∈ {1, . . . , m} ∀Pj� ∈ Dj� [t�+1 Pj� t� and ∀u ∈ S \ T mp , t�+1 Pj� u] ⇒ Pj� ∈ P � .
Let � ∈ {1, . . . , m} and Pj� ∈ Dj� such that the hypothesis in the above is satisfied. Since
Pj� ∈ Djmax= P \ P(t�+1 , t� , T mp ), we have�[∀u ∈ S \ T mp , u Pj� t�+1 or t� Pj� u] or ∃u� ∈ S \ T mp , u� Pj� t�+1

⇒ ∀u ∈ S \ T mp , t� Pj� u(∵ the hypothesis)⇒ Pj � ∈ P � .

Step 3: We show that the following cycle selection C for DAτ is qualified.

C(P, �) =
{(j , . . . , j )} ∪ {(i) | i ∈ I \ J}1m

{(i) | i ∈ I}¯
if P ∈ D∗ and �= �,otherwise.

Let (P, �) ∈ D × AS , i ∈ I, and Pi� ∈ Di such that U (Pi� , s∗ ) ⊆ U (Pi , s∗ ) where s∗ is the target
school of i in Ci (P, �). Let s∗ be the target school of i in Ci (Pi� , P−i , �). We need to show s∗ = s∗∗ .
26

¯ or [i ∈ {j1 , . . . , jm }, �= �,¯ P �∈ D∗ , (Pi� , P−i ) �∈ D∗ ]. We canCase 1 : [i �∈ {j1 , . . . , jm } and ��= �]conclude that s∗ = s∗∗ using the corresponding argument in the proof of Theorem 2-(2).
¯ and P ∈ D∗ . Let i = j� for some � ∈ {1, . . . , m}. As P ∈ D∗ , byCase 2 : i ∈ {j1 , . . . , jm }, �= �,
Step 1, s∗ = t�+1 .
We show Pi� ∈ P � and thus (Pi� , P−i ) ∈ D∗ . By Step 2, it is suﬃcient to show that t�+1 Pi� t�
and for each u ∈ S \ T mp , t�+1 Pi� u. Fix u ∈ S \ T mp . Note that U (Pi� , t�+1 ) ⊆ U (Pi , t�+1 ) , Pi ∈ P �, and t�+1 Pi t� . Thus t�+1 Pi� t� and t�+1 Pi� u. Hence Pi� ∈ P � .
Then, since (Pi� , P−i ) ∈ D∗ , it follows from Step 1 that s∗∗ = t�+1 . Hence s∗∗ = t�+1 = s∗ .
¯ and P �∈ D∗ . It is suﬃcient to show (Pi� , P−i ) �∈ D∗ , as in thisCase 3 : i ∈ {j1 , . . . , jm }, �= �,case s∗ = s∗∗ by Case 1. Suppose (Pi� , P−i ) ∈ D∗ . Let i = j� for some � ∈ {1, . . . , m}.
We first show s∗ = t� . Note that as P �∈ D∗ , Ci (P, �) = {i} and DAτi (P, �) = s∗ . Since
U (Pi� , s∗ ) ⊆ U (Pi , s∗ ), by strategy-proofness of DAτ , DAτi (Pi� , P−i , �) = s∗ . On the other hand,since (Pi� , P−i ) ∈ D∗ , by Step 1, DAτi (Pi� , P−i , �) = t� . Hence s∗ = t� .
We finally obtain Pi ∈ P � , a contradiction. By Step 2, it is suﬃcient to show that t�+1 Pi t�
and for each u ∈ S \ T mp , t�+1 Pi u. Fix u ∈ S \ T mp . Note that t�+1 ∈ U (Pi� , s∗ ) ⊆ U (Pi , s∗ ) ands∗ = t� . Thus t�+1 Pi t� . Moreover, t�+1 Pi u by the following reasoning. Suppose u Pi t�+1 . Since
the DA matching is student-optimal stable, we would have DAτ (P, �) = DAτ (Pi� , P−i , �) and thus
for some in+1 ∈ In+1 , DAτin+1 (Pi� , P−i , �) = u. Hence, as u Pi t�+1 Pi t� and DAτi (Pi� , P−i , �) = t� ,u is weakly underdemanded at (Pi� , P−i , �; τ ). Moreover, as Pin+1 ∈ P 1 ∩ P(T mp ), we have for eachk ∈ {1, . . . , m}, tk Pin+1 u = DAτin+1 (Pi� , P−i , �). This implies that all schools in T mp are weakly
underdemanded at (Pi� , P−i , �; τ ). Hence all schools in T mp ∪ {u} are weakly underdemanded at(Pi� , P−i , �; τ ), which violates Lemma 1-(2). This completes Step 3.
�C.2

Proof of the impossibility result

We show the impossibility result. Let Dmax � D ⊆ P I . Suppose that a mechanism ϕ dominatesDAτ on D. We start with several claims. To this end, we introduce a notation Qi (P, �): For each(P, �) ∈ D × AS and each i ∈ I with ϕi (P, �) �= DAτi (P, �), let Qi (P, �) be the set of preferencesPi� ∈ P such that for some weakly underdemanded school su at (P, �; τ ), Pi� upgrades su aboveDAτi (P, �) in Pi , and su = DAτi (Pi� , P−i , �) is weakly underdemanded at (Pi� , P−i , �; τ ).
Claim 4. Let (P, �) ∈ D × AS and i ∈ I with ϕi (P, �) �= DAτi (P, �). Then Qi (P, �) �= ∅.
Proof. By Lemma 2, school DAτi (P, �) is overdemanded at (P, �; τ ). Then Claim 4 follows from
Lemma 3.
Claim 5. Let (P, �) ∈ D × AS and i ∈ I with ϕi (P, �) �= DAτi (P, �). If Qi (P, �) ⊆ Di , then ϕ is
not strategy-proof.

27

Proof. Suppose Qi (P, �) ⊆ Di . By Claim 4 there is Pi� ∈ Qi (P, �). Then some school su =DAτi (Pi� , P−i , �) is weakly underdemanded at (Pi� , P−i , �; τ ). By Lemma 2, ϕi (Pi� , P−i , �) =DAτi (Pi� , P−i , �) = su . Moreover, since ϕi (P, �) Pi DAτi (P, �) and Pi� upgrades su above DAτi (P, �), we have ϕi (P, �) Pi� su . Thus ϕi (P, �) Pi� ϕi (Pi� , P−i , �). Hence, since P ∈ D and Pi� ∈ Qi (P, �) ⊆ Di , ϕ is not strategy-proof on D.
Claim 6. Let (P, �) ∈ D × AS and i ∈ I with ϕi (P, �) �= DAτi (P, �). If i ∈ I \ J, then ϕ is not
strategy-proof.
Proof. Let i ∈ I \ J. By Claim 5, it suﬃces to show Qi (P, �) ⊆ Di . Since i ∈ I \ J, Di = P. Thus,
since Qi (P, �) ⊆ P, we have Qi (P, �) ⊆ Di .
Claim 7. Let (P, �) ∈ D×AS and � ∈ {1, . . . , m} with ϕj� (P, �) �= DAτj� (P, �). If DAτj� (P, �) �= t�
or ϕj� (P, �) �= t�+1 , then ϕ is not strategy-proof.
Proof. Suppose DAτj� (P, �) �= t� . By Claim 5 it suﬃces to show Qj� (P, �) ⊆ Dj� . Let Pi� ∈ Qi (P, �). Then for some weakly underdemanded school su at (P, �; τ ), Pi� upgrades su above DAτi (P, �)in Pi . Note that Djmax= P \ P(t�+1 , t� , T mp ) ⊆ Dj� and su ∈ S. Since DAτj� (P, �) �= t� and Pj���
upgrades su above DAτj� (P, �), Pj�� ∈ P \ P(t�+1 , t� , T mp ) ⊆ Dj� . Hence Qj� (P, �) ⊆ Dj� .
Suppose on the contrary that ϕj� (P, �) �= t�+1 but ϕ is strategy-proof. Then it follows fromwhat we just proved that DAτj� (P, �) = t� . Since t� �= t�+1 , we have two cases: t� Pj� t�+1 andt�+1 Pj� t� .
Case 1: t� Pj� t�+1 . Let Pj�� ∈ Qj� (P, �). Then DAτj� (P, �) = t� Pj� t�+1 . Thus, since Pj��
upgrades some su above DAτj� (P, �) = t� , we have Pj�� ∈ P \ P(t�+1 , t� , T mp ) = Djmax⊆ Dj� . Thus�
Qj� (P, �) ⊆ Dj� . By Claim 5, ϕ is not strategy-proof. This is a contradiction.
Case 2: t�+1 Pj� t� . Denote t̃ = ϕj� (P, �). Let P̃j� ∈ P such that t�+1 is put below t� andthe relative ranking over the other schools in P̃j� is kept the same as in Pj� . Then, since t̃ =ϕj� (P, �) Pj� DAτj� (P, �) = t� by the domination of ϕ over DAτ , we have U (P̃j� , t̃) ⊆ U (Pj� , t̃).
By strategy-proofness of ϕ, ϕj� (P̃j� , P−j� , �) R̃j� ϕj� (P, �) ≡ t̃. Thus, since U (P̃j� , t̃) ⊆ U (Pj� , t̃),ϕj� (P̃j� , P−j� , �) Rj� t̃. Moreover, by strategy-proofness of ϕ, t̃ ≡ ϕj� (P, �) Rj� ϕj� (P̃j� , P−j� , �).
Therefore, since preferences are strict, ϕj� (P̃j� , P−j� , �) = t̃. Similarly, since U (P̃j� , t� ) ⊆ U (Pj� , t� )and DAτj� (P, �) = t� , the strategy-proofness of DAτ implies DAτj� (P̃j� , P−j� , �) = t� .
Now, since ϕj� (P̃j� , P−j� , �) = t̃ �= t� = DAτj� (P̃j� , P−j� , �), Qj� (P̃j� , P−j� , �) is not empty by
Claim 4. Let Pj�� ∈ Qj� (P̃j� , P−j� , �). Then Pj�� updates some school su above t� in P̃j� . Thus, ast� P̃j� t�+1 , we have t� Pj�� t�+1 . Thus Pj�� ∈ P \ P(t�+1 , t� , T mp ) = Djmax⊆ Dj� . Thus, by Claim 5, ϕ�is not strategy-proof. This is a contradiction.
Finally we prove the impossibility result by contradiction. Suppose that mechanism ϕ isstrategy-proof on D. Then, by Lemma 5, there is a qualified cycle-selection C for (ϕ, DAτ ). Since
it is qualified, C is nontrivial. Thus there is (P̂ , �) ∈ D × AS such that some cycle in C(P̂ , �) is not28trivial. For notational simplicity, as we keep � fixed, we omit � in the expression of mechanisms
throughout the proof.
Step 1: We show that for each P ∈ D with ϕ(P ) �= DAτ (P ), DAτ(j1 ,...,jm ) (P ) = (t1 , . . . , tm ) andϕ(j1 ,...,jm ) (P ) = (t2 , . . . , tm+1 ). Let P ∈ D with ϕ(P ) �= DAτ (P ). Then C(P, �) has a nontrivial
cycle. By Claims 6 and 7, C has the unique cycle (j1 , . . . , jm ) for (ϕ, DAτ ), which leads to thedesired result.
Step 2: For each � ∈ {1, . . . , m}, let Pj��� ∈ P(T mp ) such that school t�+1 is the top choice in S
and school t� is the top-|T mp | choice in S. For each � ∈ {0, . . . , m}, let J� := ∅ for � = 0; andJ� := {j1 , . . . , j� } otherwise. We show by induction on � ∈ {0, . . . , m} that DAτ(j1 ,...,jm ) (PJ��� , P̂−J� ) =(t1 , . . . , tm ) and ϕ(j1 ,...,jm ) (PJ��� , P̂−J� ) = (t2 , . . . , tm+1 ).
Since the claim is trivial for � = 0, suppose that the claim is true up to � − 1, that is,DAτ(j1 ,...,jm ) (PJ���−1 , P̂−J�−1 ) = (t1 , . . . , tm ) and ϕ(j1 ,...,jm ) (PJ���−1 , P̂−J�−1 ) = (t2 , . . . , tm+1 ). By strategyproofness of ϕ, ϕj� (PJ��� , P̂−J� ) Rj��� ϕj� (PJ���−1 , P̂−J�−1 ) = t�+1 . Thus, as t�+1 is the top choice in
S under Pj��� , ϕj� (PJ��� , P̂−J� ) = t�+1 . Also, by strategy-proofness of DAτ , DAτj� (PJ���−1 , P̂−J�−1 ) R̂j�
DAτj� (PJ��� , P̂−J� ). Thus, since t�+1 P̂j1 t� = DAτj� (PJ���−1 , P̂−J�−1 ), we have DAτj� (PJ��� , P̂−J� ) �= t�+1 .
Therefore, ϕj� (PJ��� , P̂−J� ) �= DAτj� (PJ��� , P̂−J� ). By Step 1, we have the desired result.
Step 3: We finally show a contradiction. Since Dmax � D ⊆ P I , for each i ∈ I \ J, Di = P andthus we may assume without loss of generality that Djmax
� Dj1 . Then there is Pj�1 ∈ Dj1 \ Djmax
⊆
1
1
mp
mp
�
�
P(t2 , t1 , T ). Thus for some u ∈ S \ T , t2 Pj1 u Pj1 t1 . There are two cases:������, P̂−J ) �= DAτ (Pj�1 , PJ\{j, P̂−J ). Then, by Step 1, DAτ(j1 ,...,jm ) (Pj�1 , PJ\{j, P̂−J ) =Case 1: ϕ(Pj�1 , PJ\{j
1}
1}
1}
�
��
(t1 , . . . , tm ) and ϕ(j1 ,...,jm ) (Pj1 , PJ\{j1 } , P̂−J ) = (t2 , . . . , tm+1 ). Thus j2 is assigned the last school t2
��in T mp under DA, and thus each school in T mp \ {t2 } is overdemanded at (Pj�1 , PJ\{j, P̂−J , �; τ ).
1}
�
�
τ
�
��
Moreover, by our assumption, t2 Pj1 u Pj1 t1 = DAj1 (Pj1 , PJ\{j1 } , P̂−J ), and thus schools t2 and u��are overdemanded at (Pj�1 , PJ\{j, P̂−J , �; τ ). Hence all schools in T mp and school u ∈ S \ T mp are1}
overdemanded at the same problem, which contradicts Lemma 1-(2).
����Case 2: ϕ(Pj�1 , PJ\{j, P̂−J ) = DAτ (Pj�1 , PJ\{j, P̂−J ). By strategy-proofness of DAτ ,1}1}��DAτj1 (PJ�� , P̂−J ) Rj��1 DAτj1 (Pj�1 , PJ\{j, P̂−J ). Thus, since school DAτj1 (PJ�� , P̂−J ) = t1 (the equality1}��follows from Step 2) is the last choice in T mp under Pj��1 , we have DAτj1 (Pj�1 , PJ\{j, P̂−J ) ∈ {t1 } ∪
1}
mp
�
mp
�
mp
�
(S \ T ). Thus, since U (Pj1 , t2 ) ⊆ T \ {t1 } (∵ as Pj1 ∈ P(t2 , t1 , T ), t2 Pj1 t1 and for eachu� ∈ S \ T mp , t2 Pj�1 u� ), we have��DAτj1 (Pj�1 , PJ\{j, P̂−J ) �∈ U (Pj�1 , t2 ).
1}

(3)

��
On the other hand, by strategy-proofness of ϕ, ϕj1 (Pj�1 , PJ\{j, P̂−J ) Rj� 1 ϕj1 (PJ�� , P̂−J ). Thus,1}��since ϕj1 (PJ�� , P̂−J ) = t2 by Step 2, we have ϕj1 (Pj�1 , PJ\{j, P̂−J ) ∈ U (Pj�1 , t2 ). Hence, by (3),1}����ϕj1 (Pj�1 , PJ\{j, P̂−J ) �= DAτj1 (Pj�1 , PJ\{j, P̂−J ), which is a contradiction.
�
1}
1}

29

References
Abdulkadiroğlu, A., Y.-K. Che, and Y. Yasuda (2015): “Expanding "Choice" in School
Choice,” American Economic Journal: Microeconomics, 7, 1–42.
Abdulkadiroğlu, A., P. A. Pathak, and A. E. Roth (2005a): “The New York City HighSchool Match,” American Economic Review Papers and Proceedings, 95, 364–367.
——— (2009): “Strategy-proofness versus Eﬃciency in Matching with Indiﬀerences: Redesigning
the NYC High School Match,” American Economic Review, 99, 1954–1978.
Abdulkadiroğlu, A., P. A. Pathak, A. E. Roth, and T. Sönmez (2005b): “The Boston
Public School Match,” American Economic Review Papers and Proceedings, 95, 368–372.
——— (2006): “Changing the Boston School Choice Mechanism,” Working paper.
Abdulkadiroğlu, A. and T. Sönmez (2003): “School Choice: A Mechanism Design Approach,”American Economic Review, 93, 729–747.
Alcalde, J. and S. Barbera (1994): “Top Dominance and the Possibility of Strategy-Proof
Stable Solutions to Matching Problems,” Economic Theory, 4, 417–435.
Anno, H. and M. Kurino (2014): “Second-best Incentive Compatible Allocation Rules forMultiple-type Indivisible Objects,” WZB discussion paper SPII 2014-201.
Atakan, A. E. and M. Ekmekci (2014): “Bargaining and Reputation in Search Markets,”
Review of Economic Studies, 81, 1–29.
Balinski, M. and T. Sönmez (1999): “A Tale of Two Mechanisms: Student Placement,” Journalof Economic Theory, 84, 73–94.
Bergemann, D. and S. Morris (2005): “Robust Mechanism Design,” Econometrica, 73, 1771–
1813.
Board, S. and M. Pycia (2014): “Outside Options and the Failure of the Coase Conjecture,”
American Economic Review, 104, 656–671.
Calsamiglia, C. and M. Güell (2014): “The Illusion of School Choice: Empirical Evidence
from Barcelona,” Working paper.
Chen, Y. and O. Kesten (2015): “Chinese College Admissions and School Choice Reforms: A
Theoretical Analysis,” Forthcoming in Journal of Political Economy.
Compte, O. and P. Jehiel (2009): “Veto Constraint in Mechanism Design: Ineﬃciency with
Correlated Types,” American Economic Journal: Microeconomics, 1, 182–206.
30

Dubins, L. E. and D. A. Freedman (1981): “Machiavelli and the Gale-Shapley algorithm,”
American Mathematical Monthly, 88, 485–494.
Ehlers, L. and A. Erdil (2010): “Eﬃcient Assignment Respecting Priorities,” Journal of Economic Theory, 145, 1269–1282.
Erdil, A. (2014): “Strategy-proof Stochastic Assignment,” Journal of Economic Theory, 151,
146–162.
Erdil, A. and H. Ergin (2008): “What’s the Matter with Tie-breaking? Improving Eﬃciency
in School Choice,” American Economic Review, 98, 669–689.
Ergin, H. (2002): “Eﬃcient Resource Allocation on the Basis of Priorities,” Econometrica, 70,
2489–2498.
Ergin, H. and T. Sönmez (2006): “Games of School Choice under the Boston Mechanism,”
Journal of Public Economics, 90, 215–237.
Figueroa, N. and V. Skreta (2009): “The Role of Optimal Threats in Auction Design,” Journalof Economic Theory, 144, 884–897.
Gale, D. and L. S. Shapley (1962): “College Admissions and the Stability of Marriage,”
American Mathematical Monthly, 69, 9–15.
Guillen, P. and O. Kesten (2012): “Matching Markets with Mixed Ownership: The Case fora Real-life Mechanism,” International Economic Review, 53(3), 1027–1046.
Haeringer, G. and F. Klijn (2009): “Constrained School Choice,” Journal of Economic Theory,
144, 1921–1947.
Hiller, V. and O. Tercieux (2014): “Choix d’écoles en France: Une Évaluation de la Procédure
Aﬀelnet,” Revue Economique, 65, 619–656.
Jehiel, P., B. Moldovanu, and E. Stacchetti (1996): “How (Not) to Sell Nuclear Weapons,”
American Economic Review, 86, 814–829.
Jullien, B. (2000): “Participation Constraints in Adverse Selection Models,” Journal of Economic
Theory, 93, 1–47.
Kandori, M., F. Kojima, and Y. Yasuda (2010): “Tiers, Preference Similarity, and the Limits
on Stable Partners,” Working paper.
Kesten, O. (2006): “On Two Competing Mechanisms for Priority-based Allocation Problems,”
Journal of Economic Theory, 127, 155–171.
31

——— (2010): “School Choice with Consent,” Quarterly Journal of Economics, 125(3), 1297–1348.
Kesten, O. and M. U. Ünver (2015): “A Theory of School-Choice Lotteries,” Theoretical
Economics, 10, 543–595.
Kojima, F. and M. U. Ünver (2014): “The ‘Boston’ School-Choice Mechanism: An Axiomatic
Approach,” Economic Theory, 55, 515–544.
Lauermann, S. and G. Virág (2012): “Auctions in Markets: Common Outside Options andthe Continuation Value Eﬀect,” American Economic Journal: Microeconomics, 4, 107–130.
Lee, J. and Q. Liu (2013): “Gambling Reputation: Repeated Bargaining with Outside Options,”
Econometrica, 81, 1601–1672.
Nash, J. F. (1950): “The Bargaining Problem,” Econometrica, 18, 155–162.
——— (1953): “Two-Person Cooperative Games,” Econometrica, 21, 128–140.
Pathak, P. A. and T. Sönmez (2008): “Leveling the Playing Field: Sincere and SophisticatedPlayers in the Boston Mechanism,” American Economic Review, 98, 1636–1652.
Rasul, I. and S. Sonderegger (2010): “The Role of the Agent’s Outside Options in PrincipalAgent Relationships,” Games and Economic Behavior, 68, 781–788.
Roth, A. E. (1982): “The Economics of Matching: Stability and Incentives,” Mathematics ofOperations Research, 7, 617–628.
——— (1984): “The Evolution of the Labor Market for Medical Interns and Residents: A Case
Study in Game Theory,” Journal of Political Economy, 92, 991–1016.
Roth, A. E. and M. A. O. Sotomayor (1990): Two-sided Matching: A Study in Gametheoretic Modeling and Analysis, Cambridge: Cambridge University Press.
Sönmez, T. and U. Ünver (2011): “Matching, Allocation, and Exchange of Discrete Resources,”in Handbook of Social Economics, ed. by J. Benhabib, A. Bisin, and M. O. Jackson, Amsterdam:
North Holland, vol. 1A, 781–852.
Wilson, R. (1987): “Game Theoretic Analysis of Trading Processes,” in Advances in Economic
Theory, ed. by T. Bewley, Cambridge: Cambridge University Press, chap. 2, 33–77.

32