1. 개요
Mechanism Design메커니즘 디자인은 정보경제학 및 게임 이론의 하위 분야로, 특정 조건 내지 목표를 충족하는 게임의 구조 즉 메커니즘을 설계하는 분야이다. 여러 참가자들의 행동 하에서 특정 목표를 달성하는 법을 다루기 때문에 경제학 뿐이 아니라 정치, 네트워크 디자인 등의 분야에서도 응용이 가능하다. 최근에는 컴퓨터공학과도 연관지어 algorithmic mechanism design이라는 분야가 생겼는데, 이러한 메커니즘들을 컴퓨터로 구현하는 것에 초점을 맞추는 분야다.
동등수입 정리, 기바드-사데르스웨잇 정리, 마이어슨-사데르스웨잇 정리 등의 주요 결과가 있으며 그로브스-레야드 메커니즘, VCG 경매, Deferred Acceptance, Top Trading Cycle,
2. 잠정 수락 알고리즘
Deferred-Acceptance Algorithm다른 이름으로는 Gale-Shapley 알고리즘으로도 불린다. 경매같은 시장 참여자 간의 매칭 뿐만 아니라 컴퓨터 과학에서도 매우 중요한 주제.
m명의 수험생과 n개의 대학이 있고 각각은 서로에 대한 선호도를 가지고 있다. 이 때 수험생들은 다음과 같은 메커니즘으로 대학에 지원한다.
- 1단계
- 각 학생은 자신의 최선호 대학에 지원한다.
- 한 대학에 여러 수험생이 지원했을 경우, 대학은 대학의 수험생 선호 랭킹이 높은 순서대로 수험생을 받고, 남는 수험생들은 탈락시킨다.
- 원하는 대학에 들어가지 못한 수험생이 남는다.
- 2단계
- 1단계에서 탈락한 수험생들을 대상으로 1단계를 반복한다. 탈락한 각 학생은 자신이 아직 지원하지 않은 모든 대학 중에서 자신의 최선호 대학에 지원한다.
- 마찬가지로 한 대학에 여러 수험생이 지원했을 경우 대학은 이미 잠정적으로 합격한 학생들과 새로이 지원한 학생들 모두를 고려하여 선호 랭킹을 기준으로 새로이 자리를 채운다.
- 더 이상 탈락한 학생이 없을 때까지 2단계를 반복한다.
이런 메커니즘(기제)을 통해 생성된 매칭은 다음과 같은 성질을 갖는다.
- 항상 수험생-안정적인(stable)한 매칭 결과를 낳는다. 여기서 안정성이란 어떤 매칭상태가 주어졌을 때 더 선호하는 매칭상태가 없다는 뜻이다. 즉 수험생들은 이보다 더 좋은(선호되는) 결과를 낳을 수 없다.
- 수험생들의 최적 전략은 자신의 대학 선호를 진실되게 밝히는 것이다. 왜냐하면 그럴 때 자신이 가장 선호하는 결과를 낳을 수 있기 때문이다.