본문으로 이동

안정 매칭 문제

위키백과, 우리 모두의 백과사전.

수학, 경제학, 컴퓨터 과학에서 안정 매칭 문제(Stable matching problem)[1][2][3]는 각 요소에 대한 선호도 순서가 주어졌을 때, 두 개의 동일한 크기의 요소 집합 사이에 안정적인 매칭을 찾는 문제이다. 매칭은 한 집합의 요소에서 다른 집합의 요소로의 전단사이다. 매칭은 다음의 경우 불안정하다.

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

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

안정 결혼 문제는 다음과 같이 서술되었다.

n명의 남성과 n명의 여성이 주어지고, 각 사람은 이성 구성원 모두를 선호도 순서대로 순위를 매겼을 때, 남성과 여성을 짝지어 현재 배우자보다 서로를 더 선호하는 이성 쌍이 없도록 한다. 그러한 쌍이 없을 때, 결혼 집합은 안정적이라고 간주된다.

서로 짝을 이루어야 할 두 계층(이 예에서는 이성애자 남성과 여성)의 존재는 이 문제를 안정 룸메이트 문제와 구별한다.

응용

[편집]

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

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

안정 매칭을 위한 게일-섀플리 알고리즘은 히브리 유니언 칼리지 졸업 랍비를 유대인 회중에게 배정하는 데 사용된다.[7]

다른 안정 매칭

[편집]
 이 부분의 본문은 안정 매칭의 격자입니다.

일반적으로 여러 가지 안정 매칭이 있을 수 있다. 예를 들어, 세 명의 남성(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).

세 가지 모두 안정적이다. 불안정성은 두 참가자 모두 다른 대안 매칭에 더 만족해야 하기 때문이다. 한 그룹에게 첫 번째 선택을 주는 것은 매칭이 안정적임을 보장하는데, 이는 그들이 다른 어떤 제안된 매칭에도 불만족할 것이기 때문이다. 모든 사람에게 두 번째 선택을 주는 것은 다른 어떤 매칭도 당사자 중 한 명에게 불만을 일으킬 것임을 보장한다. 일반적으로 안정 결혼 문제의 모든 인스턴스에 대한 해결책 집합은 유한 분배 격자의 구조를 가질 수 있으며, 이 구조는 안정 결혼에 관한 여러 문제에 대한 효율적인 알고리즘을 이끌어낸다.[8]

n명의 남성과 n명의 여성이 있는 안정 결혼 문제의 균일 무작위 인스턴스에서 안정 매칭의 평균 수는 점근적으로 이다.[9] 안정 매칭의 최대 수를 갖도록 선택된 안정 결혼 인스턴스에서 이 수는 n의 지수 함수이다.[10] 주어진 인스턴스에서 안정 매칭의 수를 세는 것은 #P-완전이다.[11]

알고리즘적 해결책

[편집]
 이 부분의 본문은 게일-섀플리 알고리즘입니다.
게일-섀플리 알고리즘의 예시를 보여주는 애니메이션

1962년, 데이비드 게일과 로이드 섀플리는 대학 입학과 결혼을 원하는 개인들의 맥락에서, 다른 그룹에 동일한 수의 개체가 있을 경우 모든 결과적인 짝짓기/매칭 요소가 안정적이도록 항상 짝지어진 커플로 해결하는 것이 가능함을 증명했다. 그들은 이를 위한 알고리즘을 제시했다.[12][13]

게일-섀플리 알고리즘 (지연 수락 알고리즘이라고도 함)은 여러 "라운드"(또는 "반복")를 포함한다.

  • 첫 번째 라운드에서, 먼저 a) 아직 약혼하지 않은 각 남성은 자신이 가장 선호하는 여성에게 청혼하고, 다음으로 b) 각 여성은 자신이 가장 선호하는 구혼자에게 "아마도"라고 답하고 다른 모든 구혼자에게는 "아니오"라고 답한다. 그런 다음 그녀는 지금까지 가장 선호하는 구혼자와 잠정적으로 "약혼"하고, 해당 구혼자도 그녀와 잠정적으로 약혼한다.
  • 각 후속 라운드에서, 먼저 a) 아직 약혼하지 않은 각 남성은 자신이 아직 청혼하지 않은 여성 중 가장 선호하는 여성에게 청혼하고 (여성이 이미 약혼했는지 여부와 관계없이), 다음으로 b) 각 여성은 현재 약혼하지 않았거나 현재 잠정적 배우자보다 이 남성을 더 선호하는 경우 "아마도"라고 답한다 (이 경우 그녀는 현재 잠정적 배우자를 거부하고, 그 배우자는 약혼하지 않은 상태가 된다). 약혼의 잠정적 특성은 이미 약혼한 여성이 "더 나은 상대로 갈아탈" (그리고 그 과정에서 그때까지의 배우자를 "저버릴") 권리를 보존한다.
  • 이 과정은 모든 사람이 약혼할 때까지 반복된다.

