모두가 만족하지 않아도 무너지지 않는 배정: 게일-섀플리의 안정 매칭과 제도의 설계

1. 합격 통지서 너머에 도사린 보이지 않는 균열

수험생이 가장 원하던 1지망 대학에 떨어지고 2지망 대학에 합격했다면, 겉으로 보기에 입학 전형은 끝난 것처럼 보인다. 합격증이 발부되었고 공적인 절차는 완결되었다.

그러나 제도의 바깥을 들여다보면 보이지 않는 균열이 숨어 있을 수 있다. 다른 대학에 배정된 지원자 중에는 자신이 붙은 대학보다 이 학생의 대학을 더 선호하는 사람이 있고, 대학 입장에서도 지금 붙여둔 학생보다 그 탈락자를 더 높게 평가하고 있을지 모른다. 만약 그렇다면 두 주체는 공적인 배정 결과를 파기하고 뒤에서 사적인 계약을 맺고 싶어질 것이다.

이것은 단순히 누군가 결과에 아쉬움을 토로한다는 뜻이 아니다. 기존의 배정을 벗어나 서로 손을 잡았을 때 양쪽 모두가 지금보다 더 나은 결과를 얻는 탈출로가 열려 있다는 뜻이다. 이런 틈새가 방치된 제도는 구성원들의 자발적인 이탈로 인해 안쪽에서부터 서서히 무너져 내린다.

대학 입학이나 취업, 결혼처럼 양쪽 모두가 상대를 선택해야 하는 양면 시장에서는 모든 사람이 동시에 1지망을 얻는 마법 같은 배정은 불가능하다. 그렇다면 완전한 만족이 불가능한 세계에서 제도는 어떤 기준 위에 세워져야 하는가?

2. 엇갈린 욕망: 민우와 지수의 선호도 역설

이 문제의 본질을 직관적으로 들여다보기 위해, 정원이 각각 1명인 두 대학(A대학, B대학)과 두 학생(민우, 지수)이 마주한 단순한 입시 시장을 가정해 보자.

각자가 마음속에 품은 선호 순위는 다음과 같이 극적으로 엇갈려 있다.

상황을 보면 민우는 A대학을, 지수는 B대학을 가장 원한다. 그런데 대학의 평가는 정반대다. A대학은 지수를 1순위로 원하고, B대학은 민우를 1순위로 원한다.

정원이 1명씩이므로 모든 사람이 1지망을 차지할 수는 없다. 누군가는 반드시 2지망으로 밀려나야 한다. 그렇다면 제도는 어떤 기준으로 이들의 자리를 정해야 하는가?

확대

3. 제도를 안쪽에서 무너뜨리는 힘: 블로킹 쌍(Blocking Pair)

1962년 수학자 데이비드 게일과 로이드 섀플리는 논문 〈대학 입학과 결혼의 안정성〉에서 이 문제를 정면으로 다루었다. 이들이 던진 질문은 모두를 행복하게 만드는 방법이 아니었다. 서로의 사적인 선택 때문에 쉽게 깨지지 않는 배정을 언제나 찾을 수 있는가라는 지극히 현실적인 질문이었다.

제도의 존속을 위협하는 핵심 요인은 개인의 불만 그 자체가 아니다. 중요한 것은 공모의 가능성이다. 매칭 이론에서는 이를 블로킹 쌍(Blocking Pair)이라고 부른다.

flowchart LR
    subgraph Official["공식적인 배정 결과"]
        S["학생: 2지망 대학에 배정됨"]
        C["대학: 2순위 학생을 선발함"]
    end

    subgraph BlockingPair["블로킹 쌍: 상호 이탈 유인"]
        S <==>|"공식 배정을 깨고 결탁할 유인\n(둘 모두 현재 상대보다 서로를 더 선호함)"| C
    end

    style BlockingPair fill:#fff1f0,stroke:#cf1322,stroke-width:2px
    style Official fill:#f6ffed,stroke:#52c41a,stroke-width:1px

어떤 학생이 자신이 배정받은 대학보다 대학 X를 더 선호하고, 동시에 대학 X 역시 현재 뽑아둔 학생보다 그 학생을 더 높게 평가한다면 두 주체는 하나의 블로킹 쌍이 된다. 둘은 중앙 배정 시스템의 결정을 무시하고 사적으로 결탁하여 약속을 깰 명확한 동기를 갖는다.

