안정적인 룸메이트 문제

Stable roommates problem

수학, 경제, 컴퓨터 과학, 특히 결합기, 게임 이론, 알고리즘 분야에서 안정적 롬메이트 문제(SRP)는 짝수 세트의 안정적인 매칭을 찾는 문제다.매칭은 세트를 분리쌍("룸메이트")으로 분리하는 것이다.룸메이트가 아닌 두 가지 요소가 없고 둘 다 매칭 중인 룸메이트보다 서로를 선호하는 두 가지 요소가 없다면 매칭은 안정적이다.이는 '남성'과 '여성'의 계층 간만의 문제가 아니라 어떤 두 요소 간에든 매칭을 허용한다는 점에서 안정적 결혼 문제와 구별된다.

일반적으로 다음과 같이 명시된다.

안정적 룸메이트 문제(SRP)의 한 예에서, 2n 참가자는 각각 다른 참가자들을 엄격한 선호도 순으로 순위를 매긴다.매칭은 참가자들의 n개의 분리된 쌍들의 집합이다.SRP의 한 예에서 일치하는 M은 두 명의 참가자가 없을 경우 안정적이며, 각 참가자는 M의 파트너보다 다른 참가자를 선호한다.그러한 쌍은 M을 차단하거나, M에 관해서는 차단 쌍이라고 한다.

해결책

안정적인 결혼 문제와 달리, 특정 참가자와 선호도에 대한 안정적인 매칭은 존재하지 않을 수 있다.존재하지 않는 안정적인 페어링의 최소 예를 위해 4명을 고려하십시오.A,B,C그리고D, 랭킹은 다음과 같다.

A:(B,C,D), B:(C,A,D), C:(A,B,D), D:(A,B,C)

이 순위에서는 A, B, C 각자가 누군가에게 가장 선호하는 사람이다.어떤 해법에서든 A, B, C 중 하나는 D, 나머지 두 개는 서로 짝지어져야 한다(예: AD, BC). 그러나 D와 짝을 이룬 사람에게는 다른 멤버가 가장 높은 등급을 매겨 D의 파트너는 D보다 이 멤버를 선호할 것이다.이 예에서 AC는 AD보다 더 호의적인 페어링이지만, BD의 나머지 페어링은 동일한 문제를 제기하여, 이들 참가자에 대한 안정적인 매칭의 부재와 그들의 선호도를 보여준다.

알고리즘.

효율적인 알고리즘이 (Irving 1985)에 제공되었다.[1]알고리즘은 문제의 어떤 예에 대해서도 안정적인 일치가 존재하는지 여부를 결정하고, 만약 있다면 그러한 일치를 찾을 것이다.선호 리스트의 필요한 조작과 회전 식별을 구현하기 위해 적절한 데이터 구조를 사용한다면 어빙의 알고리즘은 O(n2) 복잡성을 가진다.

알고리즘은 두 단계로 구성된다.1단계에서 참가자들은 안정적인 결혼 문제를 위한 게일-샤플리 알고리즘과 유사한 방식으로 서로에게 프로포즈를 한다.각 참가자는 선호도에 따라 다른 참가자를 주문하여, 다른 참가자의 순서 집합인 선호 목록이 작성된다.그런 다음 참여자는 현재 제안이 거부된 경우 다음 사람에게 순서대로 제안한다.참가자는 자신이 선호하는 사람의 제안을 이미 보유하고 있는 경우 제안을 거부할 것이다.참가자는 또한 나중에 자신이 선호하는 제안을 받으면 이전에 수락한 제안을 거절할 것이다.이 경우, 거부된 참가자는 자신의 목록에 있는 다음 사람에게 제안하여 제안이 다시 받아들여질 때까지 계속한다.어떤 참가자가 결국 다른 모든 참가자에 의해 거절당한다면, 이것은 안정된 매칭은 불가능함을 나타낸다.그렇지 않으면, 1단계는 각 개인이 다른 사람 중 한 명으로부터 제안을 받는 것으로 종료될 것이다.

q와 p라는 두 명의 참가자를 고려하라.q가 p로부터 제안서를 들고 있다면, 우리는 q의 목록에서 모든 참가자를 p 뒤에 x, 그리고 대칭적으로, q의 목록에서 q를 제거하여 q가 p의 리스트에서 첫 번째가 되도록 하고 p는 q와 어떤 x도 어떤 안정적인 매칭에서도 파트너가 될 수 없기 때문에 q의 리스트에서 q를 제거한다.결과적으로 함께 줄어든 선호 리스트 집합을 1단계 표라고 한다.이 표에서 축소된 목록이 비어 있으면 안정적인 일치가 없다.그렇지 않으면 1단계 테이블은 안정적인 테이블이다.안정적인 테이블은 정의에 따라 하나 이상의 목록에서 구성원을 제거한 후 원래 테이블에서 기본 설정 리스트의 집합이며, 다음 세 가지 조건이 충족된다(여기서 축소된 테이블은 안정화된 테이블의 목록을 의미한다).

