학생 4명이 동아리 4곳에 지원한다. 각자 선호 순위가 있고, 정원은 1명씩.
어떻게 짝을 지어야 "안정적(stable)"일까? — 서로 지금 짝보다 상대를 더 원하는
불안정 쌍(blocking pair)이 하나도 없는 매칭.
게일-섀플리(Gale–Shapley, 1962) 알고리즘은 제안 → 임시 수락 → 파혼을
반복해 항상 안정 매칭을 찾아낸다. 2012년 노벨 경제학상(Roth&Shapley)의 이론이자,
전공 배정·전지 배정·신장 기증 교환에 실제로 쓰인다.
👩🎓 학생 (제안하는 쪽)
PROPOSE →
🏛️ 동아리 (수락/거절하는 쪽)
📋 진행 로그
📊 상태
round0
proposals0
rejections0
matched0 / 4
알고리즘을 실행해 보세요.
🧪 안정성 검사 — 모든 (학생, 동아리) 쌍 확인
최종 매칭에서, 서로가 현재 짝보다 상대를 더 선호하면 그 쌍은 불안정 쌍이다.
게일-섀플리 결과에는 이런 쌍이 존재할 수 없다.
동작 원리 — 제안, 임시 약혼, 파혼
1. 제안 — 아직 짝이 없는 학생이 자기 선호 목록에서 아직 제안하지 않은 가장 위 동아리에 지원한다. 2. 임시 수락 — 동아리가 비어 있으면 일단 받아 준다(engaged). 확정이 아니라 임시다. 3. 파혼(trade-up) — 이미 다른 학생 s'와 약혼한 동아리에 새 학생 s가 제안하면,
동아리는 자기 선호 순위로 둘을 비교한다. s가 더 좋으면 s'를 차 버리고(s'는 다시 미혼) s와 약혼,
아니면 s를 거절한다. 4. 종료 — 미혼이면서 제안할 곳이 남은 학생이 없을 때. 모든 임시 약혼이 확정된다.
functiongaleShapley(students, clubs):
while∃ 미혼 학생 s 이면서 아직 제안 안 한 동아리가 남음:
c = s.prefs 중 아직 제안 안 한 최상위 동아리
s.proposeTo(c)
if c 가 미혼:
engage(s, c) # 임시 수락else:
s2 = c.partner
if c.prefers(s, s2): # 새 제안자가 더 좋다
break_up(s2, c) # s2 는 다시 미혼
engage(s, c)
else:
c.reject(s) # s 는 다음 동아리로return모든 engaged 쌍 = 안정 매칭
왜 항상 안정적일까?
최종 매칭에 불안정 쌍 (s, c)가 있다고 하자 — s는 자기 짝보다 c를,
c는 자기 짝보다 s를 더 원한다. s는 선호 순서대로 위에서부터 제안하므로, 지금 짝보다 위인 c에게 반드시 이미 제안했다.
그런데 거절당했다. 동아리는 더 좋은 상대가 생길 때만 파트너를 바꾸므로,
c의 최종 짝은 s보다 같거나 더 나은 사람이다.
→ c가 s를 더 원한다는 가정과 모순. 그래서 불안정 쌍은 존재할 수 없다. ∎
제안자 최적성(proposer-optimal): 제안하는 쪽(여기선 학생)은 가능한 모든 안정 매칭 중 자기에게 가장 좋은 짝을 얻는다.
반대로 수락하는 쪽(동아리)은 가장 나쁜 결과를 받는다. 그래서 "누가 제안하느냐"가 공정성 논쟁의 핵심이다.
성질 요약
• 항상 종료: 각 학생은 각 동아리에 최대 1번 제안 → 제안 횟수 ≤ n² → 시간복잡도 O(n²).
• 항상 완전 매칭: 인원수가 같으면 모두 짝이 생긴다(어떤 동아리가 끝까지 비면, 어떤 학생도 끝까지 미혼 → 그 학생은 그 동아리에 제안했어야 함 → 모순).
• 파트너는 학생 입장에선 나빠지기만, 동아리 입장에선 좋아지기만 한다(단조성).
• 정직이 최선(제안자에겐 전략 내성): 학생은 선호도를 거짓말해도 이득이 없다.