안정 매칭 (Stable Matching)

Photo by Christophe Hautier on Unsplash

오랜만에 글을 적습니다. 미국에서 인턴을 마치고 돌아온 후 그동안 좀 바빴습니다. 인턴을 하는 동안 연구한 결과를 잘 마무리하여 학회에 제출하기도 했고, 이론 컴퓨터 과학을 연구하거나 그것에 관심이 있는 학생들을 모아 교내 학생 모임을 발족하기도 하였습니다. 모쪼록 좋은 결과가 있기를 바라 봅니다.

 

그러는 와중에 최근 흥미로운 논문을 하나 읽었습니다. 지난 포스트에서 다루었던 다중 슬롯머신 문제(multi-armed bandits)에다가 안정 매칭(stable matching)을 결합한 문제였습니다. 다중 슬롯 머신이 무엇인지 궁금하시면 아래 포스트를 참고하시기 바랍니다.

다중 슬롯머신 문제 & 비적응 탐사 알고리즘 (Multi-Armed Bandits & Non-Adaptive Exploration Algorithms)

매칭은 제가 가장 관심을 갖는 연구 주제이고 다중 슬롯머신 문제는 근래 제가 눈여겨보던 문제였기에 해당 논문에 관심이 갈 수밖에 없었습니다. 그 논문을 다 읽은 현재는 발전 방향을 모색하고 있습니다. 개인적으로 몇 가지 아이디어가 있어서 그 방향으로 파고 들어가 볼 예정입니다.

 

이 과정에서 안정 매칭에 대해 스스로 공부를 해야할 필요를 느꼈습니다. 어찌저찌 귀동냥한 것이 있어서 개괄적인 내용은 알고 있었지만, 제대로 공부해 본 적은 없었기 때문입니다. 이번에 안정 매칭에 관해 공부한 내용을 이 글에 담습니다. 안정 매칭의 이론적인 내용이 궁금하신 분들에게 도움이 되기를 바랍니다.

문제 정의

총 \(n\) 명의 구직자와 동일한 개수의 회사가 있다고 합시다. 구직자의 집합은 \(A\), 회사의 집합은 \(B\)라고 하겠습니다. 각 회사는 정확히 한 명의 인원을 선발하려고 합니다. 우리의 목표는 각 구직자를 하나의 회사에 중복 없이 모두 할당하는 방법을 찾는 것입니다. 다시 말해, \(A\)와 \(B\) 사이의 완벽 매칭(perfect matching)을 하나 찾아야 합니다.

 

이 문제가 어려운 지점은 구직자와 회사가 각자 선호하는 회사와 구직자가 따로 있다는 것입니다. 어떤 구직자 \(i \in A\)와 두 회사 \(j, j' \in B\)에 대해, \(i\)가 \(j\)를 \(j'\)보다 선호한다면, 이를 \( j >_i j' \)으로 표현하겠습니다. 같은 이치로, 어떤 회사 \(j \in B\)와 두 구직자 \(i, i' \in A\)에 대해, \(j\)가 \(i\)를 \(i'\)보다 선호한다면, 이를 \( i >_j i' \)으로 쓰겠습니다. 각자의 선호에 비기는 경우는 없다고 가정하겠습니다. 따라서 각 구직자는 회사들로 이루어진 한 순열(permutation)을 선호 순서로 가지며, 각 회사도 구직자들로 이루어진 한 순열을 선호 순서로 갖습니다.

그림 1. 불안정한 상태.

우리는 이들의 선호를 고려하여 완벽 매칭을 찾아야 합니다. 예를 들어, 어떤 구직자 \(i \in A\)가 회사 \(j' \in B\)에 할당되었다고 합시다. 동시에 어떤 회사 \(j \in B\)는 다른 구직자 \(i' \in A\)에 할당된 상태라고 합시다. 그런데 이때, \(i\)는 \(j'\)보다 \(j\)를 선호하고 \(j\)는 \(i'\)보다 \(i\)를 더 선호한다면 \(i\)와 \(j\)는 현재의 짝을 버리고 서로에게 연결될 충분한 동기가 있습니다. 이런 상태를 우리는 매칭이 불안정(unstable)하다고 부릅니다. 만약 어떤 매칭에 불안정한 상태를 만드는 \(i, i' \in A\)와 \(j, j' \in B\)가 존재하지 않으면, 우리는 이런 매칭을 안정 매칭(stable matching)이라고 부릅니다. 우리의 목표는 안정 매칭을 찾는 것입니다.

게일-섀플리 알고리즘 (Gale-Shapley Algorithm)

과연 어떻게 하면 안정 매칭을 찾을 수 있을까요? 그 전에 안정 매칭이 존재하기는 할까요? 1962년 D. 게일과 L. S. 섀플리는 다음의 간단한 알고리즘을 통해 안정 매칭이 항상 존재함을 증명하였습니다.

