[기억할 오늘] 로이드 섀플리(3.12)

'안정적 결혼 알고리즘'의 수학자 로이드 섀플리가 2016년 오늘 별세했다. 연합뉴스

‘안정적 결혼(The Stable Marriage) 알고리즘’이란, 같은 수의 남녀가 결혼한 뒤 다른 이성과 바람이 나서 이혼하지 않을 수 있도록 짝을 짓는 방법을 수학적으로 정리한 방법이자 이론이다. 원리는 간단하다. 남녀 각 3명이 모였고, 각각이 이성에게 느끼는 호감도를 서열화할 수 있다고 가정하자. 첫 라운드에서 남자들이 차례로 가장 마음에 드는 여성에게 청혼해 2쌍의 약혼이 성사됐다고 치자. 2라운드에서 남은 남자는 2순위로 호감을 느낀 여성에게 청혼을 하고, 그 여성이 이미 약혼한 남자보다 청혼한 남자가 더 마음에 들 경우 파혼하게 될 것이다. 도로 혼자가 된 남자가 남은 여성에게 청혼을 한다. 남녀의 수가 몇 명이든 그렇게 반복하다 보면 언젠가는 모든 쌍이 짝을 찾게 되고, 커플들에게 각자 더 선호하는 상대가 있어 유혹을 하더라도 그 상대는 이미 맺어진 상대를 더 선호하기 때문에 유혹에 넘어가지 않는다는 것이다.

UCLA 수학자 로이드 섀플리와 동료 수학자 데이비드 게일(1921~2008)은 1962년 논문을 통해 ‘안정적 결혼 알고리즘’이라고 불리는 저 ‘게일-섀플리 알고리즘’을 발표했다. 그들은 각각 10명 남녀의 선호도가 아무리 얽혀도 선택 라운드를 반복하면 언젠가는 모두 결혼에 이르고, 안정적 결혼생활을 유지하게 된다는 것을 수학적으로 증명했다. 물론 최악의 경우 차라리 혼자 살겠다고 작심한 남녀는 없다는 게 전제다. 알고리즘의 목표는 물론 주관적 정성적(定性的) 행복이 아니라 정량적 관계 안정성, 효율 극대화에 있다.

근 50년 뒤 하버드 대 경제학과 앨빈 로스(1951~)는 ‘게일-섀플리 알고리즘’을 현실에 적용했다. 그는 의대생과 병원을 이어주는 레지던트 지원 프로그램과 뉴욕 공립학교 배정 프로그램, 장기기증 매칭시스템 등을 통해 알고리즘의 실용성을 입증, 2012년 셰플리와 함께 노벨 경제학상을 수상했다.

로이드 섀플리(Lloyd S. Shapley, 1923.6.2~2016.3.12)는 세페이드 변광성 연구로 우리 은하의 크기와 태양계 위치 등을 규명하는 데 기여한 천문학자 할로 섀플리(1885~1972)의 아들로, 하버드와 프린스턴에서 수학을 전공하고, 랜드연구소와 UCLA에서 교수로 재직했다. 그는 랜드연구소에서 만난 컴퓨터 공학자 메리언(Marian 97년 작고)과 안정적 결혼 생활을 영위했다.

최윤필 기자