(i) p는 q가 p의 마지막인 경우에만 q의 축소 목록에 첫 번째 있다.
(ii) ii) q가 p의 경우에 해당하지 않는 경우에만 p가 q의 축소 목록에 없으며, q가 목록에서 마지막 사람을 p보다 선호하거나 p가 q는 q의 축소 목록에 포함되지 않는다.
(iii) 축소된 목록이 비어 있지 않음

안정적인 표에는 몇 가지 중요한 특성이 있으며, 이러한 특성이 절차의 나머지 부분을 정당화하는 데 사용된다.

  1. 모든 안정된 테이블은 1단계 테이블의 하위 테이블이어야 하며, 하위 테이블은 하위 테이블의 선호 목록이 서로 다른 개인 목록에서 제거된 수퍼 테이블의 선호 리스트인 테이블이다.
  2. 모든 안정된 테이블에서, 모든 축소된 목록에 정확히 한 명의 개인이 포함되어 있는 경우, 각 개인을 목록에 있는 한 명의 개인과 짝을 지어 안정적인 일치를 제공한다.
  3. 안정적인 룸메이트 문제 인스턴스가 안정적인 매칭을 가지고 있다면, 안정된 매칭이 어떤 테이블에도 포함되어 있다.
  4. 안정 테이블의 모든 안정적 하위 테이블, 특히 2와 같이 안정적 일치를 지정하는 안정적 하위 테이블은 안정 테이블의 일련의 회전 제거로 얻을 수 있다.

이러한 회전 제거는 어빙 알고리즘의 2단계를 구성한다.

2까지, 1단계 표의 축소된 각 목록에 정확히 한 명의 개인을 포함하면, 일치하는 개인을 제공한다.

그렇지 않으면 알고리즘이 2단계로 들어간다.안정적인 표 T에서의 회전은 x가i 구별되는 순서(x0, y0), (x1, y1), ..., (xk-1k-1, y)로 정의되며, y는i x의i 축소 리스트(또는 x는i y의i 축소 리스트에서 마지막), y는i+1 x의i 축소 리스트에서 두 번째로, i = 0, ..., k-1의 경우, 지수를 모둘로 한다.최소 두 명의 개인을 포함하는 축소 리스트가 있는 안정된 테이블에서는 그러한 회전이 항상 존재한다는 것을 따른다.그러한 p0 그들의 줄어든 목록에서 적어도 두 사람을 시작하게 되며, 재귀적으로까지 이 순서를 회전 발견된다 일부 pj, 되풀이되는 것을의 리스트와 pi+1은 qi+1의 마지막에, 두번째:쌍(pj, qj)의 처음 발생하고 월에서 시작점의 시퀀스 qi+1 이것을 정의합니다.e쌍기 전에최후의 일p까지의j p의i 순서를 회전의 꼬리라고 한다.이 검색이 일어나는 안정적인 테이블이라는 사실은 각각의 p가i 적어도 두 명의 개인을 목록에 가지고 있다는 것을 보장한다.

회전을 없애기 위해 y는i x를i 거부하여 x가 각 i에i 대해 y를i+1 제안한다.안정적인 테이블 속성(i) 및 (ii)을 복원하기 위해 각 i에 대해 x의i-1 모든 후계자를 y 목록에서i 제거하고 y를i 목록에서 제거한다.이러한 제거 중에 축소된 목록이 비어 있으면 안정적인 일치 항목이 없다.그렇지 않으면 새 테이블은 다시 안정된 테이블로, 각 리스트에는 정확히 한 명의 개인을 포함하고 있기 때문에 이미 일치를 지정하거나, 찾거나 제거하기 위해 다른 회전이 남아 있기 때문에 그 단계가 반복된다.

이제 알고리즘의 2단계를 다음과 같이 요약할 수 있다.

