Guillaume Haeringer

Vincent Iehlé

Itai Ashlagi

Nicole Immorlica

Jacob Leshno

Baharak Rastegari

Al Roth

Daniela Saban

Jay Sethuraman

Peter Troyan

Two-Sided Matching with One-Sided Preferences *

Keywords: JEL codes C78, J41, C81 School Choice, Hall's marriage theorem, stable matching, zoning policy, Pareto improvement

In a school choice context we show that considering only schools' priorities and the set of acceptable schools for each student -but not how these schools are ranked in their preferences-we can restrict the set of possible stable matchings that can arise for any preference profile of the students that leaves the set of acceptable schools unchanged. We characterize impossible matches, i.e., of pairs student-school that cannot be matched at any stable matching, for any preference profile. Our approach consists of linking Hall's marriage condition to stable matchings. Our results offer a new methodology to assess to what extent the preferences on one side of a matching market can preset the stable matchings that can emerge. First, we use this technique to discuss the impact of priority zoning in school choice problems. Second, a new mechanism for school choice problems is proposed. It is shown that it (weakly) Pareto dominates the Student Optimal Stable Mechanism and retain some of its incentives.

Introduction

This paper is aimed at understanding further the implications of stability in two-sided matching markets. There is now a large consensus in the matching literature that stability, which can be understood as the equilibrium notion for matching markets, is one of the most desirable properties we should care about when designing matching institutions. 1 Evidence collected by [START_REF] Roth | New Physicians: A Natural Experiment in Market Organization[END_REF], and later by [START_REF] Kagel | The Dynamics of Reorganization in Matching Markets: A Laboratory Experiment Motivated by a Natural Experiment[END_REF], indeed suggests that the lack of stability can be a cause of market failure. Stability, in one-to-one matching problems, is a conjunction of two requirements: no agent is matched to an unacceptable partner (individual rationality), and no pair of agents who would prefer to be matched to one another rather than to their current mate (absence of blocking pairs). 2 As the second requirement shows, stability hinges on the preferences of both sides of the market. We challenge in this paper this interpretation by showing how we can identify unstable matchings by considering only the preferences on one side of the market.

Our goal is to investigate, when considering one side's preferences, whether there exists some preference profile of the other side so that a particular pair of agents can be matched at a stable matching (for that profile). Answering this question is valuable because the more we can find such pairs, the more we are able to narrow down the stable matchings that may emerge. This insight has several major implications for matching theory. First, it provides a tool for data analysis and preference estimation. With the preferences of one side of the market (whether observed or estimated), one can identify for instance which part of the other side's preferences does matter to compute the final matching, thereby narrowing the set of preferences that need to be estimated. Second, it provides a methodology to analyze the extent to which the preferences on one side of the market does preset the matchings that can emerge. Our approach can prove therefore particularly useful when the design of a matching mechanism involves "constructing" the preferences on one side of the market. This is the case for instance in school choice problems, where schools' "preferences" are usually the outcome of some political or administrative decision. Having some freedom to design the preferences on one side of a matching market can indeed be valuable when one also 1 See [START_REF] Shapley | On Cores and Indivisibilities[END_REF] and [START_REF] Quinzii | Core and Competitive Equilibria with Indivisibilities[END_REF] for early approaches about the link between market competitive equilibrium and stable matchings, or [START_REF] Azevedo | A Supply and Demand Framework for Two-Sided Matching Markets[END_REF] for a more recent account on the matter.

2 For many-to-one matching problems the definition of a stable matching changes slightly.

3 cares about the distributional aspect of a matching (e.g., school districts usually care about maintaining a certain level of social or racial diversity among schools). Our methodology can permit market designers to test the impact of a particular pattern of preferences under minimal assumptions on agent's preferences.

