안정 매칭(Stable matching)

학생 넷과 학교 넷이 있고, 학교마다 자리가 하나입니다. 학생은 학교들에, 학교는 학생들에 좋아하는 순서를 매깁니다. 학생과 학교를 짝짓는 것은 두 무리 사이의 일대일대응인데, 어떤 짝짓기는 오래가지 못합니다. 학생 s와 학교 c가 둘 다 지금 짝보다 서로를 더 좋아하면, 둘은 배정을 무시하고 손을 잡을 테니까요. 이런 쌍을 차단 쌍⁠(blocking pair)⁠이라 하고, 차단 쌍이 없는 짝짓기를 안정 매칭이라 합니다.

1962년 미국의 수학자 데이비드 게일과 로이드 섀플리는 안정 매칭이 언제나 있다는 것을, 그것을 찾는 절차로 보였습니다. 짝이 없는 학생은 아직 거절당하지 않은 학교 가운데 가장 좋아하는 곳에 지원합니다. 학교는 지금까지 받은 지원자 가운데 가장 나은 한 명만 '보류'하고 나머지는 거절합니다. 보류는 확정이 아니어서, 더 나은 학생이 오면 보류하던 학생을 놓아 줍니다. 아무도 더 지원할 필요가 없어지면 끝납니다.

진행: . 새 선호

'직접 짝짓기'에서는 학생 하나와 학교 하나를 차례로 누르면 둘이 짝이 되고, 원래 짝들끼리 서로 바뀝니다. 차단 쌍이 사라질 때까지 손으로 고쳐 보세요. 지금 차단 쌍은

왜 늘 끝나고, 왜 안정할까요? 학생은 같은 학교에 두 번 지원하지 않으니 지원은 많아야 $n^2$번입니다(점근 표기법⁠, asymptotic notation⁠). 학교는 한 번 누군가를 보류하면 끝까지 누군가를 보류하고 상대는 좋아지기만 합니다. 끝났는데 짝 없는 학생이 있다면 그 학생은 n개 학교에 모두 거절당했고, 그러면 n개 학교가 모두 다른 학생을 보류하고 있으니 학생이 n명보다 많아야 합니다(비둘기집 원리⁠, pigeonhole principle⁠). 안정성⁠(stability)⁠도 곧바로 나옵니다. 학생 s가 자기 학교보다 c를 더 좋아한다면 s는 c에 먼저 지원했다가 거절당했고, c는 그때 s보다 나은 학생을 보류했으며 그 뒤로는 더 나아지기만 했으니 c는 s를 원하지 않습니다.

안정 매칭은 여러 개일 수 있고, 어느 쪽이 지원하느냐가 중요합니다. 지원하는 쪽은 저마다 어떤 안정 매칭에서든 얻을 수 있는 가장 좋은 짝을 얻고, 받는 쪽은 가장 나쁜 짝을 얻습니다. 위에서 '학교가 제안'으로 바꿔 두 결과의 평균⁠(mean)⁠ 순위를 견줘 보세요(새 선호는 두 결과가 달라지는 예만 골라 줍니다). 선호가 무작위이면 지원 횟수는 최악의 $n^2$보다 훨씬 적어서, 평균이 대략 $n \ln n$ 정도로 자란다는 것이 알려져 있습니다. 이 어림은 쿠폰 수집 문제⁠(coupon collector's problem)⁠에서 옵니다. 과자 봉지마다 n종류 쿠폰 가운데 하나가 무작위로 들어 있을 때 모든 종류를 다 모으려면 평균 $n H_n$봉지를 사야 합니다(기댓값⁠, expected value⁠). 여기서 $H_n = 1 + \tfrac12 + \cdots + \tfrac1n$은 조화급수⁠(harmonic series)⁠의 부분합⁠(partial sum)⁠으로 $\ln n$에 가깝습니다. 학생이 이미 거절당한 학교를 잊고 매번 무작위 학교에 다시 지원한다고 쳐 봅시다. 그러면 지원 횟수는 늘기만 하고, 모든 학교가 한 번씩 지원을 받는 순간 끝나므로 정확히 쿠폰 수집이 됩니다. 그래서 무작위 선호에서 평균 지원 횟수는 $n H_n$ 이하입니다. 학생 수 명으로 무작위 선호 100벌을 풀어 보면 평균 번 지원합니다. $n H_n$ = , $n^2$ = 입니다.

이어지는 곳. 미국 의대 졸업생을 수련 병원에 배정하는 전국 레지던트 매칭⁠(matching)⁠은 1950년대부터 사실상 같은 절차를 병원 쪽이 제안하는 형태로 써 왔고, 1990년대에 지원자 쪽이 제안하도록 다시 설계되었습니다. 뉴욕과 보스턴 같은 여러 도시의 학교 배정에도 쓰입니다. 같은 연구는 신장 교환⁠(kidney exchange)⁠으로도 이어졌습니다. 신장을 주려는 가족과 받을 환자가 서로 맞지 않을 때, 그런 쌍 여럿을 엇갈려 짝지어 서로의 환자에게 주고받게 하는 일입니다. 섀플리와 미국의 경제학자 앨빈 로스는 이 연구로 2012년 노벨 경제학상을 받았습니다. 짝이 존재하는지만 묻는다면 홀의 정리⁠(Hall's theorem)⁠가, 모두의 만족 합을 최대로 하려면 최적 수송⁠(optimal transport)⁠ 같은 배정 문제⁠(assignment problem)⁠가 알맞습니다. 한 무리 안에서 둘씩 짝짓는 '룸메이트 문제⁠(stable roommates problem)⁠'에서는 안정 매칭이 아예 없을 수도 있습니다. 예를 들어 A는 B를, B는 C를, C는 A를 가장 좋아하고 셋 모두 D를 가장 싫어하면, D와 짝이 된 사람은 늘 자기를 더 좋아하는 누군가와 차단 쌍을 이룹니다. 게일–섀플리 절차는 매 순간 가장 좋은 곳에 지원하지만 보류로 결정을 미루기 때문에, 한 번 고르면 끝인 욕심쟁이 알고리즘⁠(greedy algorithm)⁠과 달리 늘 안정한 답에 닿는 알고리즘입니다.