안정 결혼 문제(stable matching, stable marriage, gale shapley algorithm)
1. 어떻게 남녀를 맺어줘야 행복하게 살수 있을까?
결혼중매업자인 대혁에게는 200명의 고객이 있다. 100명은 남자, 100명은 여자이다.
여자 고객은 각자 남자 고객 100명을 대상으로 선호도에 따라 순위를 매겨 대혁에게 제출한다.
각자 명단의 맨 위에는 완벽한 이상형이 있고, 아래로 갈수록 호감도가 떨어져 맨 아래에는 최악의 기피남이 있다.
남자 고객 100명도 마찬가지로 여자 고객 100명을 대상으로 순위를 매겨 제출한다
대혁은 이 선호도 조사 결과를 바탕으로 남녀 고객을 맺어줘야한다.
어떻게 맺어줘야 이들이 결혼에 골인하고 가정을 이루고 오래오래 행복하게 살 수 있을까?
당연한 말이지만, 일부는 자신의 제1지망과 맺어지지 못한다.
같은 남자를 여러 여자가 제1지망으로 찍었다면 누군가는 고배를 마셔야한다.
만약 여러 여자에게 제1지망으로 뽑힌 남자가 없고, 여러 남자에게 제1지망으로 뽑힌 여자도 없다고 해보자.
그렇다고 해도 모두에게 행복이 보장되는 것은 아니다.
편의상 남자 3, 여자 3을 생각해보면
남자 a,b,c의 선호도
a: A,B,C
b: B,C,A
c: C,A,B
여자 A,B,C의 선호도
A: b,c,a
B: c,a,b
C: a,b,c
이 예시에서는 남자마다 좋아하는 여자가 다르고, 여자들도 좋아하는 남자가 각기 다르다.
하지만 서로 눈이 맞은 천생연분이 없으며 불행의 소지가 다분하다.
장래의 배우자들은 서로가 서로의 제1지망이어야 더 없이 행복할 수 있다.
예를 들어 B가 c를 열렬히 사랑하지만 c도 B를 열렬히 사랑해야한다.
남자 a,b,c의 선호도
a: A,B,C
b: C,A,B
c: B,C,A
여자 A,B,C의 선호도
A: a,b,c
B: c,a,b
C: b,a,c
하지만 다음과 같이 세 남자가 모두 한 여자를 좋아하는 경우는 흔하다
남자 a,b,c의 선호도
a: A,B,C
b: A,B,C
c: A,C,B
모든 여자가 똑같은 명단을 제출할 수도 있다
여자 A,B,C의 선호도
A: a,b,c
B: a,b,c
C: a,b,c
대혁은 어떻게 맺어주는 것이 좋을까?
되도록 많은 사람을 제 1지망으로, 적어도 제 2지망과 맺어주는 것?
아니면 가장 싫은 상대와 맺어지는 사람을 최소화 해주는 것?
이 질문에 분명한 답은 없지만 대혁은 현실주의자다.
모두가 행복한 세상이란 애초에 존재하지 않는다는 것을 안다.
그래서 목표를 소박하게 잡는다. 자신이 맺어준 부부들이 바람피우지 않고 결혼을 안정적으로 유지하는 것이다.
이 목표는 현실적으로 무엇을 의미할까?
일단 바람을 방지하려면 마음에 둔 상대가 엇갈려 배치된 부부들이 발생하지 않게 조치해야한다.
c와 A부부, a와 B 부부를 생각해보자.
c는 아내 A보다 B를 더 좋아하고 B도 남편 a보다 c를 더 좋아한다고 하면?
이런 조합은 바람이 나서 깨지기 쉽다.
여기서 주목할 점은 c가 A보다 B를 더 좋아한다고 하더라도, B가 c보다 남편 a를 더 사랑한다면, 문제가 없다.
왜냐하면 B가 c의 접근을 거부할테니까
만약 c가 아내 A보다 B를 더 좋아하고 B도 남편 a보다 c를 더 좋아하는데 마침 a도 아내 B보다 A를 더 좋아하고
A도 남편 c보다 a를 더 좋아한다면?
이래도 문제는 없다. 서로 부부관계를 바꾸면 네 사람 모두 행복해지니까
2. 안정적 결혼 알고리즘(stable marriage algorithm)
안정적 결혼 알고리즘은 gale - shapley 알고리즘이라고도 불린다.
미국 수학자이자 2012년도 노벨 경제학상 수상자인 로이드 섀플리와 데이비드 게일이
1962년 안정적 짝짓기 문제를 제시하고 그 문제를 풀 수 있는 알고리즘을 밝혔다.
이들의 논문은 동수의 남녀 그룹이 있을 때 이들을 아무도 바람나지 않도록 짝 지우는 방법을 보여준다
이 때 기억할 점은 게일 섀플리 알고리즘은 행복을 보장하지 않고 안정성만 보장한다.
다시 말해 A가 b에게 반했더라도 결혼은 c와 하는 상황이 충분히 가능하다.
다만 이 경우 b가 A보다 아내를 더 사랑하는 상황을 보장해서 바람이 나는 것을 방지한다.
그렇다고 b가 행복한 결혼을 했다는 것은 아니다. 그도 다른 여자를 꿈꿀 수 있다.
다만 그 경우에도 게일 섀플리 알고리즘은 꿈속의 여인이 b보다 자기 남편을 선호하는 상황을 만들어 바람을 방지한다.
-------------------------------------------------------------------------------------------------------------------------------------------------------------
4명의 남자 대혁, 상혁, 중혁, 소혁과 4명의 여자 가연, 수경, 수연, 서현을 예로 들어 설명해보자.
남녀의 수는 상관없고 남녀가 동수이기만 하면 된다. 몇명이든 게일 섀플리 알고리즘의 작동원리는 같다.
남자들의 선호도가 다음과 같고
| 1 | 2 | 3 | 4 | |
| 대혁 | 가연 | 수경 | 수연 | 서현 |
| 상혁 | 수연 | 서현 | 가연 | 수경 |
| 중혁 | 서현 | 가연 | 수연 | 수경 |
| 소혁 | 가연 | 수연 | 수경 | 서현 |
여자들의 선호도가 다음과 같다.
| 1 | 2 | 3 | 4 | |
| 가연 | 대혁 | 소혁 | 상혁 | 중혁 |
| 수연 | 소혁 | 대혁 | 중혁 | 상혁 |
| 서현 | 대혁 | 소혁 | 상혁 | 중혁 |
| 수경 | 대혁 | 소혁 | 중혁 | 상혁 |
1라운드에서 남자들은 각자 가장 선호하는 여자에게 구애한다.
대혁과 소혁은 가연에게 대시하고 상혁은 수연에게 고백하고, 중혁은 서현에게 전화한다.
만약 2명 이상에게 구애를 받은 여자는 그 중 가장 선호하는 남자를 고른다.
1명에게 구애를 받으면 그 남자와 짝이 된다.
누구에게도 구애를 받지 못하면 이번 라운드에 짝 없이 남는다.
가연의 명단에서 소혁보다 대혁의 순위가 높으므로 가연은 대혁을 선택한다.
지금까지 나온 조합은 다음과 같다.
대혁 - 가연, 상혁 - 수연, 중혁 - 서현
아직은 잠정적 약혼 상태이지, 결혼한 것은 아니다.
다음 라운드에서는 짝이 없는 남자가 자신을 거절한 적 없는 여자중에 가장 선호하는 여자에게 구애한다.
1라운드에서 짝을 찾지 못한 남자는 소혁뿐이다.
소혁은 가연을 제외하고 다른 여자들 중 선호도가 제일 높은 수연에게 고백한다.
마침 수연도 현재 짝 상혁보다 소혁을 더 좋아하므로 현재 약혼을 취소하고 소혁과 약혼하게 된다.
대혁 - 가연, 소혁 - 수연, 중혁 - 서현
이제 상혁이 짝이 없는 유일한 남자가 되었다.
이번 라운드에서 상혁은 거절당한 수연을 제외하고 선호도가 제일 높은 서현에게 고백한다.
마침 상혁은 서현의 명단에서 중혁보다 순위가 높다.
따라서 현재 약혼 명단은...
대혁 - 가연, 소혁 - 수연, 상혁 - 서현
이제는 중혁만이 홀로 남겨졌다.
중혁은 서현을 제외한 나머지 중 선호도가 가장 높은 가연에게 전화해보지만 이미 가연은 대혁이가 제일 마음에 든다.
따라서 아무 변화도 일어나지 않는다.
중혁은 다시 서현, 가연을 제외한 나머지 중 선호도가 가장 높은 수연에게 고백한다.
하지만 수연도 현재 약혼자 소혁이 제일 좋으므로 고백을 받아들이지 않는다.
절박해진 중혁은 마지막 남은 수경에게 어쩔 수 없이 전화해보고 수경은 환영한다.
너무 오래 혼자였던 수경의 입장에서는 비록 호감도 3위이지만 중혁이라도 감지덕지다.
게일 섀플리 알고리즘은 이렇게 남자들이 구애하고 여자들이 구애받는 라운드를 반복하다가,
모든 남자가 짝을 찾으면 종료하게 된다. 남녀 동수이므로 같은 단계에서 여자들도 모두 짝을 찾게 된다.
이로써 최종 결과는
대혁 - 가연, 소혁 - 수연, 상혁 - 서현, 중혁 - 수경
그리고 이들은 모두 언제까지나 행복하게, 적어도 안정적으로 산다.
-------------------------------------------------------------------------------------------------------------------------------------
1. 이 알고리즘은 무한정 진행할 수 없다. 유한한 횟수에 반드시 종료한다.
최악의 경우 모든 남자가 모든 여자에게 돌아가며 구애하는 경우이다. 이때도 오래걸려서 그렇지 끝은 난다.
2. 약혼한 남자의 수는 항상 약혼한 여자의 수와 같다.
또한 여자는 일단 약혼하면 약혼자가 바뀔 수는 있지만 약혼 상태를 쭉 유지한다.
남자는 아직 자신을 거절한 적 없는 여자 중 가장 선호하는 여자에게 구애하므로 과정의 끝에서 짝 없이 남는 사람이 있을 수도 없다.
예를 들어 대혁이 수경을 명단에 적으면, 수경을 원하는 남자가 아무도 없다면 결국에 대혁과 수경이 맺어진다.
이 알고리즘은 전원의 결혼을 보장하게 된다.
3. 이 알고리즘은 결혼의 안정성을 보장한다.
만약 대혁과 가연이 맺어지고, 상혁과 서현이 맺어졌다고 가정하자.
이 때 가연은 상혁을, 상혁은 가연을 배우자보다 더 좋아하는 상황이 가능할까?
이런 상황이 가능하다면 결혼이 깨지는 건 시간문제지만 가능하다고 가정하는 순간 논리적 모순에 직면하게 된다.
그러므로 역으로 이런 상황은 불가능하다는 뜻이다.
불안정한 결혼을 가정해보자.
대혁과 가연, 상혁과 서현은 부부다. 하지만 가연은 상혁을 상혁은 가연을 배우자보다 더 좋아한다고 해보자.
그렇다면 애초에 이 알고리즘에 따라 결혼한다면 상혁은 서현에게 구애하기 전 가연에게 먼저 구애해야한다.
이때 발생가능한 상황은 1) 가연이 상혁의 구애를 받아들이거나, 2) 가연이 상혁의 구애를 거절하거나
만약 1)이라면 어째서 현재 가연은 상혁과 부부가 아닌가?
가연이 결과적으로 상혁을 버리고 상혁보다 좋은 남자를 선택했기 때문이다.
가연이 현재 대혁과 부부라는 것은 어쨌거나 가연의 명단 상위에 대혁이 상혁보다 상위에 있었다는 증거다.
따라서 논리적으로 모순이다.
만약 2)라면 가연이 이미 상혁보다 좋은 남자를 선택했기 때문이다.
가연이 현재 대혁과 부부라는 것은 어쨌거나 대혁이 상혁보다 상위에 있었다는 증거고 이번에도 애초에 가정에 모순이다.
결과적으로 게일 섀플리 알고리즘은 유한번 반복하고, 모두가 배우자를 얻게 되고 조합이 안정적이다.
-----------------------------------------------------------------------------------------------------------------------------------------------------------
3. 알고리즘이 완벽한가?
게일 - 섀플리 알고리즘은 남자가 구애하고 여자가 받아들였지만, 반대로 여자가 구애하고 남자가 받아들이면 어떨까?
남자들의 선호도
대혁: 가연, 수경, 서현
상혁: 수경, 서현, 가연
중혁: 서현, 가연, 수경
여자들의 선호도
가연: 상혁, 중혁, 대혁
수경: 중혁, 대혁, 상혁
서현: 대혁, 상혁, 중혁
이 경우에 게일 섀플리 알고리즘에 의하면 1라운드만에 끝난다.
남자들이 각자 1지망에 구애하면 대혁 - 가연, 상혁 - 수경, 중혁 - 서현으로 깔끔하다.
하지만 여자들의 입장에서는 모두 최악의 남자와 짝이 되었다.
반대로 여자들이 먼저 선택해보자.
1라운드에 가연 - 상혁, 수경 - 중혁, 서현 - 대혁으로 끝났다.
여자들은 각자 가장 선호하는 남자를 얻었지만 남자들은 최악의 여자와 평생을 보내게 된다.
게일 섀플리 알고리즘은 복잡하지 않지만 만능 열쇠는 아니다. 현실에는 다양한 변수가 있다.
그럼에도 불구하고 복잡하지 않게 안정적인 조합을 얻으니 실생활에 많이 활용된다.
의대 졸업생들을 병원에 인턴으로 배정할때, 지원자는 가고 싶은 병원의 순위를 매기고,
병원은 원하는 인턴의 순위를 매겨 안정적 결혼 알고리즘을 이용한 컴퓨터 배정 프로그램을 돌린다.
물론 병원이 갑이 되어 1라운드 구애자의 유리한 고지에 선다.
또한 유저를 인터넷 서비스 서버에 배정할때도 안정적 결혼 알고리즘이 유용하게 쓰일 수 있다.
4. 연습문제
위에서 예시로 설명한 상황을 그대로 구현하면 된다.
1) 현재 라운드에 짝이 없는 남자들은 이전 라운드에서 거절당하지 않은 여자들 중 가장 선호도가 높은 여자에게 고백
2) 짝이 없는 여자들 중 여러명에게 고백받은 여자는 그 중 가장 선호하는 남자와 약혼, 1명에게 고백받은 여자는 그 남자와 약혼
3) 짝이 있는 여자라면, 현재 짝인 남자와 고백한 남자의 선호도를 비교하여 가장 선호도가 높은 남자로 바꿀 수 있다
4) 모든 남자가 짝을 찾을때까지 위 라운드를 반복
조금 느리긴 한데... 통과 됐다는 것에 의의를 두자
from sys import stdin
n = int(stdin.readline())
man = [0]*(n+1)
woman = [0]*(n+1)
for i in range(1,n+1):
man[i] = list(map(int,stdin.readline().split()))
for i in range(1,n+1):
woman[i] = list(map(int,stdin.readline().split()))
matching = [0]*(n+1)
no_matching_woman = list(range(1,n+1))
man_reject_woman = [[] for _ in range(n+1)]
#각 남자의 라운드마다 득표현황
vote_man = [[] for _ in range(n+1)]
while 1:
#짝이 없는 사람중에서..
for i in no_matching_woman:
#여자가 best인 사람을 왼쪽부터 차례대로 뽑는데
for best in woman[i]:
#거절당하지 않은 남자중에서..
if best not in man_reject_woman[i]:
#베스트에 투표를 한다
vote_man[best].append(i)
break
#matching 시작
for i in range(1,n+1):
#2표 이상 득표를 한 남자는..
if len(vote_man[i]) >= 2:
#최선의 선호도를 가지는 여자를 선택한다
min_ind = n+1
for j in vote_man[i]:
j_index = man[i].index(j)
#index가 가장 작아야 최선의 선호도를 가진 여자
if min_ind > j_index:
min_ind = j_index
#i번째 남자는 min_ind가 최선의 여자
matching[i] = man[i][min_ind]
for j in vote_man[i]:
if j != man[i][min_ind]:
man_reject_woman[j].append(i)
elif len(vote_man[i]) == 1:
matching[i] = vote_man[i][0]
no_matching_woman = []
vote_man = [[] for _ in range(n+1)]
for i in range(1,n+1):
if i not in matching:
no_matching_woman.append(i)
if matching[i] != 0:
vote_man[i].append(matching[i])
if no_matching_woman == []:
break
for i in range(1,n+1):
print(matching[i])
