일전에 matching problem, 결혼 문제에 대해 다룬 적이 있다.
오늘은 여기서 더 나아간 stable matching problem 이란 것을 소개하고, 이를 해결하는 알고리즘은 GS 알고리즘을 소개해 볼까 한다. [ stable marriage problem 이라고 부르기도 한다. 약자로 SMP]
stable matching problem 이란, n 명의 남상과 n 명의 여성이 모두가 각각 선호하는 순서로 된 파트너 목록을 가질 때, (만약 그런 목록이 존재한다면), 모두가 1대1 매칭이 되는 매칭을 찾는 문제를 말한다.
이러한 매칭은 반드시 존재하는 것은 아니고, 또 존재한다고 해서 unique 한 것도 아니다. 즉 하나도 없거나 아주 많을 수 있다.
이전에 쓴 글의 결혼문제, 혹은 비서 문제는 한 명의 남성 혹은 여성이 n 명을 만나 짝을 찾으려고 할 때, 37% 지점에서의 선택으로 최적한 매칭을 한다는 것이었고, 이를 남성 n 명 여성 n 명으로 확장하고 모든 사람들을 1대1 매칭을 하려는 것이 stable matching problem 이다.
이 문제를 푸는 방법에 대해서 Propose and rejection 알고리듬이라고 불리는 소위 GS 알고리즘이 있다. [Gale, Sahpley 1962]
룰은 두 가지이다. 매 라운드를 거쳐 다음과 같은 룰을 통해 짝을 맺는다.
남자는 자신의 선호도에 순서에 따라 여자에게 프로포즈를 한다. [거절 당하면 다음 선호도의 순서로 간다]
여자는 한 번 짝이 맺어지면 절대 짝이 없는 상태로 돌아가지 않는다.
게일-섀플리 알고리즘은 사실 증명하기 매우 쉽다. 일단 알고리즘을 뜯어보면 남성에게 있어서는 최선의 선택을 하는 것이고, 여성의 입장에서는 최악의 선택이다. [귀류법을 통해 이들을 보일 수 있다.]
GS 알고리즘의 단점
1 . GS 알고리즘은 바람 피우는 것을 방지하지만 바람 피우고 싶은 욕구는 막지 못한다.
2 . 이성애자가 아닌 경우는 어떻게 해야 하는가
3 . 한쪽 성만 최선의 선택을 하게 된다. [위의 남성과 여성의 역할을 바꾸면 여성의 입장에서 최선의 선택이 된다.]
참고문헌
0 . 위키피디아
1 . 오스카 E. 페르난데스, 수학의 참견, chapter 6
2 . TAOCP - 알고리즘 책의 바이블 관련 글
3 . 티스토리 - 증명 과정 등이 아주 잘 설명되어 있음