안정적 매칭 폴리토프

Stable matching polytope

수학, 경제, 컴퓨터 과학에서 안정 매칭 폴리토프 또는 안정 결혼 폴리토프는 안정 매칭 문제의 한 예에 대한 해결책에서 파생된 볼록 폴리토프다.[1][2]

설명

안정적인 일치 폴리토프는 주어진 문제의 안정적인 일치에 대한 지시 벡터의 볼록한 선체다.일치할 수 있는 각 요소 쌍에 대한 치수와 각 안정적인 일치에 대한 꼭지점이 있다.각 정점에 대해 데카르트 좌표는 해당 일치에서 일치하는 쌍에 대해 1이고 일치하지 않는 쌍에 대해서는 0이다.[1]

안정적인 매칭 폴리토페에는 다항식 면수가 있다.여기에는 (각 좌표는 0과 1 사이여야 하며, 각 요소와 관련된 쌍에 대한 좌표의 합은 정확히 1이어야 함) 안정성의 요구조건이 없는 일치를 기술하는 전통적인 불평등이 포함된다(각 포에 대해) 결과 일치가 안정되도록 구속하는 불평등도 포함된다.tential 일치 쌍 요소, 적어도 두 요소 중 하나에 대해 양호한 일치에 대한 좌표 합계는 하나 이상이어야 한다.이 모든 제약을 만족시키는 점은 안정적인 일치 문제의 선형 프로그래밍 완화의 부분적 해결책이라고 생각할 수 있다.

통합성

위에 열거한 면의 제약조건에 의해 기술된 폴리토프는 위에서 기술한 정점만 가지고 있다는 것이 반데 바테(1989)의 정리다.특히 그것은 일체형 폴리토프다.이것은 두 세트 사이의 모든 부분 일치의 집합을 설명하는 비르코프 폴리토프, 유사한 폴리토프가 일체화된 개럿 비르코프의 정리의 아날로그로 볼 수 있다.[3]

동일한 정리를 진술하는 동등한 방법은 모든 부분 일치가 적분 일치의 볼록한 조합으로 표현될 수 있다는 것이다.Teo & Sethuraman(1998)은 주어진 분수 일치와 동일한 기대값을 설정할 수 있는 적분 일치에 대한 확률 분포를 구성함으로써 이를 증명한다.이를 위해 다음 단계를 수행하십시오.

  • 안정적 매칭 문제의 한 쪽에 있는 각 요소(의사, 예를 들어 의사를 병원에 매칭하는 문제에서)에 대해 다른 쪽(병원)의 요소와 쌍을 이루는 데 할당된 분수 값을 고려하여 해당 의사의 선호도에 따라 이러한 값을 감소 순서대로 정렬하십시오.
  • 단위 간격을 정렬된 순서에 따라 이 부분 값과 동일한 길이의 하위 절편으로 분할하십시오.단위 간격에서 무작위 번호를 선택하면 선택한 의사에게 무작위 일치가 주어지며, 그 일치의 분수 무게와 같은 확률도 주어진다.
  • 대칭적으로, 안정적 매칭(병원)의 반대편에 있는 각 요소에 대해 고려하고, 선호도에 따라 증가하는 순서로 해당 요소와 관련된 쌍에 대한 부분 값을 정렬하고, 하위 교차점이 정렬된 순서로 이러한 부분 값을 갖는 단위 간격의 파티션을 구성한다.
  • 각각의 일치된 쌍에 대해, 그 쌍과 관련된 하위 절연이 의사를 위한 칸막이와 그 쌍의 병원 칸막이 모두에서 동일하다는 것을 증명할 수 있다.따라서 단위 간격에서 무작위 번호 하나를 선택하고, 그 선택을 사용하여 각 의사별 병원과 각 병원별 의사를 동시에 선택하는 것이 매칭이 된다.게다가 이 매칭은 안정적이라는 것을 보여줄 수 있다.

결과적으로 무작위로 선택한 안정적인 일치는 해당 쌍의 부분 좌표 값과 동일한 확률로 특정 일치 쌍을 선택한다.따라서 이러한 방식으로 구성된 안정적 일치에 대한 확률 분포는 주어진 부분 일치를 통합적 안정 일치의 볼록한 조합으로 표현한다.[4]

부분 매치 격자

모든 안정적인 성냥갑은 분배 격자, 즉 안정적인 성냥갑이 형성되는데, 두 성냥갑이 결합하면 모든 의사들이 두 성냥갑에 배정된 병원 중에서 선호하는 것을 갖게 되고, 그 만남은 모든 병원에게 선호도를 부여한다.[5]안정 매칭 폴리토프의 포인트인 모든 부분 안정 매칭의 패밀리도 마찬가지다.[3]

