안정 결혼 문제

1. 개요[편집]

안정 결혼 문제 Stable Marriage Problem
발표	David Gale · Lloyd Shapley (1962), "College Admissions and the Stability of Marriage"
입력	두 집단 각 $n$명, 상대 집단 전원에 대한 완전 선호 순위
안정성	서로를 현재 짝보다 선호하는 쌍(차단쌍)이 없음
알고리즘	지연 수락(deferred acceptance) — $O(n^2)$
보장	안정 매칭은 항상 존재 · 제안자 최적 · 제안자 측 전략 조작 불가
해집합 구조	분배 격자 (Conway) · 개수 세기는 #P-완비
실무	NRMP 전공의 배정 · 뉴욕/보스턴 고교 배정
수상	2012 노벨 경제학상 (Shapley · Roth)

안정 결혼 문제(stable marriage problem)는 크기가 같은 두 집단의 구성원이 각각 상대 집단 전원에 대한 순위를 가지고 있을 때, “서로 지금 짝보다 상대를 더 좋아하는 두 사람”이 한 쌍도 없도록 전원을 짝지을 수 있는가를 묻는 문제다. 1962년 데이비드 게일과 로이드 섀플리가 American Mathematical Monthly에 실은 다섯 쪽짜리 논문이 문제를 정의하고, 존재성 증명과 알고리즘을 한꺼번에 내놓았다.¹

이름에 “결혼”이 붙어 있고 홀의 결혼정리와 발표 시기도 멀지 않지만, 두 문제는 전혀 다르다. 홀의 정리는 “짝지을 수 있느냐”(존재성)를 묻고 선호가 없다. 안정 결혼 문제는 짝짓기가 가능하다는 것을 전제로 깔고 — 선호가 완전하므로 완전 매칭은 $n!$개나 있다 — 그중 아무도 이탈할 유인이 없는 것을 찾는다. 목적함수를 최소화하는 헝가리안 알고리즘류의 배정 문제와도 다르다. 여기엔 최소화할 총비용이 없고, 개인의 순위만 있다.

그래서 이 문제는 조합 최적화이면서 동시에 게임 이론이다. “안정”은 최적성이 아니라 균형 개념이고, 그 균형을 계산하는 알고리즘이 그대로 시장 설계의 엔진이 된다. 2012년 노벨 경제학상이 섀플리와 앨빈 로스에게 간 이유가 이것이다.

2. 문제 정의와 차단쌍[편집]

제안자 집합 $M$과 수락자 집합 $W$가 각각 $n$명이고, 각자 반대편 $n$명에 대한 엄격한 전순서(무승부 없음)를 갖는다고 하자. 완전 매칭 $\mu$에 대해 쌍 $(m, w)$가 차단쌍(blocking pair)이라는 것은

$$w \succ_m \mu(m) \quad\text{이면서}\quad m \succ_w \mu(w)$$

즉 $m$은 현재 짝보다 $w$를 더 좋아하고 $w$도 현재 짝보다 $m$을 더 좋아하는 상태다. 이런 쌍이 존재하면 둘은 매칭을 무시하고 자기들끼리 붙어 버릴 유인이 있다. 차단쌍이 하나도 없는 매칭이 안정 매칭이다.

여기서 오해가 잦은 지점 하나. 안정성은 모두가 만족한다는 뜻이 아니다. 꼴찌를 배정받은 사람도 자기를 원하는 더 나은 상대가 없다면 안정하다. 안정성이 배제하는 것은 오직 “쌍방이 동시에 이득을 보는 이탈”뿐이며, 개인의 불만이나 총합 후생과는 무관하다.²

3. 지연 수락 알고리즘[편집]

게일-섀플리의 답은 지연 수락(deferred acceptance, DA)이다. 핵심은 이름 그대로 — 수락자가 제안을 받아도 확정하지 않고 보류한다는 것.

1. 아직 짝이 없는 제안자 $m$은 자기 선호 목록에서 아직 거절당하지 않은 최상위 상대 $w$에게 제안한다.
2. $w$는 현재 보류 중인 상대와 $m$을 비교해 더 좋은 쪽을 보류하고 나머지를 거절한다.
3. 짝 없는 제안자가 없을 때까지 반복한다.

