게임이론 · 제5회
4회의 경매처럼, 이번엔 짝짓기 규칙을 설계해요. 서로 다른 선호를 가진 두 집단을 짝지을 때, ‘둘 다 지금보다 서로를 더 원하는’ 쌍이 없게 만들 수 있을까요? 이게 안정 매칭입니다.
A는 X와 짝인데 사실 Y를 더 좋아하고, Y도 지금 짝보다 A를 더 좋아한다면? 둘은 몰래 갈아타요(불안정). 이런 ‘탈주 쌍’이 하나도 없는 짝짓기가 가능할까요?
게일과 섀플리는 “항상 가능하다”를 증명하고, 만드는 방법(지연 수락)까지 줬어요 — 노벨경제학상 업적이에요.
지원자(A·B·C)가 선호 순으로 회사(X·Y·Z)에 제안하고, 회사는 더 나은 제안이 오면 갈아타요. 반복하면 안정 매칭이 나와요!
지연 수락(deferred acceptance): 회사는 더 나은 제안이 올 때까지 임시로 붙잡고, 더 좋은 제안이 오면 갈아타요. 이 과정은 반드시 끝나고, 결과는 항상 안정적이에요. 미국 전공의 배정·학교 배정이 이 방식이에요.
지연 수락 알고리즘 → 언제나 안정 매칭 (탈주 쌍 없음)
제안하는 쪽에 유리한 안정 매칭이 나와요. ‘좋은 규칙 설계’로 모두가 받아들일 결과를 보장하는 거죠(메커니즘 디자인의 꽃). 전공의 배정·공립학교 배정·장기 교환이 이 이론으로 운영돼요.
게임이론 5부작 완주! — 딜레마부터 매칭시장까지, 전략적 상호작용의 수학을 훑었어요. 궁금한 건 방의 Q&A 봇에! → 제6회 · 협력게임과 샤플리 값
『수요를 따라가는 수학 · 게임이론』 제5회. 게일–섀플리 안정 매칭 시뮬레이터 + 자동채점. · 게임이론방으로