채널A <하트시그널> 시즌3가 내년 초 방영될 예정입니다. <하트시그널>은 청춘남녀들이 한 달 동안 시그널하우스에서 함께 생활하며 소위 '썸타는' 모습을 그려낸 리얼리티 프로그램입니다. 실감나는 멜로를 보여주며 시청자들을 설레게 했는데요.

과연 시즌3의 입주자들은 모두 제 짝을 찾고 행복해질 수 있을까요?

 

그런데 수학자들은 이미 하트시그널 상황에서 모두가 짝을 만날 방법을 알고 있다고 합니다.

 

모두 바람나지 않는 방법?!

 

2012년 노벨 경제학상 수상자인 로이드 섀플리(Lloyd Shapley)와 미국 수학자이자 경제학자인 데이비드 게일(David Gale)은 1962년 안정적인 결혼(The Stable Marriage)라는 알고리즘을 고안했는데요.

 

<The American Mathematical Monthly>에 게재된 논문을 통해 같은 수의 남녀가 모두 바람나지 않도록 짝을 맺는 방법을 제시합니다.

단, 게일-섀플리 알고리즘에서 행복은 보장하지 않는다는 점은 참고하셔야 합니다. 맺어진 커플이 바람나지 않는 안정성은 보장된다고 합니다.

 

<하트시그널> 시즌2에 나왔던 출연진을 토대로 게일-섀플리 알고리즘을 설명해드리겠습니다.

 

방송 내용을 바탕으로 남녀 출연진의 선호도를 정해봤습니다. 현재, 남자들이 선호하는 여성 출연자 순위는 다음과 같습니다.

여자 출연진은 각각 누구에게 호감이 갔을까요?

1라운드 결과

 

1라운드에서 남자들은 각자 선호도가 가장 높은 여성에게 구애합니다. 김도균과 김현우는 임현주를 향해 화살을 쐈습니다. 이규빈은 송다은에게, 정재호는 오영주에게 대시합니다. 

 

남성 2명 이상으로부터 대시받은 여자는 그 중 1명을 고릅니다. 한 명에게 구애를 받았다면 그 남자와 짝이 된다고 가정합니다.

 

만약 누구에게도 구애받지 못하면? 해당 라운드에서는 짝을 맺지 못합니다.

임현주의 선호 순위상 김현우가 김도균보다 높습니다. 따라서 임현주는 김현우를 선택합니다.

지금까지 나온 조합은 다음과 같습니다. 아직 1잠정적 상태입니다. 완벽히 커플이된 건 아닙니다.

 

2라운드, 변화의 시작

 

1라운드에서 짝을 못 만난 남성. 이제 자신을 거절한 적 없는 여자 중 가장 선호하는 여성에게 대시합니다.

 

1라운드에서 짝을 찾지 못한 남자는 김도균 뿐입니다. 김도균은 선호도 2위인 오영주에게 다가갑니다.

마침 오영주는 현재 짝인 정재호보다 김도균을 더 선호합니다. 선호도 1위였죠. 오영주는 정재호를 버리고 김도균과 커플을 맺습니다. 그럼 다음과 같은 조합이 나오죠?

 

정재호는 유일하게 짝 없는 외기러기 신세가 됐습니다. 이번 라운드에서 정재호는 선호도 2순위였던 송다은에게 대시합니다. 

정재호는 송다은의 명단에서 이규빈보다 순위가 높습니다. 이에 송다은은 이규빈을 차고 정재호의 구애를 받아들입니다. 현재 상황은 다음과 같습니다. 

 

이규빈이 홀로 남았습니다. 그는 송다은에게 다시 접근해보지만 그녀는 현재의 짝 정재호와 꿀이 떨어집니다.

 

3라운드 '해피앤딩'

 

다음 라운드에서 이규빈은 큰맘을 먹고 오영주에게 다가갑니다. 하지만 그녀도 현재의 짝 김도균과 깨가 쏟아집니다.

 

절박해진 이규빈은 할 수 없이 선호도 4순위였던 김장미에게 고백합니다. 선택 받지 못하고 있던 김장미는 너무 오래 혼자 있었던 터라 이규빈의 대시를 흔쾌히 받아들입니다.