To streamline the analysis we consider school choice problems where one has to match students to schools, but our results are not confined to this class of models; they can be applied to any many-to-one matching model with responsive preferences. 3 In the canonical school choice model of [START_REF] Abdulkadiroglu | School Choice: A Mechanism Design Approach[END_REF] students have preferences over schools (and the option of not being matched to any school), and schools have priority orderings over students (the schools' "preferences"). 4 The environments we consider are made of schools' priority lists over students and, for each student, the list of acceptable schools. Students' preferences over their acceptable schools, however, are left unspecified.

We call such environments pre-matching problems. 5 The question we address is the following. Given a pair student-school, is there a realization of students' preferences such that they can be matched at a stable matching (for those preferences)? If the answer is negative then the pair is called an impossible match. 6 Our first contribution consists of characterizing impossible matches in pre-matching problems.

In a pre-matching problem, the only way to know with certainty that a matching cannot 3 See [START_REF] Roth | The College Admission Revisited[END_REF]. 4 Since schools' "preferences" are usually the outcome of some political or administrative decision, schools' orderings over students are called priorities in the literature as they do not reflect genuine preferences that the schools may have over students. 5 There are two ways to interpret a pre-matching problem. A first case is when we have access to preferences from both sides, but we simply "ignore" how students rank their acceptable schools (see Section 2.3 for the relation between a "classic" school choice problem and a pre-matching problem). A second case is when we do not have access to student's preferences but we known their sets of acceptable schools. This is the case for the French academic job market (where we replace schools by departments and students by candidates),

where both departments and candidates submit a preference ordering over potential matches to a central clearinghouse (see [START_REF] Haeringer | Enjeux Stratégiques du Concours de Recrutement des Enseignants-Chercheurs[END_REF]). Candidates' preferences in this market are confidential, but departments' are not. In the context of the French market, it is natural to assume that if a candidate appears in the preference list of a department then the associated position is acceptable for the candidate (candidates bear the traveling costs to attend the interview with the department, the position offered are tenured, and the market takes place relatively late (around May, for a position usually starting September 1st)). 6 Our approach about students' potential preferences over schools is distribution-free, i.e., we do not make any assumption on the distribution over student's preference profiles.

be stable, for any realization of students' preferences, is when a student is unmatched and one of his acceptable schools either has an empty seat or is matched to a student with a lower priority. So, a necessary condition for having a student i matched to a school s at any stable matching, for any students' preference profile, is that all the students with higher priority than i at s are matched to a school. 7 If some of these students are matched to other schools, we have to repeat the procedure. That is, for each student matched to a school we have to match all the students with a higher priority at that school. Matching those additional students may in turn bring additional students to our problem, and so on and so forth. Student i will be an impossible match for school s when, for any possible way we match the other students, there is always at least one student in excess, that is, a student that we must match (because at some school he has higher priority than the student matched to that school), but all his acceptable schools have filled their capacities with other students.

In other words, the impossibility to match a student to a school will arise when there is a set of students "with sufficiently high priority" that outnumber the total capacities of the schools acceptable to them. This condition is reminiscent of one of the very first results of matching theory, namely [START_REF] Hall | On Representatives of Subsets[END_REF] marriage theorem, which provides a necessary and sufficient condition for the existence of a matching (without preferences), which selects a distinct individual from each of a collection of finite sets. Hall's condition is not sufficient for our purposes, however, as it provides no link to stability. Part of our contribution consists precisely of carefully selecting the set of individuals for which we have to check

Hall's condition (Theorem 2).8 As a by-product, our results establish a formal connection between stability and Hall's marriage condition. In very rough terms, our characterization is as follows. A pair student-school (i, s) is an impossible match if, and only if, there is a set of students that can exhaust all the seats of the schools acceptable to them, including school s (i.e., a set of students for which Hall's condition holds), but if we want to match i to s then Hall's condition does not hold anymore for that set of students.9

In the second part of the paper we show how we can apply our results to address two different issues in matching theory, which both deal with the Student Optimal Stable Mechanism (SOSM). This mechanism consists first of asking students to reveal their preferences over schools, and then running [START_REF] Gale | College Admissions and the Stability of Marriage[END_REF] Deferred Acceptance algorithm with students proposing. SOSM's appeal comes mainly from the fact that for each student it is a dominant strategy to submit his true preferences and its outcome is not only a stable matching but it is also the student-optimal stable matching, i.e., student's most preferred stable matching.

The first issue we focus on deals with the distributional aspects of SOSM. This is an important question because many school districts tend to care about maintaining certain levels of social or racial diversity among schools. Except for trivial or unrealistic cases, it is however notoriously difficult to make precise distributional predictions based solely on schools' priority lists. Accordingly, most of the literature on matching has focused on proposing new algorithms or more complex priority structures that would implement the distributional constraints set by policy makers. 10 Using our characterization of impossible matches we show how mild assumptions on students' preferences can shed light on the distributional aspects of SOSM. For the sake of simplicity, we focus on the problem of zone priority (giving, for each school, a high priority to the students who live close to the school), but our approach is not limited to this case and can be applied to other settings.

The second issue we want to address deals with the efficiency of SOSM (or rather the lack thereof). 11 The matching literature has studied to what extent we can improve upon SOSM while maintaining as much as possible the non-manipulation and stability properties. 12 Building on our characterization of impossible matches, we propose a new mechanism that can alleviate the lack of efficiency of SOSM. In line with previous results (e.g., Kesten

(2010)), our mechanism turns out not to be strategy-proof, but we show that it is nevertheless a dominant strategy for all students to truthfully rank all schools that are declared as acceptable. 13

10 See [START_REF] Dur | The Demise of Walk Zones in Boston: Priorities vs. Precedence in School Choice[END_REF], [START_REF] Ehlers | School Choice with Controlled Choice Constraints: Hard Bounds versus Soft Bounds[END_REF], [START_REF] Fragiadakis | Market Design under Distributional Constraints: Diversity in School Choice and Other Applications[END_REF]Troyan (2013), Halafir et al. (2013), [START_REF] Kamada | Efficient Matching Under Distributional Concerns: Theory and Application[END_REF], [START_REF] Kojima | School Choice: Impossibilities for Affirmative Action[END_REF], [START_REF] Kominers | Designing for Diversity: Matching with Slot-Specific Priorities[END_REF].

11 See [START_REF] Ergin | Efficient Resource Allocation on the Basis of Priorities[END_REF].

12 Another source of inefficiency may come from the fact that schools may have weak priority orderingssee Erdil and Ergin (2006) or [START_REF] Abdulkadiroglu | Strategyproofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match[END_REF]. We restrict ourselves in this paper to the case of strict preferences.

13 [START_REF] Kesten | School Choice with Consent[END_REF] showed that there is no mechanism that is strategy-proof, Pareto efficient and that selects the student-optimal matching whenever it is efficient.

The existence of impossible matches is strongly related to the fact that students do find some schools unacceptable. If there are enough schools to accommodate all students and students find all schools acceptable then no student is an impossible match for any school. 14 So, although we do not state it explicitly, our results are of particular relevance when students' sets of acceptable schools are small compared to the size of the market, which is a salient feature of most (if not all) real-life matching markets. 15 However, as our model of zoning policy in school choice illustrates, the concept of impossible matches can also have a bite when students find all schools acceptable.

From a broader perspective, this paper addresses the question of extracting information from partial matching data. One of the earliest results in that direction is the so-called Rural Hospital Theorem in the context of matching interns to hospitals [START_REF] Roth | On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets[END_REF]. This theorem states that if a hospital does not fill its capacity at some stable matching, then it is matched to the same set of interns at any stable matching. 16 From the observation of one stable matching we can thus extract some information about all stable matchings. Echenique, Lee and Shum (2013) go one step further and show for aggregate matchings how the observation of stable matchings can be used to estimate agents' preferences. 17 Behind these results is the idea to extract information on preferences or (stable) matchings from the observation of some matchings. Our contribution takes the opposite approach, as we aim at deducing information 14 Take any student i and any school s, and construct a matching where i is assigned to s and all other students are assigned to some school. The resulting matching will be stable for the students' preference profile where each student is matched to his most preferred school.

15 There are various explanation for this stylized fact. For instance, some matching markets involve a large number of participants, making it virtually impossible to expect complete preference lists by all participants.

Also, some matching institutions may constrain agents with respect to the length of their preference lists (e.g., school choice in New York City, university admission in Spain). See [START_REF] Kojima | Matching with Couples: Stability and Incentives in Large Markets[END_REF] for a discussion for the medical match. Abdulkadiroglu, Pathak and Roth (2005), [START_REF] Haeringer | Constrained School Choice[END_REF], [START_REF] Calsamiglia | Constrained School Choice: An Experimental Study[END_REF], [START_REF] Pathak | School Admissions Reform in Chicago and England: Comparing Mechanisms by their Vulnerability to Manipulation[END_REF] or Bodoh-Creed (2013) constitute additional accounts on the length of submitted preference lists in centralized matching markets. 16 The original Rural Hospital Theorem is stated for a many-to-one matching problem where hospitals have responsive preferences. Another celebrated result is that in marriage problems, the set of agents matched at a stable matching is the same for all stable matchings [START_REF] Roth | The Evolution of the Labor Market for Medical Interns and Resident: A Case Study in Game Theory[END_REF] and [START_REF] Gale | Some Remarks on the Stable Matching Problem[END_REF]). 17 See also [START_REF] Echenique | The Revealed Preference Theory of Stable and Extremal Stable Matchings[END_REF]. Agarwal (2013) presents an estimation of preferences in the medical matched based upon the observation of the matching. Another result reminiscent of the Rural Hospital Theorem is [START_REF] Roth | The College Admission Revisited[END_REF], who show how the observation of different stable matchings for a College Admission problem gives some information about colleges' preferences over group of students.

on (un)stable matchings from the partial observation of preferences. A recent example of this approach is [START_REF] Martínez | On the Invariance of the Set of Core Matchings with Respect to Preference Profiles[END_REF] who, starting from a profile of incomplete preferences, identify all the possible completions thereof that give the same set of stable matchings. The two closest papers to ours are [START_REF] Rastegeri | Two-sided Matching with Partial Information[END_REF], and [START_REF] Saban | The Complexity of Computing the Random Priority Allocation Matrix[END_REF].

Rastegeri and her coauthors consider a one-to-one matching market where agents from both sides do not know their preferences and must conduct interviews to uncover them. They

show that as preferences become more complete, some potential interviews may be discarded because the parties involved in such interviews can never be matched at any stable matching, for any possible completion of preferences. Unlike the other works we have just cited, Saban and Sethuraman focus on efficient assignments. They consider random serial dictatorship, and address a question similar to ours, i.e., upon observing agent's preferences for objects they aim at knowing whether there exists an ordering of agents such that an agent will get a specific object.

The paper is structured as follows. In Section 2 we outline the basic model we shall work with. Section 3 contains the first main contribution of this paper, i.e., the characterization of impossible matches. In Section 4 we analyze the impact of zone priorities in a simple school choice model. In Section 5 we propose a new mechanism that improves upon the Student-Optimal Stable Mechanism and study some of its properties. Most of the proofs are relegated to the Appendix.

Preliminaries

Matchings

We consider throughout this paper a (finite) set I of students and a (finite) set S of schools, where each school s is endowed with a positive capacity q s . The problem studied here is that of matching students to schools in the limit of their capacities. A matching is a mapping µ : I ∪ S → 2 I ∪ S such that, for each i ∈ I and each s ∈ S,

• µ(i) ∈ S ∪ {i}, • µ(s) ∈ 2 I ,
• µ(i) = s if, and only if, i ∈ µ(s), and

• |µ(s)| ≤ q s .
For v ∈ S ∪ I, we call µ(v) agent v's assignment. For i ∈ I, if µ(i) = s ∈ S then student i is matched to school s under µ. If µ(i) = i then student i is said to be unmatched under µ.

School choice problem

A school choice problem is given by a 5-tuple (I, S, (≻ s , q s ) s∈S , (≻ i ) i∈I ), where I is a set of students, S a set of schools, ≻ s a priority ordering for school s, q s a capacity constraint for school s, and ≻ i a preference ordering for student i.

Each school s ∈ S is endowed with a fixed capacity of seats q s and a strict priority ordering over the students, i.e., ≻ s is a linear ordering over I. We say that student i has higher priority (or is ranked higher) than student j at school s if i ≻ s j. Without loss of generality, we assume that q s > 0 for each school in s.

Each student i ∈ I has a strict preference relation ≻ i over the schools and the option of remaining unassigned, i.e., ≻ i is a linear ordering over S ∪ {i}, where i denotes his outside option (e.g., going to a private school). The notation s ≻ i s ′ means that student i prefers to go to school s than school s ′ . A school s is acceptable for a student i under the preferences ≻ i if i prefers to be matched to s than being matched to himself, i.e., s ≻ i i.

When there is no risk of confusion we shall simply use ≻ to denote a school choice problem.

Given a preference relation ≻ i we denote by i the weak relation associated to it, i.e.,

v i v ′ ⇔ v ≻ i v ′ or v = v ′ .
For a set I ′ ⊆ I, we denote by ≻ I ′ the profile (≻ i ) i∈I ′ . Given a school choice problem ≻ we denote by A ≻ i the set of schools that are acceptable to i, and for a set I ′ of students A ≻ I ′ denotes the set of all schools that are acceptable to students in I ′ , i.e., A ≻ I ′ = ∪ i∈I ′ A ≻ i .18 If a school s / ∈ A ≻ i then s is unacceptable for i. Students' preferences over schools can be straightforwardly extended to preferences over matchings. We say that student i prefers the matching µ to the matching µ ′ if he prefers his assignment under µ to his assignment under µ ′ . Formally (and abusing notation), µ ≻ i µ ′ if, and only if, µ(i) ≻ i µ ′ (i), and µ i µ ′ if, and only if, ¬ (µ ′ ≻ i µ).

A matching is stable if, for each student, all the schools he prefers to his assignment have exhausted their capacities with students that have higher priority, and he is matched to an acceptable school. Formally, a matching µ is stable for a school choice problem ≻ if (a) it is individually rational, i.e., for all i ∈ I, µ(i) i i, (b) it is non wasteful [START_REF] Balinski | A Tale of Two Mechanisms: Student Placement[END_REF], i.e., for all i ∈ I and all s ∈ S, s ≻ i µ(i) implies |µ(s)| = q s , and (c) there is no justified envy, i.e., for all i, j ∈ I with µ(j) = s ∈ S, s ≻ i µ(i) implies j ≻ s i.

Given a school choice problem ≻, we denote the set of stable matchings by Σ(≻). For a matching µ, the pair (i, s) is a blocking pair (or that i and s block the matching µ) if either i prefers s to his assignment and |µ(s)| < q s , or student i has justified-envy against a student j and a school s (i.e., µ(j) = s, i ≻ s j, and s ≻ i µ(i)).

We follow the traditional approach here by restricting welfare analysis to the students. 19A matching µ ′ Pareto dominates a matching µ if all students prefer µ ′ to µ and there is at least one student that strictly prefers µ ′ to µ. Formally, µ ′ Pareto dominates µ if µ ′ i µ for all i ∈ I, and µ ′ ≻ i ′ µ for some i ′ ∈ I. A matching is Pareto efficient if it is not Pareto dominated by any other matching.

Pre-matching problems

A pre-matching problem is similar to a school choice problem except that for students it only specifies the schools that are acceptable to them, and schools' priorities are restricted to the set of students that view them as acceptable. Formally, a pre-matching problem is given by a 5-tuple (I, S, (P s , q s ) s∈S , (A P i ) i∈I ), where I is a set of students, S a set of schools, P s a priority of school s, q s a capacity of school s and A P i ⊆ S a set of acceptable schools for student i. In a pre-matching problem, the priority ordering of school s, P s , is a linear ordering over A P s , which is the subset of students considering s as acceptable, i.e. A P s := {i ∈ I : s ∈ A P i }.20 For a set I ′ of students, A P I ′ denotes the set of all schools that are acceptable to students in I ′ . For a set S ′ of schools, A P S ′ denotes the set of all students that are acceptable to schools in S ′ . Whenever there is no risk of confusion we shall use the shorthand P to denote a prematching problem.

The concept of stability, as defined for school choice problems, is not adapted to prematching problems, because student's preferences are not completely defined. Stability has a bite, however, whenever a student is matched to an unacceptable school or when a student is unmatched and an acceptable school has an empty seat or is matched to a student with a lower priority. We summarize these two situations with the following concepts.

• A matching µ is feasible for P if for each i ∈ I, µ(i) = i implies µ(i) ∈ A P i .

• A matching µ is comprehensive for P = (I ′ , S ′ , (P s , q s ) s∈S ′ , (

A P i ) i∈I ′ ) if for each i ∈ I ′ , µ(i) = i implies µ(i) ∈ A P i , and for each school s ∈ S ′ , if µ(i) = s for some i ∈ I ′ , jP s i implies µ(j) ∈ S.
We shall sometimes consider comprehensiveness among a subset of students only. In this case we say that a matching µ is comprehensive for P among students in

I ′ ⊆ I if it is feasible and if for each school s ∈ S, if µ(i) = s for some i ∈ I ′ , jP s i and j ∈ I ′ implies µ(j) ∈ S.
Remark 1 Comprehensiveness shares some similarities with the concept of stability in a school choice problem. The feasibility constraint is akin to individual rationality. The second condition for comprehensiveness is simply a condition on the absence of blocking pairs, but for unmatched students only. We can thus intuit that if a matching is not comprehensive for a pre-matching problem it cannot be stable for any compatible school choice problem.

The reader will notice, however, that a concept related to non-wastefulness is missing in the definition of comprehensiveness. This is deliberate because such a requirement will not be needed for our purposes. 21,22 Given a pre-matching problem P , a school choice problem ≻ with the same sets of students and schools and identical schools' capacities is P -compatible if 21 Our main objective is to characterize to which schools a student can be matched at a stable matching.

If there is a matching µ such that a student, say, i, is matched to a school, say s, and µ satisfies individual rationality and there is no justified envy but µ is wasteful, then it is easy to construct a stable matching µ ′ such that µ ′ (i) = s by filling schools' capacities with unmatched students (starting with those with the highest priority).

22 Comprehensiveness in a pre-matching problem P is in fact equivalent to individual rationality and the absence of justified envy in the school choice problem where each student is indifferent among all his acceptable schools.

(a) for each student i, A ≻ i = A P i (b) for each school s, and each pair of students i, i ′ ∈ A P s , i ≻ s i ′ if, and only if, iP s i ′ .

Note that the same pre-matching problem can generate different school choice problems (and thus generate different sets of stable matchings). We denote by Θ(P ) the set of school choice problems that are P -compatible.

Finally, notice that when representing a pre-matching problem (I, S, (P s , q s ) s∈S , (A P i ) i∈I ) it is sufficient to describe only the profile of schools' priorities (and their capacities), since by construction i ∈ A P s if, and only if, s ∈ A P i . That is, all the relevant information can be summarized on one side of the market (here the schools).

Impossible matches

The purpose of this section is to define and characterize the students that are impossible matches for some specific school in a given pre-matching problem. The question addressed by the concept of impossible match is the following: upon observing one side of the markets' preferences/priorities (i.e. a pre-matching problem), is there a stable matching with respect to some realization of the other side's preferences such that a particular student is matched to a particular school at a stable matching? If the answer is "no" then that student is said to be an impossible match for that school.

Definition 1 Given a pre-matching problem P , a student i is an impossible match for school s ∈ A P i if, for each school choice problem ≻∈ Θ(P ), there is no matching µ ∈ Σ(≻) such that µ(i) = s.

Introductory elements

To understand how the preferences of only one side of the market can suffice to check the stability of a matching consider the following instances of school choice problems.

Example 1 The simplest case occurs if q s students with higher priority than i at school s admit no other acceptable school. Then for any school choice problem ≻∈ Θ(P ) and stable matching µ ∈ Σ(≻) either all those students are matched to s, or at least one of them is not matched to any school. 23 In either case, i cannot be matched to s at a stable matching, for otherwise one of the students with a higher priority than i would form a blocking pair with school s.

Example 2 A (slightly) more complex case is the following. For simplicity we assume that each school has only one seat to offer. Let i 1 , i 2 , i 3 and i 4 be students whose sets of acceptable schools are {s 1 , s 2 }, {s 2 , s 3 }, {s 3 , s 4 }, and {s 2 , s 4 }, respectively. Table 1 describes the schools' priority orderings over these four students. For instance, at school s 2 student i 2 has a higher priority than student i 1 , who has higher priority than student i 4 .

P s 1 P s 2 P s 3 P s 4 i 1 i 2 i 3 i 4 i 1 i 2 i 3 i 4 Table 1: Student i 1 is an impossible match for school s 2 .
We claim that for any preference profile of the students that does not affect the set of acceptable schools (e.g., s 2 and s 3 are always acceptable for student i 2 ), it is impossible to obtain a stable matching where i 1 is matched to s 2 . To see this, note that if this is the case then i 2 must be matched to s 3 , for otherwise (i 2 , s 2 ) would form a blocking pair. This in turn implies that i 3 is matched to s 4 , which is only possible if i 4 is matched to s 2 , a contradiction.

So, there is no preference profile (that does leave unchanged the set of acceptable schools for each student) and a stable matching for that preference profile where i 1 is matched to s 2 .

Without entering into much details, it is important to note that in the previous example the key property of schools s 2 , s 3 and s 4 's priorities to ensure that i 1 is an impossible match for school s 2 is not, as it may appear, that there is some sort of cycle with the relative positions of students i 2 , i 3 and i 4 . As we shall see, i 1 being an impossible match for s 1 is rather due to the more general feature that there are (at least) 3 students competing for 23 There could be more than q s students with higher priority than i at s and a P -compatible school choice problem such that some of these students have school s being their most preferred school.

three schools and such that their relative rankings in the priorities of the schools allow them to claim the seats against i 1 .24

Finally, note that to establish that student i 1 is an impossible match for school s 1 only students i 2 , i 3 and i 4 were needed. That is, if there were other students who also find one of those schools acceptable student i 1 would remain an impossible match for s 2 . For instance, we could have a student, say, i 5 with a higher priority than i 3 at school s 3 , or a student, say, i 6 , ranked between i 4 and i 3 at school s 4 , without altering our conclusion about student i 1 .

Given a pre-matching problem P , for any P -compatible matching problem ≻ and any matching µ ∈ Σ(≻), µ is also comprehensive for the pre-matching problem P . However, the reverse may not be true. Hence, given a pre-matching problem P , if a student can be matched to a school at a stable matching for some P -compatible problem ≻ then he can be matched to that school at a matching comprehensive for P . Similarly, if there is no P -compatible problem for which a student i is matched to a school s at a stable matching (i.e., i is an impossible match for s), then there is no comprehensive matching for P where i is matched to s.

Proposition 1 A student is an impossible match for a school in a pre-matching problem P if, and only if, there is no comprehensive matching for P such that they are matched together.

Proof Let P be a pre-matching problem and suppose that student i is not an impossible match for s. So, there exists ≻∈ Θ(P ) and µ ∈ Σ(≻) such that µ(i) = s. Clearly, µ is a feasible matching for P , and since µ satisfies no justified envy, it is also comprehensive for P , the desired result.

Conversely, let µ be a comprehensive matching in P such that µ(i) = s. Consider the schools that do not exhaust their capacities under µ and fill these schools taken in any particular order with the best ranked and unmatched remaining students (if any). The resulting matching, that we call µ ′ , still satisfies comprehensiveness in P . Let (≻ j ) j∈I be the preference profile such that for each j ∈ I with µ ′ (j) = j school µ ′ (j) is the most preferred school under ≻ j and such that ≻∈ Θ(P ). By construction, µ ′ satisfies individual rationality and no wastefulness in the school choice problem ≻∈ Θ(P ). Under µ ′ , each j ∈ I with µ ′ (j) = j gets his top choice, hence envy originates only from students j ∈ I such that µ ′ (j) = j. But since µ ′ is comprehensive in P these students are ranked below the least ranked students matched to schools according to schools' priorities, hence no blocking pair can be formed. The matching µ ′ is thus stable in the school choice problem ≻∈ Θ(P ) and µ ′ (i) = s. Therefore i is not an impossible match for s.

In the next two propositions we first establish a Rural-Hospital type of result when some students are impossible matches for some schools. We next show that the impossible match property is not monotonic with respect to the priorities of the school.

Proposition 2 If a school admits an impossible match then it fills capacity at any stable matching, for any compatible school choice problem.

Proof Let P be a pre-matching problem and suppose that student i is an impossible match for school s. Suppose that for some P -compatible school choice problem ≻, there exists a matching µ ∈ Σ(≻) such that |µ(s)| < q s . Since µ satisfies non wastefulness, µ(j) = j for every j ∈ A ≻ s . Consider then the school choice problem ≻ ′ ∈ Θ(P ) such that for each student j = i matched to a school under µ, µ(j) is the most preferred school under ≻ ′ j and school s is student i's most preferred school under ≻ ′ i . Let µ ′ be the matching such that µ ′ (j) = µ(j) for each j = i, and µ ′ (i) = s. In addition, if there exists a student acceptable for µ(i) who is unmatched under µ, match under µ ′ the highest priority student among those unmatched students. Since |µ(s)| < q s the matching µ ′ is feasible. It is easy to check that, since µ ∈ Σ(≻), µ ′ satisfies individual rationality, no justified envy and non-wastefulness.

Finally, observe that ≻ ′ ∈ Θ(P ), so i is not an impossible match for s, a contradiction.

Proposition 3 If a student is an impossible match for a school, students with lower priority at that school are not necessarily impossible matches for that school.

Proof Consider again the pre-matching problem P given in Table 1. It is easy to check that student i 1 is also an impossible match for s 2 , yet student i 4 is not an impossible match for s 2 . Indeed, let ≻∈ Θ(P ) be such that i 1 's most preferred school is s 1 , s 2 is the most preferred school of i 4 , s 3 is the most preferred school of i 2 , and s 4 is the most preferred school of i 3 . The matching µ such that µ(s

1 ) = i 1 , µ(s 2 ) = i 4 , µ(s 3 ) = i 2 , µ(s 4 ) = i 3 is stable for ≻.

