Scribd
Upload
8 views

Matching Algorithm

Uploaded by

ipl03saanvia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
8 views

Matching Algorithm

Uploaded by

ipl03saanvia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 12

Algorithm Design

Stable Matching Problem

Goal. Given n men and n women, find a "suitable/stable"


matching.

o Participants rate members of opposite sex.

o Each man lists women in order of preference from best to worst.

o Each woman lists men in order of preference from best to worst.


Stable marriages

A pair (m, w) is called a blocking pair for a marriage matching, M, if both m


and w prefer each other more than there mate in the marriage, M.

M is stable if there is no blocking pair. If there is a blocking pair then it is


unstable.
Find a set of stable marriages?
Initialize each person to be free.

while (some man m is free and hasn't proposed to every woman w)

{
Choose such a man m

w = 1st woman on m's list to whom m has not yet proposed

if (w is free)

assign m and w to be engaged

else if (w prefers m to her fiancé m')

assign m and w to be engaged, and m' to be free else w rejects m


}
Observations

Observation 1. The stable marriage has a shortcoming that it is


not gender neutral. It is man-optimal.

Observation 2. Once a woman is matched, she never becomes


unmatched; she only "trades up."
Applications

Write a report on the college admission problem (residents-hospitals assign-ment) that generalizes the stable
marriage problem in that a college can accept “proposals” from more than one applicant.

Consider the problem of the roommates, which is related to but more difficult than the stable marriage
problem: “An even number of boys wish to divide up into pairs of roommates. A set of pairings is called stable if
under it there are no two boys who are not roommates and who prefer each other to their actual roommates.”
[Gal62] Give an instance of this problem that does not have a stable pairing.
2012 Nobel Prize in Economics: Alvin Roth and Lloyd Shapley win
Sverges Riksbank prize in memory of Alfred Nobel.
Market-Clearing
A set of prices p1, p2, . . . , pn, one for each item, is called market-
clearing if

• There is a matching in the preferred graph H (at these prices) that


matches all the buyers to items, and

• if an item i is not matched, then its price pi = 0. (This is irrelevant


when the number of items equals the number of buyers, since if
all buyers are matched, so are the items. But if you had more
items, you need this condition.)
Theorem

The stable marriage algorithm terminates after no more then n2


iterations with a stable marriage.
Proof

The algorithm starts with n men and a total of n2 women on their preference list. Each preference is examine at
most once. Therefore the algorithm has at most n2 iteration.

We prove the marriage matching is stable by contradiction.

 Suppose that M is unstable.

 Therefore there exist a blocking par of m and w.

 They are unmatched in M.

 Since m proposes to each woman by the ranking on his preference list and m is mated to a woman with
lower ranking then w, m must have proposed to w.

 Weather w refused m's proposal or accepted and then replacing it, she must be mated with some man she
prefers more.

 This is a contradiction that m and w are a blocking pair.

You might also like