The prize in economic sciences 2012

The prize in economic sciences 2012

현실과 시장경제에서 자원들을 어떻게 잘 매칭할 수 있을까? 예를 들어 이런 경우가 있다. 학생들이 다음 교육기관에 어떻게 진학할 것인가? 학교마다 정원이 정해져 있으므로 모든 학생이 원하는 학교 갈 수는 없을 것이다. 기증받은 장기를 어떤 환자에게 이식할 것인가? 장기의 수가 부족하니 가장 효율적인 방법을 찾아야 할 것이다. 2012년 노벨 경제학상을 받은 Alvin Roth와 Lloyd Shapley가 해결했다.

Matching Theory

Gale과 Shapley는 matching을 분석하기 위해 쉽게 그릴 수 있는 예시인 결혼을 생각했다. 여기서 stable matching은 어떤 커플도 깨지고 싶지 않아하는 상태를 말할 수 있다. 이 예시는 이렇게 설정된다. 1. 남자나 여자가 프로포즈를 하는데 가장 선호하는 사람에게 한다. 2. 가장 선호하는 사람에게 프로포즈를 받으면 수락하고 나머지는 거절한다. 3. 거절당하면 다음으로 선호하는 사람에게 프로포즈를 한다. 모두가 짝을 만날 때까지 반복한다. Gale과 Shapley는 이 알고리즘이 언제나 stable matching을 만들어 낸다는 것을 보였다.

Evidence

미국 의대생들이 졸업 전에 병원과 어떻게 match될 것인가에 대한 문제이다. 학생들을 놓치지 않기 위해 offer시기가 점점 빨라져 학생들이 충분히 자격을 갖추기 전에 계약이 진행되었고, 학생들은 다음에 어떤 기회가 있는지 알지도 못한 상태로 결정을 내려야 했다. Gale-Shapley Algorithm과 밀접한 NRMP가 해결했다.

Matching students and high-schools

Gale-Shapley 알고리즘은 상급학교 진학 등 다른 응용 문제에도 유용하다. 가장 가고 싶은 학교 5개를 정하고 같은 알고리즘으로 최선의 선택을 만들어낼 수 있다. 오늘날에도 많은 지역들이 Gale-Shapley 알고리즘의 다양한 변형을 이용하고 있다.

Matching kidneys and patients

지금까지는 matching의 주체 양 쪽 모두가 의지를 갖고 있는 경우를 보았다. 장기이식의 경우는 조금 다른데, 한 쪽은 완전히 Passive하다. Top trading cycle 이라고 하는 이 알고리즘은 initial allocation과 subsequent swapping이 핵심이다.