안정 매칭 문제

수학, 경제학, 컴퓨터 과학에서 안정 매칭 문제(Stable matching problem)는 각 원소에 대한 선호도 순서가 주어졌을 때, 두 개의 크기가 같은 집합 사이에 안정적인 매칭을 찾는 문제이다. 이때 매칭은 한 집합의 원소에서 다른 집합의 원소로 가는 전단사이며, 다음 조건이 성립할 때 매칭이 불안정하다고 한다.

 첫 번째 매칭된 집합의 원소 A가 이미 매칭된 원소보다 두 번째 매칭된 집합의 특정 원소 B를 선호하고,
 B 역시 이미 매칭된 원소보다 A를 선호하는 경우.

다시 말해, 매칭이 안정적일 조건은 모든 (A, B) 쌍이 서로를 현재 매칭된 상대보다 선호하는 경우가 없는 경우이다.

안정 결혼 문제는 다음과 같이 서술할 수 있다.

이 문제는 서로 다른 두 집단(여기서는 이성애자 남성과 여성)이 짝을 이룬다는 점에서 안정 룸메이트 문제와는 다르다.

응용
안정 결혼 문제의 해를 찾는 알고리즘은 다양한 실제 상황에서 응용된다. 이 중 가장 잘 알려진 것은 졸업하는 의대생을 첫 병원 배치에 배정하는 것이다. 2012년, 노벨 경제학상은 로이드 S. 섀플리와 앨빈 E. 로스에게 "안정적인 할당 이론과 시장 설계의 실제"에 대한 공로로 수여되었다.

안정 결혼의 중요하고 대규모 응용 중 하나는 대규모 분산 인터넷 서비스에서 사용자를 서버에 할당하는 것이다. 수십억 명의 사용자가 인터넷에서 웹 페이지, 비디오 및 기타 서비스에 액세스하며, 각 사용자는 해당 서비스를 제공하는 전 세계 수십만 개의 서버 중 하나에 매칭되어야 한다. 사용자는 요청된 서비스에 대해 더 빠른 응답 시간을 제공할 만큼 근접한 서버를 선호하여 각 사용자에 대한 서버의 (부분적인) 선호도 순서를 생성한다. 각 서버는 낮은 비용으로 서비스를 제공할 수 있는 사용자를 선호하여 각 서버에 대한 사용자의 (부분적인) 선호도 순서를 생성한다. 전 세계 콘텐츠 및 서비스의 대부분을 배포하는 콘텐츠 전송 네트워크는 이러한 거대하고 복잡한 사용자-서버 간의 안정 결혼 문제를 수십 초마다 해결하여 수십억 명의 사용자가 요청된 웹 페이지, 비디오 또는 기타 서비스를 제공할 수 있는 각 서버와 매칭되도록 한다.

히브리 유니언 칼리지 졸업 랍비를 유대인 회중에게 배정하는 데 안정 매칭 문제를 푸는 게일-섀플리 알고리즘이 사용된다.

안정 매칭의 개수

일반적으로 여러 가지 안정 매칭이 있을 수 있다. 예를 들어, 세 명의 남성(A, B, C)과 세 명의 여성(X, Y, Z)이 다음의 선호도를 가지고 있다고 가정해 보자.

 A: YXZ   B: ZYX   C: XZY  
 X: BAC   Y: CBA   Z: ACB

이 조건의 매칭에는 세 가지 안정적인 해가 있다.

 남성은 첫 번째로, 여성은 세 번째로 선호하는 상대와 매칭되는 경우 (AY, BZ, CX)
 모든 구성원이 두 번째로 선호하는 상대와 매칭되는 경우 (AX, BY, CZ)
 여성은 첫 번째로, 남성은 세 번째로 선호하는 상대와 매칭되는 경우 (AZ, BX, CY)