안정적인 매칭 폴리토프에서 적어도 병원만큼 좋은 (의사에게) 매칭에 할당된 총 분수 값이 적어도 첫 번째 매칭에서 두 번째 매칭에서만큼 클 경우, 한 매칭이 다른 매칭을 지배하도록 정의할 수 있다.이것은 부분 일치 순서에 대한 부분 순서를 정의한다.이 부분 순서는 의사들이 성냥을 제안하고 병원이 제안에 응답하는 Gale-Shapley 알고리즘 버전에 의해 발견되는 정수 안정 매칭이라는 고유한 가장 큰 요소를 가지고 있다.또한 병원에서 제안서를 작성하는 게일-샤플리 알고리즘 버전에 의해 발견되는 정수 안정 매칭인 고유한 최소 요소를 가지고 있다.[3]

이 부분 순서와 일관되게, 두 부분 일치의 만남을 두 부분 순서에서 가능한 한 낮은 부분 일치로 정의할 수 있다.각 의사와 병원의 경우, 그것은 해당 쌍의 총 중량과 동일한 의사의 모든 더 나은 쌍을 주어진 두 개의 일치 항목에서 해당하는 총합 중 더 큰 값과 같게 만드는 가중치를 잠재적 일치 쌍에 할당한다.결합은 대칭적으로 정의된다.[3]

적용들

안정적인 매칭 폴리토프에 선형 프로그래밍을 적용하면 최소 또는 최대 무게 안정 매칭을 찾을 수 있다.[1]동일한 문제에 대한 대안적 방법으로는 안정적인 일치의 격자에서 파생된 부분 순서 집합에 폐쇄 문제를 적용하거나,[6] 이 부분 순서의 폴리토프 순서에 선형 프로그래밍을 적용하는 것이 있다.

순서 폴리토페와의 관계

연속적인 분배 격자를 정의하는 안정적 일치 폴리토프의 속성은 격자의 충족과 결합을 통해 좌표현상 최대화와 최소화가 이루어지는 폴리토프인 분배 폴리토프의 정의 속성과 유사하다.[7]그러나 안정적인 일치 폴리토프를 위한 만남과 결합 연산은 좌표적 최대화 및 최소화와는 다른 방식으로 정의된다.대신, 안정적인 일치의 격자의 기본 부분 순서의 폴리토프 순서는 안정적인 일치의 집합과 관련된 분산적인 폴리토프를 제공하지만, 그 중 하나를 위한 폴리토프 순서는 각각의 일치된 쌍과 관련된 분수 값을 판독하기가 더 어렵다.사실 안정적인 매칭 폴리토프와 기저 부분 순서의 순서 폴리토프는 서로 매우 밀접하게 연관되어 있는데, 각각은 다른 하나의 아핀 변형이다.[8]

참조

  1. ^ a b c Vande Vate, John H. (1989), "Linear programming brings marital bliss", Operations Research Letters, 8 (3): 147–153, doi:10.1016/0167-6377(89)90041-2, MR 1007271
  2. ^ Ratier, Guillaume (1996), "On the stable marriage polytope" (PDF), Discrete Mathematics, 148 (1–3): 141–159, doi:10.1016/0012-365X(94)00237-D, MR 1368286
  3. ^ a b c d Roth, Alvin E.; Rothblum, Uriel G.; Vande Vate, John H. (1993), "Stable matchings, optimal assignments, and linear programming", Mathematics of Operations Research, 18 (4): 803–828, doi:10.1287/moor.18.4.803, JSTOR 3690124, MR 1251681
  4. ^ Teo, Chung-Piaw; Sethuraman, Jay (1998), "The geometry of fractional stable matchings and its applications", Mathematics of Operations Research, 23 (4): 874–891, doi:10.1287/moor.23.4.874, MR 1662426
  5. ^ Knuth, Donald E. (1976), Mariages stables et leurs relations avec d'autres problèmes combinatoires (PDF) (in French), Montréal, Quebec: Les Presses de l'Université de Montréal, ISBN 0-8405-0342-3, MR 0488980. 특히 문제 6, 페이지 87–94를 참조하라.
  6. ^ Irving, Robert W.; Leather, Paul; Gusfield, Dan (1987), "An efficient algorithm for the "optimal" stable marriage", Journal of the ACM, 34 (3): 532–543, doi:10.1145/28869.28871, MR 0904192
  7. ^ Felsner, Stefan; Knauer, Kolja (2011), "Distributive lattices, polyhedra, and generalized flows", European Journal of Combinatorics, 32 (1): 45–59, doi:10.1016/j.ejc.2010.07.011, MR 2727459.
  8. ^ Aprile, Manuel; Cevallos, Alfonso; Faenza, Yuri (2018), "On 2-level polytopes arising in combinatorial settings", SIAM Journal on Discrete Mathematics, 32 (3): 1857–1886, arXiv:1702.03187, doi:10.1137/17M1116684, MR 3835234