누군가 누구를, 혹은 누군가 무엇을 선택하는 문제는 매우 중요하며 우리는 이런 선택을 도처에서 매순간 마주하며 산다고 해도 과언이 아니다. 그 중 유튜브 알고리즘과 같이 무엇인가를 누구에서 일대 다로 연결해 주는 경우도 있고 장보기와 같이 한 사람이 여러 물건을 선택하는 알고리즘도 존재한다. 사람과 사람의 커플을 구성하는 문제는 어떨까?
그렇지 않은 경우가 물론 있을 수 있지만 수학적으로 단순하게 분석하기 위하여 여성과 남성 한 사람씩 반드시 두 사람이 한 쌍의 커플을 이루어야 한다고 하자. 그런데 세상에는 그 두 사람만 존재하는 것이 아니기 때문에 어느 정도의 경쟁을 피할 수가 없다. 편의상 남성을 소문자 여성을 대문자로 표기하자. 먼저 a가 A와 커플이고 b는 B와 커플이라 가정해 보자. 그런데 A는 a보다 b를 선호하고 b는 B보다 A를 선호한다고 가정해 보자. 그렇다면 이 두 쌍의 커플은 유지되기 어렵다. 왜냐하면 A가 b에게 청혼하는 경우 b는 B를 버리고 A를 선택하는 것이 합리적이기 때문이다. (수학적 단순화의 결과임을 명심하자. 실제로 커플이 깨지기 위해서는 다른 다양한 요인이 필요할 지도 모르겠다.)
몇 명의 남성과 몇 명의 여성이 모두 참여하여 커플을 이루고 있는 경우를 생각하자. 편의상 여성은 대문자로 남성은 소문자로 생각하자. 임의의 커플 Aa에 대하여 a가 A보다 더 선호하는 다른 어떤 X의 짝인 x보다 a가 (X가 선호하는) 선호도가 낮으며, 또한 A가 a보다 선호하는 다른 어떤 y의 짝인 Y보다 (y가 선호하는) 선호도가 낮을 때 이 상태를 ‘안정된 상태’라 한다. 곧, 커플의 구성원 중 하나가 결별을 선언한 다음 다른 커플을 깨뜨릴 유인이 없는 경우를 말하는 것이다.
남성의 수와 여성의 수가 같은 집단에서 각각의 개인이 이성에 대한 선호도가 확고할 때 안정된 상태는 항상 존재할까? 존재한다면 어떻게 찾을까?
만일 그런 방법을 찾는다면 존재성도 같이 증명이 되는 셈이다. 그런데 놀랍게도 그런 방법이 존재한다. 물론 약간의 가정이 필요하다. 모두는 커플이 되지 않는 것 보다는 커플이 되는 것을 선호한다고 하자. 다음과 같은 상황을 보자. 나연, 정연, 지효, 채영은 여성이고 수호, 첸, 디오, 카이는 남성이다. 부등호로 선호도를 표현하였다.
| 나연: 디오>첸>수호>카이 정연: 카이>디오>수호>첸 지효: 첸>디오>수호>카이 채영: 첸>수호>디오>카이 | 수호: 나연>정연>지효>채영 첸: 정연>채영>지효>나연 디오: 정연>채영>나연>지효 카이: 나연>채영>정연>지효 |
그 방법을 예시로 설명한다면 다음과 같다. 먼저 수호, 첸, 디오, 카이가 가장 선호하는 이성에게 각자 청혼한다. 그러면 정연은 디오를 선택하고 나연은 수호를 선택한다. 첸과 카이는 선택을 받지 못했기 때문에 2순위인 채영에게 동시에 청혼을 한다. 그러면 체영 입장에서는 첸을 마음에 두고 있기 때문에 첸을 선택한다. 이 전략의 부제는 ‘잠정 수학’알고리즘이다. 그 이유는 지금 형성된 커플은 아직 ‘영원’하지 않기 때문이다. 다음 라운드에서 아직 짝이 없는 카이는 3순위이지만 이미 짝이 있는 정연에게 청혼을 하게 된다. 정연은 이미 디오와 짝을 이루기로 ‘약속’했지만, 카이를 마음에 더 두고 있기 때문에 디오를 버리고 카이를 선택한다. 이제 졸지에 짝이 없어진 디오. 디오는 2순위인 채영에게 다가간다. 하지만 첸이 있는 채영은 난공불락! 디오는 3순위인 나연에게 청혼한다. 나연은 수호에서 당연히 디오로 선택을 바꾸고 수호는 다시 정연에게 청혼하지만 차이고 지효에게 다가간다 아직 짝이 없는 지효는 수호를 선택한다.
나연-디오, 정연-카이, 채영-챈, 지효-수호
이는 안정적이라는 것을 확인할 수 있을 것이다. 이렇게 커플을 맺어주는 알고리즘을 게일-섀플리 알고리즘이라 한다.
굳이 이 방식을 슈도코드 등으로 설명하지 않아도 예시를 통해 충분히 방법이 설명되었으리라 믿는다. 이것을 슈도코드로 나타내 보자.
먼저 남성 $n$명과 여성
$n$명의 각각의 선호도 순위에 대한 정보를 입력정보로 한다. 여기에 추가로 각각이 맺어진 이성(있을 경우) 그리고 현재 탐색중인 이성의 (논리적)위치 등을 포함시켜도 좋다. 남성의 초기 탐색위치는 각각에 대응되는 여성의 배열의 첫 위치로 한다.
- 맺어지지 않은 남성의 현재 탐색 위치에 있는 여성에게 각각 청혼한다.
- 청혼을 받은 여성은 현재 교제중이 아니거나 혹은 교제중인 이성보다 청혼해온 이성의 순위가 높으면 청혼한 남성과 교제하고 기존의 남성(있다면)은 차버린다.
- 차인 남성 혹은 청혼을 거절당한 남성중 탐색 위치가 마지막(더이상 탐색할 이성이 없음)이거나 혹은 차인 남성이나 청혼을 거절당한 남성이 없다면 종료한다.
- 차인 남성 혹은 청혼을 거절당한 남성의 탐색 위치를 하나 올린다(순위가 낮은 이성쪽으로 한 칸 움직인다.)
- 1로 이동한다.
과연 그런데 임의의 선호도에 대하여 이 알고리즘은 모든 사람들의 짝을 찾고 종료될 것인가? 이 또한 놀랍게도 이 알고리즘은 주어진 $n$명의 남성과 $n$명의 여성에 대하여 $n$쌍의 커플을 탄생시키고 종료된다. 이것을 한 번 증명해 보자. 이 알고리즘이 끝이 난 시점에서 짝이 없는 남성이 존재한다고 가정해 보자. 짝이 없는 여성도 그럼 있다는 이야기. 이 남성은 자신의 리스트를 모두 소진했다. 그랬다는 말은 그 짝이 없는 여성에게 또한 청혼 했다는 이야기. 이건 말이 안 된다. 청혼을 한 번이라도 받은 여성은 반드시 짝이 있어야 하니까. 곧, 처음 한 가정이 모순을 이끌어 내기 때문에 알고리즘이 종료되면 모든 사람은 짝이 있어야 한다!
그런데 이렇게 얻어진 상태가 안정적 상태인지를 생각해 보자. 이를 위하여
이 알고리즘의 결과 얻어진 상태가 안정적이지 않다고 가정해 보자. 예를 들어 민준과 서연이 맺어졌지만 민준이 서연보다 더 호감을 갖는 하윤이가 있고 하윤이는 하윤이의 짝인 이준이보다 민준이에게 호감을 가진다고 가정을 해 보자. 지금 민준이가 서연이와 맺어졌다는 것은 그 전에 하윤이에게 청혼했다가 여하튼 차인적이 있다는 뜻이다. 당시 하윤이는 민준이보다 더 마음이 가는 누군가와 맺어졌었다. 그런데 그렇다면 그 누군가는 이준이이거나 혹은 이준이보더 덜 호감가는 누군가였었기 때문에 이는 모순이다. 따라서 민준이는 서연이와 결별하고 누군가에게 가는 일은 일어날 수 없다.
그렇다면 서연이는 민준이와 결별하고 더 호감이 가는 하준이에게 갈 수 있을것인가? 그런데 이는 하준이 입장에서 생각하면 마찬가지로 불가능하다. 즉 안정적인 결론이다.
그런데 이제 이 알고리즘이 최선인가를 생각해 보면 몇가지 문제를 찾을 수 있다. 우선 게일-섀플리 알고리즘은 남성에게 유리한 알고리즘이라는 사실이다. 사실 안정적 상태는 유일하지 않을 수 있다. 그러면 게일-섀플리 알고리즘은 우리를 어떤 안정적인 상태로 안내하는것일까?
다소 극단적인 예로 A:a>b>c, B:a>c>b, C: b>a>c , a:C>A>B, b:A>B>C, c:A>C>B 인 경우를 생각해 보자. A-b, C-a B-c 가 안정적이다. 또 한 가지는 a-A, b-C, c-B가 안정적이다.
이 두 결과는 사실 첫 번째는 게일-셰플리 알고리즘을 남성이 여성을 선택하는 방식으로 사용한 것이고 두 번째는 여성이 남성을 선택하는 방식으로 사용한 것이다. A-b, C-a, B-c와 A-a, C-b, B-c를 비교해 보면 여성 입장에서 보면 전자가 후자보다 못한 선택이라는 것을 알 수 있다. 반대로 남성 입장에서 보면 확실히 전자가 후자보다 모든 면에서 나은 선택이다.
(이 문단의 내용은 영문 위키피디어 Gale-Shapley algoritms 의 Optimality of the solution 부분을 번역, 각색한 것이다.) 일반적으로 게일-섀플리 알고리즘을 남성이 여성에게 청혼하는 방식으로 적용하면 남성에게는 유리하고 여성에게는 불리한 결과가 얻어진다는 것을 보일 수 있다. 이를 위해 남성이 청혼하는 알고리즘에 의해 얻어진 매칭을 $A$라고 하고 이제 어떤 다른 안정적인 매칭 $B$보다 $A$의 남성들이 더 나은 결과를 얻어갔다는 것을 보일 것이다. 이를 위해 어떤 남성 $m_0$ 그리고 안정적인 매칭 $B$가 존재하여 $B$에서는 $m_0$가 지금 $A$에서 맺어진 짝 보다 더 좋아하는 $w_1$과 맺어졌다고 가정하자. 그 말은 $A$가 만들어질 때 $m_0$는 $w_1$에게 청혼했고, 차였다는 말이다. 그러면 그 때 $w_1$은 $m_2$를 $m_0$보다 선호해서 $m_0$를 찼을 것이다. 따라서 지금 $B$상황에서 $w_1$은 여전히 $m_2$를 $m_0$보다 선소할 것이다. $B$는 안정적이므로 $m_2$가 맺어진 $w_3$를 $w_1$보다 선호해야 한다. 여기까지 이야기를 그림으로 한 번 정리해 보자.
$m_2$는 A에서 $m_0$를 $w_1$에게 차이게 만든 적이 있다. 그 말은 $m_2$가 $w_3$에게 청혼한 적이 (A에서) 있다는 말이다. 그리고 차였다는 말이지. 그러니까 $w_1$에게 청혼하게 이른거니까. 그러면 A에서 $m_2$가 차이게 만든 남자 $m_4$가 있을 것이다. 이와같은 방식으로 계속하면 $m_0$가 $w_1$에게 A에서 차이고 B에서 맺어지고, $w_1$은 $m_2$에게 $A$에서 청혼 받았지만 $B$에서는 못 받았고, $m_2$는 $w_3$에게 $A$에서는 차였지만 $B$에서는 맺어졌고, $w_3$는 $m_4$에게 $A$에서는 청혼을 받았지만 $B$에서는 못 맏았고 이런 사이클이 얻어진다. 그런데 그래프는 유한하므로 이 사이클은 닫힌 사이클이 되어야 한다. 이 사이클에 등장하는 남성은 왼쪽에, 여성은 오른쪽에 둔다면 왼쪽의 남성은 모두 오른쪽의 여성에게 $A$에서 차인 상태가 된다. 그 중에 어떤 한 명이 가장 먼저 차였을 것이다. 문제는 이것이 불가능하다는 것이다. 일반성을 잃지 않고 $m_0$가 $w_1$에게 거절된 사건이 가장 먼저 발생했다고 가정해 보자. 이 때는 $m_2$가 $w_1$에게 청혼을 한 당시거나 그 이후에 발생한 사건이다. 그런데 $m_2$가 $w_1$에게 청혼을 하려면 먼저 $w_3$한테 차였으야 된다. 이는 $m_0$가 가장 먼저 차였단 사실에 모순이다. 곧, $m_0$가 $A$에서보다 더 선호하는 여성과 맺어진 안정적인 상태는 존재하지 않는다.
이와 비슷하게 $A$에서 여성들은 모든 안정적인 상태 중에서 가장 선호도가 낮은 남성들과 맺어져 있다는 것을 알 수 있다.
이런 상황을 개선할 수 있는 다른 알고리즘이 있다면 그러니까 조금 더 형평성에 맞춰진 알고리즘이 등장한다면 이 또한 좋을 것이다.
Seoneo Blog of Mathematics and Physics 