게일-섀플리 알고리즘, 간단하죠? 이 알고리즘은 반복 횟수도 정해져 있는데요. 위의 예시에서 나오듯, 남자들이 구애하고 여자들이 구애받는 라운드를 반복하다가 모든 남자가 짝을 찾으면 종료됩니다. 그 결과 최종 커플은 다음과 같이 맺어집니다. 

 

 

한 마디로 정리하면?

 

이 알고리즘은 한 마디로 '선호 순위에 따라 순차적으로 제 짝을 찾아간다'라고 정리할 수 있겠습니다.

 

이들은 모두 최소한 당분간은 이 관계를 안정적으로 지속할 가능성이 높습니다. 임현주-김현우 커플은 서로가 각자의 선호도에서 1순위였기 때문에 천생연분이라고 할 수 있습니다.

 

오영주-김도균도 서로에 대한 호감도가 꽤 높을 것으로 추측됩니다. 이는 송다은-정재호 커플도 마찬가진데요. 이 알고리즘에서 남자는 아직 자신을 거절한 적 없는 여자 중, 가장 선호하는 여자에게 구애합니다.

 

이 과정의 끝에서 짝 없이 남는 사람이 있을 순 없습니다. 따라서 무조건 짝을 찾아야 하는 알고리즘 상황에서 '김장미-이규빈'도 커플로 성사되며, 이 조합 또한 꽤 안정적으로 유지될 가능성이 높습니다.  

 

게일-섀플리 알고리즘, 현실에선?

 

애초에 게일-섀플리 알고리즘에는 끝이 있습니다. 최악의 경우 모든 남자가 모든 여자에게 한 차례 이상 구애하는 상황이 생길지도 모릅니다.

 

이때도 오래 걸려서 그렇지 결국 끝은 납니다. 따라서 이 알고리즘 안에서는 모두가 애인을 얻고 조합은 안정성을 띱니다.

 

여자가 대시하는 경우라면?

 

만약 여자들이 각자의 선호도에 따라 남자를 선택하는 방식이라면 어떻게 될까요?

 

아마도 똑같은 결과가 나올 겁니다. 왜냐하면 이 사례에서는 서로가 서로의  1지망이었던 천생연분 커플이 딱 1쌍이기 때문입니다.

 

물론 현실에서는 다를 수 있습니다. 만약 천생연분이 여러 쌍이 있다면 그 경우 여자가 선택하면 남자가 선택할 때와 다른 결과가 나올 수도 있다고 합니다. 

게일-섀플리 알고리즘이 남녀 간의 짝짓기를 위한 만능열쇠는 아닙니다. '어장관리'를 하거나 막판에 차라리 혼자 남는 편을 선택하는 등 변수가 많기 때문인데요.

 

그럼에도 게일-섀플리 알고리즘은 실생활에서 다양하게 활용됩니다. 가령, 의대 졸업생들이 병원에 인턴으로 배정할 때가 있는데요. 지원자가 가고 싶은 병원의 순위를 매기고 병원은 원하는 인턴의 순위를 매깁니다. 이 알고리즘을 이용해 컴퓨터 배정 프로그램을 돌릴 수 있습니다. 

 

<하트시그널> 시즌3를 보기 전 알아본 중매쟁이 이론, 어떠셨나요? 이 내용은 책 <N분의 1의 함정: 합리적이고 전략적인 게임이론의 모든 것>에 나온 내용을 각색한 겁니다.

이 책에는 영화 <뷰티풀 마인드(A Beautiful Mind, 2001)>의 주인공, 천재 수학자인 존 내시가 고안해낸 '내시 균형'이 어떻게 탄생했는지, 왜 백 마리쯤 되는 버펄로 떼는 한 마리의 암사자의 등장에도 꽁지 빠지게 달아나는 건지, 그 유명한 죄수의 딜레마와 치킨 게임이 현실에서 어떻게 적용되는지 등에 관한 이야기가 담겨 있습니다.

 

협상의 달인이 되고 싶으신가요? 이 책을 따라가다 보면 자기도 모르게 '게임이론의 기본기'를 탄탄히 다지게 될 겁니다. 

 

---

##참고자료##

 

• 반니, <N분의 1의 함정: 합리적이고 전략적인 게임이론의 모든 것>, 2017
• Gale, David, and Lloyd S. Shapley. "College admissions and the stability of marriage." The American Mathematical Monthly 69.1 (1962): 9-15.