CSC3160: Design and Analysis of Algorithms Week 10: Stable Matching and Secretary Problem 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 vertexdisjoint 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
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 mi and wi like each other more than their currently assigned ones! 8
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 8
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. 9
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 9
Real applications If you think marriage is a bit artificial since there is no centralized arranger,here is a real application. Medical students work as interns at hospitals. In the US more than 20,000 medical students and 4,000 hospitals are matched through a clearinghouse,called NRMP (National Resident Matching Program) 10
Real applications ◼ If you think marriage is a bit artificial since there is no centralized arranger, here is a real application. ◼ Medical students work as interns at hospitals. ❑ In the US more than 20,000 medical students and 4,000 hospitals are matched through a clearinghouse, called NRMP (National Resident Matching Program). 10