출처 :

http://navercast.naver.com/contents.nhn?contents_id=5529&category_type=series

안정적인 결혼 문제(Stable Marrige Problem) :

남성 n 명과 여성 n 명이 서로의 파트너를 정하려는 상황이라고 생각하자.

각각의 남성은 선호도에 따라 n 명의 여성에 대해 순위를 매긴 목록을 가지고 있다.

각각의 여성도 선호도에 따라 n 명의 남성에 대해 순위를 매긴 목록을 가지고 있으며, 이 순위에 동률은 없다고 하자. 

아무렇게나 무작위로 짝을 지어서 남A-여A, 남B-여B 커플이 만들어졌다고 해보자.

그러면 남A가 자기 파트너인 여A보다 여B를 더 좋아하고,

여B 역시 자기 파트너인 남B보다 남A를 더 좋아하는 상황이 벌어질 수 있다.

이러면 바로 두 남녀가 바람이 나서 두 커플이 다 깨져 버리는 불상사가 생긴다.


따라서 이러한 사고가 발생하지 않기 위해서는,

남A가 여B를 더 좋아하더라도 여B가 자기 파트너인 남B를 더 좋아해서 남A의 구애를 거절할 수 있어야만 한다.

이런 조건 아래 남녀 각각 n 명의 짝을 맺어주는 문제를 '안정적인 결혼 문제(Stable Marriage Problem)'라 부른다.

전통적인 결혼 알고리즘(Traditional Marriage Algorithm)

해당 문제를 해결하기 위해서는 다음과 같은 알고리즘을 활용할 수 있다.

 1. 매일 아침 남성들은 자신의 목록에서 가장 위에 있는 여성을 찾아간다.

 2. 여성은 자신을 찾아온 남성 가운데, 자신의 목록에서 가장 위에 있는 사람에게는 “내일 다시 오세요.”라고 답하고,

     나머지에게는 “다른 여성을 찾아보세요.”라고 답한다.

 3. 거절당한 남성이 없으면 종료.

 4. 거절당한 남성들은 저녁에 (술집에) 모여 (울면서) 자신을 거절한 여성을 목록에서 지운다.

 5. 다시 1번부터 반복한다.

전통 결혼 알고리즘에 따른 4대4 짝짓기 예시. (남자가 원, 여자가 네모)

※ 주의

현실에서는 '어장관리'를 위해 구애를 거절하지 않는 경우도 있지만, 모든 남녀가 정직하게 반응한다고 가정하자.

또, 최종 과정에서 “차라리 솔로로 살래.”라는 결론을 내리는 경우도 있지만,

우리가 다루고 있는 상황에서는 남녀 모두 최선을 다해 커플을 만든다고 가정하자.

문제 : TMA 알고리즘을 통하여 맺어진 커플들은 모두 안정적인가?

1) 여A의 최종 커플은 남A이지만, 사실 여A는 남A보다 남B를 더 좋아하는 경우

TMA에 따르면 여A는 자신을 방문한 남성 가운데 가장 순위 높은 남성과 커플이 되어야 하므로,

여A의 최종 커플이 남A라는 사실은 남B가 여A를 방문한 적이 없다는 뜻이 된다.

즉, 남B는 자기가 여A보다 더 좋아하는 여성과 이미 커플이 되어 있다는 뜻이다.

따라서 여A-남A 커플이 남B 때문에 깨어지는 일은 없다.

2) 남A가 사실 현재 커플인 여A보다 여B를 더 좋아하는 경우

남A의 목록에서 여B는 여A보다 더 높은 곳에 있으므로, 남A는 여A를 찾아가기 전에 여B를 먼저 방문해야 한다.

그런데도 남A가 여B와 커플이 되지 않았다는 것은 여B가 남A보다 더 좋아하는 남성과 커플이 되었다는 뜻이므로,

남A-여A 커플이 여B 때문에 깨어지는 일은 없다.

