Guillaume Haeringer
email: guillaume.haeringer@baruch.cuny.edu.

Vincent Iehlé
email: vincent.iehle@univ-rouen.fr.

Atila Abdulkadiroglu

Itai Ashlagi

Francis Bloch

Françoise Forges

Nicole Immorlica

Mar Reguant

Jacob Leshno

Vikram Manjunath

Thayer Morrill

Juan Pereyra

Baharak Rastegari

Al Roth

Daniela Saban

Jay Sethuraman

Tayfun Sönmez

Olivier Tercieux

Peter Troyan

Utku Ünver

Alexander Westkamp

Two-Sided Matching with (almost) One-Sided Preferences *

Keywords: JEL classification: C78, J41, C81 Stable matchings, Partial matching data, Hall's marriage theorem, French

In a two-sided matching context we show how we can predict stable matchings by considering only one side's preferences and the mutually acceptable pairs of agents.

Our methodology consists of identifying impossible matches, i.e., pairs of agents that can never be matched together in a stable matching of any problem consistent with the partial data. We analyze data from the French academic job market for mathematicians and show that the match of about 45% of positions (and about 60% of candidates) does not depend on the preferences of the hired candidates, unobserved and submitted at the final stage of the market.

Introduction

This paper is aimed at further understanding how preferences in two-sided matching markets can shape the set of stable matchings. Stability in a matching problems is a conjunction of two requirements: no agent is matched to an unacceptable partner (individual rationality), and no pair of agents would prefer to be matched to one another rather than to their current mate (absence of blocking pairs). As the second requirement shows, stability hinges on the preferences of both sides of the market. In this paper we investigate how information about stable matchings can be retrieved even if we only consider the preferences of one side of the market once we know the set of mutually acceptable pairs.

To this end we consider job market problems, that are otherwise standard many-toone matching problems between candidates and academic departments. In our model departments have one or several job openings (positions) to fill and are assumed to have responsive preferences over candidates. 1 For most of the paper we depart from this model by considering broader environments that we call proto-matching problems. Such problems consist of a list of mutually acceptable candidate-department pairs, and departments' preferences over candidates. Candidates' strict preferences over departments, however, are left unspecified. The main question we address is, when considering a proto-matching problem, whether we can identify pairs of agents that can never be matched together in a stable matching of any job market problem consistent with the partial data. If there does not exist some candidates' preference profile so that a particular candidate-department pair can be matched at some stable matching (for that profile), the candidate is called an impossible match for the department.

Our work adds to the part of the matching literature that addresses the question of extracting information from partial matching data. One of the earliest results in that line of work is the celebrated Rural Hospital Theorem (Roth, 1986), which allows to extract some information about all stable matchings from the observation of one stable matching. 2 Echenique, Lee and Shum (2013) go one step further and show how the observation of 1 See Roth and Sotomayor (1989).

2 Another celebrated result is that in marriage problems, the set of agents matched at a stable matching 2 stable matchings can be used to estimate agents' preferences for aggregate matchings. 3 Behind these results is the idea to extract information on preferences or properties about stable matchings from the observation of some stable matchings. Our contribution takes the opposite approach, as we aim at deducing information on (un)stable matchings from the partial observation of preferences. The two closest works to this paper are Rastegari et al. (2012), and Saban and Sethuraman (2015). Rastegari 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. 4 Saban and Sethuraman's paper is even closer to ours, but contrary to us they focus on efficient assignments achieved by the random serial dictatorship. Like us, they investigate, upon observing agents' preferences, whether there exists an ordering of agents such that an agent will be assigned a specific object.

There are a number of environments that correspond to proto-matching problems.

The first situation is when a matching has to be determined when individuals have not learned their preferences yet. For instance, this is the case for the assignment of refugees to landlords in Sweden, studied by Andersson and Ehlers (2016). In their model, at the time a matching has to be determined, the only information that is available regarding the preferences of a family of refugees is the set of acceptable landlords. Landlords, in contrast, have more precise preferences (that depend on the size of the refugee family), which can be elicited. A refugee problem is thus a proto-matching problem where landlords and refugees play the role of departments and candidates, respectively. A second class of situations that correspond to proto-matching problems (albeit similar to the case of refugees) is when individuals participating in a matching or assignment mechanism can only report dichotomous preferences. This is the case with the newly introduced college admission procedure in France, where students can only report a set of acceptable programs, but each academic program has to report a strict ranking of students. Proposals by programs and students' acceptance or rejection decisions follow a decentralized procedure. 5 Identifying impossible matches can thus be useful in such situations. For instance, in the case of refugees it is reasonable to assume that, once an assignment has been implemented, refugees become better able to distinguish between landlords and thus have more accurate preferences over their potential hosts. Avoiding matching impossible matches can reduce the number of blocking pairs (and rematches) that may arise once individuals learn their preferences. A third type of situation that proto-matching problems capture is having access to partial matching data. This is the case of the French academic job market for instance (which we comment in more details later in this Introduction).

Unlike the Swedish case, agents on both sides of the market have strict preferences, but from the economist's perspective it does correspond to a proto-matching because only the departments' preferences are observable.

Our first contribution consists of characterizing impossible matches in proto-matching problems. In a proto-matching problem, the only way to know with certainty that a matching cannot be stable for any realization of candidates' preferences is when a candidate is not matched and can form a mutually acceptable pair with a position that is either unfilled or matched to a candidate ranked lower in the preferences of the department holding that position. It is this second requirement that is crucial to characterizing impossible matches. If a candidate i is matched to a position d at some stable matching then all the candidates that are ranked higher than i for position d must be matched to some other position, otherwise the matching would not be stable. Those candidates must pass the same test, i.e., all the candidates ranked higher than them (at the positions where they are matched) must be matched to a position. Matching those additional candidates may in turn bring additional candidates to our problem, and so on and so forth. Candidate i will be an impossible match for department d when, for any possible way we match the other candidates, there is always at least one candidate in excess: a 5 Kidney exchange is another situation where only partial "preferences" may be known. In some countries patients' submitted preferences are dichotomous (acceptable v. unacceptable), while in reality preferences patients may have finer preferences (e.g., the age of the donor). See for instance Nicoló and Rodríguez-Álvarez (2017) who study the efficiency gain that can be realized in paired kidney exchange when patient's "preferences" over kidneys are used instead of simple dichotomous acceptable/unacceptable preferences.

candidate that we must match, but all his acceptable departments have exhausted their positions with other candidates. In other words, the impossibility to match a candidate to a department will arise when there is a set of candidates ranked "sufficiently high" that outnumbers the total number of positions of the departments acceptable for them. This implies that the existence of impossible matches is especially relevant under the following features: not all candidate-department pairs are mutually acceptable and/or the market is imbalanced, that is, there are more candidates than positions. Indeed, if there are enough positions to accommodate all candidates and if all candidate-department pairs are mutually acceptable then no candidate is an impossible match for any department.

We show that this problem is reminiscent to Hall's (1935) marriage theorem, one of the very first results of matching theory. Phrased in our context, Hall's marriage theorem identifies a sufficient and necessary condition to match a full set of candidates to their acceptable departments. Hall's condition is not sufficient for our purposes, however, as it provides no link to stability. Part of our contribution consists of making precise what being ranked "sufficiently high" means, by carefully selecting the set of individuals for which we have to check Hall's condition (Theorem 2). As a by-product, our result establishes a formal connection between stability and Hall's marriage condition.6

In the second part of the paper we use the concept of impossible match to show how stable matchings can be (partially) predicted. To do so we introduce a prediction algorithm that identifies candidate-department pairs that are necessarily matched in every stable matching, for any realization of candidates' preferences. Incidentally, our prediction algorithm also enables us to pinpoint candidates whose submitted preferences can have an impact on the final matching and candidates whose submitted preferences can never affect the matching that will be obtained.

To demonstrate that some candidates' preferences may not have any impact on the final matching, we use data from the French academic job market, which is, unlike most academic job markets, centralized. The algorithm used in France is equivalent to Gale and Shapley's (1962) Deferred Acceptance algorithm (with candidates proposing). 7 Thus it produces a stable matching (with respect to the submitted preferences). Our data covers the years 1999-2013 for junior positions in mathematics. For each year we observe the rankings of candidates established by the departments, from which we deduce the set of mutually acceptable pairs, but not the preferences submitted to the clearinghouse by the candidates later on. 8 The identification of impossible matches permits us to correctly predict, on average, nearly 45 percent of the positions. We also find that the match of about 60 percent of the candidates does not depend on the realization of candidates' preferences.

The paper is structured as follows. In Section 2 we outline the basic model. Section 3 contains the first main contribution of this paper, i.e., the characterization of impossible matches. In Section 4 we show how the identification of impossible matches can be used to make predictions about matchings, and Section 5 illustrates our findings with an empirical analysis of the French academic job market. The main proofs are relegated to the Appendix. Additional elements and results are provided in the Web Appendix.

Preliminaries

Matchings

We consider a finite set I of candidates and a finite set D of departments, where each department d is endowed with a positive capacity q d . The problem studied here is that of matching candidates to departments subject to their capacities. A matching is a mapping µ : I ∪ D → 2 I ∪ D such that, for each i ∈ I and each d ∈ D,

• µ(i) ∈ D ∪ {i}, • µ(d) ∈ 2 I , • µ(i) = d if, and only if, i ∈ µ(d), and • |µ(d)| ≤ q d . For v ∈ D ∪ I, we call µ(v) agent v's assignment (µ(d) is possibly empty for d ∈ D). For i ∈ I, if µ(i) = d ∈ D then candidate i is matched to department d under µ. If µ(i) = i
then candidate i is said to be unmatched under µ.

