노벨상의 매칭 알고리즘, 게일-섀플리(Gale-Shapley) 알고리즘

게일 섀플리 알고리즘(Gale-Shapley)은 대표적인 매칭 알고리즘으로 일반적인 추천 알고리즘과는 차이가 있다. 우리가 흔히 추천 시스템에 추천 알고리즘을 구현할 때는 1:1이라는 개념을 생각하지 못한다. 넷플릭스(Netflix)의 영화 컨텐츠 추천이라든지, 쇼핑몰에서 연관된 상품을 추천한다던지 혹은 요즘 유행 댓글처럼 "유튜브 알고리즘이 나를 여기로 인도했다"라는 말과 같은 유튜브 알고리즘이라든지 이런것들은 컨텐츠를 추천하는 일대다 추천 알고리즘이다.

 

기본적으로 추천 시스템은 1:N이라는 개념을 가지기에 배분이라는 개념이 사라진다. 그렇기에 특정 영상들이 쏠리게 되어 있고, 인기가 많은 컨텐츠에 더 많은 사람들이 몰리게 된다. 하지만 매칭 알고리즘 즉, 여기서 설명하는 게일-섀플리 알고리즘은 남녀가 어떻게 만나야 최적의 짝이 될 수 있는가에 대해서 비롯된 알고리즘이기에 단순히 일대다의 개념이 사라지고, 최적의 매칭을 생각해야 하는 것이다.

 

 

---

 

게일-섀플리 알고리즘의 활용 사례

 

•  
• 의대생과 병원을 이어주는 레지던트 지원 프로그램
• 뉴욕 공립학교 배정 프로그램
• 장기기증 매칭 시스템
• 데이팅 앱 매칭

 

이와 같이 게일-섀플리 알고리즘은 현재 다양한 1:1의 매칭 문제에 최적의 해결 값을 제공한다.

 

 

게일-섀플리 알고리즘의 개념

 

사실 우리는 게일-섀플리 알고리즘을 매우 흔하게 접하고 있고, 알고 있다. 대표적으로 X맨, 천생연분 그리고 최근에 런닝맨으로 이어지는 예능 프로그램에서 자주 하고 있는 짝을 만들때 사용하는 방식이다(물론 자세히 보면 약간 다르지만)

 

게일-섀플리 알고리즘과 유사한 방식을 사용하여 짝을 만드는 장면

 

게일-섀플리 알고리즘은 다음과 같은 방식으로 매칭을 시도한다.

 

남자는 홍길동, 고길동, 둘리라는 남자가 있고, 여자는 또치, 하니, 나애리가 있다고 가정을 해보자 그리고 각각 마음에 드는 남성들과 여성들이 다음과 같다고 가정을 한다.

 

남성

홍길동 : 하니, 또치, 나애리

고길동 : 하니, 또치, 나애리

둘리 : 또치, 하니, 나애리

 

여성

하니 : 둘리, 홍길동, 고길동

또치 : 고길동, 둘리, 홍길동

나애리 : 홍길동, 고길동, 둘리

 

남성들이 1차적으로 선택한 여성을 짝을 선택한다.

 

하니 : 홍길동, 고길동

또치 : 둘리

나애리 : 없음

 

남성들의 선택이 마무리 되었다면 여성은 선택받은 남자들 중 가장 마음에 드는 짝을 선택한다. 

 

하니 : 홍길동

또치 : 둘리

나애리 : 없음

고길동 : 없음

 

1라운드가 끝나면 위와 같은 결과가 나온다. 2커플이 되었지만 한커플이 만들어지지 않았으니 사실상 완벽히 된 것이 아니다. 이제 2 Round를 돌리면서 선택을 받지 못한 고길동이 2번째 선택인 또치를 선택한다. 또치는 이미 둘리가 있지만, 또치의 마음속에 있던 사람은 둘리가 아니라 고길동이었기 때문에 둘리가 다시 다음 라운드에서 선택을 해야 되는 대상이 된다.

 

하니 : 홍길동

또치 : 고길동

나애리 : 없음

둘리 : 없음

 

둘리는 차선인 하니를 선택하게 된다. 이때 나애리 역시 홍길동보다 둘리를 더 좋아했기 때문에 홍길동이 다시 선택을 해야 되는 상황에 놓이게 되고, 커플은 다음과 같아진다.

 

하니 : 둘리

또치 : 고길동

나애리 : 없음

홍길동 : 없음

 

홍길동은 다음 선택지인 또치를 선택하겠지만, 또치는 이미 가장 좋아하는 사람이 고길동이기에 홍길동의 선택을 무시하게 되며, 마지막 선택인 나애리를 선택하며 커플 매칭은 끝이 나게 된다.

 

최종커플

하니 : 둘리

또치 : 고길동

나애리 : 홍길동

 

자 그럼 우리는 이렇게 선택을 하는게 최선일까? 라는 생각을 해볼 수 있다. 공리적인 접근으로 볼 때에는 다른 접근방법도 분명 있어보인다. 왜냐하면 홍길동 역시도 1순위로 하니를 좋아했었기 때문에 홍길동과 하니를 매칭해줘도 크게 문제가 없어 보이는 것이다.

 

하지만, 이 매칭 시스템은 단순히 커플을 매칭하는 것에서 끝나지 않고, 이후의 상황까지 고려를 한다. 하니와 둘리 입장에서 하니는 이미 가장 마음에 드는 남성을 선택했으니 다른 남성과 바람이 날리가 없고, 둘리에게 2순위이지만 이미 또치에게 버림을 받았기 때문에 하니와 둘리는 최적화가 된 커플이다.

 

즉, 커플을 선택하는 상황으로만 보면, 비슷해보이지만 커플 이후의 만족도까지 고려하면 이렇게 라운드를 여러번 실행하는 방식이 가장 이상적이라는 결론이다.

 

 

게일-섀플리 알고리즘의 위대함

 

어찌보면 별거 아닌 것 같은 이 짝짓기 알고리즘은 후에 로스 게일-섀플리 알고리즘은 앨빈 로스(Alvin Roth)라는 인물이 현실 문제에 적용하여 많은 문제들을 풀었으며, 이 성과로 2012년 노벨 경제학상을 받게되는 쾌거를 이루게 된다.

 

https://www.rand.org/blog/2012/10/rands-lloyd-shapley-wins-nobel-prize-in-economics.html