이 알고리즘은 남성 또는 여성의 수가 일 때 시간 내에 모든 참가자에 대해 안정적인 결혼을 생성함을 보장한다.[14]

가능한 모든 안정 매칭 중에서 이 알고리즘은 항상 모든 남성에게 가장 좋고 모든 여성에게는 가장 나쁜 매칭을 생성한다.[15]

이것은 남성(청혼하는 측)의 관점에서 진실된 메커니즘이다. 즉, 어떤 남성도 자신의 선호도를 잘못 보고하여 자신에게 더 나은 매칭을 얻을 수 없다. 또한 GS 알고리즘은 남성에 대한 그룹 전략 증명(group-strategy proof)이다. 즉, 남성 연합이 자신들의 선호도를 왜곡하여 연합 내 모든 남성이 더 나은 상태가 되도록 조정할 수 없다.[16] 그러나 일부 연합이 자신들의 선호도를 왜곡하여 일부 남성은 더 나은 상태가 되고 다른 남성은 같은 배우자를 유지하는 것이 가능하다.[17] GS 알고리즘은 여성(검토하는 측)에게는 진실되지 않다. 각 여성은 자신의 선호도를 잘못 보고하여 더 나은 매칭을 얻을 수 있다.

농촌 병원 정리

[편집]
 이 부분의 본문은 농촌 병원 정리입니다.

농촌 병원 정리는 안정 매칭 문제의 더 일반적인 변형에 관한 것으로, 병원에 의사를 배치하는 문제에 적용되는 경우 기본 n-대-n 형태의 안정 결혼 문제와 다음과 같은 방식으로 다르다.

  • 각 참가자는 매칭의 다른 쪽 참가자 하위 집합에만 매칭되기를 원할 수 있다.
  • 매칭의 한쪽 참가자(병원)는 수치적 수용 능력을 가질 수 있으며, 고용할 의사의 수를 지정한다.
  • 한쪽 참가자의 총수는 다른 쪽에서 매칭되어야 하는 총 수용 능력과 같지 않을 수 있다.
  • 결과적인 매칭은 모든 참가자를 매칭하지 않을 수 있다.

이 경우 안정성 조건은 매칭되지 않은 어떤 쌍도 매칭에서의 자신의 상황(다른 배우자이든 매칭되지 않은 상태이든)보다 서로를 선호하지 않는 것이다. 이 조건에서도 안정 매칭은 여전히 존재하며, 게일-섀플리 알고리즘으로 찾을 수 있다.

이러한 종류의 안정 매칭 문제에 대해 농촌 병원 정리는 다음과 같이 설명한다.

  • 배정된 의사의 집합과 각 병원에서 채워진 직위의 수는 모든 안정 매칭에서 동일하다.
  • 일부 안정 매칭에서 빈 직위가 있는 병원은 모든 안정 매칭에서 정확히 동일한 의사 집합을 받는다.

관련 문제

[편집]

무차별성을 포함한 안정 매칭에서는 일부 남성이 두 명 이상의 여성에게 무관심할 수 있으며 그 반대도 마찬가지이다.

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

병원 레지던트 문제 – 또한 대학 입학 문제로 알려짐 –는 병원이 여러 레지던트를 받을 수 있거나 대학이 한 명 이상의 학생으로 구성된 신입생을 받을 수 있다는 점에서 안정 결혼 문제와 다르다. 병원/레지던트 문제를 해결하는 알고리즘은 병원 중심적일 수 있다(1995년 이전 NRMP가 그랬던 것처럼).[18] 또는 레지던트 중심적일 수 있다. 이 문제는 안정 결혼 문제가 해결된 동일한 게일과 섀플리의 원본 논문에서 알고리즘과 함께 해결되었다.[12]

커플을 포함한 병원/레지던트 문제는 레지던트 집합에 커플을 포함할 수 있으며, 이들은 함께 배정되어야 한다. 동일한 병원이거나 커플이 선택한 특정 병원 쌍(예: 결혼한 커플이 함께 지내며 서로 멀리 떨어진 프로그램에 갇히지 않도록 보장하기를 원함)에 배정될 수 있다. 병원/레지던트 문제에 커플을 추가하면 이 문제는 NP-완전이 된다.[19]

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

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

같이 보기

[편집]

각주