Job Market Problem

A job market problem is a 5-tuple (I, D, ( d , q d ) d∈D , ( i ) i∈I ), where I is a set of candidates, D a set of departments, d a preference ordering for department d, q d a capacity constraint for department d, and i a preference ordering for candidate i.

Each candidate i ∈ I has a strict preference relation i over the departments and the option of remaining unassigned, i.e., i is a complete, transitive, irreflexive and asymmetric relation on D ∪ {i}. The notation d i d means that candidate i prefers to go to department d than department d . A department d is acceptable for a candidate i under the preferences i if i prefers being matched to d to being matched to himself, i.e., d i i, otherwise the department is said to be unacceptable for i.

Each department d ∈ D has a strict preference relation d over the candidates and the possibility of leaving a position unfilled, i.e., d is a complete, transitive, irreflexive and asymmetric relation on I ∪ {d}. We say that candidate i is ranked higher than candidate j at department d if i d j (and so j is ranked lower than i). Candidate i is

acceptable to department d if i d d.
When there is no risk of confusion, we shall simply use to denote a job market problem. Given a preference relation j we denote by j the weak relation associated to it, i.e., for each j ∈ I ∪ D, v j v ⇔ v j v or v = v . Given a job market problem we denote by A i the set of departments that are acceptable for i. Similarly, we denote by A d the set of candidates that are acceptable for d.

A matching µ is stable for a job market problem if:

(a) individual rationality, i.e., for each candidate i, µ(i) ∈ A i ∪ {i}, and, for each department d, i ∈ A d for each candidate i ∈ µ(d).

(b) no blocking pair, i.e., there is no pair (i, d)

∈ A d × A i such that d i µ(i) and (b.1) |µ(d)| < q d or (b.2) i d i for some i ∈ µ(d).
Given a job market problem , the set of stable matchings is denoted by Σ( ).

Notice that the way we defined stability implicity assumes that departement's preferences are responsive over sets of students. Following Roth (1985) The concept of stability, as defined for job market problems, is not applicable in proto-matching problems, because candidates' preferences are not completely defined.

The concept has a bite, however, when a candidate is matched to an unacceptable department; or when a candidate is unmatched and there is an acceptable department with an unfilled position or matched to another candidate ranked lower. We summarize these three situations with the following concepts.

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

• A matching µ is maximal for P if it is feasible and there is no (i, d) ∈ A such that µ(j) = j and |µ(d)| < q d . 9

• A matching µ is comprehensive for P if it is feasible and for each (i, d) ∈ A, with

µ(i) = d, jP d i implies µ(j) ∈ D.
Remark 1 The feasibility constraint is akin to individual rationality. The condition of maximality and comprehensiveness are respectively related to the conditions on the absence of blocking pairs, (b.1) and (b.2), but only for unmatched agents. Note that the condition (a) implies that A j ⊆ A j for each j ∈ I ∪ D. We also observe that the same proto-matching problem can generate different job market problems (thus generate different sets of stable matchings and possibly different sets of matched candidates). We denote by Θ(P ) the set of job market problems that are P -compatible.

The next proposition connects the notions of stability, comprehensiveness and maximality in job market and proto-matching problems.

Proposition 1 Let P be a proto-matching problem. The following assertions are equivalent:

(i) µ is a stable matching for some P -compatible job market problem .

(ii) µ is a comprehensive and maximal matching for the proto-matching problem P .

9 An equivalent definition is the following. A matching µ is maximal if it is feasible and there is no feasible matching µ such that : µ (i) = µ(i) for every i ∈ D such that µ(i) = i, and µ (j) = j for some j ∈ D such that µ(j) = j.

Proof (i) ⇒ (ii) Since µ is individually rational for the problem , every pair (i, d)

such that µ(i) = d satisfies i ∈ A d and d ∈ A i .
From the construction of a P -compatible job problem, it follows that (i, d) ∈ A. Hence, µ is feasible for P . Suppose first that µ is not comprehensive. It must be the case that there exists i, j and d such that µ(i) = i, and µ(j) = d and iP d j. Since ∈ θ(P ), we have d i i and i d j. So the pair (i, d) blocks µ in the sense of condition (b.2), which contradicts µ ∈ Σ( ). If µ is not maximal then there exists i and d such that µ(i) = i, µ(d) < q d and d ∈ A i . This implies that the pair (i, d) blocks µ in the sense of condition (b.1), which contradicts that µ ∈ Σ( ).

(ii) ⇒ (i) Let µ be a comprehensive and maximal matching for P (hence feasible for P ). From the definition of a P -compatible job market problem, µ is individually rational for any ∈ θ(P ). Let be any job market problem ∈ θ(P ) where, for each candidate i such that µ(i) = i, µ(i) is the most preferred department according to i . Suppose µ / ∈ Σ( ). So there exists a blocking pair (i, d). It must be the case that µ(i) = i from the construction of . Since µ is maximal the condition (b.1) cannot hold. Since µ is comprehensive the condition (b.2) cannot hold. Thus (i, d) cannot form a blocking pair, a contradiction.

Impossible matches

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

Definition 1 Given a proto-matching problem P , a candidate i is an impossible match for department d ∈ A i if, for each job market problem ∈ Θ(P ), there is no matching

µ ∈ Σ( ) such that µ(i) = d.
Note that we could dispense with the requirement that d ∈ A i in the definition of an impossible match. Indeed, d / ∈ A i trivially prevents the existence of a stable matching where i is matched to d, for any problem ∈ θ(P ). This is a trivial case that we will not address in the paper.

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 job market problems.

Example 1 The simplest case occurs if q d candidates ranked higher than i at department d have no other acceptable department. Then for every job market problem ∈ Θ(P )

and stable matching µ ∈ Σ( ) either all those candidates are matched to d, or at least one of them is not matched to any department.10 In either case, i cannot be matched to d at a stable matching, for otherwise one of the candidates ranked higher than i would form a blocking pair with department d.

Example 2 A (slightly) more complex case is the following, with 4 candidates and 4

departments. We assume that each department has only one position to offer. Let i 1 , i 2 , i 3 and i 4 be candidates whose sets of acceptable departments are {d 1 , d 2 }, {d 2 , d 3 }, {d 3 , d 4 }, and {d 2 , d 4 }, respectively. Table 1 describes the departments' preferences over these 4 candidates. For instance, at department d 2 candidate i 2 is ranked higher than candidate i 1 , who is ranked higher than candidate i 4 .

Table 1: Candidate i 1 is an impossible match for department d 2 .

P d 1 P d 2 P d 3 P d 4 i 1 i 2 i 3 i 4 i 1 i 2 i 3 i 4
We claim that for each P -compatible job market problem it is impossible to obtain a stable matching where i 1 is matched to d 2 . To see this, note that if this is the case then i 2 must be matched to d 3 , for otherwise (i 2 , d 2 ) would form a blocking pair. This in turn implies that i 3 is matched to d 4 , which is only possible if i 4 is matched to d 2 , a contradiction. So, there is no preference profile and a stable matching for that preference profile where i 1 is matched to d 2 .

Without entering into much detail, it is important to note that in the previous example the key property of departments d 2 , d 3 and d 4 's preferences to ensure that i 1 is an impossible match for department d 2 is not, as it may appear, that there is some sort of cycle with the relative positions of candidates i 2 , i 3 and i 4 . As we shall see, i 1 being an impossible match for d 2 is rather due to the more general feature that there are (at least) 3 candidates competing for three departments and such that their relative rankings in the preferences of the departments allow them to claim the positions over i 1 .

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

Using Proposition 1, we have the following straightforward characterization for impossible matches (its proof is omitted).

Proposition 2 A candidate is an impossible match for a department in a proto-matching problem P if, and only if, there is no maximal and comprehensive matching for P such that they are matched together.

In the next proposition we establish a Rural-Hospital type of result (Roth, 1986), when some candidates are impossible matches for some departments.

Proposition 3 Given a proto-matching problem P , if i is an impossible match for d ∈ A i then d fills its capacity at every stable matching, for each P -compatible job market problem.

Proof

Suppose by way of contradiction that i is impossible for d ∈ A i and that, for some P -compatible job market problem , there exists a matching µ ∈ Σ( ) such that |µ(d)| < q d . Since µ is stable, Proposition 2 implies that µ is maximal and comprehensive for P . From maximality it holds that µ(j) = j for every candidate j such that d ∈ A j .

Note that i is such a candidate .

Let µ be the matching such that µ (j) = µ(j) for each j = i, and µ (i) = d. In addition, if there exist candidates for which µ(i) is acceptable and who are unmatched under µ, match under µ the highest ranked candidate among those candidates to the department µ(i).

It is easy to check that µ being comprehensive and maximal for P implies that µ is also maximal and comprehensive for P . From Proposition 2 it follows that i is not an impossible match for d, a contradiction.

Remark 2

The impossible match property is not monotonic with respect to the preferences of the department. That is, if a candidate is an impossible match for a department then candidates ranked lower at that department are not necessarily impossible matches for that department. To see this, consider again the proto-matching problem P given in Table 1. It is easy to check that candidate i 1 is also an impossible match for d 2 , yet candidate i 4 is not an impossible match for d 2 . Indeed, let ∈ Θ(P ) be such that i 1 's most preferred department is d 1 , d 2 is the most preferred department of i 4 , d 3 is the most preferred department of i 2 , and d 4 is the most preferred department of i 3 . The matching