종료는 자명하다. 제안자는 같은 상대에게 두 번 제안하지 않으므로 제안의 총 횟수가 $n^2$을 넘을 수 없고, 각 제안은 상수 시간에 처리되므로 전체가 $O(n^2)$이다. 입력(선호 행렬)의 크기 자체가 $\Theta(n^2)$이므로 이건 입력을 한 번 읽는 값이며, 점근적으로 개선의 여지가 없다.

종료 시 짝 없는 사람이 남지 않는다는 것도 짧다. 어떤 $m$이 $n$명 전원에게 거절당했다면 $n$명 전원이 누군가를 보류 중이라는 뜻이고 — 수락자는 한 번 제안을 받으면 그 뒤로 절대 빈손이 되지 않는다 — 그러면 이미 $n$쌍이 만들어져 $m$의 자리가 없다는 모순이다.

안정성 증명은 두 줄이다. 결과 $\mu$에서 $m$이 $\mu(m)$보다 $w$를 선호한다고 하자. 그렇다면 $m$은 알고리즘 도중 $w$에게 이미 제안했고 거절당했다(선호 순서대로 내려가니까). 수락자가 보류하는 상대는 시간이 갈수록 좋아지기만 하므로, $w$의 최종 짝은 $m$보다 좋다. 즉 $w$는 $m$을 원하지 않고, $(m,w)$는 차단쌍이 아니다. 임의의 쌍에 대해 성립하므로 $\mu$는 안정하고, 덤으로 안정 매칭의 존재성이 구성적으로 증명된다.

4. 제안자 최적, 수락자 최악[편집]

DA가 내놓는 것은 아무 안정 매칭이 아니다. 상대 $w$가 달성 가능(achievable)하다는 것을 “$m$과 $w$가 짝인 안정 매칭이 하나라도 존재한다”로 정의하면, 게일-섀플리는 다음을 보였다.

제안자 최적성. DA의 결과에서 모든 제안자는 자신에게 달성 가능한 상대 중 최선의 상대를 얻는다.

증명은 “어떤 제안자도 달성 가능한 상대에게 거절당하지 않는다”를 거절 횟수에 대한 귀납으로 보이면 끝난다. 놀라운 부분은 모든 제안자가 동시에 자기 최선을 받는다는 것 — 개인 최적이 충돌하지 않고 하나의 매칭으로 실현된다.

반대편은 정확히 그만큼 손해를 본다. 매크비티와 윌슨(1971)이 보인 대칭 명제는 이렇다.

수락자 최악성. 제안자 최적 안정 매칭은 모든 수락자에게 달성 가능한 최악의 상대를 준다.

즉 누가 제안하느냐가 결과를 가른다. 같은 선호 데이터로 제안자와 수락자를 바꿔 DA를 돌리면 일반적으로 다른 매칭이 나오고, 양쪽 결과는 각각 두 집단의 이해가 극단으로 갈린 지점이다. 시장 설계에서 “누구를 제안자로 둘 것인가”가 정치적 쟁점이 되는 이유가 이 비대칭이다.³

한편 로스(1986)의 시골 병원 정리(rural hospital theorem)는 위안이자 한계를 준다. 정원 미달이 허용되는 확장판에서, 어떤 안정 매칭을 고르든 짝을 못 찾는 사람의 집합은 완전히 동일하다. 지원자가 안 가는 시골 병원은 알고리즘을 아무리 바꿔도 여전히 미달이라는 뜻이고, “매칭 방식을 손보면 지방 병원이 채워진다”는 기대가 수학적으로 틀렸음을 말한다.

5. 전략 조작 불가능성[편집]

각자 진짜 선호를 그대로 제출하는 것이 최선인가? 메커니즘이 조작 가능하면 참가자는 눈치 게임을 하게 되고, 시장은 그 자체로 망가진다.

두빈스-프리드먼(1981)과 로스(1982)가 각각 보인 결과는 제안자 최적 DA에서 제안자 측은 진실 신고가 우월 전략이라는 것이다. 심지어 제안자들이 담합해도 전원이 동시에 이득을 볼 수 없다. 이것이 DA가 단순한 알고리즘을 넘어 메커니즘으로 쓰이는 결정적 이유다.

다만 로스(1982)는 동시에 나쁜 소식도 증명했다.

양측 동시 전략 조작 불가능한 안정 메커니즘은 존재하지 않는다.

