Stable Matchings
Scribe: Puneet Arora, Ishan Vaishnavi
Lecture 16 by
Prof. Pradeep Dubey
We are given a group of women and a group of men and we are required to find
a desirable matching among them, i.e. we have to form couples from among them. A
few instances of this problem occuring in real life are mentioned below :
- A set of employees is to matched against a set of employers
- A class of students applying for internship is to be matched with a set of
colleges
Let
us assume there are 'n' women and 'n' men and we need to form 'n' couples. Each
of these women ranks all men in an order of preference and similarly each man
ranks all women.
Let's illustrate this with an example. Assume there are 5 men labelled A, B,
C, D, E and women labelled
The following assumptions are made
- 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.
Let the preferences for men be given as follows.
Let the preferences for women be as follows.
|
: |
A |
|
D |
|
C |
|
E |
|
B |
|
: |
A |
|
B |
|
D |
|
C |
|
E |
|
: |
D |
|
E |
|
C |
|
A |
|
B |
|
: |
C |
|
B |
|
A |
|
E |
|
D |
|
: |
A |
|
B |
|
D |
|
E |
|
C |
For , A B implies
prefers A over B, similarly A prefers to .
Consider the matching
``(A,
) (B,
) (C,
) (D,
) (E,
)''
Assuming that there is no dictatorship, i.e. there is no external factor that
can force couples to stay together after getting matched. Therefore a pair can
break their current marriage if both the partners prefer each other to their
current partners. Formally: In the above example (A, ) can
destabilise the matching as both of them rank each other higher than their
currently matched partners i.e. A prefers to and similarly prefers A
to her current match. So if free will is assumed then they will elope
destabilising the above matchings.
Also note that the couple (A,) cannot
destabilize this matching since prefers C
to A and is matched to C in reality although A may want to match with but has no
incentive of doing so.
So the desirable matching is the one where there is no pair consisting of a
woman and a man who prefer each other to the partners with whom they are
currently matched. Such a matching is called a Stable Matching.
The question now is that given any arbitary preferences does there always
exist such a stable matching? D.Gale and L.Shapley proposed a method which gives
a stable matching. The algorithm as we call it is the ``Man Proposal Procedure
(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, i.e. the woman highest
in his priority list. Now each woman has a list (possibly empty) of men who have
proposed to her. She selects her most favoured man according to her personal
preference. She keeps him 'on hold' and rejects others. So at the end of day 1,
each woman who was proposed by at least one man has someone on hold. 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. We will see later that the
procedure is guranteed to end.
Remarks on this procedure
- From the moment any woman gets a proposal she will always have a man 'on
hold'.
- This implies there is always a woman without any proposal as long as the
process is continuing. 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.
- The procedure is obviously finite and terminates in a maximum of days. This is shown as follows. There is at least one
woman proposed on the last day. Except for her the rest will be matched in a
maximum of n(n-1) days. Hence the bound.
Note:The procedure can be framed as the Woman Proposing Procedure (WPP) as
well, the man woman terminology is purely a matter of choice of society!!!
Theorem 1 This Procedure results in a stable matching.
Proof: The proof procedes by the method of contradiction. We
assume for contradiction that the procedure does not result in a stable
matching. This implies that there exist two couples (given by our matching
procedure) viz. A, and B, such that A prefers over and prefers A
over B. So A must have proposed to before
proposing to but rejected A
because there was somebody better than A in her list at some time. So it is not
possible that later she ends up with B, who she prefers less than A. Hence the
assumption is false.
A similar theorem can be formulated for WPP. A point here to note is that the
matching obtained by WPP may be different from the one obtained by MPP.
Consider the following example. Let the preferences of men be :
A: |
|
|
... |
|
B: |
|
|
... |
|
C: |
|
|
... |
|
D: |
|
|
... |
|
Let the preferences of women be:
: |
B |
|
... |
A |
: |
C |
|
... |
B |
: |
D |
|
... |
C |
: |
A |
|
... |
D |
In this case MPP results in the following matching:
And WPP results in the following matching:
Remarks
- We can see that multiple stable matchings may exist as both the matchings
obtained by MPP and WPP are stable and different.
- In general more than two stable matchings can exist. In such cases there
is no algorithm (other than brute force) to arrive at them at present .
- We can compare these stable matchings on the basis of which is preferable
to the players. For instance at a closer look we see that if MPP is followed
in the above example each man gets his best choice whereas the women are left
with their worst choices and vice versa if WPP is followed.
- For further discussion we define poss(X) as the set of all women with whom
X is paired in some stable matching i.e. set of women possible for him.
Similarly poss sets can be defined for women.
Theorem 2 When MPP is followed then each man A, ends up with
his top choice in the set poss(A).
Proof: We proceed by showing that in the course of MPP no man is
rejected by a woman who is in poss(A). We call a 'bad event' as the rejection of
a man by a woman who is possible for him (is in his poss set).We proceed to show
therefore that a bad event never occurs. Using mathematical induction on days.
Claim: Assuming that no bad event occurs from days 1 to , no bad event will occur on day .
Proof: Suppose a bad event occurs on day . Let reject A for B although belongs to
poss(A) (call this event E1). There exists some stable matching (call it S1)
where A and are matched. Now in this stable matching, assume
that B is paired with . This
implies that B prefers over since S1 is stable else B and would
destabilise the matching since E1 implies that prefers B
over A. This inturn implies that B proposed to and was
rejected by her before proposing to . Which is
a contradiction since is in poss
B and we assumed no bad event occurred on days through
.
What remains to be proven is that no bad event occured on the 1st day. Let
reject A for B although belongs to
poss(A) (call this event E0). There exists some stable matching (call it S0)
where A and are matched. Assume that E0 occurs on day 1. So
since S0 is stable B prefers over hence B will propose to only after
being rejected by which is
not possible on day 1.
A similar theorem can be formulated for WPP.
The above theorem suggests
that there exists an inherent competition between men and women since men would
prefer MPP and women would prefer WPP. However there is no competition among men
since each men gets his best choice in his possible set, when MPP is followed.
Game
Theory can be used to analyze if there exists any incentive for a person (or a
group) to misrepresent his (their) true preferences and end with a better
partner (partners). In other words is the matching given by MPP a strong Nash
equilibrium?
Definition : A profile is in strong Nash-equilibrium if there
is no subgroup that can deviate by changing strategies jointly in a manner that
increases the payoff of all its members, given that nonmembers stick to their
original choice.
- It has been shown that the above stable matchings belong to the category
of strong Nash equilibrium if MPP or WPP is followed and hence there can be no
incentive for a person to misrepresent his or her preferences.
- In case where people are allowed to be indifferent among various choices
the above procedure (MPP or WPP) need not lead to a stable matching.
One can think of variations of this problem in different settings. Two major
variations to this problem are
Homework: Prove the
following claim:
"If MPP and WPP result in the same stable matching then
that is the only existing stable matching for the given problem."
Puneet Arora 2002-11-22