香港中文大学：《Topics in Theoretical Computer Science》课程教学资源（PPT课件讲稿）Lecture 7 Stable matching.Gale-Shapley algorithm

CMSC5706oComtr Science Week 7:Stable Matching Instructor:Shengyu Zhang 1

Instructor: Shengyu Zhang 1

Bipartite graph (Undirected)Bipartite graph: G=(V,E)for which V can be partitioned into two parts oV=MUW with M∩W=④， And all edges e =(m,w) have m∈and w∈W. M W 2

Bipartite graph ◼ (Undirected) Bipartite graph: ◼ 𝐺 = (𝑉, 𝐸) for which 𝑉 can be partitioned into two parts ❑ 𝑉 = 𝑀 ∪ 𝑊 with 𝑀 ∩ 𝑊 = ∅, ◼ And all edges 𝑒 = 𝑚, 𝑤 have 𝑚 ∈ 𝑀 and 𝑤 ∈ 𝑊. 𝑀 𝑊 2

Matching,maximum matching Matching:a collection of vertex- disjoint edges 0 a subset E'E s.t.no two edges e,e'∈E'are incident. E':size of matching. Maximum matching:a matching with the maximum size. M W This lecture:matching in a bipartite graph 3

Matching, maximum matching ◼ Matching: a collection of vertex￾disjoint edges ❑ a subset 𝐸′ ⊆ 𝐸 s.t. no two edges 𝑒, 𝑒 ′ ∈ 𝐸 ′ are incident. ◼ |𝐸′|: size of matching. ◼ Maximum matching: a matching with the maximum size. ◼ This lecture: matching in a bipartite graph 𝑀 𝑊 3

Perfect matching There may be some vertices not incident to any edge. Perfect matching:a matching with no such isolated vertex. ▣needs at least:|M=lW M W We'll assume M=W in the rest of the lecture. 4

Perfect matching ◼ There may be some vertices not incident to any edge. ◼ Perfect matching: a matching with no such isolated vertex. ❑ needs at least: |𝑀| = |𝑊| ◼ We’ll assume |𝑀| = |𝑊| in the rest of the lecture. 𝑀 𝑊 4

Men's Preference Suppose a man sees these women. He has a preference among them. What's your preference list? Different men may have different lists. 5

Men’s Preference ◼ Suppose a man sees these women. ◼ He has a preference among them. ❑ What’s your preference list? ◼ Different men may have different lists. 5

Women's preference Women also have their preference lists. Assume no tie. The general case can be handled similarly. 6

Women’s preference ◼ Women also have their preference lists. ◼ Assume no tie. ❑ The general case can be handled similarly. 6

Setting n men.n women Each man has a preference list of all women Each woman has a preference list of all men We want to match them. W1>W2>W3>W4 W1 m3>m1>m2>m4 W1>W2>W3>W4 m2 W2 m3>m4>m1>m2 W2>W1>W3>W4 m3 W3 m1>m4>m2>m3 W3>W2>W4>W1 m4 m4>m1>m3>m2 7

Setting ◼ 𝑛 men, 𝑛 women ◼ Each man has a preference list of all women ◼ Each woman has a preference list of all men ◼ We want to match them. 𝑚3 > 𝑚1 > 𝑚2 > 𝑚4 𝑚3 > 𝑚4 > 𝑚1 > 𝑚2 𝑚1 > 𝑚4 > 𝑚2 > 𝑚3 𝑚4 > 𝑚1 > 𝑚3 > 𝑚2 𝑤1 > 𝑤2 > 𝑤3 > 𝑤4 𝑚1 𝑤1 𝑤1 > 𝑤2 > 𝑤3 > 𝑤4 𝑤2 > 𝑤1 > 𝑤3 > 𝑤4 𝑤3 > 𝑤2 > 𝑤4 > 𝑤1 𝑚2 𝑚3 𝑚4 𝑤2 𝑤3 𝑤4 7

Setting Consider this matching. And this pair (m1,W1). 口 m is matched to w2,but he likes wi more. wi is matched to mz,but she likes wi more. What if m and wi meet one day? W1>W2>W3>W4 m W1 m3>m1>m2>m4 W1>W2>W3>W4 m2 W2 m3>m4>m1>m2 W2>W1>W3>W4 m3 W3 m1>m4>m2>m3 W3>W2>W4>W1 m4 m4>m1>m3>m2 8

Setting ◼ Consider this matching. ◼ And this pair 𝑚1,𝑤1 . ❑ 𝑚1 is matched to 𝑤2, but he likes 𝑤1 more. ❑ 𝑤1 is matched to 𝑚2, but she likes 𝑤1 more. ◼ What if 𝑚1 and 𝑤1 meet one day? 𝑚3 > 𝑚1 > 𝑚2 > 𝑚4 𝑚3 > 𝑚4 > 𝑚1 > 𝑚2 𝑚1 > 𝑚4 > 𝑚2 > 𝑚3 𝑚4 > 𝑚1 > 𝑚3 > 𝑚2 𝑤1 > 𝑤2 > 𝑤3 > 𝑤4 𝑚1 𝑤1 𝑤1 > 𝑤2 > 𝑤3 > 𝑤4 𝑤2 > 𝑤1 > 𝑤3 > 𝑤4 𝑤3 > 𝑤2 > 𝑤4 > 𝑤1 𝑚2 𝑚3 𝑚4 𝑤2 𝑤3 𝑤4 8

A stability property Suppose there are two couples with these preferences. W1>W2 mi m1>m2 W1>W2 m2 W2 m1>m2 The marriage is unstable,because m and wi like each other more than their currently assigned ones！ 9

A stability property ◼ Suppose there are two couples with these preferences. ◼ The marriage is unstable, because 𝑚1 and 𝑤1 like each other more than their currently assigned ones! 𝑚1 𝑤2 𝑤1 𝑚2 𝑤1 > 𝑤2 𝑤1 > 𝑤2 𝑚1 > 𝑚2 𝑚1 > 𝑚2 9

Stability Such a pair is called a blocking pair. W1>W2 m W1 m1>m2 W1>W2 m2 W2 m1>m2 Question:Can we have a matching without any blocking pair? Such a matching is then called a stable matching. 10

Stability ◼ Such a pair is called a blocking pair. ◼ Question: Can we have a matching without any blocking pair? ❑ Such a matching is then called a stable matching. 𝑚1 𝑤2 𝑤1 𝑚2 𝑤1 > 𝑤2 𝑤1 > 𝑤2 𝑚1 > 𝑚2 𝑚1 > 𝑚2 10