A characterization

Part of our contribution consists of showing that we do not need to consider all students and all possible profiles of students' preferences (and compute all the corresponding stable matchings) to check whether a student is an impossible match for a school. Instead we are able to characterize impossible matches on the basis of the fundamentals of the pre-matching problem only. Proposition 1 provides a first baseline for the analysis of impossible matches, at the cost of extreme computations: checking whether a student i is an impossible match for a school s amounts to list every comprehensive matching of the pre-matching problem P to see whether one of those assigns i to s. In what follows, we will narrow down the set of cases one has to consider, showing that it is sufficient to find a particular subset of students, called a block. In addition, an interesting feature of the result is that it relies on one of the earliest results of matching theory, which we rephrase to fit our setting.

Theorem 1 (Hall's Marriage Theorem, 1935) Given a pre-matching problem P and a set of student Î, there exists a feasible matching where all students are matched to some school if, and only if,

for each I ′ ⊆ Î, |I ′ | ≤ s∈A P I ′ q s . (1)
In words, there exists a matching where all students can be matched to some school if, and only if, for each subset I ′ of students the number of students is at most equal to the total number of (admissible) seats among the schools that consider some of the students in I ′ as acceptable. Eq. ( 1) is known as Hall's marriage condition. 25To incorporate the no-justified envy condition, or its counterpart in the pre-matching framework (comprehensiveness), we shall not apply Hall's marriage condition to the original pre-matching problem but rather to a collection of restricted and truncated pre-matching problems.

In order to characterize impossible matches in terms of Hall's algebraic marriage condition it will be useful to consider particular transforms of school's priority profiles of a pre-matching problem. Given a pre-matching problem P = (I, S, (P s , q s ) s∈S , (A P i ) i∈I ) and two sets of students J and K, with K possibly empty, the pre-matching problem restricted to J and truncated at K is denoted by P (J, K). In that pre-matching problem the set of acceptable students for any school s is

A P (J,K) s = {i ∈ J ∩ A P s : iP s i ′ for each i ′ ∈ K} (2)
and the priority of school s, P s (J, K), is the ordering over A P (J,K) s

that coincides with P s on

A P (J,K) s
. The set of acceptable schools for any student i is

A P (J,K) i = {s ∈ S : i ∈ A P (J,K) s }. (3)
Remark 2 When we consider the pre-matching problem restricted to J and truncated at K the set of "available" students and schools may not be equal to J\K and A P (J,K) J\K , respectively. Indeed, it may well be that there is a student i ∈ J\K such that there is no school s for which i ∈ A P (J,K) s . Similarly, for some school s we may have A P (J,K) s = ∅. For a truncated pre-matching problem P (J, K) we say that a student i is

admissible if i ∈ ∪ s∈S A P (J,K) s . Similarly, a school is admissible if A P (J,K) s = ∅. 26
Given a pre-matching problem P , we say that Hall's marriage condition holds if Eq. ( 1) holds when Î is the set of all admissible students in P .

For a pre-matching problem P , s ∈ S, i ∈ A P s and J ⊆ I \ {i}, we denote by P s the same problem as P except that one seat of s is removed, i.e. school s's capacity is q s -1, and we denote by J i,s ⊆ J the set of students in J that have a higher priority than i by s, i.e., J i,s = {j ∈ J : iP s i}. 27 Definition 2 Given a pre-matching problem P = (I, S, (P s , q s ) s∈S , (A P i ) i∈I ), a block at (i, s) with i ∈ A P s is a set J ⊆ I\{i} such that:

1. For some J ′ ⊆ J, |J ′ | = ŝ∈A P J q ŝ and Hall's marriage condition holds in P (J ′ , ∅);

2. For each K ⊆ J \ J i,s such that |K| = |J| -ŝ∈A P J q ŝ + 1, Hall's marriage condition
does not hold in P s (J, K).

26 Note that the pre-matching problem P (J, ∅) is simply the problem P restricted to the set of students J and P (I, K) is the problem P truncated at K. 27 Note that admissibility in a pre-matching problem refers to the notion of being acceptable for a school and is independent of the schools' capacities. For instance, if for some school s we have q s = 1, in P s (J, K)

all students in A P (J,K) s remain acceptable for s, even though the capacity of school s is zero in P s (J, K).

We state now the main result of the paper.

Theorem 2 A student i is an impossible match for a school s in a pre-matching problem P if, and only if, P admits a block at (i, s).

The result provides additional insights on impossible matches. First, note that requiring that Hall's condition holds in P (J ′ , ∅) for some J ′ such that of |J ′ | = ŝ∈A P J q ŝ is tantamount to say that there exists a perfect match between the schools A J and the students J ′ , i.e., there exists a matching where all students J ′ are matched to a school and all schools exhaust their capacities with students in J ′ . Second, Condition 2 implies in particular that the ability to obtain a perfect match is tight in the following sense: If we consider the problem P s (the problem identical to P except that one seat is removed from s), then there is no perfect match between the schools A J and any subset J ′ ⊆ J that includes all the students in J i,s , such that the matching is comprehensive among students J. 28

The next examples show that the requirements of Definition 2 are all independent from each other.

Example 3 Let I = {i 0 , i 1 , i 2 , i 3 } and S = {s 0 , s 1 , s 2 , s 3 , s 4 }, and assume that for each school s ∈ S, q s = 1. The schools' priorities are described in Table 2.

P s 0 P s 1 P s 2 P s 3 P s 4 i 1 i 2 i 3 i 2 i 3 i 0 i 3 i 2 i 3 i 2 i 1 i 1 Table 2: Condition 1 not satisfied -too few students
The matching µ such that µ(i 0 ) = s 0 , µ(i h ) = s h for h = 1, 2, 3 is comprehensive, so from Proposition 1 student i 0 is not an impossible match for school s 0 . In this example condition 1 of the definition of a block is not satisfied, because for any set J ⊆ I\{i 0 } it holds that |J| < s∈A J q s . In this case, condition 2 has clearly no bite, as there cannot be a set K ⊆ J\J i 0 ,s 0 that satisfies the cardinality requirement of condition 2.

28 An alternative characterization of impossible matches can be also established. It relies on a slightly different balance between condition 1 (weaker) and condition 2 (stronger). We omit that result since the one provided here is the most appropriate from an operational point of view.

Example 4 Let I = {i 0 , i 1 , . . . , i 8 }, S = {s 0 , s 1 , . . . , s 4 }, and assume that q s = 1 for each s = s 4 , and q s 4 = 3. The schools' priorities are described in Table 3.

P s 0 P s 1 P s 2 P s 3 P s 4 i 1 i 2 i 3 i 3 i 5 i 0 i 1 i 2 i 4 i 6 i 7 i 8
Table 3: Condition 1 not satisfied -no perfect match Student i 0 is not an impossible match for school s 0 : the matching µ such that µ(i 0 ) = s 0 ,

µ(i 1 ) = s 1 , µ(i 2 ) = s 2 , µ(i 3 ) = s 3 is comprehensive.
Consider the set J = {i 1 , . . . , i 8 }. So, |J| = 8 > s∈A J q s = 7. Unlike Example 3, condition 2 of the definition of a block has a bite. For this set J, however, condition 1 is not satisfied because there cannot be a perfect match between any set J ′ ⊆ J and the schools in A J (because for any matching school s 4 does not fill its capacity). We claim that condition 2 of the definition is satisfied for this set J. To begin with, note that we need to consider all sets K ⊆ J\{i 1 } such that |K| = |J|s q s + 1 = 2.

If i 2 ∈ K, then for any other student we may add, Hall's marriage condition does not hold in P s 0 (J, K) because we cannot match i 1 . If i 3 ∈ K, then again Hall's marriage condition does not hold in P s 0 (J, K), for any other student in K: either i 1 or i 2 must remain unmatched (if K = {i 2 , i 3 } then we cannot match i 1 ).

It remains then to consider all sets K ⊂ {i 4 , i 5 , . . . , i 8 } such that |K| = 2. Routine examination shows that for any such set K, we cannot match all admissible students in P s 0 (J, K), which proves the claim.

Example 5 By restricting the previous example to students I = {i 0 , i 1 , i 2 , i 3 , i 4 } and to their acceptable schools, student i 0 is still not impossible for s 0 (see Table 4). It is an instance where the only possible set J satisfying condition 1 is {i 1 , i 2 , i 3 , i 4 }. We consider K = {i 4 } to see that condition 2 does not hold. All admissible students in P s 0 (J, {i 4 }) can be matched to schools at the matching µ such that µ(i 1 ) = s 1 , µ(i 2 ) = s 2 , µ(i 3 ) = s 3 . That is, Hall marriage condition is satisfied in P s 0 (J, {i 4 }).

P s 0 P s 1 P s 2 P s 3 i 1 i 2 i 3 i 3 i 0 i 1 i 2 i 4 Table 4: Condition 2 not satisfied
The next proposition establishes several properties of a block. First, we show that if conditions 1 and 2 hold, then condition 2 also holds when we consider all possible sets K ⊆ J\J i,s . This stronger statement of the block condition will be used to deduce the second and third properties of Proposition 4. If there are less than q s students with a higher priority then i cannot be an impossible match. So, a necessary condition for i to be an impossible match is that there are q s or more such students. The second statement of Proposition 4 states that this property is implied by the existence of a block at (i, s), but also that at least q s such students must be part of the block. Finally, we can strengthen slightly the sufficient condition given in Theorem 2. We show that in the presence of a block, whenever student i is matched to s it must be that one of the student j from the block must remain unmatched, and have a higher priority than a student matched at one of the schools acceptable for j.

Proposition 4 Every block J at (i, s) satisfies the following properties:

1. For each nonempty K ⊆ J \ J i,s , Hall's marriage condition does not hold in P s (J, K).

2. There are at least q s students in J with higher priority than i at school s, i.e., |J i,s | ≥ q s .

3. If µ is a feasible matching such that µ(i) = s then there exist k ∈ J and j ∈ J ∪ {i} such that kP µ(j) j and µ(k) = k.

To illustrate further the potential structure of a block one may consider a particular case of Definition 2 where the number of students in J is equal to the total number of seats in the acceptable schools. In that case, conditions 1 and 2 specialize respectively into a perfect match between J and A J , and Hall's marriage conditions with singleton sets K.

Definition 3 Given a pre-matching problem P = (I, S, (P s , q s ) s∈S , (A P i ) i∈I ), an exact block at (i, s) with i ∈ A P s is a set J ⊆ I\{i} such that:

1. |J| = ŝ∈A P J q ŝ and Hall's marriage condition holds in P (J, ∅);

2. For each k ∈ J \ J i,s Hall's marriage condition does not hold in P s (J, {k}).

The above tractable conditions are sufficient for the existence of impossible matches.

In the next section, we will show that those conditions are also necessary under a mild restriction on the pre-matching problem.

The following result is deduced from Theorem 2.

Corollary 1 If P admits an exact block at (i, s) then i is an impossible match for s.

The next two examples illustrate the interplay between conditions 1 and 2 (for blocks or exact blocks) in order to get impossible matches.

Example 6 Let s 0 and s 1 be two schools and i 0 , i 1 and i 2 three students. Consider the problem P depicted in Table 5, where A i 1 = {s 0 , s 1 }, A i 2 = {s 1 }, q s 0 = q s 1 = 1.

P s 0 P s 1 i 1 i 2 i 0 i 1
Table 5: Impossible match and exact block Clearly, i 0 is an impossible match for s 0 , and it is easy to see that J = {i 1 , i 2 } is an exact block at (i 0 , s 0 ). Condition 1 holds trivially. As for condition 2, K = {i 2 } is the only set K for which we have to consider condition 2. So we only have to check whether we can match i 1 in P s 0 (J, {i 2 }). This is impossible since no school is admissible. So J is a block.

An exact block J does not always exist. A counter-example, where an impossible match does not admit any exact block, is the following.

Example 7 Consider four schools, s 0 , s 1 , s 2 and s 3 , with one seat at each school, and six students i h , h = 0, . . . , 5. The problem P is depicted in Table 6. It is easy to see that student i 0 is an impossible match for s 0 .

i 1 i 2 i 2 i 3 i 0 i 3 i 4 i 4 i 5 i 1 i 5 i 1
Table 6: Impossible match and no exact block

To begin with, notice that any block must contain at least 4 students, for otherwise condition 1 cannot be satisfied. 29 The set J 1 = {i 1 , i 2 , i 3 , i 4 } satisfies condition 1, but not condition 2. To see this, consider the matching µ (feasible for P s 0 ) defined as µ(i 1 ) = s 1 , µ(i 2 ) = s 2 and µ(i 3 ) = s 3 . Student i 4 has lower priority than the matched students for all his acceptable schools. So, condition 2 is not satisfied for the block J 1 , since Hall's condition is satisfied in P s 0 (J 1 , {i 4 }).

A similar reasoning applies for the sets

J 2 = {i 1 , i 2 , i 3 , i 5 }, J 3 = {i 1 , i 2 , i 4 , i 5 }, and J 4 = {i 1 , i 3 , i 4 , i 5 }.
That is, there is no block J at (i 0 , s 0 ) such that |J| = 4, while the reader can check that J = {i 1 , i 2 , i 3 , i 4 , i 5 } is the (unique) block at (i 0 , s 0 ).

Identifying impossible matches

According to Proposition 1 we would have to consider all possible comprehensive matchings to check whether a student is an impossible match for a school. Theorem 2 greatly simplifies this task, for we only have to consider all the sets K ⊆ J of a particular size. The set J turns out to be easy to construct; the proof of the necessity part of Theorem 2 suggests a procedure to identify impossible matches, which we now detail.

Let P be a pre-matching problem and let i ∈ A P s .

Algorithm: Impossible Matches Algorithm 1. Delete student i from the priority of all schools but school s, without changing the relative ranking of the other students.

2. Construct a maximum and comprehensive matching µ.30 3. If µ(i) = s then i is not an impossible match for s. Otherwise go to step 4.

Constructing the set J:

4.1 Let J 0 be the set of all students matched to a school, and S 0 all the schools that do not fill their capacity at µ. If S 0 is empty then go to Step 5. Otherwise iterate through h until obtaining an empty set S h : 4.2 Define J h as the set J h-1 without all the students that are acceptable for a school in

S h-1 , J h = {j ∈ J h-1 : j / ∈ A P S h-1 } ,
and let S h be the set of schools that do not fill their capacities with students in J h ,

S h = {ŝ : |µ(ŝ) ∩ J h | < q ŝ} .
Set h := h + 1 and repeat step 4.2 until S ℓ = ∅ for some h = ℓ. Let J = J ℓ .

If s /

∈ AJ then i is not an impossible match for s. Otherwise check condition 2 of Definition 2 at J:

5.1 Let K be the set of unmatched students at µ (except i) that are acceptable for a school in AJ. Let J = J ∪ K.

5.2 For each K ⊆ J\J i,s such that |K| = |J| -ŝ∈A P J q ŝ + 1, find a maximum matching in the problem P s (J, K). If there is no set K such that all admissible students of P s (J, K) are matched to a school then i is an impossible match for s. Otherwise i is not an impossible match.

We show in the proof of Theorem 2 that the set J constructed in Step 5.1 satisfies conditions 1 and 2 of the definition of an exact block, and Step 5.2 consists of checking condition 3. If there is a set K satisfying the conditions set in Step 5.2 and a matching µ such that all admissible students in P s (J, K) can be matched to a school then i is not an impossible match for s. This is so because µ is comprehensive for P among the students in J. By construction no student better ranked than i at s is in K, so these students are all matched. Also, in the problem P s (J, K) the capacity of s is q s -1, so it then suffices to match i to s to have a comprehensive matching for P , the original pre-matching problem.

On the other hand, if no such set K can be found then Hall's condition is not satisfied for any set K, which simply establishes that the second condition of a block holds.

Note that the set J ′ constructed in Step 3 is clearly easy to obtain, so the complexity of our algorithm is determined by Step 5.2. This is where the added value of Theorem 2 comes, for we only have to truncate by taking sets K that have the size specified in condition 2, a clear improvement compared to Proposition 1. For a set J of size n and setting k the size of the sets K the maximal number of cases one has to consider in Step 5.2 is then n k , i.e., our procedure in Step 5.2 runs in O(n k ) time, which is maximum for k = n/2. The following result shows that, in general, we cannot hope for a better bound.

Proposition 5 [START_REF] Saban | The Complexity of Computing the Random Priority Allocation Matrix[END_REF]) Finding whether a student is an impossible match is NP-complete.

