인턴 쟁탈전을 끝낸 알고리즘
1952년, 미국 병원들은 의대생을 두고 다투기를 멈추고 배정을 하나의 절차에 맡겼다. 10년 뒤 두 수학자가 그 이론을 썼으나, 아직 아무도 둘을 연결 짓지 못했다.
2년 앞서 나가던 제안
1920년대 미국에서 수련 프로그램이 자리 잡으면서, 병원들은 인턴을 확보하려고 치열하게 경쟁했다. 채용 제안은 수련 시작 최대 2년 전에 나갔고, 학생을 제대로 평가할 수 있기 한참 전이었다. 1945년 의과대학들은 정해진 날짜 이전에는 성적 증명서와 추천서를 내주지 않기로 합의했으며, 이로써 선발 시기는 의대 4학년으로 돌아왔다.
경쟁은 이번에는 속도로 옮겨 갔다. 제안에 답할 수 있는 기한이 1945년 열흘에서 1950년에는 열두 시간 미만으로 줄었다. 학생은 다른 병원이 무엇을 내놓을지 모른 채 그 자리에서 수락해야 했다. 1951년 79개 의과대학의 대표들이 전국위원회를 구성해 다른 방식을 요구했다. 1952년 첫 매치가 열렸다. 학생과 병원이 각자 선호 순위를 제출하면 중앙의 절차가 이를 가려냈다.
원리는 한 문장으로 요약된다. 먼저 답한다고 얻을 것이 더는 없다. 선호는 미리 순위가 매겨지고, 자리는 한꺼번에 라운드를 거쳐 배정되며, 마지막까지 어떤 약속도 확정되지 않는다. 속도는 더 이상 이점이 아니게 되고, 제안을 놓칠지 모른다는 두려움도 함께 사라진다.
실천이 이론보다 앞섰다
1962년 데이비드 게일과 로이드 섀플리는 「College Admissions and the Stability of Marriage」를 발표해 유보 수락 절차를 서술하고, 이것이 언제나 안정적인 짝짓기에 이른다는 점을 보였다. 안정적이라 함은 배정된 상대보다 서로를 더 선호하는 학생과 병원이 존재하지 않는다는 뜻이다. 1984년 앨빈 로스는 30년 넘게 쓰여 온 매치의 알고리즘 또한 안정적인 결과를 낳는다는 것을 입증했다. 병원들은 시행착오로 찾아낸 것을, 수학자들이 뒤이어 증명한 셈이다.
로스는 또한 원래 방식에서는 병원이 제안하는 쪽이어서, 병원에 가장 유리한 안정적 결과를 얻고 학생은 불리해진다는 점을 짚었다. 전국 레지던트 매칭 프로그램(NRMP)은 1997년 지원자가 제안하는 방식을 채택해 1998년부터 적용했고, 로스와 섀플리는 2012년 노벨 경제학상(스웨덴 중앙은행 경제학상)을 받았다. 오늘날 학생을 학교나 학과에 배정하는 방식을 둘러싼 논쟁도 같은 물음을 던진다. 누가 제안하며, 가장 좋은 결과는 누구에게 돌아가는가?
과열된 시장은 언제나 저절로 가라앉지는 않는다. 때로는 규칙을 다시 써야 한다.