안정된 결혼 문제 해결기

안정된 결혼 문제 해결기 정보

안정된 결혼 문제 해결기는 Gale-Shapley 지연 수락 알고리즘을 구현한 대화형 도구입니다. 이 알고리즘은 1962년 David Gale과 Lloyd Shapley가 발표하였으며, 각 구성원이 상대 그룹에 대한 전체 순위를 가지고 있을 때 두 그룹 사이에 항상 안정적인 짝짓기가 존재함을 증명했습니다. 이 도구는 선호도 목록을 입력받아 알고리즘을 단계별로 실행하며, 안정 매칭 결과, 애니메이션 시각화, 선호도 히트맵, 그리고 블로킹 쌍이 없음을 입증하는 검증 결과를 보여줍니다.

안정된 결혼 문제란 무엇인가요?

동일한 크기의 두 집합(예: 남성 n명과 여성 n명, 또는 지원자 n명과 직위 n개)이 있고, 각 구성원이 상대방 집합의 모든 구성원에 대한 전체 선호도 순위를 가지고 있다고 가정할 때, 매칭은 두 집합 사이의 일대일 짝짓기를 의미합니다. 매칭 외부에 있는 어떤 쌍 (a, b)도 각자 현재 파트너보다 서로를 더 선호하지 않는다면, 이 매칭을 안정적이라고 부릅니다.

공식적으로, 매칭 M에서 a가 b'와 매칭되고 b가 a'와 매칭되었을 때 다음과 같은 블로킹 쌍이 없다면 안정적입니다.

두 조건이 모두 충족되면 a와 b는 현재 파트너를 버리고 서로를 선택하게 되어 매칭이 불안정해집니다. 안정 매칭은 이러한 쌍이 전혀 존재하지 않는 상태를 말합니다.

Gale-Shapley 알고리즘

Gale과 Shapley는 어떤 선호도 세트에 대해서도 안정 매칭이 항상 존재함을 증명하고, 이를 찾는 효율적인 알고리즘을 제시했습니다. 알고리즘은 다음과 같이 진행됩니다.

1. 약혼하지 않은 모든 제안자는 자신의 목록에서 아직 자신을 거절하지 않은 가장 높은 순위의 수락자에게 제안합니다.
2. 제안을 받은 각 수락자는 받은 제안들(현재 잠정 약혼자가 있다면 그를 포함) 중 가장 선호하는 제안을 선택하여 잠정적으로 수락하고 나머지는 거절합니다.
3. 거절당한 제안자들은 다시 자유로운 상태가 되며 다음 라운드에서 그다음 순위의 상대에게 제안합니다.
4. 모든 제안자가 약혼 상태가 되면 알고리즘이 종료됩니다. 이는 최대 n²번의 제안 내에 반드시 발생합니다.

주요 이론적 특성

존재성 및 유일성

안정 매칭은 어떤 선호도 구성에서도 항상 존재하지만(Gale & Shapley, 1962), 반드시 유일하지는 않습니다. 주어진 선호도 세트에 대해 여러 개의 안정 매칭이 존재할 수 있으며, 이들은 공동 선호도에 따라 정렬된 격자 구조를 형성합니다.

제안자 최적성

한쪽이 제안할 때, Gale-Shapley는 제안자 최적 안정 매칭을 생성합니다. 즉, 모든 제안자는 모든 가능한 안정 매칭 중에서 얻을 수 있는 가장 좋은 파트너를 얻게 됩니다. 반대로 이는 수락자 최악 매칭이 되어, 받는 쪽은 모든 안정 매칭 중 가장 낮은 순위의 파트너를 얻게 됩니다. 제안 측을 바꾸면 결과가 달라지는 경우가 많습니다.

전략적 정직성 (Strategy Proofness)

Gale-Shapley 알고리즘에서 제안자 측은 자신의 선호도를 속일 동기가 없습니다. 진실을 말하는 것이 지배 전략입니다. 그러나 수락자 측은 때때로 전략적으로 선호도를 속여 이득을 볼 수도 있습니다. 이것이 미국의 병원-거주자 매칭 시스템이 학생을 제안자 측으로 설계한 이유 중 하나입니다.

Rural Hospitals 정리

매칭되지 않는 에이전트의 집합은 모든 안정 매칭에서 동일합니다. 따라서 그룹 크기가 불균형한 경우(이 고전 도구의 범위를 벗어남) 어떤 안정적인 해법에서도 매칭되지 않는 사람은 동일하게 남습니다.

입력 형식

이 계산기는 구성원당 한 줄씩, 이름 뒤에 콜론과 쉼표로 구분된 전체 순위 목록을 요구합니다.

요구사항:

• 두 그룹은 정확히 동일한 수의 구성원을 가져야 합니다.
• 모든 구성원은 상대방 그룹의 모든 구성원 순위를 매겨야 합니다(부분 목록 불가).
• 이름에는 문자, 숫자, 밑줄, 하이픈, 공백 및 일반적인 유니코드 문자를 사용할 수 있습니다.
• 원활한 대화형 애니메이션을 위해 한쪽당 최대 15명까지 지원합니다.

이 계산기 사용 방법

