서로 원하는 자리를 정할 때, 누가 먼저 제안하느냐도 중요할까요?

학생 A,B,C와 자리 X,Y,Z가 있어요. 각각 한 명씩만 배정하며 모든 상대를 받아들일 수 있어요. 각자의 자체 희망 순서는 동순위 없이 다음과 같아요.

서로 따로 배정된 학생·자리가 모두 지금 상대보다 서로를 원하면 그 배정은 안정적이지 않다고 정해요. 학생이 제안하는 경우와 자리가 제안하는 경우에 아래 절차를 적용해 볼까요? 제안자는 아직 제안하지 않은 상대 중 가장 원하는 곳에 제안해요. 상대는 받은 제안과 기존 보류 중 가장 원하는 하나만 임시 보류하고 나머지를 거절해요. 거절받은 쪽은 다음 상대에 다시 제안해요. 제안할 수 있는 자유로운 제안자가 없으면 보류를 확정해요.

두 결과는 같을까요? 가능한 안정 배정을 모두 찾고, 같은 조건의 두 n명 집합에서도 이 절차가 완전한 안정 배정을 만드는 이유를 증명해 볼까요?

학생 제안에서는 A→X,B→Y,C→Z가 첫 제안에 모두 보류된다. 자리 제안에서는 X→B,Y→C,Z→A가 모두 보류된다. 둘 다 안정적이지만 결과는 달라요. A→Y,B→Z,C→X도 안정적이에요. 각 학생이 그보다 원하는1순위 자리는 현재 학생을 더 원해 상대를 바꿀 의사가 없기 때문이에요.

다른 세 후보 (X,Z,Y),(Y,X,Z),(Z,Y,X)는 각각 C와X, B와Z, A와Y가 서로 바꾸기를 원해요. 모든6개 일대일 대응을 확인했으므로 안정 배정은 위3개뿐이에요.

일반 절차도 끝나야 존재 증명이 돼요. 같은 제안자가 같은 상대에게 다시 제안하지 않으므로 서로 다른 제안은 최대 n²개예요. 제안을 처음 보류한 상대는 이후 더 원하는 상대가 오면 바꿀 뿐, 보류를 아예 없애지는 않아요.

끝났는데 자유로운 제안자가 남았다고 가정할게요. 아직 제안하지 않은 상대가 있다면 끝난 조건과 모순이므로 그 제안자는 n명 모두에게 제안했어요. 모든 상대가 적어도 한 번 제안을 받았고 현재도 한 명씩 보류해요. 서로 다른 n명을 이미 보류하므로 자유로운 제안자가 추가로 남을 수 없어요. 따라서 모든 제안자와 모든 상대가 한 명씩 배정된다.

안정성은 거절된 제안을 살펴보면 돼요. 학생 a가 현재 자리보다 b를 원한다면 희망 순서대로 제안했으므로 b에게 먼저 제안했어요. b가 a를 거절하거나 나중에 교체했을 때에는 a보다 원하는 다른 학생을 보류했고, 이후 보류 상대는 더 좋아지기만 해요. 그러므로 최종 b는 a보다 현재 상대를 원해요. 두 쪽이 동시에 바꾸고 싶어 하는 따로 배정된 쌍은 없어요. 자리 제안에서도 역할을 바꾸어 같은 논증을 써요.

이3×3 예의 두 제안 방향은 각 제안자가 자기1순위를 얻어요. 그러나 안정이라는 말만으로 학생 모두의1순위나 자리 모두의1순위를 요구하지 않아요. 가운데 배정도 안정적이고 학생·자리 모두2순위다. 현재의 완전 수락·동순위 없음·같은 인원수 조건을 불완전 목록이나 여러 자리의 현실 배정에 그대로 옮기지 않아요.

서로 다른 상대를 한 번씩 배정했다는 확인과, 서로 바꾸기를 원하는 쌍이 없다는 확인을 구별해 봐요. 같은 조건에서도 안정 결과가 여럿이라는 수치 예와, 모든n에서 적어도 하나를 만드는 증명도 다른 판단이에요.

출처·착안: Royal Swedish Academy of Sciences, 2012 Scientific Background, §3.1. 원문4인 예표를 사용하지 않고 자체3×3 순서·문항·논증을 작성했다.