정의
안정 매칭 문제(stable matching problem)는 두 집합에 속한 구성원들 간에 서로 선호 순위를 정해 두고, 각 구성원에게 한 명씩 혹은 여러 명에게 매칭을 할 때, “불안정한 쌍”(각자 현재 매칭된 파트너보다 서로를 더 선호하는 두 사람)이 존재하지 않도록 하는 매칭을 찾는 문제이다. 여기서 “안정”이란, 매칭된 모든 쌍이 서로에게 현재 매칭된 상대보다 더 선호하지 않는 상태를 의미한다.
주요 유형
- 일대일 안정 매칭 (Stable Marriage Problem, SMP)
- 두 집합(예: 남성 집합 M, 여성 집합 W)이 동일한 크기를 가지며, 각 사람은 이성 집합 전체에 대해 순위표를 가진다.
- 다대일 안정 매칭 (Stable Matching with Capacity, 예: 대학 입학 문제)
- 한쪽 집합(예: 대학)은 복수의 매칭을 수용할 수 있는 용량을 갖고, 다른 쪽(예: 지원자)은 한 곳에만 매칭된다.
- 동일 집합 내 안정 매칭 (Stable Roommates Problem, SRP)
- 한 집합의 구성원들이 서로에게 선호 순위를 매기며, 각자가 다른 구성원과 매칭된다.
주요 결과
- 존재성: 1962년 Gale과 Shapley가 제시한 “Gale‑Shapley 알고리즘”은 일대일 안정 매칭이 항상 존재함을 증명하였다.
- 알고리즘: Gale‑Shapley 알고리즘은 O(n²) 시간 복잡도로 실행되며, 한쪽 집합(예: 남성)이 제안자, 다른 쪽(예: 여성)이 수락/거절자 역할을 수행한다.
- 다양한 해의 특성: 제안자가 제안하는 버전은 제안자에게 최적(가장 선호하는) 안정 매칭을 제공하고, 수락자에게는 최악(가장 불리한) 안정 매칭을 제공한다. 반대로 수락자 주도 버전을 적용하면 반대 효과가 나타난다.
응용 분야
- 대학 입학 및 전공 배정: 학생과 대학 사이의 선호를 반영한 매칭 시스템.
- 의료 레지던시 매칭: 미국의 NRMP(National Resident Matching Program) 등에서 사용.
- 온라인 플랫폼: 데이트 앱, 숙소 공유 서비스 등에서 사용자 간 매칭에 적용.
변형 및 확장 연구
- 불완전 선호(Partial Preference): 모든 구성원이 전체 순위를 제공하지 않을 경우의 매칭.
- 시장 규모가 다른 경우(다대다 매칭): 각 참여자가 복수의 파트너를 가질 수 있는 상황.
- 전략적 조작 방지: 참여자가 자신의 선호를 조작해 유리한 결과를 얻는 것을 방지하는 메커니즘 설계.
학술적 의의
안정 매칭 문제는 게임 이론, 알고리즘 설계, 시장 설계 등 여러 학문 분야에서 핵심적인 모델로 활용된다. 특히, “인센티브 호환성”, “효율성”, “공정성”이라는 세 가지 기준을 동시에 만족시키는 매칭 메커니즘을 설계하는 연구가 활발히 진행되고 있다.
참고
- Gale, D., & Shapley, L. S. (1962). “College Admissions and the Stability of Marriage.” American Economic Review, 52(4), 686‑689.
- Roth, A. E., & Sotomayor, M. (1990). Two-sided matching: A study in game-theoretic modeling and analysis. Cambridge University Press.