In practice, it is however possible to reduce further the sets K one has to consider by not including the students who are necessarily matched at a comprehensive matching.

Definition 4 Given a pre-matching problem P , a student i is prevalent if for each school choice problem ≻∈ Θ(P ) and each µ ∈ Σ(≻), it holds that µ(i) ∈ S.

Finding whether a student i is prevalent is easy. It suffices to consider the profile P restricted to the schools A i truncated at i, and then check whether there is at least one school in A i that does not fill its capacity at a maximum matching. Given a pre-matching problem P , let J * denote the set of prevalent students. We can then re-write the second condition of a block in the following way, 2'. For each K ⊆ J \ (J i,s ∪ J * ), with |K| = |J| -ŝ∈A P J q ŝ + 1, Hall's marriage condition does not hold in P s (J, K).

Proposition 6 Let J ⊆ I \ {i} be a subset of students satisfying condition 1. of a block.

Then conditions 2 and 2' are equivalent.

By imposing a slight restriction on the pre-matching problem our algorithm yields a computationally easy task.

Assumption 1 Hall's Marriage condition is satisfied in P .

Under Assumption 1 there exists a matching for P such that all students are matched to a school. An instance of such problem is the pre-matching problem induced by the school choice problem with zoning policy, as given in Section 4, which satisfies Assumption 1.

