Lecture: Matching
18.03.2024/21.03
For this lecture, I have followed Douglas West, chapter 3.2 on Matching
For stable marriage: https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf
Stable roommate problem is not mentioned here though (follow this one https://www.cs.cmu.edu/~arielpro/15896s16/slides/896s16-16.pdf)
If G has a perfect matching (implies no odd cycle), then player 2 has a winning
strategy; otherwise, player 1 has a winning strategy.
Can you justify ? Could there be any other property which supports the winning strategy?
Player 1 should start from an unmatched vertex for a graph without perfect matching.
We use an algorithm called the Hungarian Method
Assignment Problem
‘
The theorem transforms the problem from an optimization problem of finding a max-weight matching into a combinatorial one of finding a perfect matching.
The theorem transforms the problem from an optimization problem of finding a max-weight matching into a combinatorial one of finding a perfect matching.
a1 1 4 5
a2 5 7 6
a3 5 8 8
b1 b2 b3
5 a1 4 1 0 X-R
7 a2 2 0 1 X-R
8 a3 3 0 0 X-R
b1 b2 b3
Excess matrix
T T
Y-T
3 a1 2 1 0
5 a2 0 0 1
6 a3 1 0 0
2 2
b1 b2 b3
Select R and/or T so that all 0s are
covered
2
2
Exercise
For ease of analysis, convert
this into complete bipartite graph by adding edges of weight 0
Max-Matching will be: ((Rob-Top),(Eva-Defense),(Tom-Mid))
Rb 1 0 4
Ev 6 8 0
Tm 0 6 1
Def Mid Top
3 4 0
2 0 8
6 0 5
4
= 8
6
3 4 0
2 0 8
6 0 5
U M M
4
= 8
6
M: Matched
U: Unmatched
0 +2 +2
3-2 4 0
2-2 0 8
6-2 0 5
4-2
8-2
6-2
=
3 4 0
2 0 8
6 0 5
U M M
4
= 8
6
0 +2 +2
3-2 4 0
2-2 0 8
6-2 0 5
4-2
8-2
6-2
=
0 +2 +2
1 4 0
0 0 8
4 0 5
2
6
4
=
Max-Matching will be: ((Rob-Top),(Eva-Defense),(Tom-Mid))
Show that this is optimal: max weighted matching and min cost cover?
Stable marriage algorithm terminates and man-optimal stable.
What happens if the ordering of proposal is reversed?
A-Y,B-X, C-Z
Woman-optimal
Construct an example where the weighted maximum matching in bipartite graph is not stable.
Example: Consider 3 men <A,B,C> and 3 women <a,b,c>, where n=3.
Given a preference list of a man/woman, then ith person in list has weight n-i. That is, if “A” has list <a,b,c> then a has weight 2 (3-1), b has weight 1 (3-2) and c has weight 0 (3-3). Similarly if “b” has list <A,B,C> then A has weight 2, B has weight 1 and C has weight 0. Then any edge (u,v) will have weight equal to summation of weight of vertices. For example, the edge (A,b) will have weight 1+2=3 as “A” has placed “b” in second position but “b” has placed “A” in 1st position.
Hint: Try to construct a weighted matching where (A,b), (B,a), (C,c) has weight >8 but stable matching is (A,a), (B,b) and (C,c). One way of doing this would be edge (B,b) has weight 0, (A,a) has weight 4 and (C,c) has weight 4, but summation of weights of (A,b) and (B,a) is >4.
Stable Roommate Problem (For general Graphs)
Stable Roommate Problem
Stable Roommate Problem
Stable Roommate Problem
Stable Roommate Problem
Previous Problem:
We have (Alana, Cynthia), But Brian has an empty list, so no matching
Prob 2: If we have proposal:
A => C,B then phase 1:
B => A,C A=> C,B
C => B,A B=> A,C
C=> B,A
Phase 2 (apply rotation):
B=>A,C B proposes to C, A unmatched
A=>C,B
C=>B,A