µ such that µ(d 1 ) = i 1 , µ(d 2 ) = i 4 , µ(d 3 ) = i 2 , µ(d 4 ) = i 3 is stable for .

A characterization

Part of our contribution consists of showing that we do not need to consider all candidates and all possible profiles of candidates' preferences (and compute all the corresponding stable matchings) to check whether a candidate is an impossible match for a department. Instead we are able to characterize impossible matches on the basis of the fundamentals of the proto-matching problem only. Proposition 2 provides a first baseline for the analysis of impossible matches, at the cost of extreme computations: checking whether a candidate i is an impossible match for a department d amounts to listing every comprehensive and maximal matching of the proto-matching problem P to see whether one of those assigns i to d. Another way is to consider all candidates' preference profiles and use Gusfield's algorithm (Gusfield, 1987) to identify all candidate-department pairs that are contained in at least one stable matching. While Gusfield's algorithm is polynomial-time, enumerating all possible preference profiles is clearly not solvable in polynomial time. The following result, due to Saban and Sethuraman (2015) shows that in fact there is no hope to identify a polynomial-time algorithm for the identification of impossible matches (unless P = N P ).

Proposition 4 (Saban and Sethuraman (2015)) Finding whether a candidate is an impossible match is NP-complete.

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 candidates, 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 now to fit our setting.