Proposition 7 Under Assumption 1, student i is an impossible match for school s if, and only if, P admits an exact block at (i, s). Furthermore, finding whether a student is an impossible match can be done in polynomial time.

Proof

From Corollary 1, the existence of an exact block J at (i, s) implies that i is an impossible match for school s.31

To show that the exact block condition is also necessary and can be checked in polynomial time, it suffices to reconsider the Impossible Matches Algorithm. Let µ be any feasible matching for P such that every student j ∈ I is matched to a school. Such a matching exists under Assumption 1. Consider the matching µ ′ be defined as follows: µ ′ (j) = µ(j) for all j = i, and µ ′ (i) = i. Then µ ′ is feasible for the problem described at step 1 of the Impossible Matches Algorithm. It follows that the maximal matching used at step 4 is such that all students but student i are matched to a school. Hence at step 5.1, K = ∅ and |J| = ŝ∈A P J q ŝ. At Step 5.2, the maximal number of cases one has to consider is thus equal to |I| -1. 32Finally, note that the identification of impossible matches can be sped up when scrutinizing the blocks. The impossible match property is not monotone with respect to the rankings in schools' priority (Proposition 3), but if we identify an exact block J at some pair student-school (i, s), then all the students with lower priority than i at s who are not part of the block J are also impossible matches for s.

Corollary 2 Let J be a block at (i, s) and let j be such that iP s j (so s ∈ A P j ) and j / ∈ J.

Then j is an impossible match for s.

The illusion of choice in a stable school choice mechanism

School choice programs usually endow students with a high priority to some school close to their homes. 33 Our characterization of impossible matches allows us to show an adverse effect that such a policy may induce when we introduce a mild form of correlation between students' preferences. In rough terms our purpose here is to show that under a simple zoning policy we can narrow down the set of possible matchings that can obtain for a wide range of preference profiles.

For this section we follow the literature by assuming here that the mechanism used to assign students to schools is SOSM. This mechanism work as follows. Each student i (or his parents) is asked to submit a preference list ≻ i over schools. Given schools' priority rankings over students and the submitted preference lists a matching is computed using Gale and Shapley's Deferred Acceptance algorithm:

Algorithm: Deferred Acceptance

Step 1: Each student i proposes to the school that is ranked first in ≻ i (if there is no such school then i remains unassigned). Each school s tentatively assigns up to q s seats to its proposers one at a time following the priority order ≻ s . Remaining students are rejected.

Step ℓ, ℓ ≥ 2: Each student i that is rejected in Step ℓ -1 proposes to the next school in the ordered list ≻ i (if there is no such school then i remains unassigned). Each school s considers the new proposers and the students that have a (tentative) seat at s. School s tentatively assigns up to q s seats to these students one at a time following the priority order ≻ s . Remaining students are rejected.

The algorithm stops when no student is rejected. Each student is assigned to his final tentative school. Let ϕ(≻) denote the matching. The mechanism ϕ is the Student-Optimal Stable mechanism and the matching ϕ(≻) is called the student-optimal matching.

One of the most appealing property of this mechanism is that it is strategy-proof for the students [START_REF] Dubins | Machiavelli and the Gale-Shapley Algorithm[END_REF][START_REF] Roth | The Economics of Matching: Stability and Efficiency[END_REF], i.e., for each student it is a (weakly)

33 See Abdulkadiroglu, Pathak and Roth (2005), and [START_REF] Abdulkadiroglu | The Boston Public Schools Match[END_REF].

dominant strategy to submit his true preferences, (abusing notation)

ϕ(≻ i , ≻ -i ) i ϕ(≻ ′ i , ≻ -i ), for each ≻ ′ i , ≻ -i .
So, from now on we shall assume that student's submitted preferences to the mechanism are their true preferences.

A zoning policy is pair (z, ≻ z S ) where z is a matching z and ≻ z S is a priority profile such that, for each school s, the students in z(s) have the highest priority, i.e., for each student i ∈ z(s) and j ∈ I\{z(s)}, i ≻ s j. We call the students z(s) the zone students of school s and z(i) is student i's zone school. We assume that z is a perfect matching between S and I. 34A school choice problem with zoning policy is a problem (S, I, (q s ) s∈S , (≻ i ) i∈I , (z, ≻ z S )), where S is a set of schools, I a set of students, q s a capacity of school s, ≻ i a preference of student i, and (z, ≻ z S ) is a zoning policy. When there is no risk of confusion we shall refer to ≻ as a school choice problem with zoning policy.

For a school choice problem with zoning policy ≻ we shall consider the ordered partitions S = {S 1 , . . . , S ℓ } of the sets of schools that satisfy the following property,

for each i ∈ I, z(i) ∈ S k ⇒ {s : s ≻ i z(i)} ⊆ ∪ h≤k S h (4)
That is, given a profile of student's preferences ≻ I , the partition {S 1 , . . . , S k } that satisfies Eq. ( 4) is such that for each student the schools that are weakly preferred to his zone school are schools that are in the elements of the partitions with an index weakly lower than the element that contains his zone school. Given a school choice problem with zoning policy ≻, an ordered partition that satisfies Eq. ( 4) is an associated partition of ≻. Note that for any problem there is always at least one associated partition -the trivial partition {S} satisfies Eq. ( 4)-but it may not be unique. For school choice problem with zoning policy ≻ and an associated partition S we denote by S i the element of S that contains student i's zone school z(i).

Let ≻ and ≻ ′ be two school choice problems with zoning policies that only differ in the profile of student's preferences. The problems ≻ and ≻ ′ are said to be equivalent if for each student the schools preferred to the zone schools are the same under ≻ and ≻ ′ , i.e.,

{s : s ≻ i z(i)} = {s : s ≻ ′ i z(i)}, for each i ∈ I. (5)
Hereafter we consider school choice problems such that, for each student, the zone school is always an acceptable school. 35Proposition 8 Let ≻ be a school choice problem with zoning policy and let S = {S 1 , . . . , S ℓ } be an associated partition of ≻. For each problem ≻ ′ equivalent to ≻ (including ≻ itself ), each student is matched under SOSM to a school s ∈ S i .

Two points are raised by Proposition 8. First, the key ingredient that allows us to "predict" the matchings that can emerge for some problem ≻ is its associated partition.

Adding more structure to the students' preferences can pinpoint a finer partition, and thus increase the predictive power of the proposition. Second, any two problems where student's sets of schools more preferred to the zone school are unchanged are equally predictable.36

Proof Let ≻ be a school choice problem with zoning policy, and P be the pre-matching problem such that ≻∈ Θ(P ). Note that under SOSM it is sufficient to consider, for each student i, the restriction of ≻ i to the set of schools preferred to his zone school. So, if ≻ and ≻ ′ are two equivalent problems then A ≻ i = A ≻ ′ i for each i ∈ I and ≻ ′ ∈ Θ(P ). Let S = {S 1 , . . . , S ℓ } be the associated partition of ≻ (so it is also the partition associated to any ≻ ′ ∈ Θ(P )). Let I = {I 1 , . . . , I ℓ } be the partition of the students such that for each i, j ∈ I, S i = S j implies I i = I j , where I i is the element of I that contains i.

Let i be any student and let S i = S k . Note that for any ≻ ′ ∈ Θ(P ) and µ ′ ∈ Σ(≻ ′ ), µ ′ (i) = i because i has top priority at his zone school z(i), and z(i) ∈ A ≻ ′ i by assumption. Note also that i cannot be matched to some school in S h , for some h > k, because such schools are unacceptable. Hence, it is sufficient to show that i is an impossible match for each school s ∈ S h , for each h < k. Let J = ∪ h<k I h . To do so, one can show, by Corollary 1, that J is an exact block at (i, s) for each s ∈ S h and each h < k. Let s be any such school.

