일본 연수의 연수병원 매칭 알고리즘에 대해 알아보자

=목차=

==Stable marriage problem==

연수의와 연수병원을 매칭시키는 문제는 __Stable marriage problem__과 비슷하다.

[[한 마을에 결혼을 간절히 바라는 이성애자 미혼 남녀가 각각 n명씩 있다고 하자. 각자는 이성 전원에 대해 나름대로 선호 순위를 가지고 있다. 이들 모두를 stable한 결혼 상태로 이끌 수 있을까?]]

이 문제에서

① stable한 조합은 항상 존재하는가?

② 존재한다면 어떻게 찾아낼 수 있는가?

③ 그 결과는 유일한가?

""아하견돈|좌|stable 한 결혼이 뭐죠?""

""펀쿨견돈|우|unstable 하지 않은 결혼.""

""아하견돈|좌|그럼 unstable 한 결혼이 뭐죠?""

""펀쿨견돈|우|서로가 서로를 더 좋아하는데 엉뚱한 사람과 맺어진 상황""

==Gale-Shapley algorithm==

1962년 Gale과 Shapley가 이 문제의 해법을 제시했다. n이 아무리 커도 stable한 매칭을 적어도 하나는 찾아낼 수 있다는 결론. 방법은 단순하다.

[[1. 솔로인 남자는 아직 퇴짜 맞지 않은 여자 중 가장 좋아하는 여자에게 프로포즈한다.]]

[[2. 여자는 짝이 없다면 프로포즈를 수락한다. 여러 명에게 동시에 프로포즈를 받았거나 이미 짝이 있는데 더 마음에 드는 남자가 나타났다면 가장 마음에 드는 남자를 남긴다.]]

[[3. 퇴짜 맞은 남자는 그 여자를 후보에서 지우고 다음 순위로 내려간다.]]

이것을 반복한다.

==이 알고리즘은 반드시 끝나는가?==

여자의 수는 유한하다. 한 남자는 같은 여자에게 두 번 프로포즈하지 않으므로 프로포즈 횟수에도 상한이 있다. 무한루프는 생길 수 없다.

==끝내 솔로로 남은 철수&영희가 존재할 수 있는가?==

알고리즘이 다 돌고도 철수와 영희가 솔로인 채로 남았다고 가정해 보자.

커플 상태인 여자는 다른 남자로 환승할 순 있어도 솔로로 되돌아갈 수는 없기 때문에, 솔로로 남은 영희는 단 한 번도 프로포즈를 받지 않은 셈이다. 즉, __영희는 철수에서 프로포즈 받지 않았다.__

한편 철수가 솔로로 남았다는 말은, 모든 여자에게 프로포즈를 했지만 전부 퇴짜를 맞았다는 뜻. 즉, __철수는 영희에게 프로포즈 했으나 차였다.__

영희는 철수에게 프로포즈 받은 적이 없는데, 철수는 영희에게 프로포즈를 한 적이 있다? 모순 발생.

==모두 stable 한가?==

unstable한 상태로 남게 된 커플이 있다고 가정해 보자. 몽룡의 취향은 춘향>향단이고, 춘향의 취향은 몽룡>방자인데 {몽룡, 향단}과 {방자, 춘향}가 맺어졌다.

알고리즘대로 진행했다면, 몽룡은 춘향이에게 먼저 프로포즈 했고 나중에 향단에게 프로포즈 했다. 몽룡과 춘향의 결합을 방해한 자는 누구인가? 방자는 몽룡보다 약해서 불가능하다. 춘향이 눈에 몽룡보다 더 멋져 보인 알파남이 범인일 텐데, __몽룡보다 센 그놈을 방자가 어떻게 이겼단 말인가?__ 모순 발생.

==유불리==

Gale-Shapley 알고리즘을 이용하면 stable 한 매칭을 적어도 하나 만들 수 있다. 그치만 그 결과가 유일하지는 않다.

[[남1의 취향: 여1 > 여2//남2의 취향: 여2 > 여1//여1의 취향: 남2 > 남1//여2의 취향: 남1 > 남2]]

라고 할 때

[[{남1,여1},{남2,여2}//또는//{남1,여2},{남2,여1}]]

두 가지 안정된 상태가 존재.

Gale-Shapley 알고리즘을 이용하면 첫 번째 결과가 나오는데 남자 쪽 선호도가 더 반영된 결과다. 프로포즈를 하는 쪽이 선택지가 넓어서 그런 듯.

==병원 매칭 알고리즘==

일본의 연수 병원 매칭은 실제로 Gale-Shapley 알고리즘을 사용