게일과 섀플리의 1962년 알고리즘은 매칭 시장을 정직하게 만들었다

데이비드 게일과 로이드 섀플리는 1962년 《미국 수학 월간》에 '대학 입학과 결혼의 안정성'을 발표했다. 그들은 결혼이나 대학 입학과 같은 양방향 시장에서, 어떤 두 당사자도 서로를 더 선호하지 않게 되는 배정인 안정 매칭이 항상 존재하는지를 물었다.

그들의 답은 건설적이었다. 한쪽이 제안하고 다른 쪽이 잠정적 제안을 보유하는 지연 수락 알고리즘은 항상 안정 매칭에서 종료된다. 같은 절차가 제안하는 쪽에 가능한 최선의 안정적 결과를 주며, 이것이 제안자에게 진실된 순위 매기기가 우월 전략인 이유다.

50년 후, 스웨덴 왕립 과학 아카데미는 섀플리와 앨빈 로스에게 '안정적 배분의 이론과 시장 설계의 실천'을 이유로 2012년 경제학상을 수여했다. 로스는 안정성이 어떤 실제 시장이 살아남는지를 설명함을 보였고, 이 알고리즘 위에 레지던시 매칭, 학교 선택, 신장 교환을 재구축했다.

지연 수락은 모두에게 안정적인 매칭을 찾는다

존재성과 알고리즘이 결합되어 안정성이 추상적인 것이 아니라 사용 가능한 것이 되었다.

진실된 선호 목록이 제안자의 우월 전략이 되었다.

설계자들에게 하나의 관점을 주었다. 안정적인 시장은 살아남고, 불안정한 시장은 붕괴한다.

의학, 교육, 장기 교환에서 실질적인 재설계를 가능하게 했다.

시장을 구축하기 전에, 매칭 메커니즘이 안정적이고 전략-증명적인지 확인하라. 허위 보고가 이득이 된다면, 시장은 조작으로 가득 찬다. 정직을 최적으로 만드는 알고리즘이 바로 시장 설계다.

이 알고리즘은 미국 레지던시 매칭 재설계, 보스턴과 뉴욕의 학교 선택, 신장 교환 체인의 엔진이 되었다. 이들은 모두 노벨상 인용문에 언급되었다. 게일-섀플리는 이제 시장 설계, 운영 연구, 컴퓨터 과학에서 표준 용어다.