Observe that any matching µ ′ such that for each j ∈ J, µ ′ (j) = z(j) assigns each student in J to a school in A P J . Clearly, any such matching restricted to the student in J is feasible for P (J, ∅). By construction it holds that |J| = s∈A P J q s , so there exists a perfect match between J and A P J for the problem P (J, ∅). So condition 1 of Definition 3 is satisfied. Let us show that condition 2 also holds. If A P z(s) = {s} then there is no need to check condition 2 and we are done. So, suppose there exists s ′ ∈ A P j \ {s} for some j ∈ z(s). Let j ′ be any student in J\J i,s , and consider now the pre-matching problem P s (J, {j ′ }) (if such a student does not exist then condition 2 does not bite either and we are done).

Let r be the rank of student j ′ at school z(j ′ ) (so r ≤ q z(j ′ ) ). Since the problem is truncated at j ′ , school z(j ′ ) can be matched to at most r -1 students, and thus in the problem P s (J, {j ′ }) at most s∈A P J q s -1 -(q z(j ′ )r) students can be matched (the total number of seats available). On the other hand, there are at least |J| -(q z(j ′ )r) students admissible in P s (J, {j ′ }). So Hall's marriage condition cannot be satisfied in P s (J, {j ′ }).

Since student j ′ ∈ J was chosen arbitrarily, Hall's marriage condition does not hold in P s (J, K) for each set K of size 1, as was to proved.

Using Proposition 8 we can now assess the impact of correlation of students' preferences on the assignment under SOSM with a zone priority policy. To this end we shall consider a very weak form of correlation, by simply assuming that there exists an ordering of schools' qualities that influences students' preferences in the following way: For each student, a school is more preferred to his zone school only if it has a higher quality than the zone school. Let ⊲ be the ordering of schools. We do not require the ordering ⊲ to be complete or strict.

Our assumptions on preferences leaves room for a wide array of possible preference profiles. For instance, students may disagree on the relative ranking of two schools they prefer to their zone schools, or a student may prefer his zone school to schools of higher quality. 37In a context where the zone school play the role of "safety school" it is natural to assume that parents would only consider schools that are of better quality than their zone school.

With the ordering ⊲ as an additional primitive we can give a more precise description of partition {S 1 , . . . , S k } associated to a school choice problem with zoning policy ≻.

Suppose that we can partition the set of schools into two subsets, say, S 1 and S 2 , such that for each pair (s, s ′ ) ∈ S 1 × S 2 , s ⊲ s ′ and ¬(s ′ ⊲ s). That is, any school in S 1 is "strictly better " than any school in S 2 . Then, the partition {S 1 , S 2 } is a partition associated to any pre-matching problem P that satisfies the above mentioned assumptions on students' preferences. In this case proposition 8 implies that no student whose district school is in S 2 can be matched to a school in S 1 . Going further, if ⊲ is a complete and strict ordering then the finest partition of I is an associated partition, which implies that each student will be matched to his district school for any realization of student's preferences.

To summarize, some mild correlation in the set of acceptable schools (but not necessarily correlation in terms of preferences over those schools) is enough to generate blocks, and thus limit mobility across school zones. To obtain our results we made two assumptions: the zone school is always acceptable, and for each school there are as many zone students as the total capacity of the school. This second assumption is certainly the most questionable, but our result can be seen as a justification of why some school districts do have a zoning policy only for some of the seats offered by the schools. 38

A welfare improvement mechanism

SOSM is not a Pareto-efficient mechanism. Conditions on schools' priorities so that SOSM is also an efficient mechanism are harsh [START_REF] Ergin | Efficient Resource Allocation on the Basis of Priorities[END_REF], and are unlikely to be met in practice.

In fact, there is no hope to find a more efficient matching while keeping with stability and strategyproofness.

Theorem 3 [START_REF] Kesten | School Choice with Consent[END_REF] There is no Pareto-efficient and strategy-proof mechanism that selects the Pareto-efficient and stable matching whenever it exists.

SOSM becomes inefficient when some students propose for a school during the course of the Deferred Acceptance algorithm, but are eventually rejected by those schools, and would make some students better off had they not proposed that school. [START_REF] Kesten | School Choice with Consent[END_REF] characterizes those students (that he calls "interrupters"), and proposes a mechanism where students are asked first whether they agree to waive their priority at those schools for which they are interrupters. Once students have waived (or not) their priorities for some schools the Deferred Acceptance algorithm is ran. By its very construction Kesten's mechanism thus implements a matching that Pareto dominates the student-optimal matching. As Kesten showed, it is however not strategy-proof.

38 See [START_REF] Dur | The Demise of Walk Zones in Boston: Priorities vs. Precedence in School Choice[END_REF] for an account on this problem.

We propose here a mechanism inspired by Kesten's strategy, but instead waiving students priorities at the schools for which they are interrupters we do so for the schools for which they are impossible matches. The structure of our mechanism is the following.

Impossible-Free Mechanism

1. Students submit a preference ordering (≻ i ) i∈I over schools and are asked whether they agree to waive their priority for the schools for which they are impossible matches.

2. Given schools' priorities and students ' preferences construct the (unique) pre-matching problem P such that ≻∈ Θ(P ) and identify the pairs student-school that are impossible matches for P .

3. For each school, make all students who are impossible matches for that school have a lower priority than the students who are not impossible matches, and let the relative priorities of impossible matches and the relative priorities of the remaining students be unchanged. 39

Let (≻ d s ) s∈S be the schools' priority ordering that obtains.

4. Run the Deferred Acceptance with the profile (≻ i ) i∈I given the priorities (≻ d s ) s∈S .

Let ϕ d (≻) denote the resulting matching. The mechanism ϕ d is the Impossible-Free mechanism.

To understand the impact of waiving priorities in the Impossible-Free Mechanism we shall thereafter assume that all students agree to waive their priorities when proposed to do so. Accordingly, for a school choice problem ≻= (I, S, (≻ s , q s ) s∈S , (≻ i ) i∈I ), we denote by ≻ d = (I, S, (≻ d s , q s ) s∈S , (≻ i ) i∈I ) the resulting school choice problem. An immediate result is that no student can be worse off under the Impossible-Free Mechanism.

Proposition 9 The Impossible-Free Mechanism Pareto-dominates the Student-Optimal Stable Mechanism. 40 39 Maintaining the relative priorities of impossible matches unchanged is only needed to make the mechanism well defined. Choosing another rule would be innocuous for our purpose.

40 A mechanism φ Pareto dominates a mechanism φ ′ if φ = φ ′ and for every problem ≻ and every student i, it holds that φ(≻) i φ ′ (≻).

Proof It is easy to verify that if µ ∈ Σ(≻), then µ ∈ Σ(≻ d ). Since ϕ d (≻) is the studentoptimal matching for the problem ≻ d , ϕ d (≻) i ϕ(≻). (Example 8 below shows that the two mechanisms are not identical.)

The next example shows that the Impossible-Free Mechanism is not strategy-proof.

Example 8 Consider the following school choice problem with three schools, s 1 , s 2 , and s 3 , and three students, i 1 , i 2 , i 3 . Each school has one seat to offer. Let the students (true)

preferences and schools' priorities be the following,

≻ i 1 ≻ i 2 ≻ i 3 ≻ s 1 ≻ s 2 ≻ s 3 s 1 s 2 s 1 i 2 i 1 i 1 s 2 s 1 s 2 i 3 i 2 i 2 s 3 s 3 s 3 i 1 i 3 i 3
Suppose that i 1 and i 3 submit their true preferences, and i 2 submits the preferences

≻ ′ i 2 = s 2 , s 1 , i 2 (i.e.
, s 3 is declared as unacceptable, and s 2 declared preferred to s 1 ). It is easy to see that no student is an impossible match for any school where is admissible.

So the Impossible-Free Mechanism coincides with SOSM and we obtain the matching µ = {(i 1 , s 2 ), (i 2 , s 1 ), (i 3 , s 3 )}.

Suppose now that student i 1 submits the preferences ≻ ′ i 1 = s 1 , s 2 , i 1 . Note that i 1 only altered the set of acceptable schools. The two schools that are declared acceptable are ranked as in his true preferences. Students i 2 and i 3 still submit ≻ ′ i 2 and ≻ i 3 , respectively. With this new profile it is easy to see that i 3 is now an impossible match for school s 1 . So, running the Impossible-Free Mechanism we obtain that i 1 is now matched to s 1 , i 2 matched to s 2 and i 3 matched to s 3 . That is, student i 1 is strictly better off declaring i 3 as unacceptable (SOSM is unchanged and still outputs the matching µ).

In spite of this negative result, we can show that our mechanism still retain part of the incentives present in SOSM.

Proposition 10 In the Impossible-Free Mechanism, for any set of schools a student may choose to declare as acceptable he can do no better than ranking those schools according to his true preferences.

Proof Let ≻= (I, S, (≻ s , q s ) s∈S , (≻ i ) i∈I ) be a school choice problem. Let ≻ ′ be any profile of submitted preferences and let i ∈ I be any student. We denote by ≻ * the preference profile such that ≻ * j =≻ ′ j for each j = i, and

≻ * i is such that A ≻ ′ i = A ≻ * i , and for each s, s ′ ∈ A ≻ * i i , s ≻ * i s ′ if
, and only if, s ≻ i s ′ . That is, ≻ * i is the preference ordering such that the set of acceptable schools is the same as for ≻ ′ i , and all the acceptable schools are ordered as in ≻ i , the true preference ordering of student i.

We claim that

ϕ d (≻ * i , ≻ -i ) i ϕ d (≻ ′ i , ≻ -i ).
By way of contradiction suppose that ϕ

d (≻ ′ i , ≻ -i ) ≻ i ϕ d (≻ * i , ≻ -i ). So, by construction, ϕ d (≻ ′ i , ≻ -i ) ≻ * i ϕ d (≻ * i , ≻ -i ). Since A ≻ ′ j = A ≻ * j
for each j ∈ I, the school choice problems (I, S, (≻ s , q s ) s∈S , (≻ * j ) j∈I ) and (I, S, (≻ s , q s ) s∈S , (≻ ′ j ) j∈I ) are P -compatible for the same prematching problem P . Hence both problems induce the same set of impossible matches and generate the same new schools' priorities at Step 3 of the Impossible-Free Mechanism. Then

ϕ d (≻ ′ i , ≻ -i ) ≻ * i ϕ d (≻ * i , ≻ -i
) contradicts the strategyproofness of ϕ.

Concluding remarks

Our results show that stability constraints in a two-sided matching problem can be sufficiently strong to rule out some matchings when do observe only one side's preferences and the other side's sets of acceptable partners. The existence of impossible matches relies on the presence of short preference lists compared to the size of the market, and some overlap in individuals' set of acceptable partners; two properties that are likely to be met in real-life settings. One could thus conjecture that, as the market size grows, the number of impossible matches increases. This in turn would imply that the number of stable matchings decreases, in line with existing results in the literature.41

