게일-섀플리 알고리즘(Gale-Shapley algorithm)

Gale과 Shapley는 1962년에 "College Admissions and the Stability of Marriage"라는 논문을 발표했습니다. 이 논문은 이후로 "Stable Marriage Problem"이라고 불리는 중요한 이론적 문제를 소개했습니다.

이 논문에서 Gale과 Shapley는 결혼 문제를 통해 안정적인 짝 매칭 알고리즘을 제안했습니다. 이 알고리즘은 남성 그룹과 여성 그룹 간의 각각의 기호 순위를 바탕으로 최적의 짝을 찾는 데 사용됩니다. 이 알고리즘은 모든 사람이 최선의 선택을 하기 때문에 안정성을 보장합니다. 이러한 안정성은 어떤 사람들이 더 나은 짝을 찾으려고 할 때에도 계속 유지됩니다.

이 논문은 컴퓨터 과학 및 경제학 분야에서 중요한 역할을 했으며, 이후 다양한 분야에서 응용되어 왔습니다. 예를 들어, 대학 입학 프로세스, 작업 배정 문제 등 다양한 영역에서 이론적 기초로 사용되었습니다. 이 알고리즘은 또한 실제 세계에서도 적용되어 왔으며, 예를 들어 의료 학제간 협력, 기부자와 수혜자의 매칭 등에도 사용됩니다.

즉 논문의 일부 중 서로 선호 구조에 따른 매칭을 해주는 알고리즘이다.

그럼 논문에 나온 방식대로 남자 3, 여자 3의 서로 매치을 해보겠습니다.

여기서 알고리즘을 세가지 순서대로 계속 반복해 보겠습니다.

1. 각 남성은 자신이 좋아하는 여성에게 프로포즈합니다. 각 여성은 받은 프로포즈 중에서 가장 선호하는 남성을 선택합니다.
2. 만약 여성이 받은 프로포즈 중에서 새로운 남성을 선택한다면, 그 전에 선택된 남성은 거절됩니다.
3. 이 프로세스는 더 이상 변화가 없을 때까지 반복됩니다. 즉, 모든 여성이 이제 더 나은 프로포즈를 받지 않을 때까지 반복됩니다.

예 )  1번남성이 3번여성을 제일 선호하고 그다음 1번여성 마지막으로 2번 여성  [1번 남자선호도 3여성>1여성>2여성]

         2번남성이 1번여성을 제일 선호하고 그다음 3번여성 마지막으로 2번 여성  [2번 남자선호도 1여성>3여성>2여성]

         3번남성이 3번여성을 제일 선호하고 그다음 2번여성 마지막으로 1번 여성  [3번 남자선호도 3여성>2여성>1여성]

여성은

                

         1번여성이 2번남성을 제일 선호하고 그다음 3번남성 마지막으로 1번 남성  [1번 여성선호도 2남성>3남성>1남성]

          2번여성이 1번남성을 제일 선호하고 그다음 3번남성 마지막으로 2번 남성  [2번 여성선호도 1남성>3남성>2남성]

         3번여성이 3번남성을 제일 선호하고 그다음 1번남성 마지막으로 2번 남성  [3번 여성선호도 3남성>1남성>2남성]

처음 시작은

결국

 

남성 1은 여성 2,  남성2은 여성1, 남성3은 여성3 이 매칭이 된다.