Theorem 1 (Hall's Marriage Theorem, 1935) Given a proto-matching problem P , there exists a feasible matching where every candidate is matched to a department if, and only if,

for each I ⊆ I, |I | ≤ d∈A I q d . (1)
In words, there exists a matching where every candidate can be matched to a department if, and only if, for each subset I of candidates the number of candidates is at most equal to the total number of positions among the departments that are considered by some of the candidates in I as acceptable. Eq. ( 1) is known as Hall's marriage condition. 11 At that matching, the positions of departments are not necessarily all filled by candidates. If this is the case, then we say that the matching is perfect. Using Hall's marriage theorem, one can deduce that a perfect matching exists if, and only if, Eq. ( 1)

is satisfied together with |I| = d∈A I q d .
To incorporate the absence of blocking pair condition (b.2 ), or its counterpart in the proto-matching framework (comprehensiveness), we shall not apply Hall's marriage condition to the original proto-matching problem but rather to a collection of restricted and truncated proto-matching problems. 11 Hall's marriage condition was originally stated for the one-to-one matching problem. It is easy to see that this condition can be extended to the case of job market problems when departments have responsive preferences by making for each department as many copies as its capacity (where each copy has only one position to offer) and making each of its copies acceptable for a candidate if the department is acceptable for that candidate.

Given a proto-matching problem P = (I, D, (P d , q d ) d∈S , A) and two sets of candidates J and K, with K possibly empty, the proto-matching problem restricted to J and truncated at K is denoted by P (J, K). The set of acceptable pairs for P (J, K) is

A P (J,K) = {(i, d) ∈ A : i ∈ J and iP d i for each i ∈ K} (2)
and the preference of department d is the ordering over A P (J,K) d

that coincides with P d on

A P (J,K) d . 12
When we consider the proto-matching problem restricted to J and truncated at K the set of "available" candidates and departments may not be equal to J \ K and A J\K , respectively. Indeed, it may well be that there is a candidate i ∈ J\K such that there is no department d for which i ∈ A P (J,K) d

. Similarly, for a department d we may have

A P (J,K) d = ∅.
Definition 2 For a truncated proto-matching problem P (J, K) we say that a candidate i

is admissible if i ∈ ∪ d∈D A P (J,K) d . Similarly, a department d is admissible if A P (J,K) d = ∅.
Remark 3 Note that admissibility in a proto-matching problem refers to the notion of being acceptable for a department and is independent of the departments' capacities.

For instance, if for a proto-matching problem P (J, K) there is a department d such that q d = 0, all candidates in A P (J,K) d consider d as acceptable (and thus are admissible), even though the capacity of department d is zero in P (J, K).

For sake of completeness, the meaning of the Hall's marriage condition applied to a proto-matching problem restricted to J and truncated at K is precisely stated in the next definition.

Definition 3 Given a proto-matching problem P , and two sets of candidates J and K, with K possibly empty, Hall's marriage condition holds in P (J, K) if

for each I ⊆ ∪ d∈D A P (J,K) d , |I | ≤ d∈A P (J,K) I q d . (3)
Given a proto-matching problem P and a department d ∈ D, we denote by P d the same problem as P except that one position of d is removed, i.e. department d's capacity is q d -1. Note that P d is a proto-matching problem. Given a pair (i, d) ∈ A and a subset J ⊆ I \ {i}, we denote by J i,d ⊆ J the set of candidates in J that are ranked higher than i by d, i.e., J i,d = {j ∈ J : jP d i}.

Definition 4 Given a proto-matching problem P = (I, D, (P d , q d ) d∈D , A), a block at

(i, d) ∈ A is a nonempty set J ⊆ I\{i}, with d ∈ A J
, such that the following conditions hold:

1. There exists a set J ⊆ J such that |J | = d∈A J q d and Hall's marriage condition holds in P (J , ∅);

2. For each K ⊆ J \ J i,d such that |K| = |J| -d∈A J q d + 1, Hall's marriage condition does not hold in P d (J, K).
We state now the main result of the paper.

Theorem 2 A candidate i is an impossible match for a department d in a proto-matching problem P if, and only if, P admits a block at (i, d).

The result provides additional insights on impossible matches. As illustrated by the examples in the sub-section 1, an impossible match i for d is by no way determined by the sole ranking of d or the way i is ranked elsewhere by his acceptable departments. 13 Nevertheless we do not need to consider the whole market. Our main result shows that the impossible match property can be captured locally through a block of candidates, at least one of them being ranked by d. More precisely, we prove in the Web Appendix 13 In Example 2, there is a block at (i 1 , d 2 ) formed by the set of candidates J = {i 2 , i 3 , i 4 }. Condition 1 is indeed satisfied for J = J since the three candidates in J can be clearly matched to the three available positions in the set of admissible departments {d 2 , d 3 , d 4 }. To check condition 2, we first observe that the sets K satisfying the cardinality condition are necessarily singletons since |J| -d∈A J q d + 1 = 1.

In addition, i 2 cannot belong to K since i 2 ∈ J i1,d2 . Hence, it remains to check Hall's marriage condition (3) in P d2 (J, K) with K equal to {i 3 } or {i 4 }. If K = {i 3 }, then the two remaining admissible candidates in P d2 ({i 2 , i 3 , i 4 }, {i 3 }) are i 2 and i 4 . They cannot both be matched to an admissible department since d 3 is not admissible in P d2 ({i 2 , i 3 , i 4 }, {i 3 }) and the capacity of the admissible department

d 2 in P d2 ({i 2 , i 3 , i 4 }, {i 3 }) is equal to 0.
A similar reasoning applies to the case K = {i 4 }. Hence Hall's marriage condition (3) cannot be satisfied for every K.

(Proposition A.1) that the conditions 1. and 2. in the definition of a block imply there are at least q d candidates in J ranked higher than i at department d, i.e., |J i,d | ≥ q d .

Next, Hall's condition (3) holds in P (J , ∅) for some J such that of |J | = d∈A J q d is tantamount to saying that there exists a perfect matching between the departments A J and the candidates J , i.e., there exists a matching where all candidates J are matched to a department and all departments exhaust their capacities with candidates 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 d (the problem identical to P except that one position is removed from d) then there is no perfect match between the departments A J and any subset J ⊆ J that includes all the candidates in J i,d , and such that the matching is comprehensive for P (J, ∅).14

The Appendix provides several examples to illustrate the notion of block and its role in the determination of impossible matches. We extend our formal analysis in Section A of the Web Appendix. We introduce there several variants of the notion of block and an algorithm for finding blocks, that is, finding impossible matches.

Matching prediction

We now investigate what the identification of impossible matches entails. Our claim is that such an identification can be used to predict matchings, thereby measuring the extent to which one side's preferences matter in the determination of a final matching.

Identifying impossible matches will permit us to single out two sets of candidates. On the one hand, we shall have the set of candidates for whom the strict preferences over departments is irrelevant for their final match. For them, no strict preferences, even partial, can be deduced from the data. On the other hand, we shall have candidates for whom the strict ordering in their (submitted) preference lists matters for the final match, but only their (relative) top choice can be sometimes recovered.

Our strategy is the following. Given an observed proto-matching problem, deleting candidates identified as impossible matches (from the departments' rankings for which they are impossible matches) creates a reduced proto-matching problem. In this new problem, a candidate who is ranked top by some department, and ranked only once, must either have begun with only one acceptable department or have all but one department deemed an impossible match. It is straightforward to show that the candidate is necessarily matched to that department, irrespectively of the way candidates rank departments in their preferences.

If the observed data also contains the final (realized) matching we can go one step further by considering the assignments of market stars, that is, candidates that are always top ranked by all acceptable departments in the reduced problem. For those candidates, there is no way to infer their final match on the basis of the sole proto-matching problem.

Note, however, that their match trivially indicates their top choice (within the remaining choices). Once market stars' choices are taken into account new impossible matches may be identified and so on and so forth. This is the baseline of our general procedure.

Let P be a proto-matching problem. The reduced proto-matching problem of P , denoted by R(P ), is the proto-matching problem where impossible matches have been deleted from the rankings of the positions for which they are impossible matches, and where the lists of acceptable candidates or departments are made mutually consistent.

Formally, the set of mutually acceptable pairs is The next result motivates the construction of the predicting algorithm that we present hereafter.

A R(P ) = A\{(i,
Proposition 5 Let P be a proto-matching problem. For every P -compatible job market problem we have:

1. Candidate i is matched to department d under every matching that is stable for if, and only if, A R(P ) i

= {d} and |{j : jP d i}| < q d 2. Candidate i is unmatched under every matching that is stable for ∈ θ(P ) if, and

only if, A R(P ) i = ∅.
In other words, Proposition 5 says that a candidate's match is always the same for every stable matching of every P -compatible job market problem if, and only if, the candidate falls into one of the two cases mentioned in the Proposition. The reduction procedure can be generalized if the economist has access to the final match of the candidates. The initial data is a proto-matching problem P and a matching µ for P . If the matching is not observed, then the matching µ used in the algorithm is the empty matching, i.e., µ(i) = i for each candidate i.15

Predicting Algorithm

Input: A pair (P, µ), where µ is a matching for P .

Step 1 Identify and remove all impossible match pairs in P and construct P 1 := R(P ).

Step h For h ≥ 2 Note that if we do not observe the final matching then the algorithm stops at step 2.2.

h.1 Identify the set S h ⊆ {i ∈ I | µ(i) = i}
The algorithm implicitly partitions candidates in three sets:

• Candidates for which we will predict their matches for the proto-matching problem: Any candidate who does not belong to the sets S 2 , S 3 , . . . , but there is a problem P h in which the candidate is ranked by only one department, say, d, and is among the top q d candidates in that department's ranking.

• Candidates for which we use their observed match, i.e., they belong to the sets S 2 , S 3 , . . . .

• All the other candidates.

For each step h ≥ 2, the candidates in S h play a particular role. A candidate i ∈ S h is called a market star at step h, that is, i is a matched candidate under µ and is ranked among the top q d candidates in all the acceptable departments d ∈ A P h i , with |A P h i | ≥ 2. In that case, we say that a market star is extracted in the algorithm. By construction, the algorithm makes sure that the match of such candidate is only used once, i.e., for every h, h ≥ 2, S h ∩ S h = ∅. Adding the fact that there is a finite number of candidates and departments, we deduce that the algorithm eventually stops after a finite number of steps.

Definition 5 In the Predicting Algorithm, the match of a candidate i is predicted at step h if there is no h = h such that i ∈ S h and h is the smallest index such that either:

(a) A P h i = {d} for some d and |{j : jP h d i}| < q d ; or

(b) A P h i = ∅.
In case (a) the prediction is d and it is consistent with µ if µ(i) = d. Similarly, in case (b) the prediction is i and it is consistent with µ if µ(i) = i.

The Predicting Algorithm can use any matching µ as an input. This implies that the predictions used made through the algorithm are not necessarily consistent. However, if the matching µ is stable for a job market problem that is P -compatible then predictions turn out to be consistent.16

Proposition 6 Let (P, µ) be a pair such that µ is a stable matching of an unobserved job market problem ∈ Θ(P ). All the predictions of the algorithm with input (P, µ) are consistent with µ.

Since at

Step 1 the Predicting Algorithm does not use market stars we obtain the following corollary: the final matching of candidates whose match is predicted in Step 1

does not depend on the profile of candidates' preferences.

Corollary 1 Let (P, µ) be a pair such that µ is a stable matching of an unobserved job market problem ∈ Θ(P ). If the match of a candidate is predicted in Step 1 of the Predicting Algorithm, then the match of that candidate is the same, for every stable matching of every job market problem in Θ(P ).

The predictions obtained from the Predicting Algorithm obviously depend on the match of the market stars, i.e., the candidates from the sets S 1 , S 2 , . . . . We can show that the predictions of our algorithm remain the same for any preference profile of the candidates that does not alter the top choices of market stars in a certain way. To see this, suppose that µ (the input of the algorithm) is a stable matching for some problem .

We will observe that if a candidate i is a market star at some step h (i ∈ S h ) then µ(i) is necessarily candidate i's top choice among the departments in A P h i . Consider now the job market problem = ( i , -i ), with i such that µ(i) is also the top choice among the departments in A P h i , and let µ be a stable matching for . As the next proposition shows, running the Predicting Algorithm with input (P, µ) or (P, µ ) yield the same predictions, and the market stars identified throughout steps 2, 3, . . . are identical.

To prove this, we need to define a subset of the compatible job market problems.

Given (P, µ), let Θ(P, µ) be the set of job market problems ∈ Θ(P ) such that, for every market star i at some step h, µ(i) i d for all d ∈ A P h i .

Proposition 7 Let (P, µ) be a pair such that µ is a stable matching of an unobserved job market problem ∈ Θ(P ) and consider the Predicting Algorithm with input (P, µ). Then for every problem ∈ Θ(P, µ) and matching µ stable for , 1. The set of market stars is the same with input (P, µ) and (P, µ ).

2. µ (i) = µ(i) for every candidate i whose match is predicted and for every market star i (i ∈ S h for some h ≥ 2).

In addition, the Predicting Algorithm allows for a partial identification of the market stars' preferences, that is, the unobserved job market problem must belong to Θ(P, µ).

The last statement of Proposition 7 simply says that, for every market star i at step h of the algorithm, µ(i) is i's most preferred department among those remaining at step h (and acceptable for i).

The main feature to be deduced from Proposition 7 is stated explicitly in the next corollary.

Corollary 2 If the match of a candidate is predicted in the Predicting Algorithm then the order in which that candidate ranks the acceptable departments is irrelevant for the final match of the candidate.

Finally, note that the Predicting Algorithm does not fully clear the market. Some departments and candidates are not considered at any step of the algorithm. Typically, this means that the remaining candidates are not top ranked in the remaining acceptable departments of the final proto-matching problem. Those assignments are the most difficult to sort out in the market. From Proposition 7, we only know that the preferences of the remaining candidates affect neither the matches of the stars and nor the predictions.

Empirical analysis

The French academic job market

We consider in this paper junior positions, called Maître de Conférences. They correspond to a lectureship in the U.K., or to an assistant professorship in the US. Junior positions in France are civil servant, tenured positions. 17 We first outline the general timeline of the French job market, and then comment on several aspects. There is much to say about this market, but to avoid unnecessary digressions we only present the aspects that are relevant for this paper (more details can be found in the Web Appendix).

Unlike, for instance, the US academic job market, most of the hiring procedure in French universities is centralized. 18 During the hiring season all departments first submit to the Ministry of Higher Education an ordered list of candidates (after interviewing them, usually in May), and then candidates are invited to submit a preference list over the positions that ranked them (usually in June). The final step is made by the ministry, where an algorithm is run to compute a match. Haeringer and Iehlé (2010) showed that the algorithm used in France is equivalent to the Deferred Acceptance algorithm with candidates proposing. That is, the matching computed is stable, and thus comprehensive in the context of proto-matching problems.

Market for mathematicians

In 1998 a small group of young mathematicians set up a web site, Opération Postes, inviting recruiting committees to announce the lists of candidates to be interviewed as well as the rankings of candidates that will be submitted to the clearinghouse (the ministry), as soon as these would be decided. 19 The community of mathematicians was very responsive and the web site quickly became a central tool in the job market. 20 The data for each position (interviewees list and rankings) is usually uploaded by the the chairs of the 17 Tenure is made official after one year of service, but it is extremely rare that tenure is not confirmed.

18 Since 2008 there is a "decentralized" market running parallel to the regular, centralized market, but with much less job openings. See the Web Appendix for more details. recruiting committees themselves (and if not, by a member of the committee). On average, about 90-95 percent of the job openings' interview lists and rankings are available. 21 The data of Opération Postes is public, although not in a format that makes it immediately usable for any analysis. There are many misspellings, and we sometimes found confusions between the married and maiden names of some female candidates. By cross-referencing the data with other sources we were able to compose a clean dataset. 22 We also collected for each year the assignment of candidates to departments. This assignment is computed by the Ministry of Higher Education by using candidate's submitted preference lists over the departments and the rankings of candidates established by the recruiting committees. 23

Data analysis

Our data does not contain the preferences submitted by the candidates in June. Such lists are considered confidential by the Ministry of Higher Education; access to this data has been denied. It is nevertheless reasonable to assume that whenever a candidate appears on the ranking for a position that position is also acceptable for the candidate, i.e., he would prefer to be matched to that position than not being matched to any position. There are several observations that uphold this acceptability assumption for that market.

First, a candidate can only be ranked for a position if he has been interviewed, on campus, for that position. Since transportation and lodging costs accrue to the candidates it is unlikely that a candidate would bear the cost of applying for a position he would 21 The missing data usually concerns overseas departments (e.g, La Réunion, Martinique or New Caledonia). The web site also invites the recruiting committees to submit the date when the interview list will be decided, the date of the interviews, and the date when the ranking will be decided. We discarded the positions that are reserved for administrative transfer (postes à la mutation), i.e., positions that are only open to candidates that are already Maître de Conférences. Such positions represent only a small fraction of the total number of openings, most positions being reserved for rookies. 22 To be able to apply to a job opening candidates must first pass an evaluation by a national committee.

The lists of candidates that have passed that evaluation (without spelling errors) is published by the Ministry of Higher Education and is freely available at https://www.legifrance.gouv.fr/initRechJO.do. 23 Unfortunately, the assignment computed by the Ministry is not published. However, all of the assignments could have been easily collected manually using web searches, looking at the departments' lists of faculty, submitted rankings (hired candidates have to be ranked by the departments), and candidates résumés (some departments also have an archive of the candidates they hired the previous years).

eventually refuse. 24 The timeline of the job market is another element to sustain our assumption. Interviews take place in May for a position that starts in September. That is, candidates still looking for a job have usually few outside options (if any). Finally, the vast majority of candidates have French degrees (and are French), and mathematics departments in France rank well according to international standards. Adding the fact that the departments offer tenured positions, such jobs are very attractive for mathematicians.

Using the observed matching we can also check, to some extent, whether our acceptability assumption is satisfied. Since we know that the final matching must be comprehensive (stable), any candidate i ranked for a position above the candidate that has been hired must be hired by another department. If this is not the case, then we must conclude that candidate i declared that position unacceptable in June. So from the observation of the matching we can refine the candidates' sets of acceptable departments. 25

After carrying out this necessary exercise, our analysis in this paper will consider the rankings submitted by the recruiting committees, where a candidate i ranked by a department d means that (i, d) is a mutually acceptable pair. So our data is a reallife example of proto-matching problems and we can use the Predicting Algorithm from Section 4. Before describing our results, we first observe that the predicted matches we obtain are always correct.

Table 3 together with Table 3 of the Web Appendix give a good picture of the complexity of the problems. In 2013, for instance, there are 73 positions and 193 candidates ranked at least once in one of them; the length of the ranking is between 5 and 7 in 75 percent of the positions. For each year in our dataset, we first identify all the pairs that form impossible matches. Once all such pairs (c, d) are identified we simply delete candidate c from the ranking list of department d. From this reduced market we count the number of positions' matchings that are predicted. Table 3 reports for the years 1999 to 2013, in this order: the number of job openings, the number of candidates that ap-24 Interviews are not "flyouts" where the candidate can meet his (potentially) future colleagues and have a better knowledge of the department. The interview lasts only 20 or 30 minutes, and the candidate leaves the department quickly after the interview. 25 The number of such violations and violators for every year is given in the Web Appendix, Table 5.

Most of those candidates turn out to be also participating to the job market for another discipline (e.g., physics or biology), obtaining a job in a research institution (e.g., CNRS, INRIA, etc.) or getting a job at a foreign institution.

pear in the rankings, the number of predictions of candidates' matches and the number of predictions of positions' matches (the percentage in parenthesis relates the number of predictions to the numbers of candidates and job openings, respectively). The last two columns (with the "total" term) are obtained when running our Predicting Algorithm.

The input matching we used in the algorithm is the observed matching, i.e., the matching computed by the Ministry of Higher Education. 26 We are not aiming to identify what drives departments' strategies when establishing their rankings of candidates, a future research project will address that question. Nevertheless, Table 3 is illustrating the impact that department's strategies have on final outcomes (together with the set of mutually acceptable partners). Indeed, recall that in the French market all departments establish their rankings of candidates before candidates are called to submit their preferences. Table 3 shows that, on average, nearly 45 percent of the positions are awarded independently of the way candidates rank the positions in their preferences. If we consider the (observed) choices of market stars to refine our analysis, we end up with almost 60 percent of the positions' matches being predicted. In other words, the way candidates rank their choices have little impact on the final matching. Table 3 is also instructive, from candidates' viewpoint. On average, we are able to predict ex ante the matches of 60 percent of the candidates, be they matched to a department or not. According to Corollary 2, for 78 percent of the candidates, the way each of them ranks his acceptable departments is irrelevant for his final match (all other things remaining equal), and up to 91 percent in 2012.

Remark 4 The French academic job market is clearly unbalanced: there are more candidates than positions available. In a recent contribution, Ashlagi, Kanoria and Leshno (2017) explore the impact of such imbalances, showing that agents on the short side of the market (the departments in our case) tend to be matched with their top choices. This is confirmed by Table 4 in the Web Appendix, showing that nearly half of the hired candidates are ranked either top or second by the department that hire them.

Simulations

One may wonder what drives the number of impossible matches we can identify and, more generally, the number of matchings that can be predicted. It turns out that across the 15 years of data a large number of candidates are ranked only once. Table 4 (first row) shows the average rank distribution for the years 1999-2015. Undoubtedly, the high proportion of candidates being ranked only once or twice (almost 70 percent) has a great impact on the number of impossible matches present in the ranking profiles. Indeed, a candidate ranked only once is a trivial singleton block, so all candidates ranked below him or her are impossible matches. Since the number of impossible matches is a key parameter to determine the number of matches that can be predicted, we may legitimately conjecture that our prediction rate is due to the skewness of the distribution. If we consider only hired candidates (second line of Table 4), the distribution is still less skewed, though. To understand the impact of each of these parameters we ran two types of simulations, for each year in our dataset. The first type of simulation (called reshuffled rankings)

simply consists of reshuffling randomly departments' preferences (independently), thereby maintaining the overlaps between the rank lists. For the second type of simulations (called simulated rankings) we restrict to the profiles such that the rank distribution of the candidates (first line of Table 4) and the distribution of the length of departments' rankings are the same as for the year under consideration. Within this subset of profiles we pick one at random.

For each year, we ran 10,000 simulations for each specification (simulated rankings and reshuffled rankings). Figure 1 shows the averages (over 10,000 runs) of the percentage of positions being predicted for both randomizations protocols and the prediction using the original rankings. 27 q q q q q q q q q q q q q q q 2000 2002 2004 2006 2008 2010 2012 20 30 40 50 60 year % positions predicted q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q Original rankings Reshuffled rankings Simulated rankings

Figure 1: Prediction rate 27 To make the comparison meaningful between observed and simulated rankings we did not withdraw the candidates that violate the acceptability assumption (we did withdraw these candidates for the results in Table 3). Table 8in the Web Appendix presents, for each year, the average percentage of positions predicted for the random and reshuffled rankings, and the percentage of predicted positions for the original rankings when we do not withdraw the candidates violating the acceptability assumption.

Reshuffled rankings (resp. the original rankings) allow on average about 15 percent (resp. 22 percent) more predictions than simulated rankings. This difference indicates that the high level of prediction we observe in the original data is mostly due to the overlaps in departments ranking. Perhaps more surprising is the difference in the prediction rates of the reshuffled and original rankings, which is on average only of 5.8 percent. This suggests that the way departments rank the candidates are not as important as who they rank.

Concluding remarks

Our main result, Theorem 2, shows that identifying impossible matches relies on a combination of two factors: relative rankings and mutual acceptability.

The role of relative rankings shows up in the second condition of a block when we truncate, below some candidates, the proto-matching problem restricted to a subset of candidates (the block). This is precisely how we are able to connect Hall's marriage conditions to stability. However, extracting a precise pattern of rankings that would guarantee or not the existence of impossible matches seems unattainable. Our examples and simulations indeed illustrate how ambiguous can be the impact of rankings on the existence of impossible matches. For instance, increasing the correlation between some departments' rankings can create new impossible matches while making some candidates no longer impossible matches for some departments.

The set of mutually acceptable pairs obviously also plays an important role in the definition of a block (for both the first and second conditions). This set not only determines the imbalance between each side of the market but also specifies the overlaps of the mutually acceptable pairs, which is a key implicit element in the definition of a block. The presence of many unacceptable pairs implies that there can be "local" imbalances that create bottlenecks when matching certain candidate-department pairs, even if the total number of positions exceeds the total number of candidates. That is, local competition matters. 28 Our results are thus of particular relevance when at least one side of the market submits short preference lists, which is a salient feature of most (if not all) real-life matching markets. There are various explanations for this stylized fact. For instance, some matching markets involve a large number of participants or take place on a non-trivial geographic extent, 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., position choice in New York City, university admission in Spain or the French academic job market). 29

Analyzing the effects of competition on stable outcomes is a direction taken by Ashlagi, Kanoria and Leshno (2017). Unlike us, they assume that every candidate-department pair is acceptable (i.e., complete preference lists) and specify preferences of each side (random, iid). 30 They show that the slightest imbalance between the number of agents on the two sides of the market is sufficient to get a set of stable matchings that is essentially unique.

Our contribution suggests that the global imbalance condition is not any more sufficient when the preference lists are incomplete. Instead, Hall's marriage conditions, i.e., local imbalance conditions, might provide the adequate tool for capturing local competition effects.

A. Appendix

Examples

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

Example 3 Let I = {i 0 , i 1 , i 2 , i 3 } and d = {d 0 , d 1 , d 2 , d 3 , d 4 }, and assume that for each department d ∈ D, q d = 1. The admissible departments for each candidate are given by

A i 0 = {d 0 }, A i 1 = {d 0 , d 1 , d 2 }, A i 2 = A i 3 = {d 1 , d 2 , d 3 , d 4 }.
The departments' preferences are described in Table 5.

The matching µ such that µ(i 0 ) = d 0 , µ(i h ) = d h for h = 1, 2, 3 is comprehensive and maximal, so from Proposition 2 candidate i 0 is not an impossible match for department d 0 . In this example condition 1 of the definition of a block is not satisfied, because for 29 Abdulkadiroglu, Pathak and Roth (2005), Haeringer and Klijn (2009), Calsamiglia, Haeringer and Klijn (2010), Pathak and Sönmez (2013) or Bodoh-Creed (2013) constitute additional accounts on the length of submitted preference lists in centralized matching markets. 30 In contrast, our approach to candidates' potential preferences over positions is distribution-free, i.e., we do not make any assumption on the distribution over candidates' preference profiles.

Table 5: Condition 1 not satisfied -too few candidates

P d 0 P d 1 P d 2 P d 3 P d 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 every set J ⊆ I\{i 0 } it holds that |J| < d∈A J q d .
In this case, condition 2 is satisfied but has clearly no bite since, for each J ⊆ I \ {i 0 } with d 0 ∈ A J (e.g., J = {i 1 }), there cannot be a set K ⊆ J\J i 0 ,d 0 that satisfies the cardinality requirement of condition 2.

Example 4 Let I = {i 0 , i 1 , . . . , i 7 }, D = {d 0 , d 1 , d 2 , d 3 }, and assume that q d = 1 for each d = d 4 , and q d 3 = 4. The departments' preferences are described in Table 6.

Table 6: Condition 1 not satisfied -no perfect match

P d 0 P d 1 P d 2 P d 3 i 1 i 2 i 3 i 3 i 0 i 1 i 2 i 4 i 5 i 6 i 7
Candidate i 0 is not an impossible match for department d 0 : the matching µ such that µ(i 0 ) = d 0 , µ(i h ) = d h for h = 1, 2, 3, is comprehensive. Consider the set J = {i 1 , . . . , i 7 }.

So, |J| = 7 = d∈A J q d . For this set J, however, condition 1 is not satisfied because there cannot be a perfect match between any set J ⊆ J and the departments in A J (because, for each matching, d 3 does not fill its capacity).

Unlike Example 3, condition 2 of the definition of a block does bite. To see this, note that we need to consider all sets

K ⊆ J\{i 1 } such that |K| = |J| -s q d + 1 = 1. If K = {i 2 }
P d 3 i 1 i 2 i 3 i 3 i 0 i 1 i 2 i 4
2. Preliminaries before the proof of Theorem 2

Let P = (I, D, (P d , q d ) d∈D , A) be a proto-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 E) is an alternating path for a matching µ if it alternates matched and free edges. Given a matching µ, E) 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 candidates than µ, i.e., |{i ∈ I : µ(i) = i}| ≥ |{i ∈ I : µ (i) = i}| for any feasible matching µ in 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. 35 It follows then that finding a maximum and comprehensive matching can be done in polynomial time.

V = I ∪D and the set of edges is E = {(v, v ) ∈ V ×V : v ∈ A v }. 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,
a vertex v is neutral if either v ∈ I and µ(v) = v, or v ∈ D and |µ(v)| < q v . A path π = (v 1 , . . . , v k ) in G P (V,

Proof of Theorem 2

Remark 6 To prove Theorem 2 it is more convenient to rely on the notion of maximum matching, which has been defined in the previous sub-section. More precisely, we will use the existence of a maximum and comprehensive matching to show the necessary condition of Theorem 2 (i.e., construction of a block). Note that a maximum matching is necessarily maximal.

Necessity

Let i 0 be an impossible match for d 0 in the proto-matching problem P . We need to

show that there exists a block J at (i 0 , d 0 ), with i 0 / ∈ J. Let P be the problem that is identical to P except that in P candidate i 0 finds only acceptable d 0 . 36 Observe that if µ is such that µ(i 0 ) = d 0 and µ is maximal and comprehensive for P (resp. P ) then µ is also maximal and comprehensive for P (resp. P ). So from Proposition 2 i 0 is an impossible match for d 0 in P if, and only if, i 0 is an impossible match for d 0 in P . So it is without loss of generality that we can assume P being such that A i 0 = {d 0 }.

Let µ be a maximum and comprehensive matching in P such that A i 0 = {d 0 }. By

Remark 5, such a matching exists. So by Proposition 2 and the assumption that A i 0 = {d 0 }, µ(i 0 ) = i 0 . Hence, |µ(d 0 )| = q d 0 , otherwise µ would not be maximum. The next procedure constructs explicitly a block at (i 0 , d 0 ). To start with, define the following sets D 0 and J 1 ,

D 0 = {d ∈ D : |µ(d)| < q d } J 1 = {i ∈ I : µ(i) = i}\A D 0 .
35 See Lovász and Plummer (1986).

36 The problem P is such that P d0 = P d0 (and thus A P d0 = A d0 ), and for each d = d 0 , A P d = A d \{i 0 } and for each i, i = i 0 , iP d i if, and only if, i P d i .

In other words, D 0 is the set of departments that do not fill their capacity under the maximum and comprehensive matching µ, and the set J 1 is the set of all matched candidates minus the candidates for department in D 0 . For h ≥ 1, we define recursively the following sets,

D h = d ∈ D\ ∪ h <h D h : |µ(d) ∩ J h | < q d J h+1 = J h \A D h .
So, the set D 1 is the set of departments that are acceptable by candidates in J 1 and that do not fill their capacity with candidates in J 1 . The set J 2 is then the set of candidates in J 1 minus the candidates acceptable for departments in D 1 .

Observe that at each step we withdraw candidates, i.e., J h+1 ⊆ J h , for h ≥ 1. The inclusion is strict until we eventually reach a step such that J +1 = J , which occurs when there is a step such that D = ∅. We show later in the proof that J = ∅. Note also that A J h+1 ∩ D h = ∅, for h ≥ 0, and D h ∩ D h = ∅ whenever h = h , h, h < .

We claim that

A J = D\ ∪ h< D h . (4)
To see this, observe first that A Suppose by way of contradiction that A T A J . So there exists d ∈ A T such that d / ∈ A J . Hence, there is a candidate, say, i, such that i ∈ T and d ∈ A i , and, by Eq. ( 4), d ∈ D h for some h < . Since µ is a maximum matching and µ(i) = i it must be that |µ(d)| = q d , and thus d / ∈ D 0 . So h ≥ 1.

We then have |µ(d) ∩ J h | = q d for each h < h, and, from the definition of D h , |µ(d) ∩ J h | < q d . Therefore, there exists a candidate, say, i h , such that µ(i h ) = d, i h / ∈ J h and i ∈ J h . Since J h = J h-1 \A D h-1 we have i h ∈ A D h-1 . It follows that there is a department d h ∈ D h-1 such that i h ∈ A d h . Note that D h ∩ D h-1 = ∅ implies d h = d. We have shown that d ∈ A i , {d, d h } ⊆ A i h , so (i, d, i h , d h ) is an alternating path.

From d h ∈ D h-1 we deduce as before the existence of a candidate, say i h-1 such that

i h-1 / ∈ J h-1 and µ(i h-1 ) = d h . So i h-1 = i because µ(i) = i. Since i h ∈ J h-1 , i h-1 = i h .
Hence, (i, d, i h , d h , i h-1 ) is an alternating path. Continuing this way we eventually end up with a department d 1 ∈ D 0 and an alternating path π = (i, d, i h , d h , i h-1 , . . . , i 1 , d 1 ).

However, d 1 ∈ D 0 implies that |µ(d 1 )| < q d 1 , and thus π is an augmenting path. Berge's Theorem then implies that µ is not maximum, a contradiction. So A T ⊆ A J .

Claim: µ(d 0 ) ⊆ J .

Suppose by way of contradiction that there exists a candidate, say, i such that i ∈ µ(d 0 )

and i / ∈ J . So i ∈ A D h for some h < . So there is a department d ∈ D h such that i ∈ A d h .

Observe that (d 0 , i, d) is an alternating path. We can use the same arguments used for the previous claim to construct an alternative path (i, d, i h , d h-1 , . . . , i 2 , d 1 ) with d 1 ∈ D 0 . Therefore, since µ(i) = d 0 , i 0 ∈ A d 0 and µ(i 0 ) = i 0 , (i 0 , d 0 , i, d, i h , d h-1 . . . i 2 , d 1 ) is an augmenting path. Again applying Berge's Theorem we deduce that µ is not a maximum matching, a contradiction. So, µ(d 0 ) ⊆ J .

Let J = J ∪ T. We claim that J is a block at (i 0 , d 0 ).

Since |µ(d 0 )| = q d 0 , µ(d 0 ) ⊆ J ⊆ J implies J = ∅. By construction |µ(d)| = q d for each d ∈ A J and µ(i) = i for each i ∈ J . Moreover, A J = A J , so µ is a perfect matching between J and A J , i.e., the first condition for a block is met with the set J -where J plays the role of J in Definition 4.

It remains to show that condition 2 of a block also holds. Suppose by way of contradiction that there exists a non-empty set K, with K ⊆ J\J i 0 ,d 0 and |K| = |J| -d∈A J q d + 1, such that Hall's condition (3) is satisfied in P d 0 (J, K). This is tantamount to saying that there exists a matching µ for P d 0 (J, K) such that all admissible candidates are matched to a department. We construct the following matching µ for P . For each i / ∈ J, let µ (i) = µ(i). For each i ∈ J that is admissible in P d 0 (J, K), let µ (i) = µ(i). Finally, for each i ∈ J that is not admissible in P d 0 (J, K) let µ (i) = i. 38 Note that, since i 0 / ∈ J that P h = P h for every h ≥ 1. By construction it is clear that P 1 = P 1 since neither the realized matching, nor the realization of the preferences are used at this step. Suppose that P h = P h , for some h ≥ 2. We show that P h+1 = P h+1 .

At step h.1, notice that S h = T h , for otherwise there would be i ∈ S h \ T h or i ∈ T h \ S h . Assume without loss of generality that i ∈ S h \ T h . the construction of the sets S h and T h , together with P h = P h , imply that µ (i) = i. But since i ∈ S h , |{j : jP h d i}| = |{j : jP h d i}| < q d for any d ∈ A P h i = A P h i . Therefore, there are strictly less than q d candidates ranked higher than i in P d and matched to d under µ . So µ does not satisfy the condition (b.1 ), which contradicts the stability of µ .

At step h.2, we note that if j ∈ S h then µ(j) ∈ A P h j .40 Stability implies that j can claim any of the seats in the departments A P h j and that µ(j) is the top choice in the set A P h j according to j . The exact same argument should apply to the problem (recall that P h = P h ). Since the top choice is the same department by construction, j obtains the same department under µ . So µ(j) = µ (j) for every j ∈ S h . It also follows that the deletions are the same in both cases. So P h = P h . As we proceed with step h.3, the impossible matches are clearly the same in both problems. So P h+1 = R( P h ) = R( P h ) = P h+1 , as was to be proved.

Since the sequence of sets of market stars and reduced proto-matching problems are the same with inputs (P, µ) and (P, µ ). So any prediction obtained with (P, µ) is obtained with (P, µ ), and vice-versa, that is, µ(i) = µ (i) for any candidate i whose match is predicted.

  d) : i is an impossible match for d in P } and for each pair i, j ∈ A R(P ) d , iR(P ) d j if and only if iP d j. We shall denote by R(P ) d the ranking list of d in the proto-matching problem R(P ).

  19 http://postes.smai.emath.fr/.20 The web site is now supported by the main professional mathematical societies in France: the French Mathematical Society (SMF), the Society for Applied and Industrial Mathematics (SMAI, which hosts the web site), and the French Society of Statistics (SFdS).

  J h+1 ∩ D h = ∅, for each h ≥ 0. Hence we only need toshow that if d ∈ D\ ∪ h< D h then d ∈ A J h , for each 1 ≤ h ≤ . Let h be such that 1 ≤ h ≤ . Since d / ∈ ∪ h <h D h , it holds that d ∈ D \ ∪ h <h D h . Since d / ∈ D h , it must be necessarily true that |µ(d) ∩ J h | = q d . Hence, d ∈ A J h .Let T be the set of candidates, except i 0 , who are unmatched under µ but consider acceptable at least one department in A J ,T = {i ∈ I\{i 0 } : µ(i) = i and A i ∩ A J = ∅} Claim: If T = ∅ then A T ⊆ A J . 37

  , let us denote by d the preferences of a department d over sets of candidates. The preference d is responsive to the preference d if, for any I , I ⊆ I, I With a little abuse of terminology, we also say that A d is the set of acceptable candidates for d. Similarly, A i := {d ∈ D : (i, d) ∈ A} is the set of acceptable departments for i. For a set I of candidates, a department belongs to A I if, and only, it is acceptable for at least one candidate in I . For a set D of departments, a candidate belongs to A D if, and only if, she/he is acceptable for at least one department

			d I whenever I = I ∪ {v }\{v } for some
	v ∈ I and v / ∈ I such that v	d v , or, if |I | < q d , I	d I whenever I = I ∪ {v }
	and v	d d.
		3. Proto-matching problems
	A proto-matching problem is similar to a job market problem except that prefer-
	ences are summarized only by a list of mutually acceptable pairs from both sides of the
	market and the departments' preferences over their acceptable candidates. Formally, a
	proto-matching problem is given by a 5-tuple (I, D, (P d , q d ) d∈D , A), where I is a set of
	candidates, D a set of departments, P d a preference of department d, q d a capacity of
	department d and A ⊆ I × D a set of mutually acceptable pairs (i, d) of candidates and
	departments. In a proto-matching problem, the preference of department d, P d , is a linear
	ordering over A d , which is the subset of candidates that form mutually acceptable pairs
	with d, i.e. A in D .
	Note that the profile of departments' preferences over the acceptable candidates (and
	their capacities) is a sufficient information to describe a proto-matching problem (because
	i ∈ A d if, and only if, d ∈ A i ). Accordingly, whenever there is no risk of confusion we
	shall use the shorthand P to denote a proto-matching problem.