An interesting implication of the existence of impossible matches relates to the identification of agent's preferences from matching data. The more there are impossible matches, the less the precise shape of preferences of one side of the market has an impact on the (stable) matchings that can matter. Indeed, what matters is the set of agents' acceptable partners (for one side of the market) and not the exact way they rank these potential partners in their preferences. In other words, a large number of impossible matches makes the identification of preferences virtually impossible. impossible match for s 0 in P . So it is without loss of generality that we can assume P being such that A i 0 = {s 0 }.

Let µ be any maximum comprehensive matching in P . So by Proposition 1, µ(i 0 ) = i 0 .

The next procedure constructs explicitly an exact block at (i 0 , s 0 ). To start with, define the following sets S 0 and J 1 ,

S 0 = {s ∈ S : |µ(s)| < q s } J 1 = µ(S)\A P S 0 .
In other words, S 0 is the set of schools that do not fill their capacity under the maximum and comprehensive matching µ, and the set J 1 is the set of all matched students minus the students that are acceptable for a school in S 0 . For h ≥ 1, we define recursively the following sets, S h = {s ∈ A P J h : |µ(S) ∩ J h | < q S } J h+1 = J h \A P S h .

So, the set S 1 is the set of schools such that are acceptable by students in J 1 that do not fill their capacity with students in J 1 . The set J 2 is then the set of students in J 1 minus the students who are acceptable by schools in S 1 .

Observe that at each step we withdraw students, i.e., J h+1 ⊆ J h , for h ≥ 1. Since the number of students is finite we eventually reach a step ℓ such that J ℓ+1 = J ℓ . 47

Let K be the set of students, except i 0 , who are matched to themselves under µ but are acceptable for some school in A J ℓ , K = {i ∈ I\{i 0 } : µ(i) = i and i ∈ A P J ℓ } Finally, let J = J ℓ ∪ K. We claim that J is an exact block at (i 0 , s 0 ).

Claim:

A P K ⊆ A P J ℓ
Suppose by way of contradiction that A P K A P J ℓ . So, there exists a student i h+1 ∈ K and s h ∈ A i h+1 such that s h / ∈ A P J ℓ . Since µ is a maximal matching and µ(i h+1 ) = i h+1 it must be that |µ(s h )| = q s h , and thus s / ∈ S 0 . Hence, there is a step 1 ≤ h < ℓ such that s h ∈ S h-1 and s h / ∈ S h ′ for each h ′ < h -1. So, |µ(s h ) ∩ J h ′ | = q s h for each h ′ < h -1 and |µ(s h ) ∩ J h-1 | < q s h .

47 This occurs when there is a step ℓ -1 such that S ℓ = ∅.

It follows that there is at least one student, say, i h , such that i h ∈ µ(s h ) with i h / ∈ J h-1 and i h ∈ J h ′ for h ′ < h -1. Since J h-1 = J h-2 \A P S h-2 there is a school, say, s h-1 , such that i h ∈ A P s h-2 and s h-1 ∈ S h-2 . From s h / ∈ S h ′ for h ′ < h -1 we deduce s h = s h-1 . Hence, (i h+1 , s h , i h , s h-1 ) is an alternating path. From s h-1 ∈ S h-2 we deduce that there exists a student, say, i h-1 such that i h-1 ∈ µ(s h-1 ) and i h-1 / ∈ J h-2 . Therefore, i h-1 = i h , i h+1 . Note that we also have i h-1 ∈ J h ′ for h ′ < h -2. 48 Hence, there exists a school, say, s h-2 such that i h-1 ∈ A s h-2 and s h-2 ∈ S h-3 . Continuing this way we eventually end up with a path π = (i h+1 , s h , i h , s h-1 , i h-1 , s h-2 , . . . , i 2 , s 1 ) with µ(i h ′ ) = s h ′ , i h ′ ∈ A P s h-1 and s h ′ ∈ S h ′ -1 . Observe however that s 1 ∈ S 0 implies that |µ(s 1 )| < q s 1 . So π is an augmenting path and thus from Berge's Theorem µ is not maximum. Applying Lemma 1 we deduce that µ is not a maximum and comprehensive matching, a contradiction. So, A P K ⊆ A P J ℓ . Claim: µ(s 0 ) ⊆ J h , for each h ≤ ℓ.

Let i h+1 ∈ µ(s 0 ) such that j / ∈ J ℓ . So j ∈ A P S h for some h < ℓ. Let h be such that S h ′ ∩ µ(s 0 ) = ∅ for h ′ < h, i.e., i h+1 is among the first students in µ(s 0 ) to be withdrawn. 49 Like for the previous Claim, we can deduce that there exists a path π = (i h+1 , s h , i h , s h-1 , . . . , i 2 , s 1 ) with s 1 ∈ S 0 . Let j 0 be the student with the highest priority for s 0 such that µ(j 0 ) = j 0 (such a student exists since µ(i 0 ) = i 0 ). Observe that the path π ′ = (i 0 , s 0 , i h+1 , s h , i h , . . . i 2 , s 1 ) is an augmenting path since s 1 ∈ S 0 . Again applying Berge's Theorem and Lemma 1 we deduce that µ is not a maximum and comprehensive matching, a contradiction. So, µ(s 0 ) ⊆ J h , for each h ≤ ℓ.

From the previous claim we deduce that J = ∅. By construction |µ(s)| = q s for each s ∈ A P J ℓ . Since A P K ⊆ A P J ℓ = A P J , we have then all seats of schools in A J are filled under µ. That is, the first condition for a block is met with the set J.

It remains to show that condition 2 of a block also holds. Suppose by way of contradiction that there exists K ⊆ J\J i,s with | K| = |J| -s∈A P J q s + 1, such that Hall's condition is satisfied in P s 0 (J, K). This is tantamount to saying that there exists a matching μ for P s 0 (J, K) such that all admissible students are matched to a school. Obviously, μ is also comprehensive for P . Let µ ′ be the matching such that µ ′ (i 0 ) = s 0 , µ ′ (j) = μ(j) for each 48 If i h-2 ∈ J h ′ \J h ′ +1 for some h ′ < h -2 then we would have j / ∈ J h ′ +2 , which would contradict j ∈ J h-1 . 49 Although it is not needed for the proof, note that if there is j ∈ µ(s 0 ) such that j / ∈ J ℓ then µ(s 0 )∩J ℓ = ∅.

Indeed, j / ∈ J ℓ implies that there is a step h such that j ∈ A P S h . So we have s 0 ∈ S h+1 and thus µ(s 0 ) ⊆ A P S h+1 , which implies µ(s 0 ) ∩ J h+2 = ∅. j ∈ J\ K, and µ ′ (j) = µ(j) for each j ∈ I\(J ∪ {i 0 }). Notice that by construction for each student j such that µ(j) = j and j / ∈ J, A P j ∩ A P J = ∅, so µ ′ is a feasible matching for P . Observe that µ ′ (j) = j for each j such that jP s 0 i 0 because K ∩ {i : iP s 0 i 0 } = ∅. Therefore µ ′ is comprehensive for P . From Proposition 1 we deduce then that i 0 is not an impossible match for s 0 , a contradiction.

Sufficiency

Let J be a block at (i 0 , s 0 ). Suppose that there exists a matching μ comprehensive for P such that μ(i 0 ) = s 0 . Let µ be the matching such that µ(i 0 ) = i 0 and µ(i) = μ(i) for each i = i 0 . Thus, µ is a comprehensive matching in P s 0 (J, ∅), and in particular µ(i) = i for each i such that iP s 0 i 0 .

Let r = |J| -s∈A J q s + 1. For any matching, let K( µ) = {i ∈ J : µ(i) = i}. From Lemma 2 we have |K(µ)| > r. So we can invoke Lemma 3 to deduce that there exists a matching, say, µ 1 , such that µ 1 is comprehensive for P s 0 (J, ∅) and µ 1 (i) = i for each i such that iP s 0 i 0 and |K(µ 1 )| < |K(µ)|. Note that by Lemma 2 |K(µ 1 )| > r, so we can invoke Lemma 3 and deduce that there exists a matching, say, µ 2 , that satisfies the properties required by Lemma 2 and 3. Again by Lemma 2, |K(µ 2 )| > r, so by Lemma 3 there exists µ 3 that satisfies the properties required by Lemma 2 and 3, and such that |K(µ 3 )| < |K(µ 2 )|.

Repeating the process yields |K(µ)| = ∞, a contradiction with I being a finite set. Hence there is no comprehensive matching μ in P such that μ(i 0 ) = s 0 . From Proposition 1 we deduce then that i 0 is an impossible match for s 0

Additional proofs

The next Lemma will be useful to demonstrate Propositions 4 and 6.

Lemma 4 Let P be a pre-matching problem and i ∈ A P s . Let J ⊆ I \ {i} be a subset of students such that for some J ′ ⊆ J with |J ′ | = ŝ∈A P J q ŝ, Hall's condition is satisfied in P (J ′ , ∅). The following three conditions are equivalent, (a) For each nonempty K ⊆ J \ J i,s , Hall's marriage condition does not hold in P s (J, K).

(b) For each K ⊆ J \ J i,s , with |K| = |J| -ŝ∈A P J q ŝ + 1, Hall's marriage condition does not hold in P s (J, K).

This is because, by assumption, those students deem school s as being acceptable.