반대로 안정적인 배정(Stable Matching)이란 시장 전체에 단 하나의 블로킹 쌍도 존재하지 않는 상태를 의미한다. 누군가는 2지망에 머물러 아쉬움을 느낄 수 있다. 그러나 그 불만을 품은 사람과 손을 잡고 함께 이득을 볼 수 있는 파트너가 시장 전체에 단 한 명도 남아있지 않다면, 그 제도는 외부의 물리적 강제력 없이도 단단하게 유지된다.

4. 지연 수락 알고리즘: 잠시 미루는 제도의 지혜

이 안정적인 상태를 찾아내는 절차가 바로 지연 수락(Deferred Acceptance) 알고리즘이다. 학생들이 대학에 순차적으로 지원하는 구조를 시각화하면 다음과 같다.

flowchart TD
    Start["1단계: 탈락한 학생이\n자신의 다음 지망 대학에 지원"] --> CollegeReview["2단계: 대학은 새로 접수된 지원자와\n기존 보류자를 정원 내에서 비교"]
    CollegeReview --> HoldDecision{"정원 내 최선호자만\n'임시 보류' 상태로 유지"}
    HoldDecision --> RejectAction["정원을 초과한 하위 지원자에게\n탈락 통보"]
    RejectAction --> CheckUnmatched{"아직 지원할 대학이 남은\n탈락자가 존재하는가?"}
    CheckUnmatched -- "예" --> Start
    CheckUnmatched -- "아니오" --> FinalMatch["3단계: 최종 보류된 지원자들을\n공식 합격으로 확정 (종료)"]

    style HoldDecision fill:#e6f7ff,stroke:#1890ff,stroke-width:2px
    style FinalMatch fill:#f6ffed,stroke:#52c41a,stroke-width:2px

핵심은 지연(Deferred)이라는 개념에 있다. 대학은 마음에 드는 지원자가 나타났다고 해서 즉시 최종 합격을 보장하지 않는다. 더 나은 인재가 지원할 가능성을 열어두고 결정을 잠시 보류할 뿐이다. 학생은 거절당할 때마다 자신의 차선책 대학으로 이동하여 다시 문을 두드린다.

대학이 임시로 확보한 지원자들의 수준은 절차가 진행될수록 유지되거나 개선되며, 한 번 거절한 학생을 나중에 다시 불러들이는 일은 없다. 따라서 절차가 모두 끝났을 때 학생이 특정 대학에 들어가지 못했다면, 그 대학은 이미 그 학생보다 우수한 지원자들로 정원을 채운 상태다. 이 원리에 의해 결과표에는 사적인 결탁을 맺을 블로킹 쌍이 단 하나도 남지 않는다.

확대

5. 엇갈린 최적성: 누구에게 먼저 제안할 기회를 줄 것인가

그런데 여기서 제도의 설계자가 직면하는 가장 중대한 문제가 드러난다. 무너지지 않는 안정적인 배정이 하나만 존재하는 것이 아니라는 사실이다.

앞서 살펴본 민우와 지수, A대학과 B대학의 사례에 이 절차를 적용해보자.

경우 1: 학생이 먼저 지원하는 경우. 민우는 1지망인 A대학에 지원하고, 지수는 1지망인 B대학에 지원한다. 각 대학에 지원자가 1명씩 들어왔으므로 대학은 거절 없이 둘을 임시 보류한다. 탈락자가 없으므로 절차는 1단계에서 즉시 종료된다. 민우는 A대학(1지망)에, 지수는 B대학(1지망)에 최종 배정된다. 두 학생 모두 최우선 선택지를 얻었다. 대학들은 각각 2순위 학생을 선발하게 되어 아쉽지만, 학생 측에서 다른 대학으로 옮겨갈 이유가 없으므로 결탁은 불가능하다. 완벽하게 안정적이다.

경우 2: 대학이 먼저 제안하는 경우. A대학은 가장 선호하는 지수에게 제안하고, B대학은 가장 선호하는 민우에게 제안한다. 지수와 민우는 각각 들어온 제안을 임시로 보류한다. 거절당한 대학이 없으므로 절차는 즉시 종료된다. 민우는 B대학(2지망)에, 지수는 A대학(2지망)에 최종 배정된다. 두 대학 모두 최우선 인재를 선발했다. 학생들은 모두 2지망으로 밀려났지만, 대학 측에서 다른 학생을 원하지 않으므로 결탁이 일어나지 않는다. 이 역시 완벽하게 안정적이다.

두 결과 모두 수학적으로 흠결이 없다. 어느 쪽을 택하든 사적인 담합으로 제도가 깨질 위험은 없다.

