Matching Model
1
Course Outline
Microeconomics
Firms and
How Markets
Introduction Organization of
Work Additional
industries
Topics
What is Demand and Cost of
Economics? supply Production
Matching Model
Gains from Perfect
Elasticity
Trade Competition
Efficiency and
Equity Monopoly
Government
Policies in Oligopoly
Markets
International
Trade
2
Matching Model
Importance:
College admission
Marriage
Families—houses
Hospitals—doctors
3
2012 Nobel Prize in Economics
Lloyd Shapley and Alvin Roth
[Link]
sciences/2012/shapley/prize-presentation/
The Deferred Acceptance Algorithm
discovered by Gale and Shapley is the corner
stone on which matching theory and
applications rest.
4
5
Marriage market
Monogamous: one to one match
Heterosexual
A matching is an one to one pairing of each
man to a woman.
Call a matching stable if no pair of one man
and one woman can object the proposed
assignment.
Stability is important!
6
7
Marriage market
Find a stable matching for the following
preferences:
M1 M2 M3 M4 W1 W2 W3 W4
---------------------------------||--------------------------------
W4 W4 W3 W4 || M2 * M1 M1
* W3 W1 W1 || M1 * M2 *
* * * * || M4 * * *
* * * * || M3 * * *
* Stands for celibacy.
8
Stable matching
Sometimes there are more than one stable
matching for a set of preferences.
M1 M2 M3 W1 W2 W3
-------------------------------------------------
W2 W1 W1 M1 M3 M1
W1 W3 W2 M3 M1 M3
W3 W2 W3 M2 M2 M2
9
Stable matching
Check that the following two matchings are
stable.
Matching 1: (M1, W2; M2,W3; M3,W1)
Matching 2: (M1,W1; M2,W3; M3,W2)
Check everyone’s preference over matching
1 and matching 2.
We call matching 1 M-optimal, matching 2 W-
optimal.
10
Gale and Shapley theorem (1962)
In any marriage market with strict preferences.
(a). There is at least one stable matching.
(b). There is a stable matching, called the M-optimal
matching where every man gets the best of all his
stable mates and every woman gets her worst stable
mates. There is a stable matching called W-optimal
matching, where every woman gets the best of all her
stable mates. There is a unique stable matching if and
only if M-optimal and W-optimal matching coincide.
11
Gale and Shapley theorem (1962)
(c) The M-optimal matching is computed by
means of the Gale-Shapley algorithm where men
propose.
(d) A statement symmetrical to (c) holds for W-
optimal matching.
12
Gale-Shapley algorithm
Gale-Shapley algorithm where men propose
Step 1: Each man proposes to his first choice woman.
If a woman receives exactly one proposal, this man is
called her engagee. If a woman receives more than
one proposal, she keeps the proposer she likes best
as her engagee and rejects the others. Men are now
partitioned into engaged or rejected. The algorithm
stops if all men are engaged or stay single as they
preferred, otherwise we go to the next step.
13
Gale-Shapley algorithm
Step 2: All rejected men propose now to their
second best choice. Each woman receiving new
proposals keeps as her engagee the man she
likes best among current proposer(s) and possibly
former engagee and rejects the others. (Thus a
man previously engaged may now be rejected.)
The algorithm stops if all men are engaged or stay
single as they preferred. Otherwise we go to the
next step.
14
Gale-Shapley algorithm
Step 3: All rejected men propose now to their next
choice, and women update their engagements
according to new proposal(s) if any. The algorithm
stops if all men are engaged or stay single as
they preferred. Otherwise repeat step 3.
end of the algorithm
15
examples
Find M-optimal and W-optimal matching for
the following preferences.
M1 M2 M3 W1 W2 W3
------------------------------------------------
W2 W2 W3 M1 M3 M2
W1 W1 W1 M3 M1 M3
W3 W3 W2 M2 M2 M1
16
Applications
U.S. National Resident Matching Program
started in the 1950s with programs/hospitals
proposing algorithm and switched to
applicant proposing in 1997.
Matching students with public high schools in
New York City—2003 reform
JUPAS
17
Topic Intended Learning Outcome
12.1 Find M-optimal and W-optimal stable
matchings in marriage market and understand
gender discrimination in M-proposing societies.
18
