노벨상 받은 기적의 수학, 돈 대신 알고리즘이 생명을 구했다.

노벨 경제학상 수상자 앨빈 로스는 돈이 오갈 수 없는 장기 기증 시장에 수학적 매칭 알고리즘을 도입해 수많은 생명을 살렸습니다.
특히 아무 대가 없이 신장을 내어주는 '이타적 기증자' 한 명이 시스템에 합류할 때, 최대 30쌍에 달하는 연쇄적인 교환 수술이 가능해진다는 사실을 증명했습니다.
이 매칭 원리는 부부 의사의 레지던트 동시 배정 문제를 해결하는 데 쓰였으며, 향후 한국의 학교 배정 등 일상적인 분배 문제에도 유용하게 적용될 수 있습니다.

우리가 생각하는 것과는 다르게, 세상에는 돈으로 살 수 없는, 혹은 사서는 안 되는 것들이 있습니다. 대표적인 것이 바로 '장기 기증'과 '학교 배정'입니다. 돈으로 해결되지 않는 시장에서 우리는 제한된 자원을 어떻게 효율적으로 나누어야 할까요? 노벨 경제학상 수상자인 앨빈 로스(Alvin Roth)는 수학적인 '매칭 알고리즘'을 통해 이 복잡한 문제를 해결하고 수천 명의 생명을 살려냈습니다. 가격표가 없는 시장에서 최적의 짝을 찾아내는 매칭의 경제학이 어떻게 세상을 바꾸고 있는지 살펴보겠습니다.

돈으로 풀 것인가, 알고리즘으로 풀 것인가?

가족이 아파서 내 신장을 떼어주고 싶어도 혈액형이나 조직형이 맞지 않아 좌절하는 경우가 많습니다. 이런 안타까운 상황을 어떻게 해결해야 할까요? 여기서 두 명의 노벨 경제학상 수상자의 의견이 극명하게 갈립니다.

먼저 게리 베커(Gary Becker)는 "합법적인 매매를 허용하자"고 주장했습니다. 현금 거래를 양성화하면 수요와 공급에 의해 가장 빠르게 문제가 해결된다는 논리였죠. 실제로 이란은 전 세계에서 유일하게 신장 거래를 허용하는 국가입니다. 하지만 현실은 녹록지 않았습니다. 돈이 오가기 시작하자, 결국 기증자는 모두 경제적으로 궁핍한 사람들로 채워지는 윤리적 문제가 발생했습니다. 시장의 제약으로서 '도덕적 혐오'가 작동한 것입니다.

반면 앨빈 로스는 "돈이 아니라 교환 시스템을 만들자"고 제안합니다. 내가 남편에게 신장을 줄 수 없다면, 나와 조건이 맞는 다른 부부와 '맞교환'을 하자는 아이디어입니다. 1980년대부터 의사들이 수작업으로 두 커플을 연결하던 것을, 로스는 방대한 유전자 정보와 매칭 알고리즘을 시스템에 등록해 세 커플, 네 커플이 서로 신장을 주고받을 수 있는 거대한 교환의 장으로 발전시켰습니다.

신장 교환 매칭 알고리즘을 설명하는 프레젠테이션 슬라이드와 토크 장면

수술실의 한계와 '이타적 기증자'의 마법

그런데 여기서 중요한 건, 이 매칭 시스템에도 치명적인 한계가 있었다는 점입니다. 네 커플이 서로 신장을 교환하기로 했다고 가정해 볼까요? 만약 누군가 내 가족이 먼저 신장을 받은 직후 마음을 바꿔 "나는 기증하지 않겠다"고 도망가 버리면 이를 법적으로 강제할 방법이 없습니다.

이런 '먹튀'를 막기 위해 병원들은 네 커플의 적출과 이식 수술을 동시에 진행해야만 했습니다. 수술실만 8개가 필요하고 엄청난 수의 의료진이 동원되어야 하니, 대학병원의 시스템이 마비될 지경이었죠. 알고리즘은 완벽했지만 현실의 벽에 부딪힌 겁니다.

책상에 책을 두고 대담을 진행하는 김나영 작가의 인터뷰 장면

이 꽉 막힌 상황을 뚫어준 것은 경제학 공식이 아니라, 아무런 조건 없이 자신의 신장을 내어주는 단 한 명의 '이타적 기증자'였습니다.

편의점 가서 담배 살 때를 생각해 볼까요? 돈부터 줘야 담배를 줄지, 담배부터 줘야 돈을 줄지 서로 눈치만 보고 있으면 밤새도록 거래를 할 수 없습니다. 누군가 먼저 돈이든 담배든 내놓아야 거래가 시작되잖아요? 신장 매칭도 마찬가지입니다. 순수한 마음으로 신장을 내어주는 사람이 등장하자, 동시에 수술을 진행할 필요 없이 연쇄적인 기증 릴레이가 가능해졌습니다. 이타적 기증자 한 명이 시작한 나비효과로 무려 최대 30커플이 줄지어 신장을 교환하는 기적이 일어났습니다.

