미국 레지던시 매치, 매년 2만 명의 의사가 1순위를 매기고도 결코 평가받지 못하다

NRMP는 매년 약 2만 명의 신규 의사를 미국 레지던시에 매칭한다. 1990년대까지 지원자들은 병원 제안형 알고리즘이 자신들에게 불리하게 작용한다고 믿었고, 인근의 두 일자리를 필요로 하는 커플들은 1952년 원래 설계가 전제했던 단순한 매칭 모델을 깨뜨렸다.

1995년 NRMP 이사회는 앨빈 로스에게 의뢰했고, 그는 엘리엇 페런슨과 함께 1997년 대체 알고리즘을 설계하여 1998년 매치에 채택했다. 보완성(커플, 연계된 직위) 때문에 표준 이론이 적용될 수 없었으므로, 그들은 변형들을 컴퓨터로 테스트했고 — 안정적 매칭의 집합과 전략적 조작의 여지가 놀랍도록 작다는 것을 발견했다.

그런 다음 그들은 안전한 방향의 선택을 했다: 지원자 측에서 제안하도록 한 것이다. 지원자들은 달성 가능한 최선의 안정적 결과를 얻으며, 알고리즘은 그들에게 전략 증명적이어서 순위 목록을 게임하려는 유인이 사라졌다. 이 작업은 이후 로스의 2012년 경제학 노벨상의 토대가 되었다.

제안하는 주체를 뒤집어라: 지원자 측에서 지연 수락을 실행하라

이론은 시장의 복잡성이 안정성을 깨뜨릴 수 있다고 말했지만, 컴퓨터 실험은 그 피해가 극히 작다는 것을 보여주었다.

지원자 제안형 지연 수락은 불신하는 측에게 최적이며 전략 증명적임이 입증된다.

커플 매칭은 별도의 거래로 처리되는 대신 알고리즘에 설계적으로 통합되었다.

재설계는 1998년 실제 시장에 전면 채택되었다 — 시범 운영 없이, 그리고 그것은 성공했다.

시장의 규칙집이 불신받을 때, 해결책은 방향적일 수 있다: 보호하고자 하는 측에서 동일한 안정 매칭 기제를 실행하고, 이론의 경고를 믿기 전에 측정하라.

지원자 제안형 알고리즘은 1998년 이후 모든 메인 레지던시 매치에서 운영되어 왔으며, 현재 매년 4만 명 이상의 지원자를 배치한다. 로스와 페런슨의 1999년 《미국 경제 리뷰》 논문은 시장 설계의 창시적 문헌이 되었고, 로스의 2012년 노벨상에서 인용되었다.