Stable Matching Problem

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Stable Matching Problem

Stable matching problem은 두 개의 집합에서 서로의 선호도가 있다고 가정했을 때, 최선의 짝을 짓도록하는 문제이다. 다르게 말하면, 선호도에 근거한 더 나은 짝이 없는 상태를 만드는 것이다.

 

Unstable pair : 짝이 지어진 상태에서 X-Y는 서로 짝이 아닌데 X는 현재 상태보다 Y를 더 선호하고, Y는 X를 더 선호하는 짝을 말한다. 

 

Stable assignment : 어느 하나도 unstable pair가 없도록 만드는 것이다.

 

Perfect matching : 집합의 모두가 1:1로 matching한 상태

 

Stable matching : Perfect matching이면서 unstable pair가 없는 것

 

 

* Stable roommate problem : 2n element가 있는 하나의 그룹에서 stable matching을 만드는 것

->  이 문제의 경우 stable matching이 존재하지 않을 수 있다.

 

 

Propose-and-Reject Algorithm

(Gale-Shapley Algrithm)

 

 

1. 여자와 짝지어지지 않은 남자가 없을 때까지 while을 반복한다.

2. 그 남자의 선호도 리스트 중에서 propose한적이 없으면서, 제일 높은 선호도의 여자를 택한다.

2.1. 여자가 free일 경우, 약혼상태로 만든다.

2.2. 여자 입장에서 약혼자보다 남자가 선호도가 높을 경우 약혼을 끊고 약혼상태로 만든다.

      (남자는 free상태가 됨)

2.3. 모두 해당되지 않으면 남자는 거절되며, 다음 while문을 돈다.

 

 

Observation

1. 남자의 여자 선호도리스트는 선호도가 낮아지는 방향으로 진행한다.

2. 여자의 남자 선호도리스트는 선호도가 높아지는 방향으로 진행한다.

 

 

Proof of correctness : Termination

이 알고리즘은 적어도 $n^2$ iteration 안에 종료된다.

 

Pf ) 남자 입장에서, 한번 propose한 여자는 다시 propose하지 않고, 선호도가 낮아지는 방향으로 진행하기 때문에 가능한 iteration 수는 남자 수 X 여자 수 = $n^2$이다.

 

 

Proof of correctness : Perfection

모든 남자와 여자는 짝지어진다.

 

Pf ) 귀류법 : 종료 시에, 짝지어지지 않은 남자 Z - 여자 A가 있다 하자.

free상태가 있는 상태에서 종료되기 위해서는 모든 여자한테 propose했을 경우이다. A입장에서는, 짝지어지지 않기 위해서는 어떤 남자도 propose하지 않았을 때이다. 하지만, 위에서 모든 여자한테 propose했으므로 모순이다. (남자는 내림차순으로 propose)

 

 

Proof of correctness : Stability

Stable pair가 없다.

 

Pf ) 귀류법 : A-Z가 unstable pair라 가정하자. A-Z는 unstable pair이므로 각자가 더 선호하는 사람이 존재한다.

 

A : Y > Z, Y : A > B

B : Z > Y, Z : B > A

 

이렇게 가정해도 일반성을 잃지 않는다.

 

GS algorithm에서 짝이 형성되는 과정은 다음 두 case로 나눌 수 있다.

 

Case 1 : Z가 A에게 propose한 적 없을 때

-> GS algorithm에서 Z의 선호도 순으로 propose를 한다. Z는 B를 먼저 propose하기 때문에 A-Z 짝이 형성될 수 없다.

 

Case 2 : Z가 A에게 propose했을 때

A가 Z를 reject하지 않았고 engage한 상태에서 Y의 propose를 받았을 때, Y의 선호도가 더 높기 때문에 A-Z의 engagement가 깨지게 된다. 그렇기 때문에 A-Z 짝이 형성될 수 없다.

 

두 가지 case에 대해 A-Z 짝이 이루어질 수 없으므로, 모순이 생긴다.

 

 

 

Man Optimality

GS algorithm은 남자 입장에서 optimal이다. (valid partner중에서 가장 선호도가 높은 partner와 짝이 됨)

* Valid partner : 여러 개의 가능한 stable matching 중에서의 짝

 

Pf ) GS algorithm이 man optimal하지 않다고 가정하자.

GS algorithm에 의해 정해진 matching을 $S^*$라하자. Y-A가 best valid partner라 하면, Y가 A에 의해 reject되는 일이 발생하게 된다.

그 이유는 A가 다른 남자(Z)가 Y보다 선호도가 높기 때문이다.

A : Z > Y

그리고 짝이 되기 위해서 Z입장에서 A는 첫 번째로 propose한 valid partner이다.   --- (1)

 

한편, Y-A가 짝이된 stable matching $S$가 존재한다. $S$에서 짝은 다음과 같다.

Y-A, Z-B

 

(1)에 의해 Z의 선호도는 다음과 같다.

Z : A > B

그리고 A : Z > Y이므로 $S$에는 unstable pair가 존재한다.

따라서 $S$가 stable matching이라는 가정에 모순이므로 Man-optimal이다.

 

 

Woman Pessimality

GS alorithm은 여자입장에서 worst valid partner를 만난다.

 

Pf ) GS algorithm에 의해 정해진 matching을 $S^*$라하자. $S^*$에서 A-Z가 matching되었고 Z는 A의 worst valid partner가 아니라고 가정하자. 

 

한편, worst valid partner와 matching된 Stable matching $S$가 존재한다.

$S$에서 A-Y, B-Z가 matching되었고 Y가 A의 worst valid partner라 할 수 있다.

A : Z > Y이고, Man optimality으로 인해, Z : A > B이다.

이는 $S$에서 unstable pair가 생기기 때문에 $S$가 stable matching이라는 가정에 모순이다.