그러나 누구에게 먼저 선택의 문을 두드릴 권리를 주었는가에 따라 한쪽 집단은 최선의 결과를 얻고, 반대편 집단은 최악의 결과를 감수해야 한다. 학생이 제안하는 방식은 존재하는 모든 안정 배정 가운데 학생들에게 가장 유리한 안정 배정을 보장한다. 반대로 대학이 제안하는 방식은 대학에 가장 유리한 결과를 안긴다.

알고리즘을 설계하는 일은 가치중립적인 계산에 머물지 않는다. 제안권을 누구에게 부여할 것인가를 결정하는 순간, 제도는 이미 누구의 복리를 우선 보호할 것인가를 규정하는 규범적 판단을 내리고 있는 것이다.

6. 정직함이 손해가 되지 않는 조건: 전략적 조작의 배제

제도의 규칙은 결과뿐 아니라 구성원들이 자신의 마음을 표현하는 태도까지 변화시킨다.

일반적인 입시나 청약 제도에서는 고도의 눈치작전이 벌어진다. 자신이 가장 원하는 곳을 1지망에 썼다가 떨어지면, 2지망 기관마저 이미 다른 지원자들로 채워져 완전히 배제될 위험이 있기 때문이다. 결국 참가자들은 자신의 진정한 선호를 숨기고 합격 가능성이 높은 차선책을 1지망으로 위장 보고한다.

정보력이 뛰어난 소수는 이 틈에서 이득을 얻지만, 제도를 순진하게 믿고 소신 지원한 이들은 손해를 입는다.

지연 수락 방식의 위력은 여기서 다시 한번 입증된다. 학생 제안 방식에서는 학생이 자신의 실제 선호를 있는 그대로 정직하게 써내는 것이 가장 유리한 행동이 된다. 1지망 대학에서 거절당하더라도 차선책 대학의 대기자들과 동등한 위치에서 다시 경쟁할 수 있기 때문이다. 다른 사람들의 선택이나 경쟁률을 눈치 보며 거짓 순위를 써낼 유인이 원천적으로 사라진다.

실제로 2005년 미국 보스턴 학군 배정 개혁은 이를 증명한 대표적 사례다. 이전까지 사용되던 즉시 수락 제도는 학부모들에게 거짓 보고와 눈치작전을 강요하여 정보 취약 계층의 자녀들을 불리한 환경으로 내몰았다. 교육위원회가 지연 수락 방식을 채택한 이유는 바로 학부모들에게 아무런 전략적 계산 없이 자녀가 가고 싶은 학교를 순서대로 적어도 불이익을 받지 않는다는 신뢰를 회복시키기 위함이었다.

7. 제도의 정당성: 안정성은 정의의 충분조건인가

그렇다면 누구도 약속을 깨지 않는 안정적인 배정이 곧 정의롭고 공정한 결과를 뜻하는가? 우리는 이 질문 앞에서 경계를 늦추지 말아야 한다. 안정성과 공정성은 전혀 다른 차원의 문제다.

어떤 대학이 특정한 계층이나 배경을 가진 지원자를 구조적으로 낮게 평가하는 편향된 기준을 갖고 있다고 가정해 보자. 알고리즘은 그 불공정한 선호 체계를 넘겨받아도 오차 없이 완벽한 안정 매칭을 도출해낸다. 그 결과에는 사적으로 결탁할 블로킹 쌍이 전혀 없으므로 제도는 흔들림 없이 유지된다.

그러나 사적 이탈이 발생하지 않는다는 사실이 그 제도가 정의롭다는 보증이 될 수는 없다. 지원의 기회는 모든 이에게 공평하게 열려 있었는가? 대학이 지원자를 평가한 기준은 정당한 역량에 근거했는가? 정보와 자원이 부족한 이들에게 출발선의 평등이 보장되었는가? 이러한 물음들은 알고리즘의 공식 바깥에 있다.

안정성은 단지 약속을 깨뜨릴 상호 이탈의 틈새를 메워주는 기술적 최소 조건일 뿐, 그 제도가 지향해야 할 가치와 정의까지 대신 판단해주지는 못한다.

제도를 설계한다는 것은 모든 이를 완벽하게 만족시키는 유토피아를 건설하는 일이 아니다. 한정된 자원과 엇갈리는 이해관계 속에서 구성원들이 서로를 불신하며 사적인 결탁으로 제도를 무너뜨리지 않도록 최소한의 신뢰의 방파제를 세우는 일이다.

무너지지 않는 배정을 만드는 기술적 해법을 손에 넣었다면, 그 다음으로 던져야 할 질문은 온전히 인간의 몫으로 남는다. 우리는 이 견고한 제도를 통해, 누구의 권리와 선택을 우선적으로 지켜낼 것인가?