d := {i ∈ I : (i, d) ∈ A}.

  ∈ I × D : i ∈ A d and d ∈ A i = A (b)for every department d, and every pair of candidates i, i such that i, i ∈ A d :i d i if,and only if, iP d i

	Given a proto-matching problem P , a job market problem	with the same sets of
	candidates and departments and identical departments' capacities is P -compatible if
	(a) the sets of acceptable candidates and acceptable departments in generate the set
	of mutually acceptable pairs in P :
	(i, d)

Table 2 :

 2 A predicted matching P d 1 P d 2 Even though Proposition 5 seems straightforward, deleting matches is not innocuous for the property of impossible matches. Deleting iteratively impossible pairs one after the other can alter the matching predictions we can make, by declaring erroneously some pairs not impossible. To see this, consider the proto-matching problem depicted in Table2. It is easy to see that i 3 is an impossible match for d 1 and d 2 , and i 2 is an impossible match for d 1 (and i 1 for d 2 ). So R(P ) d 1 = i 1 and R(P ) d 2 = i 2 . The unique comprehensive matching for P that fills the available positions is µ(i 1 ) = d 1 and µ(i 2 ) = d 2 (indicated by the square boxes in Table2), thus it is the stable matching of any compatible job

	i 1	i 2
	i 3	i 3
	i 2	i 1