수락자 쪽은 선호를 잘라내거나 순서를 비트는 방식으로 이득을 볼 수 있다. 물론 그러려면 남들의 선호를 상당히 알아야 하고, 시장이 크면 이득 볼 확률이 급격히 줄어든다는 대규모 시장 결과들이 있어 실무에서는 대체로 무시된다. 메커니즘 설계에서 “불가능성 정리 옆에 실용적 근사가 붙는” 전형적인 그림.

6. 안정 매칭의 격자 구조[편집]

안정 매칭은 하나가 아니다. 안정 매칭 전체 집합 $\mathcal{S}$에 모든 제안자가 $\mu$를 $\mu'$보다 약하게 선호한다는 관계로 순서를 주면, 존 콘웨이가 관찰하고 커누스(1976)가 정리한 다음 사실이 나온다.

$\mathcal{S}$는 이 순서에 대해 분배 격자(distributive lattice)를 이룬다.

결합과 만남이 노골적으로 구성적이다. $\mu \vee \mu'$는 각 제안자에게 두 짝 중 더 좋은 쪽을 주는 배정인데, 이게 다시 안정 매칭이 된다는 것이 정리의 알맹이다(그리고 이때 각 수락자는 자동으로 나쁜 쪽을 받는다). 격자의 최대원이 제안자 최적 매칭, 최소원이 수락자 최적 매칭이다.

구조가 격자라는 사실은 알고리즘으로 직결된다. 버코프 표현정리에 따라 분배 격자는 어떤 부분순서집합의 하향 닫힌 집합족으로 표현되는데, 어빙과 레더(1986)는 그 부분순서집합을 회전(rotation)이라는 국소 재배열의 순서로 명시적으로 구성했다. 회전 포셋의 크기는 $O(n^2)$이라 안정 매칭 전체를 압축해 표현할 수 있고, 여기에 가중치를 얹어 “총 순위합 최소” 같은 목적함수를 최적화하는 문제가 포셋 위의 최대 폐쇄(maximum closure) 문제, 곧 네트워크 흐름의 최소 절단으로 풀린다. 반면 안정 매칭의 개수를 세는 것은 #P-완비이고, 개수 자체가 $n$에 지수적으로 커질 수 있다.

포셋 표현은 딜워스 정리나 전체 단모듈성과 같은 계열의 이야기다 — 조합 구조가 다면체·격자로 정리되는 순간 최적화가 다항시간으로 떨어지는 그 패턴.

7. 실무 — NRMP와 학교 배정[편집]

이 문제가 순수 조합론에 머물지 않은 것은 실제 시장이 먼저 같은 답에 도달해 있었기 때문이다.

• NRMP(National Resident Matching Program). 미국 의대 졸업생과 수련병원을 짝짓는 중앙 매칭으로 1952년부터 가동됐다. 로스(1984)는 당시 쓰이던 알고리즘이 병원 제안 DA와 본질적으로 동치임을 밝혔다. 게일-섀플리보다 10년 앞서 현장이 같은 알고리즘을 경험적으로 찾아냈던 셈. 1990년대에 “지원자에게 불리하다”는 비판이 커지자 로스와 페란슨이 재설계해 지원자 제안 방식으로 바꾸고 1998년 매칭부터 적용했다.
• 부부 문제. NRMP 재설계의 진짜 난제는 방향 전환이 아니라 부부(couples)였다. 두 사람이 “같은 도시의 자리 쌍”을 하나의 단위로 지원하면 선호가 개인 단위로 분해되지 않고, 로스(1984)가 보였듯 안정 매칭이 아예 존재하지 않을 수 있다. 존재 여부 판정 자체가 NP-완전이다. 실무 코드는 순차적 재삽입 휴리스틱으로 처리하며, 대규모 시장에서는 대부분 안정해를 찾아낸다.
• 공립학교 배정. 뉴욕시 고교 배정(2003)과 보스턴 초·중등 배정(2005)이 DA 기반으로 전환됐다. 이전에 쓰이던 “보스턴 메커니즘”은 1지망 지원자를 우선 처리하는 방식이라, 안전한 학교를 1지망에 쓰는 것이 유리해지는 노골적 조작 유인을 만들었다. 학부모 커뮤니티가 이 눈치싸움 공략법을 공유하는 상황 자체가 메커니즘의 실패 증거였고, DA로 바꾸면서 “그냥 원하는 순서대로 쓰세요”가 실제로 정직한 조언이 됐다.⁴

