香港中文大学：《Design and Analysis of Algorithms》课程教学资源（辅导课件）tutorial 09

CSCI 3160 Design and Analysis of Algorithms Tutorial 9 Chengyu Lin

CSCI 3160 Design and Analysis of Algorithms Tutorial 9 Chengyu Lin

Outline ·Stable Matching ·Secretary Problem

Outline • Stable Matching • Secretary Problem

Stable Matching 免 免免 Figures borrowed from Lecture Notes of CSCI2110

Stable Matching Figures borrowed from Lecture Notes of CSCI2110

Perfect Matching in Bipartite Graph Given a bipartite graph G(V,W,E)with IVI Wl, 。. Matching:a collection of vertex-disjoint edges Perfect matching:every vertex gets matched Men Women

Perfect Matching in Bipartite Graph • Given a bipartite graph G(V, W, E) with |V| = |W|, • Matching: a collection of vertex-disjoint edges • Perfect matching: every vertex gets matched Men Women

Preference Each man has a preference list of all women Each woman has a preference list of all men Assume there is no tie Men Women 1:CBEAD A:35214 2:ABECD B:52143 3:DCBAE C:43512 4:ACDBE D:12345 5:ABDEC E:23415

Preference Men Women 1: CBEAD A : 35214 2 : ABECD B : 52143 3 : DCBAE C : 43512 4 : ACDBE D : 12345 5 : ABDEC E : 23415 • Each man has a preference list of all women • Each woman has a preference list of all men • Assume there is no tie

Blocking Pairs A Blocking Pair is a pair of man and woman that prefer each other to their current partners. Man 4 prefer Woman C to current partner Woman B Woman C prefer Man 4 to current partner Man 1 Men Women 1:CBEAD A:35214 2:ABECD B:52143 3:DCBAE C:43512 4:ACDBE D:12345 5:ABDEC E:23415

Blocking Pairs A Blocking Pair is a pair of man and woman that prefer each other to their current partners. Men Women 1: CBEAD A : 35214 2 : ABECD B : 52143 3 : DCBAE C : 43512 4 : ACDBE D : 12345 5 : ABDEC E : 23415 • Man 4 prefer Woman C to current partner Woman B • Woman C prefer Man 4 to current partner Man 1

Stable Matching Stable Matching:a matching without any blocking pair Given a matching,you can verify whether it's a stable matching in O(n2) time,but Dose stable matching always exist? 。 How to find a stable matching? Men Women 1: CBEAD A:35214 2:ABECD B:52143 3:DCBAE C:43512 4:ACDBE D:12345 5:ABDEC E:23415

Stable Matching Men Women 1: CBEAD A : 35214 2 : ABECD B : 52143 3 : DCBAE C : 43512 4 : ACDBE D : 12345 5 : ABDEC E : 23415 Stable Matching: a matching without any blocking pair Given a matching, you can verify whether it’s a stable matching in O(n2) time, but • Dose stable matching always exist? • How to find a stable matching?

Consider a Simple Dynamics ·廿matching f,V blocking pair(m,w), -Remove the old pairing (m,f(m))and (w,f(w)) f(m):the woman matched to m in f.(f(w):similar.) Match m and w Match f(m)and f(w) Question:Would repeating this finally lead to a stable matching? Men Women A:12 1:AB B:12 2:AB

Consider a Simple Dynamics • ∀ matching 𝑓, ∀ blocking pair (𝑚,𝑤), – Remove the old pairing 𝑚, 𝑓 𝑚 and 𝑤, 𝑓 𝑤 • 𝑓(𝑚): the woman matched to 𝑚 in 𝑓. (𝑓(𝑤): similar.) – Match 𝑚 and 𝑤 – Match 𝑓 𝑚 and 𝑓(𝑤) • Question: Would repeating this finally lead to a stable matching? Men A:12 B:12 1:AB 2:AB Women

Counterexample with 2 Men and 2 Women? Men Women 2 Man A and Woman 1 have no incentive to breakup Counterexample with 2 Men and 2 Women is IMPOSSIBLE

Counterexample with 2 Men and 2 Women? Men Women A B 1 2 Man A and Woman 1 have no incentive to breakup Counterexample with 2 Men and 2 Women is IMPOSSIBLE !

Counterexample with 3 Men and 3 Women? Men Women A:?22 1:?2? B:?? 2:222 C:?22 3:2?2

Counterexample with 3 Men and 3 Women? Men Women A:??? B:??? C:??? 1:??? 2:??? 3:???