양쪽 집단의 두 참가자 모두가 현재 매칭된 상대보다 서로에게 더 만족해야 불안정 매칭이 되므로, 위의 세 가지 해는 모두 안정적이다. 한쪽 집단의 모든 구성원이 가장 선호하는 상대와 매칭되는 경우에는 다른 어떤 매칭을 선택해도 현재의 매칭보다 만족스럽지 않으므로 반드시 안정적인 매칭이 된다. 모든 구성원이 두 번째로 선호하는 상대와 매칭되는 경우에는 다른 어떤 매칭을 선택해도 구성원 중 적어도 한 명이 불만족하게 된다. 일반적으로 어떻게 주어진 안정 결혼 문제이든 그 해의 집합은 유한 분배 격자의 구조를 가질 수 있으며, 이 구조에서 여러 가지 안정 결혼 문제를 효율적으로 해결할 수 있는 알고리즘을 유도할 수 있다.

명의 남성과 명의 여성이 균등한 무작위의 선호도를 가지는 안정 결혼 문제에서 안정 매칭의 평균 개수는 점근적으로 이다. 안정 매칭의 개수가 최대가 되도록문제를 구성할 경우에는 의 지수 함수가 된다. 주어진 문제에서 안정 매칭의 수를 세는 것은 #P-완전이다.

알고리즘

섬네일|right|게일-섀플리 알고리즘의 예시를 보여주는 애니메이션
1962년, 데이비드 게일과 로이드 섀플리는 대학 입학과 결혼을 원하는 개인들의 맥락에서, 두 집단에 속한 구성원의 수가 같을 경우 모든 쌍이 안정적이 되는 짝짓기가 항상 존재함을 증명하고, 안정 매칭을 찾는 알고리즘을 제시했다.

게일-섀플리 알고리즘 (지연 수락 알고리즘이라고도 함)은 여러 번의 라운드로 이루어진다.
 첫 번째 라운드에서, 먼저 a) 아직 약혼하지 않은 각 남성은 자신이 가장 선호하는 여성에게 청혼하고, 다음으로 b) 각 여성은 자신의 구혼자 중 가장 선호하는 구혼자를 잠정적으로 받아들여 서로 '약혼'하고, 다른 모든 구혼자는 거절한다.
 이후의 각 라운드에서, 먼저 a) 아직 약혼하지 않은 각 남성은 자신이 아직 청혼하지 않은 여성 중 가장 선호하는 여성에게 청혼하고 (여성이 이미 약혼했는지 여부와 관계없이), 다음으로 b) 각 여성은 현재 약혼하지 않았거나 현재 잠정적 배우자보다 이 남성을 더 선호하는 경우 그 구혼자와 '약혼'하고, 기존 약혼자가 있을 경우에는 '파혼'한다. 약혼은 근본적으로 잠정적이므로 이미 약혼한 여성이 더 나은 상대로 '갈아탈' 권리를 가지게 된다.
 이 과정을 모든 사람이 약혼할 때까지 반복한다.

이 알고리즘은 각 집단의 구성원 수가 일 때 의 시간 복잡도로 모든 참가자에 대해 안정적인 결혼을 생성함을 보장한다.

가능한 모든 안정 매칭 중에서 이 알고리즘은 항상 모든 남성에게는 최선, 모든 여성에게는 최악의 매칭을 선택한다.

남성(청혼하는 측)의 관점에서 이 알고리즘은 자신의 선호도를 속여도 더 나은 상대와 매칭될 수 없는 전략 방지 메커니즘(strategyproof mechanism)이다. 또한 이 알고리즘은 남성 집단 전체에 대해서도 전략 방지 메커니즘이다. 즉, 여러 남성이 연합해서 각자의 선호도를 속여도 연합 내 모든 남성이 더 나은 상대와 매칭될 수 없다. 단, 일부 남성만 더 나은 상대와 매칭되고 나머지는 같은 배우자를 유지하도록 연합하는 것은 가능하다. 이 알고리즘은 여성(청혼받는 측)에게는 전략 방지가 아니며, 여성이 자신의 선호도를 속여서 더 나은 상대와 매칭되는 것이 가능하다.

농촌 병원 정리