이상의 관찰로부터 최종 결과로 만들어진 커플은 모두 안정적임을 알 수 있다.

남성에게 가장 유리한 알고리즘은 바로 TMA 알고리즘이다.

우선 "남성에게 가장 유리한 알고리즘"을 다음과 같이 정의한다.

안정된 커플을 생성해내는 알고리즘에 따라 커플이 될 수 있는 모든 여성 가운데

가장 순위가 높은 여성과 커플이 되게 하는 알고리즘

그리고 "안정된 커플을 생성해내는 알고리즘에 따라 커플이 될 수 있는 모든 여성 가운데 가장 순위가 높은 여성"을

간단히 "최고의 여성"이라 하자.

TMA 알고리즘은 모든 남성들을 "최고의 여성"과 짝지어 줄 수 있으며, 따라서 남성들에게 이상적인 알고리즘이다.

이는 다음과 같이 증명될 수 있다.

1) TMA에 따라 짝을 짓고 보니, 최고가 아닌 여성과 커플이 된 남성이 있는 경우

이것은 그 남자가 어느 시점에선가 최고의 여성에게 거절을 당한 적이 있다는 뜻이다.

이런 일이 여러 남성에게 생길 수도 있으므로, 이런 일이 최초로 벌어진 때를 생각하자.

사건의 주인공인 남A가 최고의 여성인 여A에게 거절을 당한 순간을 생각하면, 그 이전에는 이런 일이 없어야 한다.

여A가 남A를 거절하려면, 여A가 가진 목록에 남A보다 더 순위가 높은 남B가 존재하고,

거절의 순간 남B는 여A에게서 "내일 다시 오세요"라는 말을 듣고 있어야 한다.

최고의 여성에게 거절당하는 최초의 순간이라고 하였으므로,

그 이전에 남B를 거절했던 여성이 있다면 이 여성은 남B에게 최고의 여성은 될 수 없다.

즉, 여A는 남B에게 최고의 여성이거나 아니면 그보다 더 순위가 높은 여성이라야 한다.

2) 남A와 여A가 커플이 될 수 있는 다른 알고리즘 S가 존재할 경우 

"최고의 여성"에 대한 정의를 생각하면 이런 알고리즘은 반드시 존재해야 한다.

이제 남A-여A 커플과 남B를 생각하자. 여A는 남B를 더 좋아한다고 했고,

남B에게 여A는 최고의 여성이거나 그보다 더 순위가 높은 여성이므로, 여A와 남B는 바람이 날 수밖에 없다.

즉, 알고리즘 S는 안정적인 커플을 만들어내지 못한다.

이것은 "최고의 여성"에 대한 정의에 모순이 되므로,

결국 TMA에 따라 만들어진 커플 가운데 최고의 여성이 아닌 다른 여성과 커플이 되는 남성은 존재하지 않는다.

같은 논법으로 생각하면 TMA에 따르면 모든 여성은 "최저의 남성"과 커플이 된다.

실제로 미국에서는 해당 알고리즘이 병원의 레지던트 배정에 사용되고 있다고 한다.

지원자는 가고자 하는 병원의 순위를 매기고,

병원은 원하는 레지던트의 순위를 매겨 TMA에 따라 컴퓨터로 배정하는 것이다.

병원 쪽이 남성, 레지던트 쪽이 여성의 역할을 맡고 있어서, 현재 이 시스템은 병원 쪽에 유리하게 되어 있다.

...


으음, 물론 연애에는 변수가 매우 많으니 이에 적합한 논리적 모델을 찾기란 쉽지 않을 것입니다.

하지만 이러한 사고 실험이 과학 발전에 도움이 될 수도 있다는 점에서는 꽤 가치가 있는 시도라고 할 수 있겠군요.

앞으로도 사회 및 인간의 행동과 관련된 수학적 분석들이 많이 나와주었으면 하는 바램입니다.