T = 위상 1 테이블; 하는 동안에 (진실의) {     신원을 확인하다 a 회전 r 에 T;     없애다 r 로부터 T;     만일 약간의 리스트를 작성하다 에 T 된다 텅 빈,         돌아오다 무효의; (아니요. 안정적 매칭 통조림 존재하다)     다른 만일 (각각 감소된 리스트를 작성하다 에 T 가지다 사이즈를 맞추다 1)         돌아오다 그 매칭 M = {{x, y}   x 그리고 y 이다 에 관하여 각각 타사의's 목록 에 T}; (이 이다 a 안정적 매칭) }

O(n2) 실행 시간을 달성하려면 i행과 j열의 항목이 ith 목록에서 j번째 개인의 위치인 랭킹 매트릭스(O)가 된다. 이 매트릭스는 O(n2) 시간을 필요로 한다.순위 매트릭스에서는 개인이 한 개인을 다른 개와 선호하는지 여부를 매트릭스 내 순위를 비교함으로써 일정 시간 내에 확인할 수 있다.나아가 선호 리스트에서 요소를 명시적으로 제거하는 대신, 각 개인의 축소 리스트에서 첫 번째, 두 번째, 마지막의 지수를 유지한다.비할 데 없는 첫 번째 개인, 즉 그들의 축소된 리스트에 적어도 두 개가 있는 개인도 유지된다.그 후, 2단계에서는 회전을 찾기 위한 p "트래버드"의i 순서가 리스트에 저장되고, 배열은 표준 깊이 우선 검색 그래프 통과에서와 같이 개인이 방문한 것으로 표시하기 위해 사용된다.회전을 제거한 후, 리스트에 그리고 배열에서 방문한 대로 그것의 꼬리만 계속 저장하고, 꼬리의 마지막 개인에서 다음 회전을 위한 검색을 시작하고, 그렇지 않으면 꼬리가 없을 경우 다음 회전을 위한 검색을 시작한다.이는 꼬리의 반복적인 횡단을 감소시키는데, 이는 주로 회전 제거에 영향을 받지 않기 때문이다.

예

다음은 1, 2, 3, 4, 5, 6명의 참가자가 참여하는 스테이블 룸메이트의 선호도 목록이다.

1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5 : 3 1 2 4 6
6 : 5 1 3 4 2

1단계의 가능한 실행은 다음과 같은 일련의 제안과 거부로 구성되며, 여기서 →는 제안을 나타내고 ×는 거부자를 나타낸다.

1 → 3
2 → 6
3 → 2
4 → 5
5 → 3; 3 × 1
1 → 4
6 → 5; 5 × 6
6 → 1

따라서 1단계는 다음과 같은 감소된 선호도 목록으로 종료된다. (예를 들어 1에 대해 5를 차감: 1: 최소 6을 얻으므로)

1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5 : 3 1 2 4 6
6 : 5 1 3 4 2

2단계에서는 회전 r1 = (1,4), (3,2)가 먼저 식별된다.2는 1의 두 번째, 4는 3의 두 번째 사랑이기 때문이다.r을1 제거하면 다음과 같은 이점을 얻을 수 있다.

1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5 : 3 1 2 4 6
6 : 5 1 3 4 2

다음으로 회전 r2 = (1,2), (2,6), (4,5)가 확인되며 제거 수율은 다음과 같다.

1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5 : 3 1 2 4 6
6 : 5 1 3 4 2

따라서 1과 6이 일치한다.마지막으로 회전 r3 = (2,5), (3,4)가 확인되며, 그 제거는 다음을 제공한다.

1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5 : 3 1 2 4 6
6 : 5 1 3 4 2

따라서 일치하는 {1, 6,}, {2,4}, {3, 5}이(가) 안정적이다.

소프트웨어 패키지의 구현

  • Python: 어빙 알고리즘의 구현은 의 일부로서 이용 가능하다.matching도서관의[2]
  • Java: 불완전한 목록과 함께 룸메이트 문제에서 모든 안정된 일치를 찾기 위한 제약 프로그래밍 모델은 SURTL 면허에 따라 이용할 수 있다.[3][4]
  • R: 동일한 구속조건 프로그래밍 모델을 R의 일부로 사용할 수도 있다.matchingMarkets꾸러미[5][6]
  • API: MatchingTools API는 알고리즘을 위한 무료 응용프로그램 프로그래밍 인터페이스를 제공한다.[7]
  • 웹 응용 프로그램:"Dyad Finder" 웹사이트는 자바스크립트로 작성된 해결사 및 웹사이트의 소스 코드를 포함한 웹 기반의 무료 구현을 제공한다.[8]
  • Matlab: 알고리즘은 에서 구현된다.assignStableRoommates미국 해군 연구소의 무료 추적기 구성요소 라이브러리의 일부인 기능.[9]

참조

  1. ^ Irving, Robert W. (1985), "An efficient algorithm for the "stable roommates" problem", Journal of Algorithms, 6 (4): 577–595, doi:10.1016/0196-6774(85)90033-1
  2. ^ Wilde, H.; Knight, V.; Gillard, J. (2020). "Matching: A Python library for solving matching games". Journal of Open Source Software (48). doi:10.21105/joss.02169.
  3. ^ Prosser, P. (2014). "Stable Roommates and Constraint Programming" (PDF). Lecture Notes in Computer Science, CPAIOR 2014 Edition, Springer International Publishing. 8451: 15–28.
  4. ^ "Constraint encoding for stable roommates problem". Java release.
  5. ^ Klein, T. (2015). "Analysis of Stable Matchings in R: Package matchingMarkets" (PDF). Vignette to R Package MatchingMarkets.
  6. ^ "matchingMarkets: Analysis of Stable Matchings". R Project. 2019-02-04.
  7. ^ "MatchingTools API".
  8. ^ "Dyad Finder". dyad-finder.web.app. Retrieved 2020-05-06.
  9. ^ "Tracker Component Library". Matlab Repository. Retrieved January 5, 2019.

추가 읽기