market problem. Note, however, that if we delete i 3 at d 1 and d 2 then i 2 is no longer an impossible match for d 1 (and i 1 for d 2 ).

  If S h is empty STOP. Otherwise, define the proto-matching problem P h such that: * for each i ∈ S h and d ∈ A P h D, the ranking list P h d is the ordering over A P h d that coincides with P h on A P h d . h.3 Construct P h+1 := R( P h ) and go to Step h + 1.

of all candidates i such that (a) i has at least 2 acceptable positions in P h ; and (b) i is ranked among the top q d candidates in every department d

∈ A P h i in the problem P h . h.2 i such that µ(i) = d, (i, d) is removed from A P h , i.e., A P h := A P h \ i ∈S h (i , d ) : d ∈ A P h i and µ(i ) = d * for each d ∈

Table 3

 3

	: Predictions

Table 4 :

 4 Rank distribution (average 1999-2013) , beyond the number of times each candidate is ranked. The first variable is the relative ranking of each candidate. A profile where most of the candidates being ranked first are also ranked only once is clearly more predictable than another profile where most of the candidates being ranked only once are at the bottom of the rank lists. The second variable relates to the overlap between the rank lists in terms of the sets of candidates being ranked. To see this, consider two candidates being ranked only twice. If these two candidates are ranked by the same departments they constitute a block for any candidate ranked below them and for the candidates ranked between them. However, they are less likely to be part of a block if they are not ranked by the same departments.

	times ranked	1	2	3	4	5	6	7 or more
	All candidates	48.3% 20.2% 12.5% 7.2% 4.4% 2.6%	5.7%
	Hired candidates 31.7% 20.6% 15.8% 11.2% 6.9% 4.7%	9.2%
	There are two variables that influence the existence of blocks (and thus of impossible
	matches)

  Hall's marriage condition (3) does not hold in P d 0 (J, K) because we cannot match i 1 .31 If K = {i 3 }, then again Hall's marriage condition does not hold in P d 0 (J, K).Indeed, either i 1 or i 2 must remain unmatched.It remains then to consider candidates in {i 4 , i 5 , i 6 , i 7 }. Routine examination shows that for any such candidate we cannot match all admissible candidates in P d 0 (J, K), which proves the claim.Example 5 Let I = {i 0 , i 1 , i 2 , i 3 , i 4 }, D = {d 0 , d 1 , d 2 , d 3 } and assume that q d = 1 for each d ∈ D. The departments' preferences are depicted in Table7. In this example candidate i 0 is not an impossible match for d 0 . Here the only possible set J satisfying condition 1 is {i 1 , i 2 , i 3 , i 4 }. Since |J| = 4 = d∈A J q d , we have to consider sets K such that |K| = 1.To see that condition does not hold it suffices to consider K = {i 4 }. The matching µ,where µ(i 1 ) = d 1 , µ(i 2 ) = d 2 and µ(i 3 ) = d 3 is such that all admissible candidates in P d 0 (J, {i 4 }), i.e., i 1 , i 2 and i 3 , are matched to a department. That is, Hall's marriage condition (3) is satisfied in P d 0 (J, {i 4 }).