붕괴된 레지던트 시장을 구한 '콤보 메뉴'

이러한 매칭 알고리즘은 생명을 구하는 데만 쓰인 것이 아닙니다. 1940년대 미국의 의대 레지던트 채용 시장은 그야말로 아수라장이었습니다. 병원들이 우수한 학생을 입도선매하기 위해 의대 2~3학년에게까지 미리 오퍼를 날렸고, 학생들은 정보가 부족한 상태에서 원치 않는 과를 선택해야 했습니다.

이 혼란을 잠재운 것이 1950년대 도입된 중앙 집중형 매칭 시스템(NRMP)입니다. 학생과 병원이 각각 선호도 순위를 제출하면 중앙에서 이를 매칭해 주는 방식이었죠. 훗날 앨빈 로스는 이 시스템이 수학적으로 완벽한 안정적 알고리즘이라는 것을 증명해 냅니다.

부부 의사의 레지던트 지원 방식을 설명하는 프레젠테이션 슬라이드와 대담 장면

재밌는 건 1990년대 들어 이 시스템이 다시 망가지기 시작했다는 겁니다. 의대생 중 부부 의사가 많아지면서, 두 사람이 같은 도시에 있는 병원에 배정받아야 하는 복잡한 조건이 추가되었기 때문입니다. 로스는 이 문제를 어떻게 해결했을까요? 부부가 각자 지원하는 대신, "A병원이 남편을 뽑으려면 아내도 B병원에 뽑혀야 한다"는 식의 '콤보 메뉴(세트 지원)'를 만들었습니다. 복잡한 선호도의 충돌 속에서도 시스템은 최적의 해를 찾아냈고, 제도는 다시 안정을 찾았습니다.

안정적인 매칭 시스템, 우리 일상으로 들어온다면

결국 여기서 핵심이 뭐냐면, 알고리즘이 얼마나 '안정적(Stable)'이냐에 따라 제도의 성패가 갈린다는 사실입니다. 안정적인 매칭이란, 배정이 끝난 후 그 어떤 두 사람도 "우리 둘이 짝을 바꾸는 게 지금보다 낫겠다"고 생각하지 않는 상태를 말합니다. 수학적으로 불안정하게 설계된 배정 시스템은 현실에서 반드시 붕괴하고 맙니다.

이 원리는 우리나라의 입시나 학교 배정 제도에도 시사하는 바가 큽니다. 현재 우리는 고등학교 배정을 운에 맡기는 '추첨제'에 의존하고 있습니다. 하지만 학생들의 선호도와 학교의 특성을 반영한 매칭 알고리즘을 도입한다면 어떨까요? 쌍둥이를 같은 학교에 배정하는 문제부터, 서로 원치 않는 학교에 배정된 학생들의 불만을 최소화하는 것까지 훨씬 더 효율적인 분배가 가능해질 것입니다. 돈이 매개되지 않는 시장이라 할지라도, 정교한 수학적 룰이 있다면 우리는 충분히 더 나은 최적해를 찾아낼 수 있습니다.

FAQ

신장 기증에 매칭 알고리즘이 필요한 이유는 무엇인가요?

가족에게 신장을 기증하고 싶어도 혈액형이나 조직형이 맞지 않아 불가능한 경우가 많습니다. 매칭 알고리즘은 이런 부부들의 데이터를 모아 서로 교차로 신장을 주고받을 수 있도록 최적의 짝을 찾아주는 역할을 합니다.

이타적 기증자 한 명이 왜 그렇게 중요한가요?

서로 교환을 약속한 후 한쪽이 수술을 거부하는 상황을 막기 위해 과거에는 모든 커플이 동시에 수술을 받아야만 했습니다. 하지만 조건 없이 신장을 주는 이타적 기증자가 한 명 합류하면 동시에 수술할 필요 없이 순차적으로 기증을 이어갈 수 있어, 한 번에 수십 커플이 생명을 구하는 연쇄 효과가 발생합니다.

부부 의사의 레지던트 배정 문제는 어떻게 해결했나요?

부부 의사가 서로 다른 도시로 배정되는 것을 막기 위해, 두 사람을 하나의 '세트(콤보 메뉴)'로 묶어서 지원하게 만들었습니다. 남편과 아내가 원하는 도시의 병원 조합을 함께 제출하면, 두 사람 모두 합격할 수 있는 경우에만 매칭을 성사시키는 방식으로 알고리즘을 수정했습니다.