[편집]
  1. ↑ Tesler, G. (2020). “Ch. 5.9: Gale-Shapley Algorithm” (PDF). 《mathweb.ucsd.edu》. University of California San Diego. 2025년 4월 26일에 확인함. 
  2. ↑ Kleinberg, Jon; Tardos, Éva (2005). “Algorithmn Design: 1. Stable Matching” (PDF). 《www.cs.princeton.edu》. Pearson-Addison Wesley: Princeton University. 2025년 4월 26일에 확인함. 
  3. ↑ Goel, Ashish (2019년 1월 21일). Ramseyer, Geo (편집). “CS261 Winter 2018- 2019 Lecture 5: Gale-Shapley Algorith” (PDF). 《web.stanford.edu》. Stanford University. 2025년 4월 26일에 확인함. 
  4. ↑ Stable Matching Algorithms
  5. ↑ “The Prize in Economic Sciences 2012”. Nobelprize.org. 2013년 9월 9일에 확인함. 
  6. ↑ 가 나 Bruce Maggs and Ramesh Sitaraman (2015). 《Algorithmic nuggets in content delivery》 (PDF). 《ACM SIGCOMM Computer Communication Review》 45. 
  7. ↑ Bodin, Lawrence; Panken, Aaron (June 2003). 《High Tech for a Higher Authority: The Placement of Graduating Rabbis from Hebrew Union College—Jewish Institute of Religion》 (영어). 《Interfaces》 33. 1–11쪽. doi:10.1287/inte.33.3.1.16013. ISSN 0092-2102. 
  8. ↑ Gusfield, Dan (1987). 《Three fast algorithms for four problems in stable marriage》. 《SIAM Journal on Computing》 16. 111–128쪽. doi:10.1137/0216010. MR 873255. 
  9. ↑ Pittel, Boris (1989). 《The average number of stable matchings》. 《SIAM Journal on Discrete Mathematics》 2. 530–549쪽. doi:10.1137/0402048. MR 1018538. 
  10. ↑ Karlin, Anna R.; Gharan, Shayan Oveis; Weber, Robbie (2018). 〈A simply exponential upper bound on the maximum number of stable matchings〉. Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (편집). 《Proceedings of the 50th Symposium on Theory of Computing (STOC 2018)》. Association for Computing Machinery. 920–925쪽. arXiv:1711.01032. doi:10.1145/3188745.3188848. ISBN 978-1-4503-5559-9. MR 3826305. 
  11. ↑ Irving, Robert W.; Leather, Paul (1986). 《The complexity of counting stable marriages》. 《SIAM Journal on Computing》 15. 655–667쪽. doi:10.1137/0215048. MR 850415. 
  12. ↑ 가 나 Gale, D.; Shapley, L. S. (1962). 《College Admissions and the Stability of Marriage》. 《American Mathematical Monthly》 69. 9–14쪽. doi:10.2307/2312726. JSTOR 2312726. 2017년 9월 25일에 원본 문서에서 보존된 문서. 
  13. ↑ Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online).
  14. ↑ Iwama, Kazuo; Miyazaki, Shuichi (2008). 〈A Survey of the Stable Marriage Problem and Its Variants〉. 《International Conference on Informatics Education and Research for Knowledge-Circulating Society (ICKS 2008)》. IEEE. 131–136쪽. doi:10.1109/ICKS.2008.7. hdl:2433/226940. ISBN 978-0-7695-3128-1. 
  15. ↑ Erickson, Jeff (June 2019). 〈4.5 Stable matching〉 (PDF). 《Algorithms》. University of Illinois. 170–176쪽. 2023년 12월 19일에 확인함. 
  16. ↑ Dubins, L. E.; Freedman, D. A. (1981). 《Machiavelli and the Gale–Shapley algorithm》. 《American Mathematical Monthly》 88. 485–494쪽. doi:10.2307/2321753. JSTOR 2321753. MR 628016. 
  17. ↑ Huang, Chien-Chung (2006). 〈Cheating by men in the Gale–Shapley stable matching algorithm〉. Azar, Yossi; Erlebach, Thomas (편집). 《Algorithms – ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11–13, 2006, Proceedings》. Lecture Notes in Computer Science. Springer. 418–431쪽. doi:10.1007/11841036_39. ISBN 978-3-540-38875-3. MR 2347162. 
  18. ↑ Robinson, Sara (April 2003). 《Are Medical Students Meeting Their (Best Possible) Match?》 (PDF). 《SIAM News》. 36쪽. 2018년 1월 2일에 확인함. 
  19. ↑ Gusfield, D.; Irving, R. W. (1989). 《The Stable Marriage Problem: Structure and Algorithms》. MIT Press. 54쪽. ISBN 0-262-07118-5. 
  20. ↑ Hatfield, John William; Milgrom, Paul (2005). 《Matching with Contracts》. 《American Economic Review》 95. 913–935쪽. doi:10.1257/0002828054825466. JSTOR 4132699. 
  21. ↑ Crawford, Vincent; Knoer, Elsie Marie (1981). 《Job Matching with Heterogeneous Firms and Workers》. 《Econometrica》 49. 437–450쪽. doi:10.2307/1913320. JSTOR 1913320. 

추가 자료

[편집]

외부 링크

[편집]
원본 주소 "https://ko.wikipedia.org/w/index.php?title=안정_매칭_문제&oldid=40866739"