농촌 병원 정리는 병원에 의사를 배치하는 등의 상황에 응용할 수 있는 일반화된 안정 매칭 문제를 다루며, 기본적인 n 대 n 형태의 안정 결혼 문제와 다음과 같은 방식으로 다르다.
 각 구성원은 반대 집단의 특정 부분집합과만 매칭되는 것을 희망할 수 있다.
 매칭의 한쪽 집단(병원)에는 정해진 수용량이 있어 그 숫자만큼의 의사를 채용할 수 있다.
 한쪽 집단의 구성원 수와 반대 집단의 총 수용량이 다를 수도 있다.
 매칭이 완료된 이후 매칭이 되지 않는 구성원이 있을 수도 있다.
이 경우 안정성 조건은 매칭되지 않은 어떤 쌍도 매칭에서의 자신의 상황(다른 배우자이든 매칭되지 않은 상태이든)보다 서로를 선호하지 않는 것이다. 이 조건에서도 안정 매칭은 여전히 존재하며, 게일-섀플리 알고리즘으로 찾을 수 있다.

위와 같은 일반화된 안정 매칭 문제에서는 농촌 병원 정리에 의해 다음이 성립한다.
 채용된 의사의 집합과 각 병원이 채용한 의사의 수는 모든 안정 매칭에서 같다.
 어떤 안정 매칭에서 빈 자리가 있는 병원은 모든 안정 매칭에서 정확히 동일한 의사 집합과 매칭된다.

관련 문제
무차별성을 포함한 안정 매칭에서는 일부 구성원이 여러 명의 상대에게 같은 선호도를 매길 수 있다.

안정 룸메이트 문제는 안정 결혼 문제와 유사하지만, 모든 참가자가 같은 수의 '남성'과 '여성' 집단으로 나뉘는 대신 하나의 집단에 속한다는 점에서 다르다.

병원/레지던트 문제 (대학 입학 문제라고도 함)는 병원이 여러 레지던트를 받을 수 있거나 대학이 한 명 이상의 학생으로 구성된 신입생을 받을 수 있다는 점에서 안정 결혼 문제와 다르다. 병원/레지던트 문제를 해결하는 알고리즘은 병원 중심적이거나(1995년 이전 NRMP와 같이), 레지던트 중심적으로 구성할 수 있다. 이 문제는 게일과 섀플리가 안정 결혼 문제를 해결한 동일한 논문에서 알고리즘과 함께 해결되었다.

커플을 포함한 병원/레지던트 문제는 레지던트 집합에 커플을 포함할 수 있으며, 이들은 동일한 병원이나 해당 커플이 선호하는 특정 병원 쌍에 배정되어야 한다(예: 결혼한 커플이 원거리의 병원에 떨어지지 않고 함께 지낼 수 있기를 희망함). 병원/레지던트 문제에 커플을 추가하면 이 문제는 NP-완전이 된다.

할당 문제는 최대 가중치를 갖는 가중 이분 그래프에서 매칭을 찾는 것을 목표로 한다. 최대 가중치 매칭은 안정적일 필요는 없지만, 일부 응용에서는 안정적인 매칭보다 최대 가중치 매칭이 더 좋다.

계약을 포함한 매칭 문제는 참가자들이 다른 계약 조건으로 매칭될 수 있는 매칭 문제의 일반화이다. 계약의 중요한 특별한 경우는 유연한 임금을 포함한 매칭이다.

 같이 보기 
 부합 (그래프 이론) – 그래프의 서로 다른 꼭짓점 간의 매칭. 일반적으로 선호도 순서와는 관련이 없다.
 시기심 없는 매칭 – 다대일 매칭 문제에 대한 안정 매칭의 완화
 가장자리 색칠된 그래프를 위한 레인보우 매칭
 안정 매칭 폴리토프
 안정 매칭의 격자
 비서 문제 (결혼 문제라고도 함) – 옵션 시퀀스에서 최상의 보상을 얻기 위해 언제 멈출지 결정하는 것

 각주 

추가 자료
 Kleinberg, J., and Tardos, E. (2005) Algorithm Design, Chapter 1, pp 1–12. See companion website for the Text .
 
 
 
 
 See Section 10.6.4; downloadable free online.
 
 

 외부 링크 
 안정 결혼 문제의 대화형 플래시 데모
https://web.archive.org/web/20080512150525/http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
 안정 결혼 문제 강의 노트

분류:조합론
분류:수학 문제