알고리즘(Algorithm) - Stable Matching

알고리즘(Algorithm) - Stable Matching

1. Stable Matching Problem

 - Perfect matching : Everyone is matched monogamously.(1대1 매칭)

 - Stability : No incentive for some pair of participants to undermine assignment by joint action.
                  (현재의 파트너 보다 서로를 서 선호해서 현재 이루어진 짝이 깨어질 가능성이 없는 경우)

 - Stable Matching : Stabilty한 Perfect matching.

 - Stable matching Problem : n명의 남자와 n명의 여자가 모두가 각각 선호하는 순서로 된 파트너 목록을 가질 때, 만약 존재한다면 stable matching을 찾는 문제.

※ stable matching은 반드시 존재하는것은 아니며, 또한 반드시 1개만 존재하는것도 아니다.
    (하나도 없거나 여러개 일 수 있다)

 

2. Propose-And-Reject Algorithm(GS 알고리즘)

 - Propose-And-Reject Algorithm : Gale-Shapley가 1962년에 제안한 stable matching을 찾는 알고리즘. (GS 알고리즘)

  * Observation 1. 남자는 자신의 선호도 순서에 따라 여자에게 프로포즈 한다.

  * Observation 2. 여자는 한번 짝이 맺어지면 절대 짝이 없는 상태로 돌아가지 않는다.

 - Proof of Correctness 1. Termination

claim) GS알고리즘은 while loop에서 최대 n^2번의 반복 안에서 끝난다.

pf) 1. 각각의 while loop에서 한 남자는 한 여자에게 프로포즈한다.

2. worst case일 때 n명의 남자 모두가 n명의 여자 모두에게 한번씩 프로포즈한 경우이며,
    이 경우 n*n = n^2번의 프로포즈가 발생한다. 

- Proof of Correctness 2. Perfection

claim) 모든 남자와 여자는 짝을 이룬다.

pf) (proof by contradiction)

1. 어떤 남자가 알고리즘이 끝나도 짝을 이루지 못했다고 가정하고, 그 남자를 Z라고 하자.

2. 그러면, 어떤 여자도 역시 알고리즘이 끝난 후에 짝을 이루지 못하며 그 여자를 A라고 하자.

3. Observation 2에 의해 A는 한번도 프로포즈를 받지 못했다.

4. 그러나, 알고리즘이 끝났으므로 Z는 모든 여자에게 프로포즈를 했으나 짝을 이루지
    못한것이며, 3번과 모순이다.

- Proof of Correctness 3. Stability

claim) unstable인 짝은 없다.

pf) (proof by contradiction)

1. 남자 Z와 여자 A가 unstable이라고 가정하자.

Case 1 : Z가 A에게 프로포즈 한 적이 없는 경우

=> Z는 현재 파트너를 A보다 선호한다.

=> A와 Z는 stable이다.

Case 2 : Z가 A에게 프로포즈를 한 경우

=> A가 Z를 거절하고 현재 파트너와 짝을 이루었다.

=> A는 Z보다 현재 파트너를 더 선호한다.

=> A와 Z는 stable이다.

2. 모든 경우에 A와 Z는 stable이며, 이는 가정과 모순이다.

※ GS알고리즘이 찾아내는 stable matching은 남자에겐 best case(Man Optimality)이고
    여자에겐 worst case(Woman Pessimality)이다.

- Man Optimality

claim) GS matching은 Man-Optimal이다.

pf) (proof by contradiction)

1. best valid 파트너가 아닌 사람과 짝이 된 남자가 있다고 가정하자.
    -> best valid 파트너에게 거절당한 적이 있으며, 처음으로 그러한 남자를 Y라 하고, 처음으로
        그를 거절한 best valid 파트너를 A라 하자.

2. S를 A와 Y가 짝이 된 stable matching이라 하자.

3. Y가 거절될 때 A와 짝이된 남자를 Z라 하자.
    -> A는 Y보다 Z를 더 선호한다.

4. S에서 B를 Z의 파트너라고 하자.

     <S> (stable)         
 

5. Z는 Y가 A에게 거절된 그 시점에 어떠한 valid 파트너에게도 거절당한 적이 없다.
    -> Z는 B보다 A를 더 선호한다.

6. A와 Z는 현재 파트너 보다 서로를 더 선호한다.
    -> S에서 A-Z는 unstable이며, 이는 2번과 모순이다.

- Woman Pessimality

claim) GS matching은 Woman-Pessimal이다.

pf) (proof by contradiction)

1. S'에서 A-Z가 짝이 되었지만 Z가 A의 worst valid 파트너가 아니라고 가정하자.

2. A가 Z보다 덜 선호하는 Y와 짝이된 Stable matching S가 존재한다.

3. S에서 B를 Z의 파트너라고 하자.

4. Man-Optimality에 의해 Z는 B보다 A를 더 선호한다.

          <S'>                                                             
      
           <S> (stable)         
 

5. A와 Z는 서로를 더 선호하므로 S는 unstable이며, 2번과 모순이다.