Matching Problems
Examples of Two Sided Markets
• Job Allotment
• School Admissions
• Job Transfers
Assortative Matching
Model
• Manager (M), Worker (S)
• Production Function: M^2*S
• Workers: Country 1: A,B
• Workers: Country 2: C,D
• A>B>C>D
Example
• A=13, B=8, C=6, D=4
• 2 workers each
• Pre Globalisation
• (AB), (C,D)
• Post Globalisation: ?
Stability in Matching
The Model
• N men and N women
• Men have preferences over the women
• Women have preferences over the men
• A person is not indifferent to two people of the opposite sex i.e. he
or she has a strict preference relation over any two people of the
opposite sex.
• A person does not prefer staying alone over marriage i.e. he or she
is willing to marry the worst person but not stay alone.
• Objective: To decide on N pairs( a matching), each containing a
man and a woman, such that no man and woman prefer each other
to their partner in the matching
Example
Preference of women A sample matching
α CDBA <Aα, Bδ, Cβ, Dγ>
β BCDA
γ CBAD Is this efficient?
δ ABCD
Can you improve the welfare of anyone
without making someone else worse off?
Preference of men
Is this stable?
A αβγδ
B αγδβ Does there exist a man and woman who
C βαγδ prefer each other to their spouses?
D βγαδ
Key Question
• Q1. Is there always a stable matching?
• Q2. Is there a way of arriving at this
matching?
Man Proposing Algorithm (MPP)
• The algorithm proceeds in rounds. For simplicity we refer
to these rounds as 'days'.
• On day 1, every man proposes to the woman he likes
best,
• Now each woman has a list (possibly empty) of men who
have proposed to her
• She selects her most favoured man
• She keeps him 'on hold' and rejects others.
• On day 2 each of the rejected men, propose to their next
best choice.
• Now again each woman selects the best man from those
who have proposed her and the one on hold, if any, and
puts him on hold while rejecting others.
• This procedure continues till no man is rejected and all
couples formed.
Application of algorithm
• From the moment any woman gets a
proposal she will always have a man 'on
hold'.
• One woman does not receive proposal till
last day since if every woman has a
proposal the matchings are made!
• This implies that there is a rejection every
day as long as the procedure continues.
• Remark: The MPP terminates in a finite
number of days
One woman does not receive proposal till
last day
Number of women receiving proposals N -1
Application
• The stable roommates problem is similar to the stable marriage
problem, but differs in that all participants belong to a single pool
(instead of being divided into equal numbers of "men" and "women")
• The hospitals/residents problem — also known as the college
admissions problem — differs from the stable marriage problem in
that the "women" can accept "proposals" from more than one "man"
(e.g., a hospital can take multiple residents, or a college can take an
incoming class of more than one student). Algorithms to solve the
hospitals/residents problem can be hospital-oriented (female-
optimal) or resident-oriented (male-optimal).
• The hospitals/residents problem with couples allows the set of
residents to include couples who must be assigned together, either
to the same hospital or to a specific pair of hospitals chosen by the
couple (e.g., a married couple want to ensure that they will stay
together and not be stuck in programs that are far away from each
other). The addition of couples to the hospitals/residents problem
renders the problem intractable