Somehow our approach lies between the standard matching theory (here Hall's theorem) and the Gale andShapley's viewpoint (1962) of matching with preferences. It is not surprising since we are precisely considering matching where preferences are observed only on one side of the market.

We do not require those students to have high priorities, our condition merely relies on their relative respective rankings in the priorities of their acceptable schools.

Note that A ≻ I ′ is a set of schools and not a collection of sets (one for each student in I ′ ).

See Abdulkadiroglu and Sönmez (2003).

This contrasts with a school choice problem where a school's priority is an ordering over the set of all students.

See Example 1 for an example where no cycle is involved.

Hall's marriage condition was originally stated for the one-to-one matching problem. It is easy to see that this condition can be easily extended to the case of school choice problems when schools have responsive preferences by making for each school as many copies as its capacity (where each copy has only one seat to offer) and a student acceptable for a school will be acceptable for each of its copy.

Student i 1 must be part of the block, and thus condition 1 implies that we must include at least two other students to fill schools s 1 and s 2 . So any block must contains at least student i 3 , or i 4 or i 5 . If any of these three students is added to the block we span all four schools, and thus any block must contains at least four students.

We describe in the proof of Lemma 1 in the Appendix a way to construct a maximum and comprehensive matching for a pre-matching problem. This construction consists of an iterative search of augmenting paths starting from a comprehensive matching (which could be empty) and can be performed in polynomial time -See the Section 7 for a definition of augmenting paths.

Note that Assumption 1 is not needed here.

We only have to check that for each student j ∈ J \ J i,s , Hall's marriage condition is not satisfied in the problem P s (J, {j}).

This assumption is to keep the exposition simple. Assuming that, for each school the number of students having that school as their zone school equals the capacity of the school and each student has only one zone school, allows us to describe a zoning policy as a (perfect) matching.

See Calsamiglia, Haeringer and Klijn (2010) for experimental evidence.

See Calsamiglia and Miralles (2013) for a result similar to Proposition 8 in a model with a continuum of students.

For instance, other factors such as the distance to the school may influence students' preferences over schools.

See Immorlica and Mahdian (2005) or[START_REF] Ashlagi | Unbalanced Random Matching Markets[END_REF] for accounts the size of the set of stable matchings in matching markets.

Special thanks to Alexander Westkamp for his numerous comments and suggestions. The first author acknowledges the support of the Barcelona GSE Research Network and of the Government of Catalonia, Spanish Ministry of Science and Innovation through the grant "Consolidated Group-C" ECO2008-04756 and the Generalitat de Catalunya (SGR2009-419). Part of this research has been made when the first author was visiting the Stanford Economics department, whose hospitality is gratefully acknowledged. The second author gratefully acknowledges the support of ANR Dynamite and Risk Foundation (Chaire Dauphine-ENSAE-Groupama "Les particuliers face au risque" and ANR Risk).

Appendix

Preliminaries

Let P = (I, S, (P s , q s ) s∈S , (A P i ) i∈I ) be a pre-matching problem. For our purposes it is convenient to describe it by a non-directed graph G P (V, E) where the set of vertices is V = I ∪ S and the set of edges is

A path π in the graph G P (V, E) is a (finite) sequence of pairwise distincts vertices (v 1 , v 2 , . . . , v k ) such that for each h = 1, . . . , k -1 we have (v h , v h+1 ) ∈ E. Given a matching µ, an edge (v, v ′ ) is free if v is not matched to v ′ under the matching µ. Otherwise the edge is matched. A path π ∈ G P (V, E) is an alternating path for a matching µ if it alternates matched and free edges. Given a matching µ, a vertex v is neutral if either v ∈ I and µ(v) = v, or v ∈ S and |µ(v)| < q v . A path π = (v 1 , . . . , v k ) in G P (E, V ) is an augmenting path for a matching µ if it is an alternating path for µ where both (v 1 , v 2 ) and (v k-1 , v k ) are free edges and where both v 1 and v k are neutral vertices. A feasible matching µ is maximum in P if there does not exist a feasible matching µ ′ in P that matches more students than µ, i.e., |{i ∈ I : µ(i) = i}| ≥ |{i ∈ I : µ ′ (i) = i}| for any feasible matching µ ′ in P . 42 A well-known result by [START_REF] Berge | Two Theorems in Graph Theory[END_REF] establishes that a matching is maximum if, and only if, there is no augmenting paths. We rephrase Berge's theorem in our context. 43 Theorem 4 ((adapted from) [START_REF] Berge | Two Theorems in Graph Theory[END_REF] Let P and µ be respectively a pre-matching problem and a feasible matching in P . The matching µ is maximum for P if, and only if, there is no augmenting path in G P (E, V ) for µ.

Let µ be a matching and let π = (i 1 , s 1 , i 2 , s 2 , . . . , i k , s k ) be an augmenting path for µ.

Without loss of generality we consider in the remainder only augmenting paths starting with a (neutral) student and ending with a (neutral) school. 44 The matching µ ′ = µ ⊕ π is the 42 A related concept (albeit different) is that of a maximal matching: a matching µ is maximal for the students if there does not exist a matching µ ′ such that µ ′ (i) = µ(i) if µ(i) = i, and there exists i such that µ(i) = i and µ ′ (i) = i. 43 Berge's original theorem is stated for matching problems where each agent can be matched to at most one other matched. It is straightforward to extend Berge's result to a many-to-one matching problem by adequately adapting the definition of a neutral vertex as we did.

44 Let π = (v 1 , v 2 , . . . , v k ) be an augmenting path for some matching µ, and suppose that v 1 ∈ S. Then it must be that v k ∈ I. We can then consider the path

, which is also, by definition, an augmenting path.

Proof

Let µ be a comprehensive matching for P and suppose that µ is not a maximum matching. So, by Berge's Theorem there exists an augmenting path for µ. Let π = (i 1 , s 1 , i 2 , . . . , s k ) be the smallest augmenting path, and if there are several augmenting paths of the same length as π assume that π is one of those paths such that iP

Let µ ′ = µ ⊕ π. We claim that µ ′ is comprehensive for P . To see this, suppose that µ ′ is not comprehensive. So, there exists j such that µ ′ (j) = j and j ′ such that jP µ ′ (j ′ ) j ′ . From the choice of π, j ′ = i 1 . Since µ is comprehensive there exists h > 1 such that j ′ = j h (and thus µ ′ (j ′ ) = s h ). Consider now the path π ′ = (j, s h , i h+1 , . . . , s k ). Clearly, π ′ is an augmenting path, and since h > 1 it has a smaller length than π, contradicting the choice of π.

Remark 3 The proof of Lemma 1 suggests an algorithm to construct a maximum and comprehensive matching, which works as follows. Start with the empty matching, which is trivially comprehensive. Now it suffices to identify augmenting paths of the smallest length and select the smallest path with the same criterion we chose π in the proof. This operation can be performed in polynomial time with a Breadth First Search algorithm. 45 It follows then that finding a maximum and comprehensive matching can be done in polynomial time. This contrasts with the result of [START_REF] Manlove | Hard variants of stable marriage[END_REF] who show that in a matching problem with indifferences and short preference lists finding a maximum and stable matching is NP-hard.

Proof of Theorem 2

The next two lemmata will be useful to prove Theorem 2.

Lemma 2 Let J be a block at (i, s) and let µ be a comprehensive matching in P s (J, ∅) where µ(j) = j for each j such that jP s i. Then

45 See [START_REF] Lovász | Matching Theory[END_REF].

Proof

Let r = |J| -ŝ∈A J q ŝ + 1. Since µ is comprehensive it is feasible for P s , and thus there are at most ŝ∈A J q ŝ -1 students in J that are matched to a school under µ. It follows that there exists a set K made by r unmatched students. Hence, µ is also feasible for P s (J, K). Since J is a block, Hall's marriage condition does not hold for P s (J, K), i.e., for any feasible matching µ ′ for the problem P s (J, K) there exists an admissible student j such that µ ′ (j). Therefore, there exists j ∈ J\K such that µ(j) = j. So, there are at least r + 1 students in J who are unmatched under µ, as was to be proved.

Lemma 3 Let J be a block at (i, s) and let µ be a comprehensive matching for P s (J, ∅) such that |{j ∈ J : µ(j) = j}| > |J| -

and µ(j) = j for each j such that jP s i. Then there exists a matching µ ′ that is comprehensive

and µ ′ (j) = j for each j such that jP s i.

Proof

Let µ be a matching satisfying the conditions of the Lemma. From condition 1 of a block we can match ŝ∈A P J q ŝ students of J in P (J, ∅). So we can match ŝ∈A P J q ŝ -1 students of J in P s (J, ∅). Hence, µ is not a maximum matching in P s (J, ∅). Since µ is comprehensive in P s (J, ∅), there exists from Lemma 1 an augmenting path π such that µ ′ = µ ⊕ π is comprehensive in P s (J, ∅). Clearly, µ ′ satisfies Eq. ( 8). Since µ(j) = j implies µ ′ (j) = j, we have also µ ′ (j) = j for each j such that jP s i.

Necessity

Let i 0 be an impossible match for s 0 in the pre-matching problem P . We need to show that there exists a block J at (i 0 , s 0 ), with i 0 / ∈ J. Let P be the problem that is identical to P except that in P student i 0 is only acceptable for s 0 . 46 Observe that if µ is such that µ(i 0 ) = s 0 and µ is comprehensive for P (resp. P ) then µ is also comprehensive for P (resp.

P ). So from Proposition 1 i 0 is an impossible match for s 0 in P if, and only if, i 0 is an 46 The problem P is such that P s0 = P s0 (and thus A b P s0 = A P s0 ), and for each s = s 0 , A b P s = A P s \{i 0 } and for each i, i ′ = i 0 , iP s i ′ if, and only if, i P s i ′ .

(c) For each K ′ ⊆ J\J i,s such that |K ′ | = |J| -ŝ∈A P J q ŝ + 1, there is no perfect match between J\K ′ and A J in the problem P s (J, K ′ ).

Proof Obviously, (a) ⇒ (b) ⇒(c). Thus it just remains to show (c) ⇒ (a). To this end, suppose there exists a set K ⊆ J\J i,s such that Hall's condition is satisfied in P s (J, K).

So, there exists a matching µ such that each student admissible in P s (J, K) is matched to a school. Define the matching µ ′ that leaves unchanged the match of admissible students in P s (J, K) under µ and such that µ ′ (j) = j for every other student j. Then µ ′ is also comprehensive in P s (J, ∅). Note also that every student in J i,s is matched to a school under µ ′ since these students are all admissible in P s (J, K).

Applying successively Lemma 1 we obtain a comprehensive and maximum matching in P s (J, ∅), where every student j ∈ J i,s is matched to a school. Since, by assumption, J ′ is such that |J ′ | = ŝ∈A P J q ŝ, each school in A J fills its capacity at a maximum matching in P s (J, ∅). Thus we have obtained a comprehensive matching μ for P s (J, ∅) where every student in J i,s is matched to a school and every school in A J fills its capacity. Consider now

1, and there is a perfect match between J\K ′ and A J in the problem P s (J, K ′ ), as was to be proved.

Proof of Proposition 4

1 . See Lemma 4.

2 . One can use the alternative to condition 2 given in (a) of Lemma 4. The set J i,s cannot be empty, for otherwise Hall's marriage condition trivially holds in P s (J, K) with K = J, which is a contradiction. If J i,s = J then condition 1 of a block implies |J i,s | ≥ q s . For otherwise, consider the nonempty set K = J \ J i,s . The set of admissible students in P s (J, K) is J i,s . Since Hall's marriage condition does not holds in P s (J, K), one cannot assign all students in J i,s to school s at any feasible matching in P s (J, K). That is, |J i,s | > q s -1.

. Let

1 of the definition of a block. Let µ ′ be such that µ ′ (i) = i, and µ ′ (j) = µ(j) if j ∈ J, and µ ′ (j) = j if j / ∈ J. Suppose that the conclusion of 3 . is not satisfied. Then µ is a comprehensive matching for P (J ∪ {i}, ∅). Since µ(i) = s we have necessarily K ⊆ J\J i,s .

In addition µ ′ is a feasible matching in P s (J, K), where, by construction, every admissible student is matched to a school under µ ′ . This contradicts the statement (a) of Lemma 4.

that there exists K ⊆ J \ J i,s with |K| = |J| -ŝ∈A P J q ŝ + 1, such that Hall's marriage condition holds in P s (J, K). From Lemma 4 (c), it means that there exists a perfect match between J\K and A J in the problem P s (J, K), i.e., where each school fills its capacity. Let j be a prevalent student. If j ∈ K, then it is possible to fill all the schools in A j with students that have higher priority than j at these schools. This would contradict the fact that j is prevalent. So j / ∈ K. It follows that K ⊆ J \ (J i,s ∪ J * ).