여기서 학교 쪽 “선호”는 사람의 취향이 아니라 우선순위 규칙(거주지·형제·추첨번호)이다. 규칙이 무승부를 만들기 때문에 동점 처리가 새 문제로 등장하는데, 무작위 추첨으로 동점을 깨면 약안정 매칭은 나오지만 학생 후생 관점의 최적성은 잃는다. 동점이 있는 경우 최대 크기 안정 매칭 찾기는 NP-난해다.

8. 룸메이트 문제 — 안정 매칭이 없을 수도 있다[편집]

두 집단으로 나뉜다는 조건, 즉 이분 구조를 빼면 어떻게 될까. 안정 룸메이트 문제(stable roommates problem)는 $2n$명 전체가 서로에 대해 순위를 갖고 두 명씩 짝짓는 문제다. 게일-섀플리 논문이 이미 반례를 제시한다. 네 사람 $a,b,c,d$에서

• $a$: $b \succ c \succ d$
• $b$: $c \succ a \succ d$
• $c$: $a \succ b \succ d$
• $d$: 아무 순서나

$a, b, c$가 서로를 물고 도는 순환 구조를 만든다. 누가 $d$와 묶이든 그 사람은 나머지 둘 중 자기를 더 좋아하는 쪽과 차단쌍을 이루므로, 안정 매칭이 아예 존재하지 않는다.

이분성이 사라지자 존재성이 무너지는 이 현상은 쾨니그 정리가 이분 그래프에서만 성립하는 것, 매칭 알고리즘이 홀수 사이클에서 깨져 블로섬 알고리즘이 필요해지는 것과 같은 뿌리를 갖는다 — 홀수 순환이 범인이다.

다만 판정은 어렵지 않다. 어빙(1985)이 $O(n^2)$ 알고리즘을 내놓았고, 이 알고리즘은 안정 매칭을 찾거나 존재하지 않음을 보고한다. 1단계는 DA와 비슷한 제안·보류 국면이고, 2단계에서 “회전 제거”로 순환을 걷어낸다. 신장 이식 교환처럼 참가자가 한 종류뿐인 시장이 이 계열이며, 그쪽은 안정성 대신 파레토 효율과 순환 교환으로 방향을 튼다.

9. 관련 문서[편집]

• 이분 매칭 · 홀의 결혼정리 · 쾨니그 정리 · 블로섬 알고리즘
• 헝가리안 알고리즘 · 네트워크 흐름
• 게임 이론 · 메커니즘 설계 · 내시 균형
• 조합 최적화 · 최소 정점 덮개 · 최대 독립집합
• 정수계획법 · 전체 단모듈성 · 딜워스 정리

10. Footnotes[편집]

1. 논문 제목이 “College Admissions and the Stability of Marriage”인데, 정작 본문에서 대학 입시 쪽이 일반형이고 결혼은 각 대학의 정원이 1인 특수 케이스다. 그런데 세상은 특수 케이스의 이름으로 이 문제를 부른다. 게일은 2008년에 세상을 떠나 2012년 노벨상을 받지 못했다 — 노벨상은 사후 수여가 없다. ↩

2. “안정 매칭 중 총 순위합이 가장 작은 것”을 찾는 문제는 별도로 정의되며(egalitarian stable matching), 어빙-레더-거스필드가 회전 포셋 위의 최소 절단으로 다항시간에 푼다. 안정성과 후생은 이렇게 따로 논다. ↩

3. 제안자 최적성과 수락자 최악성이 정확히 맞물린다는 사실 때문에, 실무 도입 논의는 늘 “누가 제안하나”에서 멈춘다. 지원자 제안으로 바꾸면 지원자가 이기고 병원이 진다. 다만 시골 병원 정리 덕분에 누가 배정되느냐(집합 자체)는 안 바뀌고 누구와 배정되느냐만 바뀐다. 파이의 분배 문제지 크기 문제가 아니라는 것. ↩

4. 이 눈치싸움은 학부모들에게 대단히 현실적인 문제였다. 보스턴 학부모 협의회가 배포하던 실전 팁이 “인기 학교를 1지망에 쓰면 떨어졌을 때 2지망 자리도 이미 없다”였다. 메커니즘이 시민에게 게임 공략법을 요구하고 있으면 그건 메커니즘이 잘못된 것이다. ↩