안정적 결혼문제

Stable marriage problem

수학, 경제, 컴퓨터 과학에서 안정적 결혼 문제(또한 안정적 매칭 문제 또는 SMP)는 각 원소에 대한 선호 순서가 주어지는 동일한 크기의 두 원소 집합 사이에서 안정적인 매칭을 찾는 문제인 것이다.일치는 한 세트의 요소에서 다른 세트의 요소들로의 편향이다.일치는 다음과 같은 경우 안정적이지 않다.

  1. 첫 번째 일치 집합의 요소 A는 이미 A가 일치된 요소보다 두 번째 일치 집합의 요소 B를 선호하며,
  2. 또한 B는 B가 이미 일치하는 요소보다 A를 선호한다.

즉, 매칭 하에서는 둘 다 현재 파트너보다 서로를 선호하는 매칭(A, B)이 존재하지 않을 때 매칭이 안정적이다.

안정된 결혼문제는 다음과 같이 명시되어 있다.

각자가 이성의 모든 구성원을 선호 순서에 따라 순위를 매긴 n명의 남자와 n명의 여성을 고려해 볼 때, 현재의 동업자보다 서로 갖는 것을 더 선호하는 이성의 두 사람이 없을 정도로 남녀가 함께 결혼한다.그런 쌍의 사람이 없을 때, 결혼은 안정된 것으로 간주된다.

서로 짝을 지어야 하는 두 계급(이 예에서는 이성애자 남녀)의 존재는 이 문제를 안정적인 룸메이트 문제와 구별한다.

적용들

안정적인 결혼 문제에 대한 해결책을 찾기 위한 알고리즘은 다양한 실제 상황에 적용되는데, 아마도 이것들 중 가장 잘 알려진 것은 졸업 의대생들이 첫 병원 예약에 배정된 것이다.[1]2012년에는 로이드 S에게 노벨경제과학상(Economic Sciences)이 수여되었다. 샤플리와 앨빈 E. 로스 "안정적 배분 이론과 시장 설계 실천을 위해"[2]

안정적 결혼의 중요하고 대규모 적용은 대규모 분산 인터넷 서비스의 서버에 사용자를 할당하는 것이다.[3]수십억 명의 사용자들이 인터넷 상의 웹 페이지, 비디오 및 기타 서비스에 액세스하여 각 사용자들이 그 서비스를 제공하는 전 세계 수십만 대의 서버 중 하나와 (잠재적으로)사용자는 요청된 서비스에 대해 더 빠른 응답 시간을 제공할 수 있을 정도로 근위부 서버를 선호하기 때문에 각 사용자에 대해 (부분) 우선 순서가 발생한다.각 서버는 더 낮은 비용으로 이용자에게 서비스를 제공함으로써 각 서버에 대해 (부분적인) 사용자 우선 순서가 생기게 된다.세계의 많은 콘텐츠와 서비스를 유통하는 콘텐츠 전달 네트워크는 사용자들과 서버들 사이의 크고 복잡한 안정적인 결혼 문제를 수십 초마다 해결하여, 수십억 명의 사용자들이 요청된 웹 페이지, 비디오 또는 다른 서비스를 제공할 수 있는 각각의 서버와 매칭될 수 있게 한다.[3]

서로 다른 안정적인 매치

주요기사 : 안정된 성냥갑

일반적으로는 여러 가지 안정된 매치들이 있을 수 있다.예를 들어 남자(A,B,C)가 3명이고 여자(X,Y,Z)가 3명이라고 가정해 보자.

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

이 매칭 배열에는 다음과 같은 세 가지 안정적인 해결책이 있다.

  • 남성은 첫 번째 선택을 받고 여성은 세 번째 선택(AY, BZ, CX);
  • 모든 참가자는 두 번째 선택 - (AX, BY, CZ)
  • 여성은 첫 번째 선택을 받고 남성은 세 번째 선택 - (AZ, BX, CY)

불안정한 상황에서 두 선수 모두 대체 매치로 더 행복해야 하기 때문에 세 선수 모두 안정적이다.한 그룹에 첫 번째 선택권을 부여하면 다른 제안된 경기에 만족하지 못하기 때문에 경기가 안정적이라는 것을 보장한다.모든 사람들에게 그들의 두 번째 선택권을 주는 것은 다른 어떤 시합도 당사자들 중 한 명에게 미움을 받을 것을 보장한다.일반적으로, 안정된 결혼 문제의 어떤 예에 대한 해결책의 가족에게는 유한한 분배 격자의 구조가 주어질 수 있으며, 이러한 구조는 안정된 결혼에 관한 몇 가지 문제에 대한 효율적인 알고리즘으로 이어진다.[4]

n남성과 n여성들로 안정적인 결혼 문제에 대한 uniformly-random 예로, 안정적인 matchings의 평균 수가 점차적으로 n.[6]Counting의 1n은 안정적인 결혼 예를 다른 안정적인 matchings의 수를 최대로 늘리는 선택에서 ln⁡ n(n}.[5]−, 이 번호는 지수 함수나 있다.그 n주어진 예에서 안정된 매치 업의 움버는 #P-완전이다.[7]

