n명의 남성과 여성이 단체 미팅에서 만났습니다. 여러 게임을 진행하는 동안 모든 사람은 자신이 원하는 상대방의 우선 순위를 맘 속에 정했고, 이제 한쌍씩 짝을 지어 줄 차례가 되었습니다. 그런데 서로 짝이 아닌 두 남녀가 각자 자신의 짝보다 상대방을 더 선호한다는 사실을 알게 되면 두 남녀는 곧장 미팅장을 뛰어나와 도망가 버리게 됩니다. 이런 일이 일어나지 않도록 짝을 지어줄수 있는 방법이 항상 있을까요? 아니면 불가능한 경우가 있을까요?
흔히들 안정적 결혼 문제(Stable marriage problem)라고 부르는 이 문제는 구성적 증명으로 해결되는 대표적 문제입니다. 이 문제를 푼 사람들은 답의 존재성을 보이는 대신 답을 만드는 알고리즘을 제시함으로써 답이 존재함을 보였지요.
이 알고리즘은 다음과 같이 진행됩니다.
처음에는 여성들이 모두 자신이 가장 선호하는 남성의 앞에 가서 프로포즈를 합니다. 남성이 그 중 제일 마음에 드는 여성을 고르면 나머지는 퇴짜를 맞고 제 자리로 돌아갑니다.
퇴짜를 맞은 여성들은 (상대에게 짝이 있는지 없는지는 관계 없이) 다음으로 마음에 드는 남성에게 다가가 프로포즈합니다. 남성들은 현재 자기 짝보다 더 맘에 드는 여성이 다가왔다면, 지금의 파트너에게 퇴짜를 놓고 새 여성에게 넘어갑니다.
더 프로포즈할 여성이 없을 때까지 2번 항목을 반복합니다.
이 알고리즘이 우리가 원하는 답을 구할 수 있음을 보이려면 이 알고리즘이 항상 종료한다는 것, 모든 사람이 짝을 찾는다는 것, 그리고 결과적으로 이뤄지는 짝들이 항상 ‘안정적’임을 증명해야만 하죠. 이 증명은 의외로 간단합니다.
종료 증명
각 여성은 퇴짜 맞을 때마다 지금까지 프로포즈했던 남성들보다 우선순위가 낮은 남성에게 프로포즈합니다. 따라서 각 여성이 최대 n명의 남성들에게 순서대로 프로포즈한 이후엔 더이상 프로포즈할 남성이 없으므로, 이 과정은 언젠가 반드시 종료합니다.
모든 사람들이 짝을 찾는지 증명
프로포즈를 받은 남성은 그 중 한 사람을 반드시 선택하고, 더 우선 순위가 높은 여성이 프로포즈해야만 짝을 바꾸므로 한 번이라도 프로포즈를 받은 남성은 항상 짝이 있기 마련이죠. 귀류법을 적용하여
남녀 한 사람씩 짝을 찾지 못하고 남았다고 가정합시다. 그런데 여성은 우선순위가 높은 순서대로 모두에게 한 번씩 프로포즈하기 때문에, 이 남성에게도 한 번은 프로포즈했겠죠. 이 남성은 프로포즈를 받아들였어야 하고, 따라서 짝을 찾지 못하는 사람은 있을 수 없습니다.
짝들의 안정성
역시 귀류법으로 증명합니다. 이 과정의 결과로 짝을 지었는데 짝이 아닌 두 남녀가 서로 자신의 짝보다 상대방을 더 선호한다고 가정합시다. 여성은 지금 자신의 짝 이전에 그 남성에게 반드시 프로포즈했어야 합니다. 그런데도 이 남성이 이 여성과 짝지어지지 않았다는 말은 더 맘에 드는 여성에게 프로포즈를 받아서 수락했다는 뜻이죠. 남성은 더 맘에 드는 여성이 나타났을 때만 짝을 바꾸므로, 프로포즈 받았던 여성보다 맘에 들지 않는 여성과 최종적으로 짝이 되는 일은 없습니다. 따라서 우리가 가정했던 상황은 존재할 수 없지요.
JongMan
노벨 경제학상이 Stable Marriage Problem을 푸는 Gale-Shapely Algorithm의 저자들에게 돌아갔다는 소식입니다.
알고리즘을 만들어서 노벨 경제학상을 받다니 오오 멋있어요 오오
기념으로 JMBook에서 해당 알고리즘을 다루는 부분을 복붙해 봅니다. ^^
안정적 결혼 문제
n명의 남성과 여성이 단체 미팅에서 만났습니다. 여러 게임을 진행하는 동안 모든 사람은 자신이 원하는 상대방의 우선 순위를 맘 속에 정했고, 이제 한쌍씩 짝을 지어 줄 차례가 되었습니다. 그런데 서로 짝이 아닌 두 남녀가 각자 자신의 짝보다 상대방을 더 선호한다는 사실을 알게 되면 두 남녀는 곧장 미팅장을 뛰어나와 도망가 버리게 됩니다. 이런 일이 일어나지 않도록 짝을 지어줄수 있는 방법이 항상 있을까요? 아니면 불가능한 경우가 있을까요?
흔히들 안정적 결혼 문제(Stable marriage problem)라고 부르는 이 문제는 구성적 증명으로 해결되는 대표적 문제입니다. 이 문제를 푼 사람들은 답의 존재성을 보이는 대신 답을 만드는 알고리즘을 제시함으로써 답이 존재함을 보였지요.
이 알고리즘은 다음과 같이 진행됩니다.
이 알고리즘이 우리가 원하는 답을 구할 수 있음을 보이려면 이 알고리즘이 항상 종료한다는 것, 모든 사람이 짝을 찾는다는 것, 그리고 결과적으로 이뤄지는 짝들이 항상 ‘안정적’임을 증명해야만 하죠. 이 증명은 의외로 간단합니다.
종료 증명
각 여성은 퇴짜 맞을 때마다 지금까지 프로포즈했던 남성들보다 우선순위가 낮은 남성에게 프로포즈합니다. 따라서 각 여성이 최대 n명의 남성들에게 순서대로 프로포즈한 이후엔 더이상 프로포즈할 남성이 없으므로, 이 과정은 언젠가 반드시 종료합니다.
모든 사람들이 짝을 찾는지 증명
프로포즈를 받은 남성은 그 중 한 사람을 반드시 선택하고, 더 우선 순위가 높은 여성이 프로포즈해야만 짝을 바꾸므로 한 번이라도 프로포즈를 받은 남성은 항상 짝이 있기 마련이죠. 귀류법을 적용하여
남녀 한 사람씩 짝을 찾지 못하고 남았다고 가정합시다. 그런데 여성은 우선순위가 높은 순서대로 모두에게 한 번씩 프로포즈하기 때문에, 이 남성에게도 한 번은 프로포즈했겠죠. 이 남성은 프로포즈를 받아들였어야 하고, 따라서 짝을 찾지 못하는 사람은 있을 수 없습니다.
짝들의 안정성
역시 귀류법으로 증명합니다. 이 과정의 결과로 짝을 지었는데 짝이 아닌 두 남녀가 서로 자신의 짝보다 상대방을 더 선호한다고 가정합시다. 여성은 지금 자신의 짝 이전에 그 남성에게 반드시 프로포즈했어야 합니다. 그런데도 이 남성이 이 여성과 짝지어지지 않았다는 말은 더 맘에 드는 여성에게 프로포즈를 받아서 수락했다는 뜻이죠. 남성은 더 맘에 드는 여성이 나타났을 때만 짝을 바꾸므로, 프로포즈 받았던 여성보다 맘에 들지 않는 여성과 최종적으로 짝이 되는 일은 없습니다. 따라서 우리가 가정했던 상황은 존재할 수 없지요.
11년 전