Decision and Risk Analysis in Operations Management
Jannik Matuschke
SCHOOL CHOICE & STABLE ASSIGNMENTS
i. School choice in Chile
ii. The old system
Until recently, school choice was decentralized (parents had to apply at different schools
inefficient). Each school could select arbitrarily which student to admit.
iii. Weaknesses of the old system
o Segregation
o Arbitrariness/unfairness
o Inefficient application process
iv. The new system
All public schools are centralized in one system; parents enter personal ranking of
schools for their child. At each school, there is a fixed number of seats and a priority list
of students, according to criteria specified by law:
o Children with disability
o Low-income families
o High-performing students
o Siblings at school
v. Mechanism design
i. Input
Students, schools, capacities of schools, priority list of students for each school,
preference list of each student
ii. Output
Assignment of students to school
NOTE parents will know the assignment mechanism (or guess it), which might influence
what preferences they report
= strategizing
,iii. Desirable properties of a centralized system
i. No school should be assigned more students than its capacity allows
ii. If a student gets a less-preferred school, there should be a good reason
iii. The system should encourage parents to tell their true preferences (make strategizing
impossible)
iv. Stable assignments
i. Justified envy
If a student i gets a less-preferred school, there should be a good reason:
o All seats in schools that are preferred by i are taken by students with a higher priority
than i
An assignment that fulfills this property is said to be free from justified envy
ii. Blocking pairs
For an assignment A, a pair of student i and school j is blocking, if
o i has been assigned no school or i prefers j over his assigned school in A; and
o j has a free seat or i has higher priority at j than some student assigned to j in A
iii. Stable assignment
An assignment that has no blocking pairs is called stable
NOTE (i, j) is a blocking pair ⇔ i has justified entry for not being assigned to j
Assignment A is stable ⇔ A is free from justified envy
The goal is to find “the best stable assignment for the students”
o Does a stable assignment always exists?
o What does ‘best’ mean?
o How do we find it?
iv. Valid
School j is valid for student i if there exists a stable assignment that assigns i to j
v. The Gale-Shapley Algorithm
= Deferred-Acceptance Algorithm
Initially, no student has applied at any school, and no seats are assigned. As long as there is a
student i that has no seat and was not rejected by all schools:
o Let i apply at her most-preferred school j that she has not tried yet
o If j is full and all students at j have higher priority than i: reject i
, o Otherwise: give i a seat at j; reject lowest-priority student if capacity at j is exceeded
i. THEOREM 1.1
The Gale-Shapley Algorithm computes a stable assignment
Proof:
o Assume a blocking pair (i, j)
o Case 1: i was rejected by all schools
o Case 2: i is assigned to j’ but prefers j
In both cases, i was rejected by j. At the moment, all seats at j were taken by higher priority
students. By (*) also in the final assignment, all seats in j are taken by higher priority
students than i
(i, j) is not a blocking pair
ii. THEOREM 1.2
The Gale-Shapley Algorithm computes a student-optimal stable assignment; every student is
assigned to their most-preferred valid school
Consequences:
o The rule by which we choose which student applies next has no influence on the
output of the Gale-Shapley Algorithm
iii. Strategy-proofness of the Gale-Shapley Algorithm
Consider a student i and two runs of the Gale-Shapley Algorithm
o Run 1: i’s parents report their true preferences i gets assigned to school j1
o Run 2: i’s parents report some other ‘fake’ preferences i gets assigned to school j2
Everyone else reports the same preferences in both runs (true of fake)
THEOREM 1.3
The Gale-Shapley Algorithm is strategy-proof for the student; school j2 is not better for i than
school j1 (w.r.t. true preferences)
NOTE it is not strategy-proof for the schools; schools can influence the outcome by changing
their priority lists
iv. Conclusions Stable Assignments
o Automated, centralized system based on the Gale-Shapley Algorithm
o Strategy-proof; parents have no incentives to lie
o Stable; no justified envy (increased fairness, reduced segregation)
, v. Other applications
i. Markets without money
o Assignment of interns to hospitals
o Student dormitories
o Public housing market
o Kidney exchange
o Stable marriage
ii. Efficient assignments
An assignment A strictly dominates assignment B if:
o There is at least one student preferring their school in A over their school in B; and
o No student prefers their school in B over their school in A
An assignment is efficient if it is not strictly dominated by any other assignment
iii. Top trading cycle algorithm (TTC)
i. The algorithm
o Start from some assignment
o For each student i: insert an arc from i to the highest-priority student assigned to the
most-preferred school of i
o Find a directed cycle in the resulting graph
o Re-assign every student on the cycle to their most-preferred school
o Fix these new assignments, remove students on the cycle, reduce capacities of involved
schools by 1
o Remove schools with capacity 0
o Repeat until there are no schools are left
ii. THEOREM 1.4
The TTC algorithm computes an efficient assignment
iii. THEOREM 1.5
The TTC algorithm is strategy-proof for the students
iv. The Boston Mechanism
Step 1: each student applies at their top choice school. Each school assigns seats to its applicant
in order of its priority list, until no seats are left or all applicants are assigned.
…
Step l: each student that has not yet been assigned applies at their lth choice school. Each school
assigns seats to its applicants in order of their priority list, until no seats are left or all applicants
are assigned.
Jannik Matuschke
SCHOOL CHOICE & STABLE ASSIGNMENTS
i. School choice in Chile
ii. The old system
Until recently, school choice was decentralized (parents had to apply at different schools
inefficient). Each school could select arbitrarily which student to admit.
iii. Weaknesses of the old system
o Segregation
o Arbitrariness/unfairness
o Inefficient application process
iv. The new system
All public schools are centralized in one system; parents enter personal ranking of
schools for their child. At each school, there is a fixed number of seats and a priority list
of students, according to criteria specified by law:
o Children with disability
o Low-income families
o High-performing students
o Siblings at school
v. Mechanism design
i. Input
Students, schools, capacities of schools, priority list of students for each school,
preference list of each student
ii. Output
Assignment of students to school
NOTE parents will know the assignment mechanism (or guess it), which might influence
what preferences they report
= strategizing
,iii. Desirable properties of a centralized system
i. No school should be assigned more students than its capacity allows
ii. If a student gets a less-preferred school, there should be a good reason
iii. The system should encourage parents to tell their true preferences (make strategizing
impossible)
iv. Stable assignments
i. Justified envy
If a student i gets a less-preferred school, there should be a good reason:
o All seats in schools that are preferred by i are taken by students with a higher priority
than i
An assignment that fulfills this property is said to be free from justified envy
ii. Blocking pairs
For an assignment A, a pair of student i and school j is blocking, if
o i has been assigned no school or i prefers j over his assigned school in A; and
o j has a free seat or i has higher priority at j than some student assigned to j in A
iii. Stable assignment
An assignment that has no blocking pairs is called stable
NOTE (i, j) is a blocking pair ⇔ i has justified entry for not being assigned to j
Assignment A is stable ⇔ A is free from justified envy
The goal is to find “the best stable assignment for the students”
o Does a stable assignment always exists?
o What does ‘best’ mean?
o How do we find it?
iv. Valid
School j is valid for student i if there exists a stable assignment that assigns i to j
v. The Gale-Shapley Algorithm
= Deferred-Acceptance Algorithm
Initially, no student has applied at any school, and no seats are assigned. As long as there is a
student i that has no seat and was not rejected by all schools:
o Let i apply at her most-preferred school j that she has not tried yet
o If j is full and all students at j have higher priority than i: reject i
, o Otherwise: give i a seat at j; reject lowest-priority student if capacity at j is exceeded
i. THEOREM 1.1
The Gale-Shapley Algorithm computes a stable assignment
Proof:
o Assume a blocking pair (i, j)
o Case 1: i was rejected by all schools
o Case 2: i is assigned to j’ but prefers j
In both cases, i was rejected by j. At the moment, all seats at j were taken by higher priority
students. By (*) also in the final assignment, all seats in j are taken by higher priority
students than i
(i, j) is not a blocking pair
ii. THEOREM 1.2
The Gale-Shapley Algorithm computes a student-optimal stable assignment; every student is
assigned to their most-preferred valid school
Consequences:
o The rule by which we choose which student applies next has no influence on the
output of the Gale-Shapley Algorithm
iii. Strategy-proofness of the Gale-Shapley Algorithm
Consider a student i and two runs of the Gale-Shapley Algorithm
o Run 1: i’s parents report their true preferences i gets assigned to school j1
o Run 2: i’s parents report some other ‘fake’ preferences i gets assigned to school j2
Everyone else reports the same preferences in both runs (true of fake)
THEOREM 1.3
The Gale-Shapley Algorithm is strategy-proof for the student; school j2 is not better for i than
school j1 (w.r.t. true preferences)
NOTE it is not strategy-proof for the schools; schools can influence the outcome by changing
their priority lists
iv. Conclusions Stable Assignments
o Automated, centralized system based on the Gale-Shapley Algorithm
o Strategy-proof; parents have no incentives to lie
o Stable; no justified envy (increased fairness, reduced segregation)
, v. Other applications
i. Markets without money
o Assignment of interns to hospitals
o Student dormitories
o Public housing market
o Kidney exchange
o Stable marriage
ii. Efficient assignments
An assignment A strictly dominates assignment B if:
o There is at least one student preferring their school in A over their school in B; and
o No student prefers their school in B over their school in A
An assignment is efficient if it is not strictly dominated by any other assignment
iii. Top trading cycle algorithm (TTC)
i. The algorithm
o Start from some assignment
o For each student i: insert an arc from i to the highest-priority student assigned to the
most-preferred school of i
o Find a directed cycle in the resulting graph
o Re-assign every student on the cycle to their most-preferred school
o Fix these new assignments, remove students on the cycle, reduce capacities of involved
schools by 1
o Remove schools with capacity 0
o Repeat until there are no schools are left
ii. THEOREM 1.4
The TTC algorithm computes an efficient assignment
iii. THEOREM 1.5
The TTC algorithm is strategy-proof for the students
iv. The Boston Mechanism
Step 1: each student applies at their top choice school. Each school assigns seats to its applicant
in order of its priority list, until no seats are left or all applicants are assigned.
…
Step l: each student that has not yet been assigned applies at their lth choice school. Each school
assigns seats to its applicants in order of their priority list, until no seats are left or all applicants
are assigned.
