Stability and strategy-proofness for college admissions

Stability and strategy-proofness for college admissions

Stability and strategy-proofness for college admissions
with an eligibility criterion∗
Azar Abizada† and Siwei Chen‡
First draft: August 15, 2010
This version: February 23, 2012
Abstract
We study college admissions with an eligibility criterion. Each student receives a
score from a central exam. The students are divided into two groups: those who are
eligible to apply to colleges, and those who are not. Eligibility respects the students’
scores. Each college has a strict preference relation over the sets of students and each
student has a strict preference relation over the colleges. We extend the model studied
by Perach and Rothblum (2010) to a general case where different students may obtain
the same scores from the central exam. We introduce three notions of stability that
respect eligibility. We define three new rules based on the McVitie-Wilson algorithm,
each of which satisfies different notions of stability. We also study an incentive comparability requirement.
JEL Classification: C78, D63
Keywords: eligibility, quasi-stability, justifiable-stability, strategy-proofness, responsive
preferences.
∗
We would like to thank William Thomson for his guidance and invaluable comments. We also would
like to thank Youngsub Chun and Vikram Manjunath for their useful comments.
†
Department of Economics, University of Rochester. [email protected]
‡
Department of Economics, University of Rochester. [email protected]
1
1
Introduction
We study college admissions. There are a group of students and a group of colleges.
Each student has the outside option of not attending college, and has strict preferences over
colleges and this option. Each college has a certain number of seats, and has the outside
option of admitting no students. It has strict preferences over the sets of students and empty
class. In countries like China, France, South Korea, Turkey, Greece, Azerbaijan, Albania,
etc, college admission is processed through a central education system. The central authority
administers an exam. All students must take this exam. Once the exam scores are revealed,
the central education system decides which students are eligible to apply to colleges. To be
fair, the eligibility criterion should respect the students’ scores. It would be unfair to declare
a student eligible if he has a lower score than some other student who is declared ineligible.
We model some eligibility criteria in college admissions. A rule is a systematic way to assign
students to colleges. We study rules that respect the eligibility criteria.
In Turkey, for a long time, the central exam had two rounds. Using the results of the
first round, the central authority decided which students were eligible to apply to colleges.
Once eligible students were identified, the second round was administered to assign students
to colleges. Note that the preferences of the colleges can differ from one another and do not
necessarily depend on the scores of the students. In South Korea, after the first round of
the exam, which also identifies eligible students, some colleges may conduct college-specific
exams. Preferences over students are based on students’ scores from this exam. As we can
see, eligibility criteria are widely used during college admissions in many countries.
College admission problems are first studied by Gale and Shapley (1962) in a seminal
paper in which they proposed the now well-known deferred-acceptance algorithm. Many
variants and extensions of the original model with useful applications have been studied
(Knuth, 1976; Roth, 1984; Gustfield and Irving, 1989; Roth and Sotomayor, 1990; Balinski
and Sönmez, 1999; Roth, 2002; Abdulkadiroǧlu and Sönmez, 2003; Abdulkadiroǧlu et al.,
2005a; Abdulkadiroǧlu et al., 2005b; Roth, 2008; and references therein.).
It is only recently that college admission problems with an entrance criterion have been
studied (Perach, Polak and Rothblum, 2008; Perach and Rothblum, 2010). In the paper
by Perach and Rothblum (2010), they propose a rule that respects an eligibility criterion
and produces a “stable” outcome. They also study an incentive compatibility requirement,
2
“strategy-proofness”. The rule proposed by them satisfies it.
One of the critical assumptions in Perach et al. (2008) and Perach and Rothblum (2010)
is that students have distinct scores from the exam. In China, every year approximately 10
million students take college admission exam. In Turkey, this number is 500 thousand. It
is highly likely that some students will obtain the same score in the exam. Therefore, we
should not ignore this possibility. We generalize the model to allow students to obtain the
same score.
For two-sided matching problems, allowing indifference in preferences result in many
complications. In most of the literature, it is assumed that agents have strict preferences
over agents on the opposite side. Allowing students to obtain the same score in the entrance
exam causes similar difficulties.
A rule is a function assigning students to colleges. We define three stability requirements
of the rule. Each respects eligibility. The first requirement is defined in the following way:
no pair of a college and an eligible student prefer assignment at which they are matched
to each other to their current assignments. The second notion is a weakening of the first
one that allows the highest score of an ineligible students and the lowest score of eligible
students coincide. The last notion respects not only eligibility but also score rankings: no
pair of a college K and an eligible student A are such that the student A prefers the college
K to his assignment, and the college K is assigned either a student B with a lower score
than student A’s or some other student C with the same score as student A, whom college
K finds less desirable than A (i.e. college K prefers student A to student C). We are also
interested in a strong incentive compatibility requirement that no student can ever benefit
by misrepresenting his preference.
We look for rules that satisfy our stability notions and the incentive compatibility requirement. We define three new rules. Our first rule satisfies the first stability notion, but
is not incentive compatible. Our second rule only satisfies the second stability notion which
is weaker than the first one, but is incentive compatible. Our last rule satisfies the third
stability notion, and is also incentive compatible. We discuss other properties of our rules
and the results of previous literature that extend to our model.
The rest of the paper is organized as follows: in Section 2, we define the model. In
Section 3, we define axioms. In Section 4, we provide rules. In Section 5 we state and prove
our main results.
3
2
Model
There are a finite set of students S = {s1 , s2 , . . . , sl } and a finite set of colleges
C = {c1 , c2 , . . . , cn }. Each student has the option of not attending college. We denote
this option ∅c . Similarly, each college has the option of closing down. We denote this option ∅s . Each student s ∈ S has a strict preference relation Rs over the colleges and staying
S
at home, i.e. Rs is a strict order on C {∅c }. Let RS ∈ R S be the preference profile of
the students. Each college c has strict preferences Rc over all subsets of students, 2S . The
preferences of a college are responsive to its preferences over individual students if
the following two conditions are satisfied (Roth 1985):
(i) For each s ∈ S, each S̄ ⊆ S \ {s}, we have S̄ ∪ {s} Rc S̄ if and only if s Rc ∅s ,
(ii) For each pair s, s0 ∈ S, each S̄ ⊆ S \ {s, s0 }, we have S̄ ∪ {s} Rc S̄ ∪ {s0 } if and
only if s Rc s0 .
Let RC ∈ R C be the preference profile of the colleges. Let N ≡ S
S
C. Let R ≡
(Ri )i∈N ∈ R N be a preference profile of N . We use R and (RS , RC ) interchangeably.
Each student s ∈ S has a score ms ∈ R+ from a central exam. Let m ≡ (ms1 , ms2 , . . . , msl )
be the list of scores. Each college c ∈ C has a capacity qc ∈ Z+ . Let q ≡ (qc1 , qc2 , . . . , qcn )
be the list of capacities. We assume that ∅c has an infinite capacity, i.e. q∅c = ∞.
A problem is a list π ≡ (S, C, R, m, q). Let Π be the set of all problems. An assignment
S
for π is a mapping µ : S → C {∅c } such that for each c ∈ C, the number of students
assigned to it does not exceed its capacity, i.e. |µ−1 (c)| ≤ qc . Let I ⊆ S. We refer to students
who are not in I as eligible, and to students in I as ineligible. An outcome for π is
a pair (µ, I). Let M (µ) ≡ {s ∈ S : µ(s) ∈ C} be the set of students assigned to colleges
at µ. Let U (µ) ≡ S \ M (µ) be the set of students who are not attending college at µ. Let
R(µ, I) ≡ (S \ I) \ M (µ) be the set of rejected students at (µ, I). Let O(π) be the set of
all outcomes for π. A rule associates each problem with an outcome for it. Formally, it is a
[
mapping ϕ : Π →
O(π) such that for each π ∈ Π, ϕ(π) ∈ O(π).
π∈Π
4
3
Axioms
Let π = (S, C, R, m, q) be a problem. Let (µ, I) be an outcome for π. Let µ0 be an
assignment for π. Let ϕ be a rule.
• Our first requirement is that eligibility should respect students’ scores.
Outcome (µ, I) is score-respecting for π if for each s ∈ I and each s0 ∈
/ I, ms < ms0 .
• Our next requirement is a weaker version of our first requirement.
Outcome (µ, I) is weakly score-respecting for π if for each s ∈ I and each s0 ∈
/ I,
ms ≤ ms0 .
• Our next requirement says that and outcome should not waste any seat.
Outcome (µ, I) is non-wasteful for π if I 6= ∅, then for each c ∈ C, |µ−1 (c)| = qc .
Before defining our stability requirements, we define several notions which include stability notion for standard college admission problems.
College c is acceptable to student s if c Rs ∅c . Let Cs be the set of acceptable colleges for s. Student s is acceptable to college c if s Rc ∅s . Let Sc be the set of acceptable
students for c. Student s and college c are mutually acceptable if (s, c) ∈ Sc × Cs .
A pair (s, c) ∈ S × C blocks µ for π if
1. c Ps µ(s);
2. either s ∈ Sc and |µ−1 (c)| < qc , or there is s0 ∈ µ−1 (c) such that s Pc s0 .
Assignment µ is stable for π if
1. for each pair (s, µ(s)) ∈ S × C, s and µ(s) are mutually acceptable;
5
2. there is no pair (s, c) ∈ S × C that blocks µ for π.
Let St(π) be the set of all stable assignments for π.
Next, we define our three stability requirements.
• The first requirement says that the outcome should be non-wasteful and score-respecting,
and each matched pair should prefer each other to the outside options, and there should
exist no pair of a college and an eligible student that blocks the assignment.
Outcome (µ, I) is quasi-stable for π if
1. (µ, I) is non-wasteful and score-respecting for π;
2. for each pair (s, µ(s)) ∈ S × C, s and µ(s) are mutually acceptable;
3. there is no pair (s, c) ∈ (S \ I) × C that blocks µ for π.
Let QSt(π) be the set of all quasi-stable outcomes for π.
Quasi-stability: For each π ∈ Π, ϕ(π) ∈ QSt(π).
• Our second stability requirement is a weakening of quasi-stability: the only difference
is that it only requires the outcome to be weakly score respecting, keeping the rest of the
definition the same.
Outcome (µ, I) is weakly quasi-stable for π if
1. (µ, I) is non-wasteful and weakly score-respecting for π;
2. for each pair (s, µ(s)) ∈ S × C, s and µ(s) are mutually acceptable;
3. there is no pair (s, c) ∈ (S \ I) × C that blocks µ for π.
Let wQSt(π) be the set of all weakly quasi-stable outcomes for π.
Weak quasi-stability: For each π ∈ Π, ϕ(π) ∈ wQSt(π).
• Our last stability requirement says that each matched pair should prefer each other to
6
the outside options, and the scores of the students should be considered in possible blockings.
Outcome (µ, I) is justifiably-stable for π if
1. for each pair (s, µ(s)) ∈ S × C, s and µ(s) are mutually acceptable;
2. for each s ∈ S and each c ∈ C, if c Ps µ(s), then either s ∈
/ Sc , or |µ−1 (c)| = qc and for
each s0 ∈ µ−1 (c), either (i) ms0 > ms , or (ii) ms = ms0 and s0 Pc s.
Let J St(π) be the set of all justifiably-stable outcomes for π.
Justifiable-stability: For each π ∈ Π, ϕ(π) ∈ JSt(π).
Next we define an incentive compatibility requirement and a natural fairness requirement.
• No student should ever benefit from misrepresenting his preference.
Strategy-proofness: For each (S, C, R, m, q) ∈ Π, each s ∈ S, and each Rs0 ∈ Rs , if
(µ, I) ≡ ϕ(S, C, R, m, q) and (µ0 , I 0 ) ≡ ϕ(S, C, (Rs0 , R−s , RC ), m, q), then µ(s) Rs µ0 (s).
• Two students with the same scores should be treated in the same way: either both eligible or both ineligible.
Equal treatment of equals: For each (S, C, R, m, q) ∈ Π and each pair s, s0 ∈ S with
T
ms = ms0 , if (µ, I) ≡ ϕ(S, C, R, m, q), then either {s, s0 } I = ∅ or {s, s0 } ⊂ I.
4
Rules
Let σ : S → N be an order on S such that for each pair s, s0 ∈ S, we have σ(s) 6= σ(s0 ).
For each s ∈ S, let σ(s) denote the order of s. Let Σ be the set of all possible orders on S.
In this section we introduce three rules. All three rules are based on the McVitie-Wilson
algorithm. We first recall the algorithm (McVitie and Wilson, 1971; Perach and Rothblum,
2010).
7
• At each step of the algorithm, we pick a student according to a predetermined order
and let the student apply to his most preferred college. If either the college has an empty
seat and the student is acceptable to it, or the college is full but the student is preferred by
the college to a previously admitted student, then the student is admitted by the college.
Admissions at each step are tentative and may be withdrawn at the following steps. For each
unassigned student, if there is a college that is acceptable to the student and hasn’t rejected
him, then we can select this student at some later step. The algorithm stops when each of
the unassigned students has been rejected by all his acceptable colleges, or no unassigned
students are left.
Let σ ∈ Σ. Let R ∈ R N .
The McVitie-Wilson rule, M W σ :
For each t ∈ Z+ and each c ∈ C ∪ {∅c }, let Mtc be the set of students assigned to college c
at Step t. For each t ∈ Z+ , let Ut be the set of unassigned students at Step t.
Step 0: For each c ∈ C ∪ {∅c }, let M0c ≡ ∅. Let U0 ≡ S.
Step 1: Let s1 ≡ min σ(s). Select s1 and let him apply to his most preferred college;
s∈U0
call it c1 .
(i) If s1 ∈ Sc1 and |M0c1 | < qc1 , then s1 is assigned to c1 . Let U1 ≡ U0 \ {s1 }, M1c1 ≡ {s1 },
and for each c 6= c1 , M1c ≡ ∅.
(ii) If either s1 ∈
/ Sc1 or |M0c1 | = qc1 , then s1 is rejected by c1 . Let U1 ≡ U0 and for each
c ∈ C ∪ {∅c }, M1c ≡ ∅.
Step 2: Let s2 ≡ min σ(s). Select s2 [Note that s2 can be the same as s1 .] and let
s∈U1
him to his most preferred college; call it c2 .
(i) If s2 ∈ Sc2 and |M1c2 | < qc2 , then s2 is assigned to c2 . Let U2 ≡ U1 \ {s2 }, M2c2 ≡
M1c2 ∪ {s2 }, and for each c 6= c2 , M2c ≡ M1c .
(ii) If s2 ∈ Sc2 , |M1c2 | = qc2 , and there is s ∈ M1c2 such that s2 Pc2 s, then s2 is assigned
to c2 and s is rejected by c2 . Let U2 ≡ (U1 \ {s2 }) ∪ {s}, M2c2 ≡ (M1c2 ∪ {s2 }) \ {s} and for
each c 6= c2 , M2c ≡ M1c .
8
(iii) If either s2 ∈
/ Sc2 , or |M1c2 | = qc2 and for each s ∈ M1c2 , s Pc2 s2 , then s2 is rejected
by c2 . Let U2 ≡ U1 , and for each c ∈ C ∪ {∅c }, M2c ≡ M1c .
Step t = 3, 4 . . .: Let st ≡ min σ(s). Select st [Note that st can be the same as sk
s∈Ut−1
for any k < t.] and let him apply to his most preferred college; call it ct .
ct
| < qct , then st is assigned to ct . Let Ut ≡ Ut−1 \ {st }, Mtct ≡
(i) If st ∈ Sct and |Mt−1
ct
c
∪ {st }, and for each c 6= ct , Mtc ≡ Mt−1
.
Mt−1
ct
ct
such that st Pct s, then st is assigned
| = qct , and there is s ∈ Mt−1
(ii) If st ∈ Sct , |Mt−1
ct
∪ {st }) \ {s} and for
to ct and s is rejected by ct . Let Ut ≡ (Ut−1 \ {st }) ∪ {s}, Mtct ≡ (Mt−1
c
.
each c 6= ct , Mtc ≡ Mt−1
ct
ct
(iii) If either st ∈
/ Sct , or |Mt−1
| = qct and there for each s ∈ Mt−1
, s Pct st , then st is
c
.
rejected by ct . Let Ut ≡ Ut−1 , and for each c ∈ C ∪ {∅c }, Mtc ≡ Mt−1
Let t∗ be such that Ut∗ −1 6= ∅ and Ut∗ = ∅. The algorithm stops at Step t∗ .
For each c ∈ C ∪ {∅c } and each s ∈ Mtc∗ −1 , let µ(s) ≡ c. Then, M W σ (S, C, R, q) ≡ µ.
0
Remark 1 For each pair σ, σ 0 ∈ Σ, for each π ∈ Π, we have M W σ (π) = M W σ (π).
The next proposition states the equivalence between the McVitie-Wilson rule and the
Deferred-Acceptance rule (McVitie and Wilson (1971), Roth and Sotomayor (1990)).
Proposition 1 The McVitie-Wilson rule coincides with the student-proposing DeferredAcceptance rule.
Remark 2 The McVitie-Wilson rule is stable and strategy-proof.
Since, the McVitie-Wilson rule satisfies several desirable properties for standard college
admission problems, we will search for natural extensions of this rule for our model. Next
three rules we define are the most natural ones.
• Our first rule is based on an algorithm constructed in the following way. We initially
declare all the students ineligible. At Step 1, we select the ineligible students whose scores
are the highest and declare them eligible. We apply the M-W algorithm to the problem
9
involving only these students. Step 1 ends when the M-W algorithm stops. If some ineligible
students are left unassigned and some seats are left empty, we cancel the assignments made
at this step and move to the next step. At Step 2 we select the ineligible students whose
scores are the highest [Note that overall, these students are the ones with the second highest
score.] and declare them eligible. We apply the M-W algorithm to the problem involving
only eligible students. If at the end of the step, some ineligible students are left unassigned
and some seats are left empty, we cancel the assignments made at this step and move to the
next step. We repeat the process. The algorithm stops when either no ineligible student is
left unassigned, or no seat is left empty.
The High-to-Low rule with deferred acceptance, HtLDA:
For each t ∈ Z+ , let It be the set of ineligible students at Step t, and Et the set of eligible
students at Step t.
Step 0: Let I0 ≡ S and E0 ≡ ∅.
Step 1: Let S1 ≡ {s ∈ I0 | ∀s0 ∈ I0 , ms ≥ ms0 }. [Note that S1 may be a singleton.]
Let I1 ≡ I0 \ S1 and E1 ≡ S1 .
Let µ1 ≡ M W (E1 , C, (RE1 , RC ), q).
If either for each c ∈ C, |µ−1
1 (c)| = qc , or I1 = ∅, STOP. Otherwise proceed to Step 2.
Step 2: Let S2 ≡ {s ∈ I1 | ∀s0 ∈ I1 , ms ≥ ms0 }. Let I2 ≡ I1 \ S2 and E2 ≡ E1 ∪ S2 .
Let µ2 ≡ M W (E2 , C, (RE2 , RC ), q).
If either for each c ∈ C, |µ−1
2 (c)| = qc , or I2 = ∅, STOP. Otherwise proceed to Step 3.
Step t= 3, 4,...: Let St ≡ {s ∈ It−1 | ∀s0 ∈ It−1 , ms ≥ ms0 }. Let It ≡ It−1 \ St and
Et ≡ Et−1 ∪ St .
Let µt = M W (Et , C, (REt , RC ), q).
If either for each c ∈ C, |µ−1
t (c)| = qc , or It = ∅, STOP. Otherwise proceed to Step t + 1.
Let t∗ be the step at which the algorithm stops. Let µt∗ ≡ M W (Et∗ , C, (REt∗ , RC ), q).
Then, HtLDA(S, C, R, m, q) = (µt∗ , It∗ ).
10
• Our second rule is similar to the HtLDA rule. The only difference is that in the algorithm through which the rule is defined, we select the students one by one. The algorithm
is constructed in the following way. We initially declare all students ineligible. At Step 1,
if there is only one ineligible student whose score is the highest, we select him. If there are
more than one ineligible student whose score is the highest, we select one of them according
to a predetermined order. We declare this student eligible. We apply the M-W algorithm
to the problem involving only this student. Step 1 ends when the M-W algorithm stops.
If some ineligible students are left unassigned and some seats are left empty, we cancel the
assignments made at this step and move to the next step. At Step 2, we select an ineligible
student whose score is the highest. Once again, if there are more than one ineligible student
whose score is the highest, we select one of them according to a predetermined order. We
declare this student eligible. We apply the M-W algorithm to the problem involving only
eligible students. If at the end of the step, some ineligible students are left unassigned and
some seats are left empty, we cancel the assignments made at this step and move to the next
step. We repeat the process. The algorithm stops when either no ineligible student is left
unassigned, or no seat is left empty.
Let σ ∈ Σ. Let R ∈ R N .
The Modified High-to-Low rule with deferred acceptance, M HtLDAσ :
Let R ∈ R N . For each t ∈ Z+ , let It be the set of ineligible students at Step t, and Et the
set of eligible students at Step t (Note that Et ≡ S\It ).
Step 0: Let I0 ≡ S and E0 ≡ ∅.
Step 1: Let S1 ≡ {s ∈ I0 | ∀s0 ∈ I0 , ms ≥ ms0 } [Note that S1 may be a singleton].
Let s1 ≡ min σ(s). Select s1 and let I1 ≡ I0 \ {s1 } and E1 ≡ {s1 }.
s∈S1
Let µ1 ≡ M W (E1 , C, (RE1 , RC ), q).
If either for each c ∈ C, |µ−1
1 (c)| = qc , or I1 = ∅, STOP. Otherwise proceed to Step 2.
Step 2: Let S2 ≡ {s ∈ I1 | ∀s0 ∈ I1 , ms ≥ ms0 }. Let s2 ≡ min σ(s). Select s2 and
s∈S2
11
let I2 ≡ I1 \ {s2 } and E2 ≡ E1 ∪ {s2 }.
Let µ2 ≡ M W (E2 , C, (RE2 , RC ), q).
If either for each c ∈ C, |µ−1
2 (c)| = qc , or I2 = ∅, STOP. Otherwise proceed to Step 3.
Step t=3, 4, ...: Let St ≡ {s ∈ It−1 | ∀s0 ∈ It−1 , ms ≥ ms0 }. Let st ≡ min σ(s). Ses∈St
lect st and let It ≡ It−1 \ {st } and Et ≡ Et−1 ∪ {st }.
Let µt = M W (Et , C, (REt , RC ), q).
If either for each c ∈ C, |µ−1
t (c)| = qc , or It = ∅, STOP. Otherwise proceed to Step t + 1.
Let t∗ be the step at which the algorithm stops. Let µt∗ ≡ M W (Et∗ , C, (REt∗ , RC ), q).
Then, M HtLDAσ (S, C, R, m, q) = (µt∗ , It∗ ).
0
Remark 3 There are σ, σ 0 ∈ Σ, and π ∈ Π, such that M HtLDAσ (π) 6= M HtLDAσ (π).
• Our next rule is used in college admissions in many countries (China, South Korea, Azerbaijan until 2010 etc.). It is defined through an algorithm, which we construct in the following
way. We initially declare all students ineligible. At Step 1, we select the ineligible students
whose scores are the highest and declare them eligible. We apply the M-W algorithm to the
problem involving only these students. Step 1 ends when the M-W algorithm stops. Assignments made by the M-W algorithm at this step are finalized. If some ineligible students are
left unassigned and some seats are left empty, we adjust the capacities of each college to the
number of empty seats and move to the next step. At Step 2, we select the ineligible students
whose scores are the highest, [Note that overall, these students are the ones with the second
highest score.] and declare them eligible. We apply the M-W algorithm to the problem
involving only these students. Step 2 ends when the M-W algorithm stops. Assignments
made by the M-W algorithm at this step are finalized. If some ineligible students are left
unassigned and some seats are left empty, we move to the next step. We repeat the process.
The algorithm stops when either no ineligible student is left unassigned, or no seat is left
empty.
The High-to-Low rule with immediate acceptance, HtLIA:
For each t ∈ Z+ , let It be the set of ineligible students at Step t, and Et the set of eligible
12
students at Step t.
Step 0: Let I0 ≡ S, and E0 ≡ ∅.
Step 1: Let E1 ≡ {s ∈ I0 | ∀s0 ∈ I0 , ms ≥ ms0 }. [Note that S1 may be a singleton.]
Let I1 ≡ I0 \ E1 . For each c ∈ C, let qc1 ≡ qc . Let q 1 ≡ (qc11 , qc12 , . . . , qc1n ).
Let µ1 ≡ M W (E1 , C, (RE1 , RC ), q 1 ).
1
If either for each c ∈ C, |µ−1
1 (c)| = qc , or I1 = ∅, STOP. Otherwise proceed to Step 2.
Step 2: Let E2 ≡ {s ∈ I1 | ∀s0 ∈ I1 , ms ≥ ms0 }. Let I2 ≡ I1 \ E2 . For each c ∈ C
2
2
2
2
let qc2 ≡ qc1 − |µ−1
1 (c)|. Let q ≡ (qc1 , qc2 , . . . , qcn ).
Let µ2 ≡ M W (E2 , C, (RE2 , RC ), q 2 ).
2
If either for each c ∈ C, |µ−1
2 (c)| = qc , or I2 = ∅, STOP. Otherwise proceed to Step 3.
Step t= 3, 4,...: Let Et ≡ {s ∈ It−1 | ∀s0 ∈ It−1 , ms ≥ ms0 }. Let It ≡ It−1 \ Et . For
t
t
t
t
each c ∈ C let qct ≡ qct−1 − |µ−1
t−1 (c)|. Let q ≡ (qc1 , qc2 , . . . , qcn ).
Let µt = M W (Et , C, (REt , RC ), q t ).
t
If either for each c ∈ C, |µ−1
t (c)| = qc , or It = ∅, STOP. Otherwise proceed to Step t + 1.
Let t∗ be the step at which the algorithm stops. Let µ be defined as follows: for each
s ∈ S, if there is t ∈ {1, 2, ... , t∗ } such that s ∈ Et , then µ(s) ≡ µt (s); otherwise µ(s) ≡ ∅c .
Then, HtLIA(S, C, R, m, q) = (µ, It∗ ).
Next, we discuss the relation between HtLDA and HtLIA rules.
Proposition 2 For each π ∈ Π, if (µ, I) ≡ HtLDA(π) and (µ0 , I 0 ) ≡ HtLIA(π), then if
for each pair s, s0 ∈ S \ I, we have ms = ms0 , then HtLDA(π) = HtLIA(π).
5
Main Results
In this section, we present out main results. We study stability and incentive compatibil-
ity for each of the three rules. We also extend some results of Perach and Rothblum (2010)
to this more general model.
13
Theorem 1 The High-to-Low rule with deferred acceptance, HtLDA, is quasi-stable.
Proof. Let π = (S, C, R, m, q) ∈ Π. Let (µ, I) ≡ HtLDA(S, C, R, m, q). By the definition of HtLDA, M W (S \ I, C, (RS\I , RC ), q) = µ. Since M W = DA and DA is stable,
µ ∈ St(S \ I, C, (RS\I , RC ), m, q). Because the students are selected in a decreasing order
of scores in the I-M-W algorithm, the first condition of plausibility is satisfied. The I-M-W
algorithm stops when either there are no ineligible students left, or there are no empty seats
left. This implies the second condition of plausibility. Thus, HtLDA is quasi-stable.
Our next theorem states some properties of the HtLDA rule. We introduce two notions:
the maximal set of ineligible students at quasi-stable outcomes, I ∗ (π) ≡ {s ∈ S : there is
some (µ, I) ∈ QSt(π) such that s ∈ I}, and the minimal set of rejected students at quasistable outcomes, Let R∗ (π) ≡ {s ∈ S : for each (µ, I) ∈ QSt(π), s ∈ R(µ, I)}.
An assignment µ (weakly) eligibility-dominates µ0 if for each s ∈ M (µ) \ M (µ0 ) and
each s0 ∈ M (µ0 ) \ M (µ), we have ms > (≥) ms0 .
An assignment µ ∈ St(π) is student-optimal in St(π) if for each µ0 ∈ St(π) and each
s ∈ S, µ(s) Rs µ0 (s).
Theorem 2 For each π = (S, C, R, m, q) ∈ Π, if (µ, I) ≡ HtLDA(π), then
1. I = I ∗ (π);
2. R(µ, I) = R∗ (π);
3. For each (µ0 , I 0 ) ∈ QSt(π), µ eligibility-dominates µ0 ;
4. For each (µ0 , I 0 ) ∈ QSt(π) and each s ∈ S \ I, we have µ(s) Rs µ0 (s).
Proof.
Statement 1. By the definition of I ∗ (π), I ⊆ I ∗ (π). Suppose by contradiction that there
are π = (S, C, R, m, q) ∈ Π, (µ0 , I 0 ) ∈ QSt(π), and s ∈ S such that s ∈ I 0 and s ∈
/ I. The case
I = ∅ is trivial. Let I 6= ∅. Let µ00 ≡ M W (S \ I, C, (RS\I , RC ), q). Let b ≡ max{ms : s ∈ I}.
Let b0 ≡ max{ms : s ∈ I 0 }.
14
Step 1. Since the I-M-W algorithm terminates at b < b0 for π, there is c∗ ∈ C such that
|µ00−1 (c∗ )| < qc∗ . Since (µ0 , I 0 ) ∈ QSt(π), then for each c ∈ C, |µ0−1 (c)| = qc . Thus, there are
s1 ∈ S and c1 ∈ C such that µ0 (s1 ) = c1 and µ00 (s1 ) = ∅c .
Step 2. Since c1 Ps1 ∅c and µ00 ∈ St(S\I 0 , C, (RS\I 0 , RC ), mS\I 0 , q), we have |µ00−1 (c1 )}| = qc1 ,
and for each s ∈ µ00−1 (c1 ), s Pc1 s1 . Then, µ0 ∈ QSt(π) implies that there are s2 ∈ S and
c2 ∈ C such that µ0 (s2 ) = c2 , µ00 (s2 ) = c1 , and c2 Ps2 c1 .
Step 3. Since c2 Ps2 c1 and µ00 ∈ St(S\I 0 , C, (RS\I 0 , RC ), mS\I 0 , q), we have |µ00−1 (c2 )| = qc2 ,
and for each s ∈ µ00−1 (c2 ), s Pc2 s2 . Then, µ0 ∈ QSt(π) implies that there are s3 ∈ S and
c3 ∈ C such that µ0 (s3 ) = c3 , µ00 (s3 ) = c2 , and c3 Ps3 c2 .
Step 4. · · · · · ·
Repeating the argument, we obtain that there are s ∈ S and c, c ∈ C such that µ0 (s) = c,
µ00 (s) = c, c Ps c, and |µ00−1 (c)| < qc . Thus, the pair (s, c) blocks µ00 for (S \ I 0 , C, (RS\I 0 , RC ), mS\I 0 , q).
This contradicts the fact that µ00 ∈ St(S \ I 0 , C, (RS\I 0 , RC ), mS\I 0 , q).
Statement 2. Suppose by contradiction that there are π = (S, C, R, m, q) ∈ Π, (µ0 , I 0 ) ∈
QSt(π), and s1 ∈ S such that s1 ∈ R(µ, I), but s1 ∈
/ R(µ0 , I 0 ). Let b ≡ max{ms : s ∈ I}.
Let b0 = max{ms : s ∈ I 0 }.
Step 1. By part 1, b0 ≤ b. Since s1 ∈
/ R(µ0 , I 0 ), there is c1 ∈ C such that µ0 (s1 ) = c1 .
Since (µ, I) ∈ QSt(π) and c1 Ps1 ∅c , we have |µ−1 (c)}| = qc , and for each s ∈ µ−1 (c), s Pc1 s1 .
Step 2. Since(µ0 , I 0 ) ∈ QSt(π), there are s2 ∈ S and c2 ∈ C such that µ(s2 ) = c1 ,
µ0 (s2 ) = c2 , and c2 Ps2 c1 . Since (µ, I) ∈ QSt(π), we have |µ−1 (c2 )| = qc2 , and for
each s ∈ µ−1 (c2 ), s Pc2 s2 .
Step 3. Since(µ0 , I 0 ) ∈ QSt(π), there are s3 ∈ S and c3 ∈ C such that µ(s3 ) = c2 ,
µ0 (s3 ) = c3 , and c3 Ps3 c2 . Since (µ, I) ∈ QSt(π), we have |µ−1 (c3 )| = qc3 , and for
each s ∈ µ−1 (c3 ), s Pc3 s3 .
Step 4. · · · · · ·
Repeating the argument, we end up with one of the following two cases:
Case 1: There are s ∈ S and c ∈ C such that µ0 (s) = c, |µ−1 (c)| = qc , and for each
s ∈ µ−1 (c) and each c ∈ C, we have s Pc s and c Rs c. Thus, there is s ∈ S such that
µ(s) = c and µ0 (s) = c 6= c. Since c Ps c and s Pc s, the pair (s, c) blocks µ0 for π. This
contradicts the fact that (µ0 , I 0 ) ∈ QSt(π).
15
Case 2: There are s, s ∈ S and c, c ∈ C such that µ(s) = c, µ0 (s) = c, c Ps c, µ(s) = c,
and µ0 (s) = ∅c . Since (µ, I) ∈ QSt(π), we have s Pc s. Since c Ps ∅c , the pair (s, c) blocks µ0
for π. This contradicts the fact that (µ0 , I 0 ) ∈ QSt(π).
Statement 3. Let (µ0 , I 0 ) ∈ QSt(π) and (µ0 , I 0 ) 6= (µ, I). Let b ≡ max{ms : s ∈ I}. We
need to show that for each s ∈ M (µ) \ M (µ0 ) and each s0 ∈ M (µ0 ) \ M (µ), ms > b ≥ ms0 . By
plausibility, for each s ∈ M , ms > b. Suppose by contradiction that there is s0 ∈ M (µ0 )\M (µ)
such that ms0 > b. This implies that s0 ∈ S \ I. Since s0 ∈
/ M (µ), we have s0 ∈ R(µ, I).
By part 2, R(µ, I) ⊆ R(µ0 , I 0 ). Thus, s0 ∈ R(µ0 , I 0 ). Thus, s0 ∈
/ M (µ0 ). This contradicts the
assumption that s0 ∈ M (µ0 ) \ M (µ).
Statement 4. Let (µ0 , I 0 ) ∈ QSt(π). Let µ00 ≡ M W (S \ I 0 , C, (RS\I 0 , RC ), mS\I 0 , q). By
Part 1, I 0 ⊆ I. Since µ = M W (S \ I, C, RS\I , RC , mS\I , q), then for each s ∈ S \ I, we have
µ(s) Rs µ0 (s). Since µ0 , µ00 ∈ St(S \ I 0 , C, (RS\I 0 , RC ), mS\I 0 , q) and µ00 is student-optimal in
St(S \ I 0 , C, (RS\I 0 , RC ), mS\I 0 , q), then for each s ∈ S \ I 0 , we have µ00 (s) Rs µ0 (s). Thus, for
each s ∈ S \ I, we have µ(s) Rs µ0 (s).
The only statement in Theorem 1 of Perach and Rothblum (2010) that doesn’t hold in
this model is: for each s ∈ S, if all colleges are acceptable for s, and s is acceptable for each
c ∈ C, then s is not rejected at (µ, I). This is shown by the following example.
Example 1: Let S = {s1 , s2 , s3 } with m = {6, 4, 4}, and C = {c1 , c2 } with q = {1, 1}.
Preferences are as follows:
Rs1
Rs2
R s3
Rc1
Rc2
c1
c2
c2
s1
s1
c2
c1
c1
s2
s2
∅c
∅c
∅c
s3
s3
∅s
∅s
Let I0 ≡ S and E0 ≡ ∅.
Step 1. Let S1 ≡ {s1 }, I1 ≡ {s2 , s3 }, and E1 ≡ {s1 }. Apply the M-W algorithm to
(E1 , C, RC , RE1 , q). Student s1 is assigned to college c1 . Since there is an empty seat in c2
and there are students in I1 , we proceed to Step 2.
16
Step 2. Let S2 ≡ {s2 , s3 }, I2 ≡ ∅, and E2 ≡ {s1 , s2 , s3 }. Apply the M-W algorithm to
(E2 , C, RC , RE2 , q). Student s1 is assigned to college c1 , student s2 is assigned to college c2 ,
and student s3 is rejected by both colleges. Since I2 = ∅, the algorithm stops.
Let µ be such that µ(s1 ) = c1 , µ(s2 ) = c2 , and µ(s3 ) = s3 . The outcome is (µ, ∅).
T
Note that Cs3 = {c1 , c2 } and s3 ∈ Sc1 Sc2 , but s3 ∈ R(µ, ∅). This is a violation of the
property above.
The How-to-Low rule with deferred acceptance is not strategy-proof. This is shown by the
following example.
Example 2: Let S = {s1 , s2 , s3 , s4 } with m = {6, 6, 4, 4}, and C = {c1 , c2 } with q = {1, 1}.
Preferences are as follows:
Rs1
Rs2
Rs3
Rs4
Rc1
Rc2
Rs0 2
c1
c1
c1
c2
s3
s4
c2
∅c
c2
c2
c1
s2
c1
c2
∅c
∅c
∅c
s1
..
.
s2
..
.
∅c
Let µ be such that µ(s1 ) = ∅c , µ(s2 ) = ∅c , µ(s3 ) = c1 , and µ(s4 ) = c2 .
Then,
HtLDA(S, C, R, m, q) = (µ, ∅).
Let µ0 be such that µ(s1 ) = c1 , µ(s2 ) = c2 , µ(s3 ) = ∅c , and µ(s4 ) = ∅c . Then,
HtLDA(S, C, (Rs0 2 , , R−s2 , RC ), m, q) = (µ0 , {s3 , s4 }).
Suppose that Rs2 is the true preference of student s2 . Since c2 Ps2 c1 , student s2 is better
off by misreporting his preference to be Rs0 2 . Thus, HtLDA is not strategy-proof.
Therefore, we consider the second rule with the goal to obtain strategy-proofness. Next,
we show that for each σ ∈ Σ, M HtLDAσ is strategy-proof. We introduce two lemmas.
Lemma 1 For each σ ∈ Σ, each (S, C, R, m, q) ∈ Π, each s ∈ S, and each Rs0 ∈ Rs ,
if (µ, I) ≡ M HtLDAσ (S, C, R, m, q), (µ0 , I 0 ) ≡ M HtLDAσ (S, C, (Rs0 , R−s , RC ), m, q), and
I 0 ⊆ I, then µ(s) Rs µ0 (s).
17
Proof. By the definition of M HtLDAσ , µ = M W (S \ I, C, (RS\I , RC ), mS\I , q), and µ0 =
M W (S \ I 0 , C, (Rs0 , RS\(I 0 ∪{s}) , RC ), mS\I 0 , q). Let µ00 ≡ M W (S \ I 0 , C, (RS\I 0 , RC ), mS\I 0 , q).
Since M W is strategy-proof, then µ00 (s) Rs µ0 (s). Since I 0 ⊆ I, then µ(s) Rs µ00 (s). Thus,
µ(s) Rs µ0 (s).
Lemma 2 For each σ ∈ Σ, each (S, C, R, m, q) ∈ Π, each s ∈ M , and each Rs0 ∈ Rs , if
(µ, I) ≡ M HtLDAσ (S, C, R, m, q), (µ0 , I 0 ) = M HtLDAσ (S, C, (Rs0 , R−s , RC ), m, q), and for
each c ∈ C, µ(s) Rs0 c, then
1. I ⊆ I 0 .
2. µ0 (s) = µ(s).
3. for each s0 ∈ S \ I 0 , we have µ0 (s0 ) Rs0 µ(s0 ).
Proof. Let I 6= ∅. By plausibility, for each c ∈ C, |µ−1 (c)| = qc . By the definition of
M HtLDAσ , µ = M W (S\I, C, (RS\I , RC ), mS\I , q) and µ0 = M W (S\I 0 , C, (Rs0 , RS\(I 0 ∪{s}) , RC ),
mS\I 0 , q). Let µ00 ≡ M W (S\I, C, (Rs0 , RS\(I∪{s}) , RC ), mS\I , q). Since µ ∈ St(S\I, C, (RS\I , RC ),
mS\I , q) and for each c ∈ C, µ(s) Rs0 c, we have µ ∈ St(S \ I, C, (Rs0 , RS\(I∪{s}) , RC ), mS\I , q).
Since µ00 is student-optimal in St(S\I, C, (Rs0 , RS\(I∪{s}) , RC ), mS\I , q), then for each s0 ∈ S\I,
we have µ00 (s0 ) Rs0 µ(s0 ). Since I 6= ∅, then for each c ∈ C, |µ−1 (c)}| = qc . Thus, for
each c ∈ C, |µ00−1 (c)| = qc . This implies that the MHtLDA algorithm stops at b0 = max{ms :
s ∈ I 0 } ≥ b = max{ms : s ∈ I} for (S \ I, C, Rs0 , (RS\(I∪{s}) , RC ), mS\I , q). Thus, I ⊆ I 0 .
Thus, for each s0 ∈ S \ I 0 , we have µ0 (s0 ) Rs0 µ00 (s0 ) Rs0 µ(s0 ). Since µ0 (s) Rs0 µ(s) and for
each c ∈ C, µ(s) Rs0 c, we have µ0 (s) = µ(s).
The case where I = ∅ follows the same logic, where b0 ≥ b holds trivially.
Theorem 3 The Modified High-to-Low rules with deferred acceptance, MHtLDA, are strategyproof.
Proof. For each σ ∈ Σ, each (S, C, R, m, q) ∈ Π, each s ∈ S, and each Rs0 ∈ Rs , let
(µ, I) ≡ M HtLDAσ (S, C, R, m, q) and (µ0 , I 0 ) ≡ M HtLDAσ (S, C, (Rs0 , R−s , RC ), m, q). If
s ∈ I, then (µ0 , I 0 ) = (µ, I). If s ∈ S \ I and I 0 ⊆ I, then by Lemma 3, µ(s) Rs µ0 (s).
The only case left is s ∈ S \ I and I ⊂ I 0 .
18
Suppose by contradiction that µ0 (s) Ps µ(s). Let c ≡ µ0 (s). By Lemma 4, we can assume
that for each c0 ∈ C, c Rs0 c0 . Let the students in S become eligible one-by-one in such a way
that in the end, the set of students who are still ineligible is I 0 , and s is the last student to
become eligible. There are two cases:
Case 1: All colleges are already full when s becomes eligible.
Consider the execution of the M HtLDAσ algorithm when the preference profile is (RS , RC ).
When s becomes eligible, the assignment from the previous step is the same as the one when
the preference profile is (Rs0 , R−s , RC ). Thus, all the colleges are already full. The new
assignment after s becoming eligible does not create empty seats. Thus, at the end of this
step, all the colleges are still full. Since no additional students can become eligible, then
I = I 0 . This contradicts the assumption that I ⊂ I 0 .
Case 2: There is exactly one empty seat when s becomes eligible.
Let cl be the college that has one empty seat. Consider the execution of the M HtLDAσ
algorithm when the preference profile is (Rs0 , R−s , RC ). When s enters, he applies to c and
he is tentatively admitted. [It is possible that c = cl .] Let s1 be the student who is rejected
by c to be replaced by s. Then, he applies to c1 and is tentatively admitted. Let s2 be the
student who is rejected by c1 to be replaced by s1 . He then applies to c2 and is tentatively
admitted · · · · · · This process ends when the empty seat in cl is filled by some student sl . We
obtain {s0 ≡ s, s1 , ... , sl } and {c0 ≡ c, c1 , ... , cl }, where for each 0 ≤ j ≤ l, sj is rejected
by cj−1 and he is tentatively admitted to cj .
Consider the execution of the M HtLDAσ algorithm when the preference profile is (RS , RC ).
When s becomes eligible, he applies to the colleges according to Rs until he is tentatively admitted to some college c0 . Let s0 be the student who is rejected by c0 to be replaced by s. He
applies to c00 and is tentatively admitted. Let s00 be the students who is rejected by c00 to be
replaced by s0 . He applies to c000 and is tentatively admitted · · · · · · If there is sj ∈ {s1 , ... , sl }
such that sj is rejected before the process reaches the step where s applies to c, then the
process will consist of {sj , sj+1 , ... , sl } and {cj , cj+1 , ... , cl }, where for each j ≤ k ≤ l, sk
is rejected by sk−1 and he is tentatively admitted to ck . If not, then after s applies to c
and he is tentatively admitted, the process will be the same as the one when the preference profile is (Rs0 , R−s , RC ). Since the empty seat in cl is filled in both cases, no additional
19
students can become eligible. Thus, I = I 0 . This contradicts the assumption that I ⊂ I 0 .
Although, for each σ ∈ Σ, M HtLDAσ rule is strategy-proof, since the outcome of this rule is
not score-respecting, M HtLDAσ rule is not quasi-stable. But it is weakly quasi-stable. The
proof is omitted, because it is very similar to the proof of Theorem 1.
Theorem 4 The Modified High-to-Low rules with deferred acceptance, MHtLDA, are weakly
quasi-stable.
Finally, we will discuss the properties of HtLIA. Although it is both non-wasteful and
score-respecting, it is easy to show that it is not quasi-stable. But it turns out that HtLIA
rule is justifiably-stable and strategy-proof.
Theorem 5 The High-to-Low rule with immediate acceptance, HtLIA, is justifiably-stable.
Proof. All we need to show is for each π ∈ Π, HtLIA rule is justified-envy-free for π.
Let (µ, I) ≡ HtLIA(π). We need to show that for each s ∈ S and each c ∈ C such that
c Ps µ(s), then for each s0 ∈ µ(c), either
(1) ms0 > ms , or
(2) ms = ms0 and s0 Pc s.
Part (1) follows from the definition of the rule: since a student with relatively higher score
becomes eligible earlier than the one with relatively lower score, and since assignments are
permanent, part (1) is satisfied.
Part (2) follows from the proof of Theorem 1.
Theorem 6 The High-to-Low rule with immediate acceptance, HtLIA, is strategy-proof.
Proof. At each step, the rule only considers students with the same score for the available
seats. The McWitie-Wilson rule used at each step is strategy-proof. Since the assignment
of a student is decided at the step at which he becomes eligible, and this assignment is
permanent, no student has an incentive to misrepresent.
20
6
Conclusion
Our first rule treats students with equal scores equally when determining eligibility. Ei-
ther they are all eligible, or they are all ineligible. But the equal treatment of equals results
in a loss of strategy-proofness. Our second rule determines students’ eligibility one-by-one.
There could be at most one group of students with the same score such that some of them
are eligible and the others are ineligible. We regain strategy-proofness (Theorem 3). Our
last rule not only treats students with equal scores equally when determining eligibility, but
also gives higher priority to students with higher scores. We again obtain strategy-proofness
(Theorem 6).
HtLDA
M HtLDA
HtLIA
Quasi − Stability
+
−
−
W eak Quasi − Stability
+
+
−
Justif iable − Stability
−
−
+
Strategy − proof ness
−
+
+
Equal T reatment of Equals
+
−
+
References
[1] Abdulkadiroǧlu, A., P.A. Pathak, and A.E. Roth (2005a), “The New York city high
school match”, American Economic Review, Vol.95, 364-367.
[2] Abdulkadiroǧlu, A., P.A. Pathak, A.E. Roth, and T. Sönmez (2005b) “The Boston
public school match” American Economic Review, Vol. 95, 368-371.
[3] Abdulkadiroǧlu, A., and T. Sönmez (2003), “School choice: a mechanism design approach”, American Economic Review, Vol.93, 729-747.
[4] Balinski, M. and T. Sönmez (1999) “A Tale of Two Mechanisms: Student Placement”,
Journal of Economic Theory, 84, 73-94.
21
[5] Gale, D. and L. Shapley (1962), “College admissions and the stability of marriage”,
American Mathematical Monthly, Vol.69, 9-15.
[6] Gustfield, D., and R.W. Irving (1989) The stable marriage problem: structure and algorithms. The MIT Press, Cambridge.
[7] Knuth, D.E. (1976) Marriages stables. Les Presses de L’Universite Montreal, Montreal.
[8] McVitie, D.G. and L.B. Wilson (1971), “Three procedures for the stable marriage problem”, Communications of the ACM, Vol.14, 491-492.
[9] Perach, N., J. Polak, and U.G. Rothblum (2008), “A stable matching model with an
entrance criterion applied to the assignment of students to dormitories at the technion”,
International Journal of Game Theory, Vol.36, 519-535.
[10] Perach, N. and U.G. Rothblum (2010), “Incentive compatibility for the stable matching
model with an entrance criterion”, International Journal of Game Theory, Vol.39, 657667.
[11] Roth, A.E. (1984), “The evolution of the labor market for medical interns and residents:
a case study in game theory”, Journal of Political Economy, Vol.92, 991-1016.
[12] Roth, A. E. (1985), “The college admissions problem is not equivalent to the marriage
problem”, Journal of Economic Theory, 36, 277-288
[13] Roth, A.E. (2002), “The economist as engineer: game theory, experimentation, and
computation as tools for design economics”, Econometrica, Vol.70, 1341-1378.
[14] Roth, A.E. (2008), “Deferred acceptance algorithms: history, theory, practice, and open
questions”, International Journal of Game Theory, Vol.36, 537-569
[15] Roth, A.E. and M. Sotomayor (1990), Two-Sided Matching. New York: Cambridge
University Press.
22