짝을 안정하게 맺기
짝을 바꿔 도망가지 않게 맺어 보세요
남학생 셋과 여학생 셋이 각자 좋아하는 상대의 우선순위를 1등부터 3등까지 적어 냅니다. 무작위로 세 쌍을 짝지어 봅니다.
그러면 서로 지금 짝보다 상대방을 더 좋아해서 둘이 손잡고 도망치는 불안정한 쌍이 꼭 생깁니다. 누구도 딴마음을 품지 않는 완벽하게 안정한 짝짓기가 언제나 가능할까요?
이야기
Konrad Jacobs, Erlangen, Copyright is wi
CC BY-SA 2.0 de · 위키미디어 공용
1962년 게일과 섀플리가 이 방법을 냅니다. 한쪽이 가장 좋아하는 상대에게 신청하고, 받은 쪽은 지금 쥔 것보다 나으면 갈아타고 아니면 거절합니다. 거절당한 사람은 다음 상대에게 갑니다. 더 신청할 데가 없을 때까지 되풀이합니다.
그런데 이 방법에는 뚜렷한 편이 있습니다. 먼저 신청하는 쪽에게 유리합니다. 남자가 신청하면 남자에게 가장 좋은 안정 짝짓기가 나오고, 여자가 신청하면 여자에게 가장 좋은 것이 나옵니다. 같은 사람들, 같은 취향인데 결과가 갈립니다.
이것이 실제로 문제가 되었습니다. 미국은 1952년부터 의대 졸업생을 병원에 배정하는 데 이 방식을 써 왔는데, 병원이 신청하는 쪽이었습니다. 1990년대에 이것이 밝혀져 학생이 신청하는 쪽으로 바뀌었습니다.
왜 늘 안정한 짝이 나올까요. 신청을 받은 쪽은 한 번 갈아탄 뒤로 더 나쁜 쪽으로 내려가지 않기 때문입니다. 그러니 갈아탈 때마다 형편이 나아지고, 사람 수가 유한하니 언젠가 멈춥니다.
멈춘 자리에 도망칠 짝이 없는 까닭도 같습니다. 어떤 남자가 지금 짝보다 더 좋아하는 여자가 있었다면 이미 그 여자에게 신청했을 것이고, 거절당했다는 것은 그 여자가 더 나은 사람을 쥐고 있다는 뜻이기 때문입니다.
그들은 이 방법을 쓰면서도 그것이 이렇게 널리 쓰일 줄은 몰랐습니다. 오늘 이 알고리즘은 의대생과 병원, 학생과 학교, 심지어 장기 기증자와 환자를 잇는 데까지 쓰입니다. 섀플리는 이 공로로 2012년 노벨 경제학상을 받았습니다.
지금 사람들의 삶을 실제로 정하고 있습니다. 미국 의대 졸업생과 병원을 맺는 배정, 뉴욕 등의 고등학교 배정이 이 방법으로 돌아갑니다.
신장 교환 프로그램에도 비슷한 수학이 쓰여, 짝이 안 맞던 기증자와 환자를 여럿 묶어 살립니다.
계단 넷 — 같은 사실을 네 깊이로
카드로 짝을 지어 본다
동물 카드 세 장과 먹이 카드 세 장을 준비하고 각자 좋아하는 순서를 정합니다. 아무렇게나 짝을 지어 주면 "난 저게 더 좋은데!" 하며 불만이 터져 나옵니다.
하지만 정해진 순서대로 제안하고 거절하는 규칙을 따르면 신기하게도 서로 눈이 맞아 도망칠 수 없는 평화로운 짝이 반드시 하나로 완성됩니다.
짝을 맺어 보세요
안정 = 서로 지금 짝보다 상대를 더 좋아하는 두 사람이 없다.
제안하고 기다리는 규칙
게일과 섀플리가 만든 규칙은 간단합니다. 남학생들이 각자 1순위 여학생에게 먼저 고백합니다. 여학생은 여러 명에게 고백을 받으면 가장 마음에 드는 한 명만 '임시로 붙잡아 두고' 나머지는 찹니다.
차인 남학생들은 다음 순위 여학생에게 다시 고백하고, 여학생은 더 나은 상대가 오면 이전 짝을 차고 갈아탑니다. 더 이상 제안할 사람이 없을 때까지 반복하면 모두가 안정한 짝을 찾게 됩니다.
청혼하는 쪽이 유리합니다
20 쌍이면 3 번째 vs 6.7 번째 — 먼저 나서는 쪽이 이깁니다.
게일–섀플리 알고리즘
이 알고리즘을 게일-섀플리(Gale-Shapley) 알고리즘이라 부릅니다. 이 과정은 최대 단계 안에 반드시 종료되며, 결과는 항상 안정 매칭(Stable Matching)임이 증명되어 있습니다.
만약 어떤 남녀가 현재 짝보다 서로를 더 선호한다면, 남자는 이미 그 여자에게 먼저 제안했어야 하고 여자는 더 좋아하는 사람을 선택했어야 하므로 탈주 쌍이 존재할 수 없는 모순이 생깁니다.
거짓말이 이득일까요
받는 쪽은 속이면 이득일 수 있습니다 — 제도가 한쪽에 기울어 있습니다.
시장 설계
앨빈 로스와 로이드 섀플리는 이 이론으로 2012년 노벨 경제학상을 수상했습니다. 제안하는 집단에게는 가장 유리한 매칭이 되고 받는 집단에게는 덜 유리하다는 비대칭성도 수학적으로 규명되었습니다.
오늘날 의대 졸업생과 수련 병원 배정, 신입생 고교 배정 알고리즘, 신장 기증자와 수혜자를 교차 연결하는 시장 설계(Market Design) 메커니즘의 핵심 뼈대로 작동합니다.
실제로 쓰입니다
로스와 섀플리가 2012년 노벨 경제학상을 받았습니다.
풀어 보기
게일-섀플리 안정 매칭 알고리즘. 남성 와 여성 의 선호도가 다음과 같다.
· ,
· ,
(1) 남성이 제안하는 게일-섀플리 알고리즘을 적용했을 때 최종 매칭 쌍을 구하시오.
(2) 만약 로 매칭되었다면 이탈하는 불안정 쌍(Blocking pair)을 찾으시오.
(3) 모든 선호 순위가 엄격할 때 게일-섀플리 알고리즘으로 도출된 안정 매칭은 항상 유일하게 존재하는지 여부를 쓰시오.
(1) , (2) 은 서로 지금 짝보다 상대를 더 선호합니다.
답과 풀이 보기
(1) 입니다.
· 1 회차 — 둘 다 에게 제안합니다
· 은 을 더 좋아하므로 을 잡아 두고 를 거절합니다
· 2 회차 — 가 에게 제안하고 받아들여집니다
더 제안할 사람이 없으므로 끝납니다.
(2) 막는 짝은 입니다.
· 은 지금 짝 보다 을 더 좋아합니다
· 은 지금 짝 보다 을 더 좋아합니다
둘 다 지금보다 낫다고 여기므로 그 둘은 갈라져 나옵니다. 그래서 그 매칭은 안정하지 않습니다.
(3) 알고리즘의 결과는 늘 하나로 정해지지만, 안정 매칭 자체가 유일한 것은 아닙니다.
· 남성이 제안하면 언제나 남성에게 가장 좋은 안정 매칭이 나옵니다
· 여성이 제안하면 여성에게 가장 좋은 안정 매칭이 나옵니다
· 이 문제에서는 그 둘이 같아 유일하지만, 선호가 엇갈리면 서로 다릅니다
다만 안정 매칭이 적어도 하나는 반드시 있다는 것은 언제나 참입니다 (1962 년 게일·섀플리).
이 알고리즘은 지금 미국 의대 졸업생과 병원을 이어 주는 데 쓰이고 있습니다. 뉴욕의 고등학교 배정에도, 신장 기증자 짝짓기에도 쓰입니다.
섀플리와 로스는 2012 년 노벨 경제학상을 받았습니다. 결혼 문제로 시작한 놀이가 사람의 목숨을 이어 주고 있습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
이 방법은 지금 실제로 사람들의 삶을 정합니다.
- 전공의 배정 — 미국 의대 졸업생과 병원을 이 방법으로 맺습니다
- 학교 배정 — 뉴욕 등에서 학생과 고등학교를 이렇게 맺습니다
- 장기 기증 교환 — 신장 교환 프로그램에도 비슷한 수학이 쓰입니다
이어지는 장
서로 좋아하는 순서가 얽혀 있어도 파탄 나지 않는 안정적인 짝짓기가 반드시 존재한다는 증명은, 여러 사람의 선호를 모아도 완벽한 투표가 불가능하다는 역설과 흥미로운 대조를 이룹니다 — 제111장 에서 사회적 선택의 한계를 함께 보세요.
영감을 받은 곳
데이비드 게일(David Gale)과 로이드 섀플리(Lloyd Shapley)가 1962년 《미국수학월보》(The American Mathematical Monthly)에 발표한 논문 「College Admissions and the Stability of Marriage」에서 왔습니다.