안정 매칭 문제

수학, 경제학, 컴퓨터 과학에서 **안정 매칭 문제**(Stable matching problem)archive-date=archive-date=archive-date=는 각 요소에 대한 선호도 순서가 주어졌을 때, 두 개의 동일한 크기의 요소 집합 사이에 안정적인 매칭을 찾는 문제이다. 매칭은 한 집합의 요소에서 다른 집합의 요소로의 전단사이다. 매칭은 다음의 경우 불안정하다. B 역시 이미 매칭된 요소보다 A를 선호하는 경우. 다시 말해, 매칭은 (A, B) 쌍이 서로를 현재 매칭된 상대보다 선호하는 경우가 없을 때 안정적이다. 안정 결혼 문제는 다음과 같이 서술되었다. n명의 남성과 n명의 여성이 주어지고, 각 사람은 이성 구성원 모두를 선호도 순서대로 순위를 매겼을 때, 남성과 여성을 짝지어 현재 배우자보다 서로를 더 선호하는 이성 쌍이 없도록 한다. 그러한 쌍이 없을 때, 결혼 집합은 안정적이라고 간주된다. 서로 짝을 이루어야 할 두 계층(이 예에서는 이성애자 남성과 여성)의 존재는 이 문제를 안정 룸메이트 문제와 구별한다.
# 응용
안정 결혼 문제의 해결책을 찾는 알고리즘은 다양한 실제 상황에서 응용된다. 이 중 가장 잘 알려진 것은 졸업하는 의대생을 첫 병원 배치에 배정하는 것이다.Stable Matching Algorithms 2012년, 노벨 경제학상은 로이드 S. 섀플리와 앨빈 E. 로스에게 "안정적인 할당 이론과 시장 설계의 실제"에 대한 공로로 수여되었다.access-date=2013-09-09 안정 결혼의 중요하고 대규모 응용 중 하나는 대규모 분산 인터넷 서비스에서 사용자를 서버에 할당하는 것이다.url = http://www.sigcomm.org/sites/default/files/ccr/papers/2015/July/0000000-0000009.pdf 수십억 명의 사용자가 인터넷에서 웹 페이지, 비디오 및 기타 서비스에 액세스하며, 각 사용자는 해당 서비스를 제공하는 전 세계 수십만 개의 서버 중 하나에 매칭되어야 한다. 사용자는 요청된 서비스에 대해 더 빠른 응답 시간을 제공할 만큼 근접한 서버를 선호하여 각 사용자에 대한 서버의 (부분적인) 선호도 순서를 생성한다. 각 서버는 낮은 비용으로 서비스를 제공할 수 있는 사용자를 선호하여 각 서버에 대한 사용자의 (부분적인) 선호도 순서를 생성한다. 전 세계 콘텐츠 및 서비스의 대부분을 배포하는 콘텐츠 전송 네트워크는 이러한 거대하고 복잡한 사용자-서버 간의 안정 결혼 문제를 수십 초마다 해결하여 수십억 명의 사용자가 요청된 웹 페이지, 비디오 또는 기타 서비스를 제공할 수 있는 각 서버와 매칭되도록 한다. 안정 매칭을 위한 게일-섀플리 알고리즘은 히브리 유니언 칼리지 졸업 랍비를 유대인 회중에게 배정하는 데 사용된다.url-access=subscription
# 다른 안정 매칭
안정 매칭의 격자 일반적으로 여러 가지 안정 매칭이 있을 수 있다. 예를 들어, 세 명의 남성(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). 세 가지 모두 안정적이다. 불안정성은 두 참가자 모두 다른 대안 매칭에 더 만족해야 하기 때문이다. 한 그룹에게 첫 번째 선택을 주는 것은 매칭이 안정적임을 보장하는데, 이는 그들이 다른 어떤 제안된 매칭에도 불만족할 것이기 때문이다. 모든 사람에게 두 번째 선택을 주는 것은 다른 어떤 매칭도 당사자 중 한 명에게 불만을 일으킬 것임을 보장한다. 일반적으로 안정 결혼 문제의 모든 인스턴스에 대한 해결책 집합은 유한 분배 격자의 구조를 가질 수 있으며, 이 구조는 안정 결혼에 관한 여러 문제에 대한 효율적인 알고리즘을 이끌어낸다.year = 1987 n명의 남성과 n명의 여성이 있는 안정 결혼 문제의 균일 무작위 인스턴스에서 안정 매칭의 평균 수는 점근적으로 e^{-1}n\ln n이다.year = 1989 안정 매칭의 최대 수를 갖도록 선택된 안정 결혼 인스턴스에서 이 수는 n의 지수 함수이다.isbn = 978-1-4503-5559-9 주어진 인스턴스에서 안정 매칭의 수를 세는 것은 #P-완전이다.year = 1986
# 알고리즘적 해결책
게일-섀플리 알고리즘 게일-섀플리 알고리즘의 예시를 보여주는 애니메이션 1962년, 데이비드 게일과 로이드 섀플리는 대학 입학과 결혼을 원하는 개인들의 맥락에서, 다른 그룹에 동일한 수의 개체가 있을 경우 모든 결과적인 짝짓기/매칭 요소가 안정적이도록 항상 짝지어진 커플로 해결하는 것이 가능함을 증명했다. 그들은 이를 위한 알고리즘을 제시했다.archive-date=September 25, 2017Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online). 게일-섀플리 알고리즘 (지연 수락 알고리즘이라고도 함)은 여러 "라운드"(또는 "반복")를 포함한다. * 첫 번째 라운드에서, 먼저 a) 아직 약혼하지 않은 각 남성은 자신이 가장 선호하는 여성에게 청혼하고, 다음으로 b) 각 여성은 자신이 가장 선호하는 구혼자에게 "아마도"라고 답하고 다른 모든 구혼자에게는 "아니오"라고 답한다. 그런 다음 그녀는 지금까지 가장 선호하는 구혼자와 잠정적으로 "약혼"하고, 해당 구혼자도 그녀와 잠정적으로 약혼한다. * 각 후속 라운드에서, 먼저 a) 아직 약혼하지 않은 각 남성은 자신이 아직 청혼하지 않은 여성 중 가장 선호하는 여성에게 청혼하고 (여성이 이미 약혼했는지 여부와 관계없이), 다음으로 b) 각 여성은 현재 약혼하지 않았거나 현재 잠정적 배우자보다 이 남성을 더 선호하는 경우 "아마도"라고 답한다 (이 경우 그녀는 현재 잠정적 배우자를 거부하고, 그 배우자는 약혼하지 않은 상태가 된다). 약혼의 잠정적 특성은 이미 약혼한 여성이 "더 나은 상대로 갈아탈" (그리고 그 과정에서 그때까지의 배우자를 "저버릴") 권리를 보존한다. * 이 과정은 모든 사람이 약혼할 때까지 반복된다. 이 알고리즘은 남성 또는 여성의 수가 n일 때 시간 O(n^2) 내에 모든 참가자에 대해 안정적인 결혼을 생성함을 보장한다.hdl-access=free 가능한 모든 안정 매칭 중에서 이 알고리즘은 항상 모든 남성에게 가장 좋고 모든 여성에게는 가장 나쁜 매칭을 생성한다.title = Algorithms 이것은 남성(청혼하는 측)의 관점에서 진실된 메커니즘이다. 즉, 어떤 남성도 자신의 선호도를 잘못 보고하여 자신에게 더 나은 매칭을 얻을 수 없다. 또한 GS 알고리즘은 남성에 대한 그룹 전략 증명(group-strategy proof)이다. 즉, 남성 연합이 자신들의 선호도를 왜곡하여 연합 내 모든 남성이 더 나은 상태가 되도록 조정할 수 없다.jstor = 2321753 그러나 일부 연합이 자신들의 선호도를 왜곡하여 일부 남성은 더 나은 상태가 되고 다른 남성은 같은 배우자를 유지하는 것이 가능하다.isbn = 978-3-540-38875-3 GS 알고리즘은 여성(검토하는 측)에게는 진실되지 않다. 각 여성은 자신의 선호도를 잘못 보고하여 더 나은 매칭을 얻을 수 있다.
# 농촌 병원 정리
농촌 병원 정리 농촌 병원 정리는 안정 매칭 문제의 더 일반적인 변형에 관한 것으로, 병원에 의사를 배치하는 문제에 적용되는 경우 기본 n-대-n 형태의 안정 결혼 문제와 다음과 같은 방식으로 다르다. * 각 참가자는 매칭의 다른 쪽 참가자 하위 집합에만 매칭되기를 원할 수 있다. * 매칭의 한쪽 참가자(병원)는 수치적 수용 능력을 가질 수 있으며, 고용할 의사의 수를 지정한다. * 한쪽 참가자의 총수는 다른 쪽에서 매칭되어야 하는 총 수용 능력과 같지 않을 수 있다. * 결과적인 매칭은 모든 참가자를 매칭하지 않을 수 있다. 이 경우 안정성 조건은 매칭되지 않은 어떤 쌍도 매칭에서의 자신의 상황(다른 배우자이든 매칭되지 않은 상태이든)보다 서로를 선호하지 않는 것이다. 이 조건에서도 안정 매칭은 여전히 존재하며, 게일-섀플리 알고리즘으로 찾을 수 있다. 이러한 종류의 안정 매칭 문제에 대해 농촌 병원 정리는 다음과 같이 설명한다. * 배정된 의사의 집합과 각 병원에서 채워진 직위의 수는 모든 안정 매칭에서 동일하다. * 일부 안정 매칭에서 빈 직위가 있는 병원은 모든 안정 매칭에서 정확히 동일한 의사 집합을 받는다.
# 관련 문제
**무차별성을 포함한 안정 매칭**에서는 일부 남성이 두 명 이상의 여성에게 무관심할 수 있으며 그 반대도 마찬가지이다. **안정 룸메이트 문제**는 안정 결혼 문제와 유사하지만, 모든 참가자가 단일 풀에 속한다는 점(동일한 수의 "남성"과 "여성"으로 나뉘는 대신)에서 다르다. **병원 레지던트 문제** – 또한 **대학 입학 문제**로 알려짐 –는 병원이 여러 레지던트를 받을 수 있거나 대학이 한 명 이상의 학생으로 구성된 신입생을 받을 수 있다는 점에서 안정 결혼 문제와 다르다. 병원/레지던트 문제를 해결하는 알고리즘은 병원 중심적일 수 있다(1995년 이전 NRMP가 그랬던 것처럼).access-date=2 January 2018 또는 레지던트 중심적일 수 있다. 이 문제는 안정 결혼 문제가 해결된 동일한 게일과 섀플리의 원본 논문에서 알고리즘과 함께 해결되었다. **커플을 포함한 병원/레지던트 문제**는 레지던트 집합에 커플을 포함할 수 있으며, 이들은 함께 배정되어야 한다. 동일한 병원이거나 커플이 선택한 특정 병원 쌍(예: 결혼한 커플이 함께 지내며 서로 멀리 떨어진 프로그램에 갇히지 않도록 보장하기를 원함)에 배정될 수 있다. 병원/레지던트 문제에 커플을 추가하면 이 문제는 NP-완전이 된다.page=54 **할당 문제**는 최대 가중치를 갖는 가중 이분 그래프에서 매칭을 찾는 것을 목표로 한다. 최대 가중치 매칭은 안정적일 필요는 없지만, 일부 응용에서는 안정적인 매칭보다 최대 가중치 매칭이 더 좋다. **계약을 포함한 매칭** 문제는 참가자들이 다른 계약 조건으로 매칭될 수 있는 매칭 문제의 일반화이다.doi=10.1257/0002828054825466 계약의 중요한 특별한 경우는 유연한 임금을 포함한 매칭이다.doi=10.2307/1913320
# 추가 자료
* Kleinberg, J., and Tardos, E. (2005) Algorithm Design, Chapter 1, pp 1–12. See companion website for the Text date=2011-05-14. * publisher=American Mathematical Society * doi-access=free * url=http://dash.harvard.edu/bitstream/handle/1/29410143/evolut.pdf * title-link= Two-Sided Matching * location=New York See Section 10.6.4; [http://www.masfoundations.org/download.html downloadable free online. * pages = 255–262 * isbn=0-262-07118-5