Table 7 :

 7 Condition 2 not satisfied P d 0 P d 1 P d 2

A similar connection has been identified by[START_REF] Demange | Multi-item Auctions[END_REF]. They use Hall's marriage conditions to show the existence of an equilibrium assignment in the context of a multi-item auction market.

See Haeringer and Iehlé (2010).

We explain in detail in Section 5 how we can deduce the set of mutually acceptable candidatedepartment pairs.

There could be more than q d candidates ranked higher than i at d and a P -compatible job market problem such that some of these candidates have department d being their most preferred department.

Note that the proto-matching problem P (J, ∅) is simply the problem P restricted to the set of candidates J and P (I, K) is the problem P truncated at K.

The notion of block echoes a strong version of market imbalance in the spirit of[START_REF] Ashlagi | Unbalanced Random Matching Markets: the Stark Effect of Competition[END_REF]. See Section 6.

The algorithm and our results also work if the matching µ is only partially observed. If the matching of candidate i (resp. department d) is not observed then it suffices to set µ(i) = i (resp. µ(d) = d).

The market stars are extracted consistently in the algorithm. That is, if i is a market star at step h then µ(i) is still an acceptable department for the candidate i in the problem P h , and remains thus the unique acceptable department in the next steps. This can be deduced from Lemma 4 in the Appendix, which shows that µ(i) is never deleted from the list of acceptable departments of i.

