메커니즘 디자인

덤프버전 :

분류



1. 개요
2. 잠정 수락 알고리즘
3. 참고



1. 개요[편집]


Mechanism Design

메커니즘 디자인은 정보경제학게임 이론의 하위 분야로, 특정 조건 내지 목표를 충족하는 게임의 구조 즉 메커니즘을 설계하는 분야이다. 여러 참가자들의 행동 하에서 특정 목표를 달성하는 법을 다루기 때문에 경제학 뿐이 아니라 정치, 네트워크 디자인 등의 분야에서도 응용이 가능하다. 최근에는 컴퓨터공학과도 연관지어 algorithmic mechanism design이라는 분야가 생겼는데, 이러한 메커니즘들을 컴퓨터로 구현하는 것에 초점을 맞추는 분야다.

동등수입 정리, 기바드-사데르스웨잇 정리, 마이어슨-사데르스웨잇 정리 등의 주요 결과가 있으며 VCG 경매, Deferred Acceptance, Top Trading Cycle, Walasian Auction 등의 주요 메커니즘이 있다.


2. 잠정 수락 알고리즘[편집]


Deferred-Acceptance Algorithm
다른 이름으로는 Gale-Shapley 알고리즘으로도 불린다. 경매같은 시장 참여자 간의 매칭 뿐만 아니라 컴퓨터 과학에서도 매우 중요한 주제.

m명의 수험생과 n개의 대학이 있고 각각은 서로에 대한 선호도를 가지고 있다. 이 때 수험생들은 다음과 같은 메커니즘으로 대학에 지원한다.
  • 1단계
  • 각 학생은 자신의 최선호 대학에 지원한다.
  • 한 대학에 여러 수험생이 지원했을 경우, 대학은 대학의 수험생 선호 랭킹이 높은 순서대로 수험생을 받고, 남는 수험생들은 탈락시킨다.
  • 학생을 다 채우지 못한 대학과 원하는 대학에 들어가지 못한 수험생이 남는다.
  • 2단계
  • 1단계에서 탈락한 수험생들과 정원을 다 채우지 못한 대학들을 대상으로, 또 다시 1단계를 반복한다. 즉, 각 학생은 정원이 남는 대학 중에서 자신의 최선호 대학에 지원한다.
  • 마찬가지로 한 대학에 여러 수험생이 지원했을 경우 대학은 탈락한 수험생들에 대한 선호 랭킹을 기준으로 남은 자리를 채운다.
  • 자리가 남는 대학과 합격하지 못한 수험생들을 대상으로, 모든 수험생이 대학과 매칭될 때까지 2단계를 반복한다.

이런 메커니즘(기제)을 통해 생성된 매칭은 다음과 같은 성질을 갖는다.

  • 항상 수험생-안정적인(stable)한 매칭 결과를 낳는다. 여기서 안정성이란 어떤 매칭상태가 주어졌을 때 더 선호하는 매칭상태가 없다는 뜻이다. 즉 수험생들은 이보다 더 좋은(선호되는) 결과를 낳을 수 없다.
  • 수험생들의 최적 전략은 자신의 대학 선호를 진실되게 밝히는 것이다. 왜냐하면 그럴 때 자신이 가장 선호하는 결과를 낳을 수 있기 때문이다.


3. 참고[편집]


한국조세재정연구원에서 발간된 메커니즘 디자인에 대한 간단한 소개
파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 2023-11-27 22:17:38에 나무위키 메커니즘 디자인 문서에서 가져왔습니다.