1. 왼쪽 텍스트 영역에 그룹 A의 선호도를 입력합니다 (구성원당 한 줄, 전체 순위 목록).
2. 오른쪽 텍스트 영역에 그룹 B의 선호도를 동일한 형식으로 입력합니다.
3. 제안 측을 선택합니다. 그룹 A 또는 그룹 B를 선택하십시오. 두 가지를 모두 시도하여 A 최적 결과와 B 최적 결과를 비교해 보십시오.
4. "안정 매칭 해결"을 클릭합니다. 계산기가 Gale-Shapley를 실행하여 안정된 쌍, 통계, 애니메이션 및 안정성 증명을 생성합니다.
5. 재생 / 단계 / 리셋 컨트롤을 사용하여 애니메이션을 탐색하며 모든 제안, 수락, 교체 및 거절 과정을 확인하십시오.
6. 히트맵을 검사합니다. 각 셀은 순위를 보여주며, 노란색 테두리 셀은 최종 매칭입니다. 해당 셀들의 위치를 통해 각 그룹의 "행복도"를 확인할 수 있습니다.

작업 예시 — 클래식 3×3

남성: Alex, Bryan, Chris. 여성: Bea, Claire, Diana. 선호도:

남성이 제안하는 방식으로 Gale-Shapley를 실행하면 단 한 라운드 만에 Alex–Bea, Bryan–Claire, Chris–Diana가 매칭됩니다(각 남성의 1순위가 다른 남성의 1순위와 겹치지 않는 여성과 매칭됨). 이 매칭은 안정적입니다. 어떤 남녀 쌍도 현재 파트너를 버리고 서로를 선택할 이유가 없으므로 블로킹 쌍이 존재하지 않습니다.

실제 응용 사례

Lloyd Shapley가 노벨상을 받은 이유

2012년 스웨덴 왕립 과학 아카데미는 Lloyd Shapley(이론 수립 공로, 고인이 된 David Gale과 함께)와 Alvin Roth(이론을 실제 시장에 적용하여 미국의 의료 거주자 매칭 및 신장 교환 네트워크를 재설계한 공로)에게 노벨 경제학상을 수여했습니다. 수여 사유는 "안정적 배분 이론과 시장 설계 실무"였습니다.

자주 묻는 질문

안정된 결혼 문제란 무엇인가요?

안정된 결혼 문제는 각 구성원이 상대 그룹의 모든 구성원을 선호도 순으로 나열한 동일한 규모의 두 그룹이 있을 때, 서로 현재 파트너를 떠나 서로를 더 선호하는 두 사람이 없도록 모두를 짝지을 수 있는지 묻는 문제입니다. 이러한 짝짓기를 안정 매칭이라고 합니다. Gale-Shapley 알고리즘은 이 문제를 O(n²) 시간 안에 해결하며 항상 안정 매칭을 찾아냅니다.

Gale-Shapley 알고리즘은 어떻게 작동하나요?

Gale-Shapley 지연 수락 알고리즘은 라운드별로 진행됩니다. 각 라운드에서 현재 약혼하지 않은 모든 제안자는 자신의 목록에서 아직 자신을 거절하지 않은 가장 높은 순위의 수락자에게 제안합니다. 각 수락자는 지금까지 받은 제안 중 가장 좋은 것을 잠정적으로 수락하고 나머지는 거절합니다. 거절당한 제안자는 다시 자유로운 상태가 됩니다. 알고리즘은 더 이상 자유로운 제안자가 없을 때 종료됩니다.

안정 매칭은 유일한가요?

아니요. 하나의 안정 매칭 사례에는 여러 개의 안정 매칭이 존재할 수 있습니다. 그러나 한쪽이 제안할 때 Gale-Shapley는 항상 제안자 최적 안정 매칭을 생성합니다. 이는 상대방에게는 수락자 최악 매칭이 됩니다. 제안 측을 바꾸면 종종 다른 안정 매칭이 결과로 나옵니다.

블로킹 쌍이란 무엇인가요?

블로킹 쌍은 현재 매칭되지 않은 쌍 (a, b) 중에서 a가 현재 파트너보다 b를 더 선호하고 동시에 b도 현재 파트너보다 a를 더 선호하는 경우입니다. 블로킹 쌍이 있으면 매칭이 불안정해집니다. 안정 매칭에는 블로킹 쌍이 없으며, 본 계산기는 해결 후 이를 자동으로 검증합니다.

안정 매칭의 실제 사례는 무엇인가요?

Gale-Shapley 알고리즘은 미국 의대생들의 수련 병원 배정 시스템(NRMP), 보스턴과 뉴욕의 학교 선택 시스템, 대학 입학 시스템, 장기 기증자 신장 교환 시스템 등에 활용됩니다. Lloyd Shapley와 Alvin Roth는 이 공로로 2012년 노벨 경제학상을 수상했습니다.

두 그룹의 크기가 같아야 하나요?

고전적인 안정된 결혼 문제에서는 그렇습니다. 양측 모두 동일한 수의 구성원이 있어야 하며 완전한 순위 목록을 제공해야 합니다. 불균형한 경우를 위한 변형 알고리즘도 존재하지만, 이 계산기는 고전적인 방식에 따라 동일 크기와 완전 목록을 요구합니다.

더 읽어보기

• 안정된 결혼 문제 — Wikipedia
• Gale-Shapley 알고리즘 — Wikipedia
• 국가 거주자 매칭 프로그램 (NRMP) — Wikipedia
• 2012년 노벨 경제학상 — Shapley & Roth