알고리즘 솔루션

주요기사: 게일-샤플리 알고리즘
게일-샤플리 알고리즘의 예를 보여주는 애니메이션

1962년, 데이비드 게일과 로이드 샤플리는 남녀 동수의 경우, SMP를 해결하고 모든 결혼을 안정적으로 하는 것이 항상 가능하다는 것을 증명했다.그들은 그렇게 하기 위한 알고리즘을 제시했다.[8][9]

게일-샤플리 알고리즘(이연 수용 알고리즘이라고도 함)은 다수의 "원형"(또는 "반복")을 포함한다.

  • 첫 번째 라운드에서, 첫 번째 a) 각 미계약 남성은 자신이 가장 선호하는 여자에게 프로포즈를 하고, 그 다음 b) 각 여성은 자신이 가장 선호하는 구혼자에게 "아마도"라고 대답하며, 다른 모든 구혼자들에게는 "아니오"라고 대답한다.그리고 나서 그녀는 그녀가 지금까지 가장 선호하는 구혼자와 잠정적으로 "계약"되고, 구혼자도 마찬가지로 그녀와 잠정적으로 약혼한다.
  • 그 후의 각 라운드에서, 첫 번째 a)각의 약혼하지 않은 남자는 자신이 아직 청혼하지 않은 가장 선호하는 여자에게 청혼하고, 그 다음 b) 각 여자는 현재 약혼하지 않았거나 현재의 잠정적인 파트너보다 이 남자를 더 좋아하는 경우(이 경우, 그녀는 현재 자신의 현재를 거절한다)라고 대답한다.참여하지 않는 임시 파트너).약혼의 잠정적인 성격은 이미 약혼한 여성이 "거래"할 권리(그리고 그 과정에서, 그 때까지 그녀의 파트너를 "제척"할 권리)를 보존한다.
  • 이 과정은 모든 사람이 약혼할 때까지 반복된다.

이 알고리즘은 시간 ( 2) 의 모든 참가자에게 안정적인 결혼 생활을 보장하며, 서 n 은 남성 또는 여성의 수이다.[10]

가능한 모든 다른 안정된 매치 중에서, 그것은 항상 모든 안정된 매치 중에서 모든 남성에게 가장 좋은 것을, 그리고 모든 여성들에게 가장 나쁜 것을 산출한다.남성(제안 측)의 관점에서 보면 진실한 메커니즘이다.즉, 어떤 사람도 자신의 선호를 잘못 전달함으로써 자신에게 더 나은 매칭을 얻을 수 없다.더욱이 GS 알고리즘은 심지어 남성들에게 그룹 전략의 증거다. 즉, 어떤 남성연대가 남성연대의 모든 남성들이 철저히 더 나은 삶을 살도록 그들의 선호도를 잘못 표현하는 것을 조정할 수 없다.[11]그러나 일부 연정은 어떤 남자는 더 잘살고 다른 남자는 같은 파트너를 유지하는 식으로 자신의 선호를 잘못 전달할 가능성도 있다.[12]GS 알고리즘은 여성들에게 진실하지 않다. 각 여성은 자신의 선호도를 잘못 전달하고 더 나은 매치를 얻을 수 있다.

농촌병원 정리

주요 기사:농촌병원 정리

시골 병원 정리는 안정적인 결혼 문제의 기본적인 n-to-n 형태와는 다음과 같은 방식으로 의사를 병원 내 직위에 매칭하는 문제에 적용하는 것과 같이 안정적 매칭 문제의 보다 일반적인 변종을 우려한다.

  • 각 참가자는 매칭의 반대편에 있는 참가자의 하위 집합에만 기꺼이 매칭될 수 있다.
  • 매칭(병원)의 한쪽에 있는 참가자는 자신이 고용할 의사 수를 명시하는 수치적 역량을 가질 수 있다.
  • 한 쪽 참가자의 총 수는 다른 쪽 참가자와 일치해야 하는 총 수용력과 같지 않을 수 있다.
  • 일치하는 결과가 모든 참가자와 일치하지 않을 수 있다.

이 경우, 안정성의 조건은 매칭(그 상황이 다른 파트너인지 아니면 비매칭인지)에서 자신의 상황보다 짝을 이루지 못한 쌍이 서로를 선호하지 않는다는 것이다.이러한 조건으로는 안정적인 매칭이 여전히 존재할 것이며, 게일-샤플리 알고리즘에 의해 여전히 발견될 수 있다.

이러한 종류의 안정적인 매칭 문제에 대해 시골 병원 정리에서는 다음과 같이 기술하고 있다.

  • 배정된 의사들의 집합, 그리고 각 병원의 충원된 직위의 수는 모든 안정된 시합에서 동일하다.
  • 어떤 안정적인 매칭에 빈 자리가 있는 병원은 모든 안정된 매칭에서 정확히 같은 수의 의사를 받는다.

관련 문제

무관심과 안정된 매칭에서, 어떤 남자들은 두 명 이상의 여자들 사이에서 무관심할 수도 있고, 그 반대의 경우도 있을 수 있다.