알고리즘 1. 게일-섀플리 알고리즘 (Gale-Shapley Algorithm)

---

입력: 각 구직자의 선호 \(\{>_i\}_{i \in A}\), 각 회사의 선호 \(\{>_j\}_{j \in B}\)

출력: 안정 매칭

 

1. 매 라운드 \(t = 1, 2, \cdots \)마다 아래를 수행한다.
   1. 각 구직자는 아직 거절받지 않은 회사 중 자신이 가장 선호하는 회사에 지원한다.
   2. 각 회사는 그 회사에 지원한 구직자 중에서 가장 선호하는 구직자를 수락하고, 나머지는 거절한다.
   3. 만약 거절받은 구직자가 존재하지 않으면 알고리즘을 끝낸다.

이제 이 알고리즘이 안정 매칭을 출력한다는 것을 증명해 봅시다. 이를 위해서는 우선 알고리즘이 언젠간 끝난다는 것을 보여야 합니다.

정리 1. 알고리즘의 종료성

---

위 알고리즘은 \((n^2 - n + 1)\) 라운드 이내에 완벽 매칭을 출력하며 종료한다.

[증명] 먼저 알고리즘이 완벽 매칭을 출력하며 종료한다는 것을 증명하겠습니다. 단계 1-a에서 각 구직자는 매 라운드마다 그동안 거절 당하지 않은 회사 중에서 가장 선호하는 회사에 지원합니다. 이를 통해 두 가지를 유추할 수 있습니다.

1. 구직자는 어느 회사로부터 한 번 거절 당하면 그 이후에는 해당 회사에 지원하지 않는다.
2. 어떤 회사가 어느 라운드에 구직자로부터 지원을 받으면, 그 이후 알고리즘이 종료할 때까지 (동일한 구직자는 아닐지라도 누군가로부터) 계속 지원을 받는다.

위 두 사실을 통해 우리는 모든 회사가 언젠간 적어도 한 번은 지원을 받게 된다는 것을 알 수 있습니다. 그 때가 바로 알고리즘이 완벽 매칭을 출력하며 종료하는 시점입니다.

 

이제 알고리즘이 완벽 매칭을 출력하기까지 많아야 \((n^2 - n + 1)\) 라운드가 필요함을 보이겠습니다. 각 구직자 \(i \in A\)와 라운드 \(t \in \mathbb{Z}_+\)에 대해, \(r_i(t)\)를 라운드 \(t\)에 구직자 \(i\)가 단계 1-a에서 지원한 회사의 선호 순번으로 정의하겠습니다. 예를 들어, \(B = \{x, y, z\}\)인 경우에 \(i\)가 \(x >_i  y >_i z\)의 선호 순서를 갖는다면, \(x\)는 \(i\)의 첫 번째, \(y\)는 두 번째, \(z\)는 세 번째 선호 순번을 갖습니다. 마지막으로 \(\Phi(t)\)를 라운드 \(t\)에 대한 모든 \(r_i(t)\)의 합, 다시 말해, \[\Phi(t) := \sum_{i \in A} r_i(t)\]로 정의하겠습니다.

 

\(\Phi(1) = n\)이라는 사실을 먼저 확인하시기 바랍니다. 이제 어떤 라운드에서 알고리즘이 끝나지 않고 다음 라운드로 넘어갔다고 가정해 봅시다. 이는 분명 어느 회사에 여러 구직자가 지원하여 적어도 한 명 이상의 구직자가 거절을 받았기 때문입니다. 따라서 다음 라운드에서 거절을 당한 구직자들은 본인의 선호 순서 상 다음 순번의 회사에 지원할 것입니다. 그러므로 임의의 라운드 \(t\)에 대해 \[ \Phi(t + 1) \geq \Phi(t) + 1 \]을 만족합니다. 그런데 앞에서 알고리즘이 언젠가는 완벽 매칭을 출력하며 종료한다고 하였고, 각 구직자의 선호 순번은 최대 \(n\)까지이므로 임의의 라운드 \(t\)에 대해 \[ \Phi(t) \leq n^2 \]을 만족해야 합니다. 위 두 사실을 통해 가능한 라운드의 횟수는 최대 \(n^2 - n + 1\)을 넘지 않음을 알 수 있습니다. ■

 

이제 이 알고리즘이 실지로 안정하다는 사실을 증명하겠습니다.

정리 2. 알고리즘의 정확성

---

알고리즘이 출력하는 완벽 매칭은 안정하다.

[증명] 모순을 이끌어 내기 위해 알고리즘이 출력한 완벽 매칭이 불안정하다고 하겠습니다. 다시 말해, 다음을 만족하는 \(i, i' \in A\), \(j, j' \in B\)가 출력된 매칭에 존재한다는 뜻입니다.