We consider in the Predicting Algorithm a less severe definition of stars, that we call pseudo stars (see Section D.2 of the Web Appendix). Proposition 7 remains valid. Also, across all years, the Predicting algorithm stops after 5 to 9 steps, the average number of steps is 6.8 (i.e., 5.8 iterations of steps h.1, h.2 and h.3).

We thank a referee for suggesting this viewpoint.

Note that the reason Hall's condition does not hold in P d0 (J, K) is because i 1 cannot be matched even though i 1 is admissible at d 0 , i.e., d 0 have zero capacity does not preclude i 1 's admissibility at d 0 (see Remark 3).

It could be that T = ∅. This is the case for instance if P d0 = i 1 , i 0 , P d = i 2 , i 1 and q d0 = q d1 = 1 with I = {i 0 , i 1 , i 2 } and D = {d 0 , d 1 }. What is necessary for the proof is that, if T = ∅, there is no department in A T that is not in A J .

Note that the students in J that are not admissible in P d0 (J, K) include the students in K but may

It can be deduced from Lemma 4, which shows that µ(j) cannot be deleted from the list of acceptable departments of j.

group for helpful comments. 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 was made during the first author's visit to the Stanford Economics department, whose hospitality is gratefully acknowledged. The second author gratefully acknowledges the support of ANR-13-BSH1-0010 -DynaMITE -Appariements et Interactions Dynamiques : Théorie et Expériences (2013) and Risk Foundation (Chaire Dauphine-ENSAE-Groupama "Les particuliers face au risque").

P . A well-known result by Berge (1957) establishes that a matching is maximum if, and only if, there is no augmenting paths. We rephrase Berge's theorem in our context. 32 Theorem 3 ((adapted from) Berge, 1957) Let P and µ be respectively a proto-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 (V, E) for µ.

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

Without loss of generality we consider in the remainder only augmenting paths starting with a (neutral) candidate and ending with a (neutral) department. 33 The matching µ = µ ⊕ π is the matching obtained when updating µ with the path π, i.e., µ (i) = µ(i)

for each i / ∈ π and µ (i h ) = d h for each i h ∈ π, h = 1, . . . , k.

Lemma 1 Let µ be a comprehensive matching in P . If µ is not a maximum matching then there exists an augmenting path π such that µ = µ ⊕ π is comprehensive in P . 34

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 , d 1 , i 2 , . . . , d k ) be the minimum length augmenting path, and if there are several augmenting paths of the same length as π assume that π is one of those paths such that

Note that µ matches a strict superset of agents than µ. 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 = i h (and thus µ (j ) = d h ). Consider now the path π = (j, d h , i h+1 , . . . , d k ). Clearly, π is an augmenting path. Since h > 1, the contradiction comes from the assumption of minimality of π.

Remark 5 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 32 Berge's original theorem is stated for one-to-one matching problems. 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.

33 Let π = (v 1 , v 2 , . . . , v k ) be an augmenting path for some matching µ, and suppose that v 1 ∈ D.

Then it must be that v k ∈ I. We can then consider the path π = (v k , v k-1 , . . . , v 2 , v 1 ), which is also, by definition, an augmenting path. 34 Andersson and Ehlers (2016) use a similar result in a different context.

matching is well defined since |µ (d 0 )| ≤ q d 0 -1. It is also comprehensive in P because i ∈ Z implies µ (i) = i. If µ is not maximal, then consider the departments that do not exhaust their capacities under µ and fill these departments with the best ranked and unmatched remaining candidates (if any). That is, we can assume without loss of generality that µ is maximal. So, by Proposition 2, i 0 is not an impossible match for d 0 , a contradiction. It follows that condition 2 of a block holds and thus J is a block at (i 0 , d 0 ).

Sufficiency

The next two lemmata will be useful to prove the sufficiency part of Theorem 2.

Lemma 2 Let J be a block at (i, d) and let µ be a comprehensive matching in P d (J, ∅)

where µ(j) = j for each j ∈ J i,d . Then

and there are at most d∈A J q d -1 candidates in J that are matched to a department under µ. It follows that there exists a set K made by r unmatched candidates. Hence, µ is also a well defined feasible matching for P d (J, K). By assumption, it also holds that K ⊆ J \ J i,d . Since J is a block, Hall's marriage condition (3) does not hold for P d (J, K),

i.e., for every feasible matching µ for the problem P d (J, K) there exists an admissible candidate j ∈ J \ K such that µ (j) = j. Therefore, there exists j ∈ J\K such that µ(j) = j. So, there are at least r + 1 candidates in J who are unmatched under µ, as was to be proved.

Lemma 3 Let J be a block at (i, d) and let µ be a comprehensive matching for P d (J, ∅)

such that µ(j) = j for each j ∈ J i,d . Then there exists a matching µ that is comprehensive

and µ (j) = j for each j ∈ J i,d .

Proof From condition 1 of a block we can match d∈A J q d candidates of J in P (J, ∅).

So we can match

Let µ be a matching satisfying the conditions of the Lemma. Using Lemma 2 we have

Hence, µ is not a maximum matching in P d (J, ∅). Since µ is comprehensive in P d (J, ∅), there exists from Lemma 1 an augmenting path π such that µ = µ ⊕ π is comprehensive in P d (J, ∅). Clearly, µ satisfies Eq. ( 6). From the definition of an augmenting path, µ(j) = j implies µ (j) = j. That is, we have also µ (j) = j for each j ∈ J i,d .

Let J be a block at (i 0 , d 0 ). Suppose that there exists a matching µ comprehensive for P such that µ(i 0 ) = d 0 . Let µ be the matching such that µ(i) = µ(i) for each i ∈ J.

Clearly, µ is a feasible matching for P d (J, ∅). Moreover, µ is comprehensive for P d (J, ∅).

Indeed, if µ is not comprehensive then there exist i, j ∈ J such that µ(i) = i, µ(j) = j and iP µ(j) j. But then µ would not be comprehensive for P . Note also that µ comprehensive for P and µ(i 0 ) = d 0 imply that, for each i ∈ J such that iP d 0 i 0 , µ(i) = i.

Let r = |J| -d∈A J q d + 1. For any matching µ, let K(µ) = {i ∈ J : µ(i) = i}.

By Lemma 2, |K(µ)| > r. So by Lemma 3 there exists a matching, say, µ 1 , such that µ 1 is comprehensive for P d 0 (J, ∅) and µ 1 (i) = i for each i ∈ J such that iP = {d} for some department d, yet for some ∈ Θ(P ) and matching µ stable for

is stable for , it is obviously comprehensive for P because ∈ Θ(P ). Furthermore, i's rank in P d being lower or equal to q d implies that | µ(d)| < q d , which contradicts that µ satisfies the condition (b.1) of stability. So µ(i) = d for some d = d (and thus d ∈ A i ).

By construction, d / ∈ A R(P ) i implies that i is an impossible match for d , which contradicts

(⇒) Suppose that for every ∈ Θ(P ) and every matching µ stable for , µ(i) = d.

To begin with, suppose that i is not among the top q d candidates in P d . Let ∈ Θ(P ) be such that d is the top choice of each candidate j whose rank in P d is lower or equal to q d .

Clearly, if µ is stable for then µ(j) = d for any candidate j ranked lower or equal to q d in P d . So i is not always matched to d at any stable matching, for any P -compatible job market problem. Suppose now that there exists

. So i is not an impossible match for d , and thus there exists by definition ∈ Θ(P ) and a matching µ stable for such that µ(i) = d , which contradicts our initial assumption.

= ∅ then i is an impossible match for each department d ∈ A i . Hence, candidate i cannot be matched to any department in A i , under any stable matching for ∈ Θ(P ). Conversely, if i is always unmatched under any stable matching then i is an impossible match for any d ∈ A i , which implies A

3 . Since the construction of the reduced problem R(P ) is the same for any P -compatible job market problem, the result follows directly from the definition of impossible matches.

The next lemma will be key to prove Proposition 6.

Lemma 4 Let P be a proto-matching problem and ∈ Θ(P ) a job market problem. Let µ be a matching stable for . The following two statements hold, for any step h ≥ 1 of the Predicting Algorithm with input (P, µ):

2. The matching µ is maximal and comprehensive for P h Proof 1 .

The first statement directly follows from the definition of the Predicting Algorithm. More precise arguments can be found in the proof of statement 2.

.

Comprehensiveness for step h = 1 directly follows from the stability of µ.

Weakly non-wastefulness for step h = 1 follows immediately from the condition (b. i , which is a contradiction. Suppose now that µ(i) = i, yet the prediction is d, predicted at some step h. Since d is a prediction, the department is acceptable at step h for candidate i, d ∈ A P h i , and |{j : jP h d i}| < q d . By Lemma 4, µ is comprehensive for the problem P h , so µ(i) = i implies that no candidate ranked below i in P h d is matched to d under µ. Again by Lemma 4, candidates j such µ(j) = d cannot be deleted from P h d , at any step h ≤ h. So we must have |µ(d)| < q d , which contradicts that µ is maximal for P .

Proof of Proposition 7

The statements of the proposition are deduced from the following lines of arguments.

Denote by P h and P h the proto-matching problems obtained at step h in the algorithm with input (P, µ) and (P, µ ), respectively. Similarly, for h ≥ 2, let S h , and T h , denote the set of market stars for (P, µ) and (P, µ ), respectively. We first show by induction