안정적인 룸메이트 문제는 안정적인 결혼 문제와 비슷하지만 모든 참가자가 단일 풀(동일한 수의 '남성'과 '여성'으로 나뉘는 대신)에 속한다는 점에서 차이가 있다.

대학입학문제로도 알려진 병원/거주자 문제는 병원이 여러 명의 거주자를 데려갈 수도 있고, 대학이 한 명 이상의 신입생을 데려갈 수도 있다는 점에서 안정적인 결혼문제와 다르다.병원/주민 문제를 해결하기 위한 알고리즘은 (NRMP가 1995년 이전과 마찬가지로)[13] 병원 지향적이거나 주민 지향적일 수 있다.이 문제는 게일과 샤플리의 같은 원문에서 알고리즘으로 해결되어 안정적인 결혼 문제가 해결되었다.[8]

부부간의 병원/거주자 문제는 거주자 집합이 동일한 병원이나 부부가 선택한 특정 병원 쌍(예: 결혼한 부부는 그들이 서로 멀리 떨어져 있는 프로그램에 갇히지 않고 함께 머물도록 보장하기를 원한다)에 함께 배정되어야 하는 부부들을 포함시킬 수 있도록 한다.병원/거주자 문제에 부부가 추가되면 문제가 NP-완전해진다.[14]

할당 문제는 가중치가 최대인 초당적 그래프에서 일치 항목을 찾으려고 한다.최대 가중 일치 항목이 안정적일 필요는 없지만, 일부 애플리케이션에서는 최대 가중 일치 항목이 안정적인 일치 항목보다 낫다.

계약문제와의 매칭은 참가자를 서로 다른 계약조건으로 매칭할 수 있는 매칭문제 일반화다.[15]중요한 계약 특례는 탄력적인 임금과 매칭하는 것이다.[16]

참고 항목

참조

  1. ^ 안정적 매칭 알고리즘
  2. ^ "The Prize in Economic Sciences 2012". Nobelprize.org. Retrieved 2013-09-09.
  3. ^ a b Bruce Maggs and Ramesh Sitaraman (2015). "Algorithmic nuggets in content delivery" (PDF). ACM SIGCOMM Computer Communication Review. 45 (3).
  4. ^ Gusfield, Dan (1987). "Three fast algorithms for four problems in stable marriage". SIAM Journal on Computing. 16 (1): 111–128. doi:10.1137/0216010. MR 0873255.
  5. ^ Pittel, Boris (1989). "The average number of stable matchings". SIAM Journal on Discrete Mathematics. 2 (4): 530–549. doi:10.1137/0402048. MR 1018538.
  6. ^ Karlin, Anna R.; Gharan, Shayan Oveis; Weber, Robbie (2018). "A simply exponential upper bound on the maximum number of stable matchings". In Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.). Proceedings of the 50th Symposium on Theory of Computing (STOC 2018). Association for Computing Machinery. pp. 920–925. arXiv:1711.01032. doi:10.1145/3188745.3188848. MR 3826305.
  7. ^ Irving, Robert W.; Leather, Paul (1986). "The complexity of counting stable marriages". SIAM Journal on Computing. 15 (3): 655–667. doi:10.1137/0215048. MR 0850415.
  8. ^ a b Gale, D.; Shapley, L. S. (1962). "College Admissions and the Stability of Marriage". American Mathematical Monthly. 69 (1): 9–14. doi:10.2307/2312726. JSTOR 2312726.
  9. ^ 해리 메어슨: "안정적인 결혼 문제", 브랜다이스 리뷰 12, 1992년 (온라인)
  10. ^ 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. pp. 131–136. doi:10.1109/ICKS.2008.7. hdl:2433/226940. ISBN 978-0-7695-3128-1.
  11. ^ Dubins, L. E.; Freedman, D. A. (1981). "Machiavelli and the Gale–Shapley algorithm". American Mathematical Monthly. 88 (7): 485–494. doi:10.2307/2321753. JSTOR 2321753. MR 0628016.
  12. ^ Huang, Chien-Chung (2006). "Cheating by men in the Gale-Shapley stable matching algorithm". In Azar, Yossi; Erlebach, Thomas (eds.). Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4168. Springer. pp. 418–431. doi:10.1007/11841036_39. MR 2347162.
  13. ^ Robinson, Sara (April 2003). "Are Medical Students Meeting Their (Best Possible) Match?" (PDF). SIAM News (3): 36. Retrieved 2 January 2018.
  14. ^ Gusfield, D.; Irving, R. W. (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press. p. 54. ISBN 0-262-07118-5.
  15. ^ Hatfield, John William; Milgrom, Paul (2005). "Matching with Contracts". American Economic Review. 95 (4): 913–935. doi:10.1257/0002828054825466. JSTOR 4132699.
  16. ^ Crawford, Vincent; Knoer, Elsie Marie (1981). "Job Matching with Heterogeneous Firms and Workers". Econometrica. 49 (2): 437–450. doi:10.2307/1913320. JSTOR 1913320.

추가 읽기

외부 링크