• \(i\)는 \(j'\)과, \(i'\)은 \(j\)와 짝지어져 있다.
• \(j >_i j'\)이고 \(i >_j i'\)이다.

\(i'\)이 \(j\)와 처음으로 짝지어진 라운드를 \(t\)라고 하겠습니다. 알고리즘의 동작에 따라 이후 \(j\)는 계속 \(i'\)만 선택할 것입니다. 먼저 \(i\)가 라운드 \(t\) 당시 \(j\)보다 선호하는 회사에 지원하고 있다고 가정해 봅시다. \(i\)는 최종적으로 \(j'\)과 짝지어질 것이므로 그 이후 라운드가 계속 진행되면 단계적으로 덜 선호하는 회사에 지원하여 결국 \(j'\)에 도달할 것입니다. 그 와중에 \(i\)는 분명 \(j\)에도 지원을 할 것입니다. \(j\)는 \(i'\)보다 \(i\)를 선호하므로 그때 \(j\)는 \(i'\)이 아닌 \(i\)의 지원을 수락했을 것입니다. 이로써 모순을 이끌어 낼 수 있습니다. 그럼 \(i\)가 라운드 \(t\) 당시에 \(j\)보다 덜 선호하는 회사에 지원하고 있을 때는 어떨까요? 이는 분명 이전에 \(j\)가 \(i\)보다 더 선호하는 구직자로부터 지원을 받았기 때문에 가능합니다. 그러니 \(i'\)이 해당 구직자를 밀어내고 \(j\)를 차지했을리 만무합니다. ■

최선 & 최악 안정성 (Optimal & Pessimal Stability)

위 절에서 우리는 게일-섀플리 알고리즘이 다항 횟수의 라운드(따라서 다항 시간)에 안정 매칭을 출력한다는 사실을 보였습니다. 그런데 이 알고리즘이 출력하는 안정 매칭은 또다른 흥미로운 성질을 갖고 있습니다. 이번 절에서는 이 성질에 대해서 알아 보겠습니다.

 

사실 안정 매칭은 하나만 존재하는 것이 아닙니다. 다음의 간단한 예시에서도 안정 매칭이 두 개가 존재함을 쉽게 확인할 수 있습니다.

• \(A := \{a, b\}, B := \{x, y\} \)
• \(x >_a y\), \(y >_b x\)
• \(b >_x a\), \(a >_y b\)
• \(\{(a, x), (b, y)\}\), \( \{(a, y), (b, x)\} \) 모두 안정하다.

그림 2. 안정 매칭이 두 개 존재하는 예시.

그렇다면 게일-섀플리 알고리즘은 많은 안정 매칭 중에서 어떤 안정 매칭을 출력해 줄까요? 결론부터 말씀 드리면 게일-섀플리 알고리즘은 지원하는 쪽에는 최선(optimal)의, 반대로 지원을 받는 쪽에서는 최악(pessimal)의 안정 매칭을 출력합니다. 다시 말해, 위 버전에서는 구직자-최선 회사-최악 안정 매칭을 출력합니다.

 

최선과 최악을 엄밀히 정의해 보겠습니다. 이를 위해서는 다음의 상황을 정의해야 합니다. 어떤 구직자 \(i \in A\)와 회사 \(j \in B\)에 대해, 만약 \(i\)와 \(j\)가 서로 짝지어진 안정 매칭이 존재하지 않을 때, 우리는 \(i\)와 \(j\)는 서로 불가능(impossible)하다고 말하겠습니다. 임의의 구직자 \(i \in A\)에 대해 만약 \(i\)가 현재 짝지어진 회사보다 선호하는 회사들은 모두 \(i\)와 불가능하다면, 우리는 이를 \(i\)에 최선이라고 부르겠습니다. 비슷한 이치로 임의의 회사 \(j \in B\)에 대해 \(j\)가 현재의 짝보다 불호하는 구직자들은 모두 \(j\)와 불가능하다면  우리는 이를 \(j\)에 최악이라고 부릅니다. 따라서 구직자-최선 회사-최악 안정 매칭은 모든 구직자는 최선인 회사와, 반면 모든 회사는 최악인 구직자와 짝지어진 매칭을 뜻합니다. 참고로 이러한 안정 매칭은 유일할 수밖에 없습니다. 한번 직접 증명해 보시기 바랍니다.

 

이제 게일-섀플리 알고리즘이 구직자-최선 회사-최악 안정 매칭을 출력한다는 것을 증명해 보겠습니다. 이를 위해 한 가지 정의를 하고 넘어가겠습니다. 어떤 라운드 \(t\) 그리고 임의의 구직자 \(i \in A\)에 대해, \(S_i(t)\)를 라운드 \(t\)가 끝났을 때까지 \(i\)가 거절 당한 회사의 집합이라고 하겠습니다. 일관성을 위해 \(S_i(0) := \emptyset\)으로 정의하겠습니다.

정리 3. \(S_i(t)\)의 성질

---

임의의 \(t \in \mathbb{Z}_{\geq 0}\), 임의의 구직자 \(i \in A\)에 대해, \(S_i(t)\)의 모든 회사는 \(i\)와 불가능하다.

[증명] \(t\)에 대한 귀납법으로 증명합니다. 기저 경우는 \(t = 0\)일 때이며, 이는 모든 \(i \in A\)에 대해 \(S_i(0) = \emptyset\)이어서 자명합니다. 이제 임의의 \(t \geq 1\)를 고려해 보겠습니다. 모순을 이끌어 내기 위해 어떤 \(i \in A\)와 어떤 \(j \in S_i(t)\)가 짝지어진 안정 매칭 \(M\)이 있다고 하겠습니다. 귀납 가정에 의해 \(j \in S_i(t) \setminus S_i(t - 1)\)이어야 합니다. 다시 말해, 라운드 \(t\)에 \(j\)는 \(i\)의 지원을 거절한 것이죠. 이때 \(j\)가 대신 수락한 구직자를 \(i'\)이라고 하겠습니다. 분명, \[ i' >_j i \]를 만족합니다. \(i'\)은 그 라운드에 지원에 성공하였으므로 \( S_{i'}(t) = S_{i'}(t - 1) \)입니다. 그러므로 귀납 가정에 의해 \(i'\)은 \(M\)에서 \[ j >_{i'} j' \]인 회사 \(j'\)과 짝지어졌다는 뜻입니다. \(M\)은 \(i'\)과 \(j\) 때문에 불안정하므로 모순입니다. ■

 

위 정리를 통해 알고리즘이 출력하는 매칭이 구직자-최선 안정하다는 것을 쉽게 보일 수 있습니다.

정리 4. 구직자-최선 안정성

---

알고리즘이 출력하는 매칭에서 모든 구직자 \(i \in A\)는 최선의 회사와 짝지어진다.

[증명] 정리 3을 통해 구직자가 그동안 제안했다가 거절 당한 회사는 애초에 불가능한 회사라는 사실을 알 수 있습니다. 알고리즘에서는 그렇지 않은 회사 중에서 구직자가 가장 선호하는 회사에 짝지어집니다. ■

 

마지막으로 알고리즘이 출력하는 매칭이 회사 입장에서는 최악이라는 것을 보이겠습니다.

정리 5. 회사-최악 안정성

---

알고리즘이 출력하는 매칭 \(M\)에서 모든 회사 \(j \in B\)는 최악의 구직자와 짝지어진다.

[증명] \(M\)에서 \(j\)와 짝지어진 구직자를 \(i\)라고 하겠습니다. 귀류법을 적용하기 위해 \[ i >_j i' \]을 만족하는 어떤 구직자 \(i' \in A\)과 \(j\)가 짝지어진 안정 매칭 \(M'\)이 존재한다고 하겠습니다. 정리 4를 통해 \(i\)에게 \(j\)보다 선호하는 회사는 불가능하다는 사실을 알기에 \(M'\)에서 \(i\)는 \[ j >_i j' \]인 어떤 회사 \(j' \in B\)와 짝지어져 있을 것입니다. 이는 \(M'\)이 \(i\)와 \(j\) 때문에 불안정하다는 사실을 알려 줍니다. ■

마치며

이것으로 안정 매칭에 대한 설명을 모두 마칩니다. 안정 매칭은 컴퓨터 과학은 물론 경제학이나 사회 과학 등 다양한 분야에서 널리 연구되는 주제입니다. 본문에서 소개한 게일-섀플리 알고리즘은 간단하지만 한쪽에는 최적의, 다른쪽에는 최악의 결과를 준다는 문제점이 있습니다. 따라서 보다 공정한 안정 매칭을 주는 것도 흥미로운 연구 주제일 것입니다. 다만, 공정한 안정 매칭은 대부분 NP-난해한 것으로 알고 있습니다. 근사해를 주는 결과는 없는지 찾아 보고 싶군요.

 

이 내용을 공부하고 정리한 이유는 안정 매칭을 다중 슬롯머신 문제와 결합하여 해결한 최근의 연구 성과들이 있기 때문입니다. 해당 주제에 많은 관심이 있는 만큼 기회가 된다면 포스팅해 보도록 하겠습니다. 다행히 난이도도 그렇게 어렵지는 않은 것 같더라고요.

 

읽어 주셔서 고맙습니다. :)

참고 문헌

[1] David Gale, and Lloyd S. Shapley. "College admissions and the stability of marriage." The American Mathematical Monthly 69, no. 1 (1962): 9-15.