온라인 이분 매칭 랭킹 알고리즘 (Ranking Algorithm for Online Bipartite Matching)

Photo by Joshua Golde on Unsplash

지난번에 온라인 이분 매칭 문제(online bipartite matching problem)에 대해서 알아 보았습니다.  그 문제는 다음과 같이 정의되었습니다.

처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 한 명도 태우지 않은 택시 가운데 한 대를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 바로 결정해야 한다. 이 결정은 번복될 수 없다. 이때 목표는 승객을 최대한 많이 태우는 것이다.

저번 글에서 공부한 내용을 요약하면 다음과 같습니다.

• 승객이 매번 들어올 때마다 가능한 택시 중 아무 하나에 이 승객을 태우는 방법은 1/2의 경쟁비(competitive ratio)를 갖는다.
• 이 문제를 해결하는 어떤 결정론적 알고리즘(deterministic algorithm)도 1/2 보다 좋은 경쟁비를 가질 수 없다.
• 승객이 들어올 때 가능한 택시 중 하나를 균등한 확률(uniformly at random)로 선택하여 승객을 태우는 랜덤 알고리즘(randomized algorithm)도 1/2의 경쟁비를 갖는다.

그러면서 마지막에 다음의 질문을 제시하였습니다.

이 문제를 해결하는 1/2 보다 좋은 경쟁비를 갖는 랜덤 알고리즘이 존재하는가?

흥미롭게도 그러한 알고리즘이 존재합니다. 바로 랭킹 알고리즘(ranking algorithm)인데요. 결론부터 말씀드리면 이 알고리즘은 $1-1/e\approx 0.632$의 경쟁비를 갖습니다. 이번 시간에는 이 알고리즘에 대해서 함께 알아 보도록 하겠습니다. 참고로 이 글은 온라인 알고리즘 및 온라인 이분 매칭을 어느 정도 알고 있다는 가정 아래 작성되었습니다. 잘 모르시는 분들은 아래를 참조하시기 바랍니다.

2020/03/14 - [온라인 알고리즘/Basic] - 온라인 알고리즘 (Online Algorithm)

온라인 알고리즘 (Online Algorithm)

2020/11/07 - [온라인 알고리즘/Online matching] - 온라인 이분 매칭 (Online Bipartite Matching)

온라인 이분 매칭 (Online Bipartite Matching)

문제 정의

온라인 이분 매칭을 다시 한 번 정의해 보겠습니다. 이번에 다룰 알고리즘은 랜덤 알고리즘이므로 이 알고리즘을 상대하는 상대방은 무지각형 상대방(oblivious adversary)으로 두겠습니다. 다시 말해, 알고리즘이 시작하기 전에 어떤 입력이 어느 순서로 들어올지가 모두 정해진 상태입니다.

 

따라서 입력은 다음과 같은 이분 그래프(bipartite graph) $G=(L\cup R,E)$라고 가정할 수 있습니다. 이때 $L$은 가용할 수 있는 택시에 대응하는 정점의 집합으로 알고리즘이 미리 알고 있는 내용입니다. 반대로 $R$은 승객에 대응하는 정점의 집합으로 이는 처음에는 알고리즘에게 제공되지 않습니다. 대신 시간이 지나면서 미리 정해진 순서에 따라 하나씩 알고리즘에 입력이 됩니다. 그때마다 동시에 해당 승객 정점에 딸린(incident) 간선이 함께 제공됩니다. 이 간선들은 앞의 예제에서 해당 손님이 이용할 수 있는 택시가 무엇인지를 나타낸다고 이해하시면 되겠습니다.

 

알고리즘은 매번 승객 정점과 그에 딸린 간선을 입력 받을 때마다 해당 승객 정점을 짝지을 것이지 말 것인지, 그리고 짝을 짓는다면 어느 택시 정점과 지을 것인지를 결정해야 합니다. 이 결정은 번복할 수 없습니다. 이때 택시는 최대 한 명의 승객을 태울 수 있다고 가정했으므로, 이번 승객 정점에 인접한(adjacent) 택시 정점 중에서 이미 이전 승객 정점과 짝이 지어진 정점과는 짝을 지을 수 없습니다. 이를 통해서 우리는 알고리즘이 출력하는 결과가 $G$ 위에서 매칭(matching)을 이룬다는 것을 알 수 있습니다.

 

우리의 목표는 $R$이 모두 들어왔을 때 알고리즘이 출력하는 매칭을 최대화하는 것입니다. 그 비교 대상은 당연히 원래 $G$의 최대 매칭(maximum matching)이 됩니다.

랭킹 알고리즘

이제 알고리즘을 소개하도록 하겠습니다.

알고리즘 1. Ranking algorithm

---

초기 입력: 택시 정점 집합 $L$

출력: 매칭

 

1. 각 $u\in L$에 대해, $y_u$를 $[0,1]$에서 균등한 확률(uniformly at random)로 고른다.
2. 매번 $v\in R$가 들어올 때마다, $v$에 인접하면서 아직 매칭에 참여하지 않은 택시 정점 중에서 $y_u$가 가장 작은 $u\in L$와 짝을 짓는다. 만약 그러한 택시 정점이 존재하지 않으면 $v$는 짝을 짓지 못한 상태로 남는다.

알고리즘이 어떻게 동작하는지를 간단히 살펴 보죠. 첫 번째 단계에서는 각 택시 정점 $u\in L$ 마다 $y_u$를 고릅니다. 따라서 만약 우리가 $L$을 $y_u$가 커지는 순서대로 나열한다면 이는 $L$의 순열(permutation)을 이루게 되죠. 이때 $y_u$가 서로 독립적으로 균등한 확률로 0에서 1 사이에서 정해지기 때문에, 어느 한 순열로 결정되는 확률도 모두 균등합니다. 다시 말해, 첫 번째 단계를 거친 후에 우리는 택시 정점들에 대한 랜덤 순열(random permutation)을 하나 얻는다고 볼 수 있습니다.

 

그 후, 알고리즘은 이번 승객 정점과 짝을 지을 수 있는 택시 정점 중 $y_u$가 가장 작은 정점에 이번 승객 정점을 짝짓습니다. 앞에서 $y_u$의 오름차순으로 $L$이 순열을 이루는 것을 고려하면, 두 번째 단계는 가능한 택시 정점 중에서 순열 상 가장 첫 번째 나오는 택시 정점에 이번 승객 정점을 짝지어 주는 것으로 볼 수 있습니다. 따라서 이 알고리즘은 처음에 택시에 일종의 우선순위(혹은 랭킹)를 정하고 매번 승객을 우선순위가 높은 택시에 태우는 방법입니다. 이러한 이유로 이 알고리즘은 랭킹 알고리즘이라고 불립니다.

동작 예시

여러분의 이해를 돕기 위해 알고리즘이 어떻게 동작하는지를 구체적인 예시와 함께 설명하도록 하겠습니다. 다음 그림과 같은 입력이 주어진다고 하겠습니다. 이 입력에는 모든 정점이 매칭에 참여하는 완전 매칭(perfect matching)이 존재합니다.

그림 1. 온라인 이분 매칭 문제 입력의 예시.

승객 정점 $R$은 위에서부터 아래의 순서로 하나씩 들어 온다고 가정하겠습니다. 다음 애니메이션은 이 입력에 대해서 랭킹 알고리즘이 동작하는 한 가지 시행을 나타냅니다.

그림 2. 랭킹 알고리즘의 동작 예시. $L$의 정점의 왼쪽은 $[0,1]$에서 균등한 확률로 선정된 $y$ 값을 의미한다.

세 번째로 들어온 승객 정점은 인접한 택시 정점들이 이미 각각 다른 승객 정점과 짝이 지어졌기 때문에 짝지어지지 않은 상태로 계속 남아있게 됩니다. 따라서 이 알고리즘은 3의 크기를 갖는 매칭을 출력합니다.

매번 균등한 확률로 선택하는 방법보다 좋은 경쟁비를 갖는 직관적인 이유

이전 글에서 각 승객 정점 $v\in R$가 들어올 때마다 현재 짝을 지어줄 수 있는 인접한 택시 정점 중에서 균등하게 하나를 골라 짝을 지어주는 알고리즘은 $1/2$의 경쟁비를 갖는다는 것을 보였습니다. 반면 랭킹 알고리즘은 그보다 좋은 $1-1/e$의 경쟁비를 갖는다고 말씀드렸죠. 도대체 무슨 연유로 더 좋은 경쟁비를 얻게 된 것일까요? 아래에서 결국 이를 보이겠지만, 그다지 직관적으로 와닿는 증명은 아닐 수 있습니다. 따라서 먼저 기존의 균등한 확률로 선정하는 $1/2$-경쟁 알고리즘보다 랭킹 알고리즘이 어째서 더 좋은 경쟁비를 가질 수 있는지에 대해 간단한 예시를 통해 살펴 보도록 하겠습니다.

 

이전 알고리즘이 멍청하게 동작하는 입력 $G=(L\cup R,E)$는 다음과 같았습니다.(그림 3)

• $L_1:=\{u_1,\cdots ,u_d\}$, $L_2:=\{u_{d+1},\cdots ,u_{2d}\}$, $L:=L_1\cup L_2$
• $R_1:=\{v_1,\cdots ,v_d\}$, $R_2:=\{v_{d+1},\cdots ,v_{2d}\}$, $R:=R_1\cup R_2$
• $E:=\{(u_i,v_i)\mid i=1,\cdots ,2d\}\cup \{(u_i,v_j)\mid u_i\in L_2,v_j\in R_1\}$

그림 3. 매번 가능한 정점 중 균등하게 선택하는 알고리즘을 망치는 입력의 예시. $d=3$인 경우이다.

균등한 확률로 선택하는 알고리즘이 이 입력에서 완전 매칭을 찾을 확률은 얼마일까요? $R_1$의 정점들이 모두 매번 $L_1$의 자기 짝을 선택했어야 하므로, 그 확률은 $$\frac{1}{(d+1{)}^d}$$가 됩니다. 반면에 정확히 $d$의 크기를 갖는 매칭을 찾을 확률은 어떻게 될까요? $v_1$은 $d+1$ 개의 인접한 정점 중에서 $u_1$을 제외한 $d$ 개의 정점 중 아무 하나와 짝을 짓고, $v_2$는 남은 $d$ 개의 인접한 정점 중에서 $u_2$를 제외한 $d-1$ 개의 정점 중 아무거와 짝지어지면 됩니다. 이러한 패턴으로 $R_1$의 정점들을 모두 고려하면, 그 확률은 $$\frac{d}{d+1}\times \frac{d-1}{d}\times \cdots \times \frac{1}{2}=\frac{1}{d+1}$$이 된다는 것을 알 수 있습니다. 이를 통해 알고리즘이 좋은 매칭을 출력할 확률보다 나쁜 매칭을 출력할 확률이 현저히 높다는 것을 유추할 수 있습니다.

 

반면 같은 입력에 대해서 랭킹 알고리즘이 어떻게 동작할지 생각해 보겠습니다. 랭킹 알고리즘이 완전 매칭을 찾을 확률은 얼마일까요? $L$의 정점들로 이루어지는 임의의 순열 중에서 $L_2$의 모든 정점보다 $L_1$의 모든 정점이 앞의 순서에 위치하면 완전 매칭을 찾게 됩니다. 따라서 그 확률은 $$\frac{d!\cdot d!}{(2d)!}\approx \frac{(\sqrt{2\pi d}(d/e{)}^d{)}^2}{\sqrt{4\pi d}(2d/e{)}^{2d}}=\frac{\sqrt{\pi d}}{2^{2d}}$$가 됩니다. 여기서 근사치는 스털링 근사(Stirling's approximation)를 통하여 얻었습니다. 놀랍게도 이는 균등한 확률로 선택하는 알고리즘이 완전 매칭을 출력할 확률보다 훨씬 높은 수치임을 알 수 있습니다.

 

그렇다면 랭킹 알고리즘이 $d$의 크기를 갖는 매칭을 찾을 확률은 어떻게 될까요? 이는 임의의 순열 중에서 $L_1$의 모든 정점보다 $L_2$의 모든 정점이 앞에 나오는 순열일 경우에 발생하게 됩니다. 따라서 그 확률은 완전 매칭을 찾을 확률인 $\frac{\sqrt{\pi d}}{2^{2d}}$와 동일하죠. 흥미롭게도 이는 균등한 확률로 선택하는 알고리즘이 $d$의 크기를 갖는 매칭을 찾을 확률보다 현저히 작다는 것을 확인할 수 있습니다. 다시 말해, 랭킹 알고리즘은 앞의 알고리즘에 비해 크기가 큰 매칭을 더 높은 확률로 찾고, 크기가 작은 매칭을 더 낮은 확률로 찾는다는 것을 알 수 있습니다.

 

물론 랭킹 알고리즘이 이 입력에 대해서 균등하게 뽑는 알고리즘보다 좋다는 것을 보였다고 항상 좋다는 것을 보장할 수 있는 것은 아닙니다. 랭킹 알고리즘을 망가뜨리는 입력은 위 입력과 완전히 다른 모양일 수도 있죠. 그럼에도 랭킹 알고리즘이 랜덤 순열을 통해서 기존보다 좋은 성능을 보일 것이라는 점을 충분히 예측할 수 있겠습니다. 그리고 실제로 그렇기도 하고요. 이제부터는 랭킹 알고리즘이 좋은 경쟁비를 갖는다는 것을 엄밀히 증명해 보도록 하겠습니다.

선형 계획법으로 표현하기

랭킹 알고리즘은 온라인 매칭 분야에서 가장 유명한 알고리즘입니다. 따라서 이 알고리즘의 경쟁성을 증명하는 방법 또한 매우 다양한데요. 그중에서도 제가 이번에 소개할 방법([1])은 선형 계획법을 이용한 것입니다. 이 방법은 여러 다른 방법들에 비해 비교적 최근에 알려진 것이기도 하거니와, 개인적으로는 가장 이해하기 쉬운 방법이라고 생각하기 때문입니다.

 

임의의 정점 $v\in L\cup R$에 대해서 그 정점에 인접한 간선의 집합을 $\delta (v)$라고 표현하겠습니다. 임의의 간선 $e\in E$에 대해, $x_e$를 간선이 선택되었는지를 결정하는 변수(decision variable)로 정의하겠습니다. 즉, 만약 $e$가 선택이 되면 $x_e:=1$로, 그렇지 않으면 $x_e:=0$으로 설정된다고 생각하면 됩니다. 그러면 우리는 $G$ 위의 최대 매칭 문제(maximum matching problem)를 다음과 같은 정수 계획법(integer programming)으로 표현할 수 있습니다.

$$\begin{array}{}\text{(IP)}& \begin{array}{lrll}\text{maximize }& {\displaystyle \sum _{e\in E}{x}_e}& & \\ \text{subject to }& {\displaystyle \sum _{e\in \delta (u)}{x}_e}& \le 1,& \mathrm{\forall }u\in L,\\ & {\displaystyle \sum _{e\in \delta (v)}{x}_e}& \le 1,& \mathrm{\forall }v\in R,\\ & x_e& \in \{0,1\},& \mathrm{\forall }e\in E.\end{array}\end{array}$$

이때 첫 번째 제약 조건(constraint)은 임의의 택시 정점이 최대 한 명의 승객을 태울 수 있다는 것을 나타내고 있고, 두 번째 제약 조건은 임의의 승객이 최대 한 대의 택시에 탈 수 있다는 것을 나타냅니다.

 

많은 경우 우리는 마지막 정수 조건을 다음과 같이 완화하여 줍니다.

$$\begin{array}{}\text{(P)}& \begin{array}{lrll}\text{maximize }& {\displaystyle \sum _{e\in E}{x}_e}& & \\ \text{subject to }& {\displaystyle \sum _{e\in \delta (u)}{x}_e}& \le 1,& \mathrm{\forall }u\in L,\\ & {\displaystyle \sum _{e\in \delta (v)}{x}_e}& \le 1,& \mathrm{\forall }v\in R,\\ & x_e& \ge 0,& \mathrm{\forall }e\in E.\end{array}\end{array}$$

이렇게 바꾸어도 괜찮은 이유는 정수 조건이 있는 문제에서 가능한 해(feasible solution)가 모두 완화된 문제에서도 가능하기 때문입니다. 이는 다음의 정리로 귀결됩니다.

정리 1. 정수 계획법과 완화된 선형 계획법의 관계

---

$G$ 위의 최대 매칭을 $M^{\star }$, 문제 IP의 최적값(optimal value)을 $Z_{\mathrm{IP}}$, 문제 P의 최적값을 $Z_{\mathrm{P}}$라고 했을 때, 항상 $$|M^{\star }|=Z_{\mathrm{IP}}\le Z_{\mathrm{P}}$$가 만족한다.^[ㄱ]

[증명] $|M^{\star }|=Z_{\mathrm{IP}}$인 이유는 $M^{\star }$의 인접 벡터(incidence vector)가 문제 IP에 가능하고, 동시에 문제 IP의 임의의 가능한 해를 $G$ 위의 어떤 매칭의 인접 벡터로 생각할 수 있기 때문입니다. 부등식 $Z_{\mathrm{IP}}\le Z_{\mathrm{P}}$인 이유는 앞에서 설명한 대로 문제 IP의 어떤 최적해도 문제 P의 가능한 해가 되기 때문입니다. ■

 

선형 계획법을 사용하면 좋은 점 중 하나는 쌍대성(duality)을 사용할 수 있다는 것입니다. 선형 계획법의 쌍대성에 대해 잘 모르시는 분은 아래를 참조하세요.

2019/07/15 - [수학적 도구/Linear programming] - [선형 계획법] 쌍대성(Duality)

[선형 계획법] 쌍대성(Duality)

따라서 원 문제(primal program) P의 쌍대 문제(dual program) D를 구해 보면 다음과 같습니다.

$$\begin{array}{}\text{(D)}& \begin{array}{lrll}\text{minimize }& {\displaystyle \sum _{u\in L}{\alpha }_u+\sum _{v\in R}{\beta }_v}& & \\ \text{subject to }& {\alpha }_u+{\beta }_v& \ge 1,& \mathrm{\forall }(u,v)\in E,\\ & {\alpha }_u& \ge 0,& \mathrm{\forall }u\in L,\\ & {\beta }_v& \ge 0,& \mathrm{\forall }v\in R.\end{array}\end{array}$$ 여기서 ${\alpha }_u$는 문제 P의 첫 번째 제약 조건에 대응하는 쌍대 변수(dual variable)이고, ${\beta }_v$는 두 번째 제약 조건에 대응합니다.

 

쌍대성이 유용한 이유는 바로 쌍대 문제에 가능한 임의의 해에 대해, 그것의 목적 함수(objective function)의 값이 항상 원 문제에 가능한 임의의 해의 목적 함수 값의 상한(upper bound)을 이룬다는 점입니다. 증명은 생략합니다. 필요하신 분은 위 포스트를 참조하세요.

정리 2. 선형 계획법의 약한 쌍대성(weak duality)

---

원 문제 P에 가능한 임의의 해 $x$와 쌍대 문제 D에 가능한 임의의 해 $(\alpha ,\beta )$에 대해, 항상 $$\sum _{e\in E}{x}_e\le \sum _{u\in L}{\alpha }_u+\sum _{v\in R}{\beta }_v$$를 만족한다. 따라서 $x$에 최적해를 넣으면 $$Z_{\mathrm{P}}\le \sum _{u\in L}{\alpha }_u+\sum _{v\in R}{\beta }_v$$를 만족한다.

분석

이제부터 선형 계획법을 활용하여 알고리즘을 분석해 보도록 하겠습니다. 앞에서 우리는 쌍대성을 활용하여 최적값의 적절한 상한을 쌍대 문제의 목적 함수로 표현할 수 있다고 하였습니다. 따라서 온라인 이분 매칭을 해결하는 어떤 알고리즘이 매칭과 함께 적절한 쌍대 변수를 함께 출력한다면 이 알고리즘의 경쟁성을 분석할 때 요긴할 것입니다. 다음 정리는 이 아이디어를 구체적으로 나타낸 것입니다.

정리 3. 쌍대성을 활용한 알고리즘의 경쟁성 분석

---

온라인 이분 매칭을 해결하는 어떤 알고리즘이 임의의 입력에 대해 매칭 $M$과 함께 다음을 만족하는 어떤 벡터 $(\alpha ,\beta )\in {\mathbb{R}}_{+}^L\times {\mathbb{R}}_{+}^R$을 출력한다고 하자.

• $|M|\ge \sum _{u\in L}{\alpha }_u+\sum _{v\in R}{\beta }_v$
• 어떤 상수 $\mathrm{\Gamma }$에 대해, $\mathrm{\forall }(u,v)\in E$, ${\alpha }_u+{\beta }_v\ge \mathrm{\Gamma }$

그러면 이 알고리즘은 $\mathrm{\Gamma }$의 경쟁비를 갖는다.

[증명] $\bar{\alpha }=\alpha /\mathrm{\Gamma }$, $\bar{\beta }=\beta /\mathrm{\Gamma }$라고 하겠습니다. 그러면 두 번째 조건에 의해, 임의의 $(u,v)\in E$에 대해, ${\bar{\alpha }}_u+{\bar{\beta }}_v\ge 1$임을 알 수 있습니다. 따라서 $(\bar{\alpha },\bar{\beta })$는 쌍대 문제 D에 가능한 해입니다. 여기서 첫 번째 조건을 활용하면, $$\frac{|M|}{\mathrm{\Gamma }}\ge \sum _{u\in L}{\bar{\alpha }}_u+\sum _{v\in R}{\bar{\beta }}_v\ge Z_{\mathrm{P}}\ge |M^{\star }|$$임을 이끌어낼 수 있습니다. 이때, 두 번째 부등식은 정리 2에서, 세 번째 부등식은 정리 1에서 유추할 수 있습니다. ■

짝지어진 정점들에다 1의 값 분배하기

이 정리를 활용하기 위해서 우리도 알고리즘 1을 약간 수정하여 $M$과 함께 어떤 $(\alpha ,\beta )$를 출력하도록 만들어 봅시다. 어떻게 하면 정리 3의 조건들을 모두 만족시키는 벡터를 만들어낼 수 있을까요? 일단 첫 번째 조건을 만족시키는 방법을 생각해 봅시다. 언젠가 알고리즘이 어떤 간선 $(u,v)\in E$를 매칭에 넣는다고 합시다. 그러면 매칭의 크기가 1이 증가하겠죠. 이때 만약 우리가 ${\alpha }_u+{\beta }_v=1$이 되도록 양 끝점의 벡터값을 증가시켜 준다면 첫 번째 조건은 반드시 만족하게 될 겁니다.

 

문제는 1의 값을 어떻게 "분배"하느냐에 달려있죠. 가장 쉽게 생각할 수 있는 것은 ${\alpha }_u={\beta }_v=1/2$씩 주는 것입니다. 하지만 이렇게 분배하면 두 번째 조건에서 $1/2$보다 좋은 $\mathrm{\Gamma }$를 설정할 수 없습니다.

그림 4. 결정론적으로 ${\alpha }_u={\beta }_v=1/2$씩 설정했을 때 $\mathrm{\Gamma }=1/2$이 최선인 예시. 간선 $(u1,v2)$, $(u2,v1)$에 대해서는 어떻게 하든 각 끝점에 해당하는 쌍대 변수의 합이 $1/2$을 모두 넘지 못한다.

사실 ${\alpha }_u$와 ${\beta }_v$를 어떻게 분배하더라도 결정론적으로는 $1/2$보다 좋은 $\mathrm{\Gamma }$를 얻을 수 없습니다. 그것이 가능했다면 정리 3을 통해 $1/2$보다 좋은 경쟁비를 갖는 결정론적 알고리즘이 존재한다는 소리이고, 이는 이전에 보인 바에 의해 모순이 되기 때문이죠.

 

우리가 지금 고려하는 알고리즘은 내부 시행에 따라 결과가 바뀌는 랜덤 알고리즘입니다. 그러니 분배하는 것도 랜덤하게 해 보죠. 랭킹 알고리즘에서 랜덤성이 활용된 곳은 각 택시 정점 $u\in L$에 대해 $y_u$를 선택한 것입니다. 따라서 이에 맞추어 랭킹 알고리즘이 간선 $(u,v)$를 매칭에 넣을 때 ${\alpha }_u$는 $g(y_u)$만큼, ${\beta }_v$에는 $1-g(y_u)$만큼 분배한다면 정리 3의 첫 번째 조건은 항상 성립하게 됩니다. 다음은 알고리즘 1에서 위 작업을 추가한 것입니다.

알고리즘 2. Ranking algorithm with dual variables

---

초기 입력: 택시 정점 집합 $L$

출력: 매칭, 벡터 $(\alpha ,\beta )\in {\mathbb{R}}^L\times {\mathbb{R}}^R$

 

1. 각 $u\in L$에 대해, $y_u$를 $[0,1]$에서 균등한 확률(uniformly at random)로 고른다.
2. 각 $u\in L$에 대해, ${\alpha }_u\leftarrow 0$
3. 매번 $v\in R$가 들어올 때마다, $v$에 인접하면서 아직 매칭에 참여하지 않은 택시 정점 중에서 $y_u$가 가장 작은 $u\in L$와 짝을 짓고 ${\alpha }_u\leftarrow g(y_u)$, ${\beta }_v\leftarrow 1-g(y_u)$로 설정한다. 만약 그러한 택시 정점이 존재하지 않으면 $v$는 짝을 짓지 못한 상태로 남으며 ${\beta }_v\leftarrow 0$으로 둔다.

추가된 단계는 붉은색 굵은 글씨로 표시하였습니다. 이는 분석을 위해서 추가한 것이므로 실제로는 알고리즘 1만 구현하는 것으로 충분합니다.

 

알고리즘 2를 통해서 출력되는 벡터 $(\alpha ,\beta )$도 결국에는 $y_u$들의 값에 의해서 결정되는 확률 변수들(random variables)입니다. 따라서 정리 3을 그대로 적용할 수 없죠. 하지만 우리는 여전히 유사한 결론을 이끌어낼 수 있습니다.

정리 4. 쌍대성을 활용한 랜덤 알고리즘의 경쟁성 분석

---

온라인 이분 매칭을 해결하는 어떤 랜덤 알고리즘이 임의의 입력에 대해 매칭 $M$과 함께 다음을 만족하는 어떤 벡터 $(\alpha ,\beta )\in {\mathbb{R}}_{+}^L\times {\mathbb{R}}_{+}^R$을 출력한다고 하자.

• $|M|\ge \sum _{u\in L}{\alpha }_u+\sum _{v\in R}{\beta }_v$
• 어떤 상수 $\mathrm{\Gamma }$에 대해, $\mathrm{\forall }(u,v)\in E$, $\mathbb{E}[{\alpha }_u+{\beta }_v]\ge \mathrm{\Gamma }$

그러면 이 알고리즘은 $\mathrm{\Gamma }$의 경쟁비를 갖는 랜덤 알고리즘이다.

[증명] 정리 3의 증명과 비슷합니다. 이번에는 $\bar{\alpha }:=\mathbb{E}[\alpha ]/\mathrm{\Gamma }$, $\bar{\beta }:=\mathbb{E}[\beta ]/\mathrm{\Gamma }$로 두겠습니다. 그러면 기댓값의 선형성(linearity of expectation)에 의해 두 번째 조건이 임의의 $(u,v)\in E$에 대해 ${\bar{\alpha }}_u+{\bar{\beta }}_v\ge 1$을 유도한다는 것을 알 수 있습니다. 첫 번째 조건에 기댓값을 취하면 $$\frac{\mathbb{E}[|M|]}{\mathrm{\Gamma }}\ge \sum _{u\in L}{\bar{\alpha }}_u+\sum _{v\in R}{\bar{\beta }}_v\ge |M^{\star }|$$를 이끌어낼 수 있습니다. ■

적절한 분배 함수 $g$의 성질

알고리즘 2가 출력하는 $(\alpha ,\beta )$가 정리 4의 첫 번째 조건을 만족한다는 것은 앞에서 보였습니다. 따라서 남은 것은 $1/2$보다 큰 $\mathrm{\Gamma }$에 대해 두 번째 조건을 만족하도록 적절히 분배하는 $g$를 찾는 것입니다. 결론부터 말씀드리면 우리는 다음의 성질들을 만족하는 $g$를 고려할 것입니다.

1. $g$는 $[0,1]$에서 $[0,1]$로 간다.
2. $g$는 단조 증가 함수(non-decreasing function)이다
3. $g(1)=1$이다.

성질 A가 필요한 이유는 알고리즘 2에서 ${\alpha }_u\leftarrow g(y_u),{\beta }_v\leftarrow 1-g(y_u)$로 두는데 $(\alpha ,\beta )\ge 0$을 만족해야 하기 때문입니다. 성질 B와 C가 필요한 이유는 아래에서 확인할 수 있습니다.

두 번째 조건 증명

위와 같은 성질을 만족하는 $g$를 가지고 오면, 정리 4의 두 번째 조건을 보일 수 있습니다. 좀 더 엄밀히 말하면, 임의의 간선 $(u,v)$에 대해서 알고리즘 2의 $\mathbb{E}[{\alpha }_u+{\beta }_v]$의 하한(lower bound)을 $g$로 표현할 수 있게 됩니다. 모든 $L$의 $y$ 값을 한번에 몽땅 고려하는 것은 어렵기 때문에, $u$를 제외한 나머지 정점들의 $y$는 특정한 값으로 고정되었다고 가정하겠습니다. 이를 $y_{-u}$라고 부르도록 하죠. 만약 임의의 $y_{-u}$에 대해, 조건부 기댓값 $$\mathbb{E}[{\alpha }_u+{\beta }_v\mid y_{-u}\text{ is fixed}]\ge \mathrm{\Gamma }$$를 보인다면, 이는 곧바로 정리 4의 두 번째 조건을 이끌어 내게 됩니다.^[ㄴ]

 

이제 $G$에서 $u$를 제외한 입력을 $G-u$라고 하죠. 이 입력에 대해서 알고리즘 2를 수행시켜 보겠습니다. 이때, 단계 1에서 뽑는 $y$ 값들은 앞에서 고정한 $y_{-u}$와 같도록 둡니다. 이 입력에서, 현재 고려하는 간선 $(u,v)$의 승객 정점 $v$가 어떤 택시 정점과 짝지어졌다면 그 택시 정점을 $u^{\ast }$, 그리고 그것의 $y$ 값을 $y^{\ast }$라고 하겠습니다. 만약 짝지어지지 않았다면 $y^{\ast }:=1$로 정의하겠습니다.

 

그러면 다음의 두 정리들을 증명할 수 있습니다. 첫 번째 정리는 고려하는 간선의 택시 정점 $u$가 $G$가 입력된 때에 반드시 짝이 지어질 조건을 나타낸 것입니다.

정리 5. 택시 정점 $u$가 짝지어질 조건

---

$L\setminus \{u\}$의 $y$ 값이 $y_{-u}$로 고정된다는 조건 하에, 알고리즘 2가 $G$ 입력에 대해 수행될 때, 만약 $y_u<y^{\ast }$이면 $u$는 어떤 승객 정점(꼭 $v$일 필요는 없다)과 반드시 짝이 지어진다. 따라서, $$\mathbb{E}[{\alpha }_u\mid y_{-u}\text{ is fixed}]\ge {\int }_0^{y^{\ast }}g(y)dy$$를 만족한다.

[증명] 만약 $G$가 입력된 알고리즘 2가 $v$가 들어올 때까지 $u$를 다른 승객 정점과 짝짓지 않았다면, $y_{-u}$가 고정되었으므로 그때까지는 $G-u$가 입력된 때와 동일하게 동작했을 것입니다. $G-u$가 입력된 알고리즘 2에서 $v$가 짝지어지지 않았다면 이번에 $G$가 입력된 때에는 $y_u$가 어떤 값이든 $u$와 $v$를 짝지어 줄 것입니다. $y_u\le 1$이라는 점은 자명하므로 이 경우는 쉽게 정리의 명제가 성립합니다.

 

반대로 $u^{\ast }$가 정의된 경우를 살펴 보죠. $G$가 입력된 알고리즘 2에서 $v$가 들어왔을 때 이제는 $u$와 $u^{\ast }$ 모두 짝지어지지 않은 상태가 됩니다. $G-u$가 입력된 때에는 $u^{\ast }$를 $v$와 짝지어 주었으므로 $u$를 제외하면 $u^{\ast }$가 이때 짝지어줄 수 있는 택시 정점 중 가장 작은 $y$ 값을 가진다는 것을 유추할 수 있습니다. 따라서 $y_u<y^{\ast }$이기만 하다면 $G$가 입력된 알고리즘 2는 $v$를 $u$와 짝지어 줄 것입니다.

 

알고리즘 2에서 $y_u$는 $[0,1]$에서 균등한 확률로 뽑히고, 만약 $[0,y^{\ast })$ 사이의 값이라면 반드시 짝이 지어질 것이므로 ${\alpha }_u$의 기댓값은 ${\int }_0^{y^{\ast }}g(y)dy$보다는 크거나 같습니다. ■

 

반대로 고려하는 간선의 승객 정점 $v$는 어떻게 될까요?

정리 6. 승객 정점 $v$가 짝지어질 조건

---

$L\setminus \{u\}$의 $y$ 값이 $y_{-u}$로 고정된 조건 하에, 알고리즘 2가 $G$ 입력에 대해 수행될 때, ${\beta }_v\ge 1-g(y^{\ast })$를 항상 만족한다.

[증명] 만약 $G-u$가 입력된 때에 $v$가 짝지어지지 않았으면 $y^{\ast }=1$로 정의하였고, 조건 C에 의해 $g(y^{\ast })=1$이 되어 ${\beta }_v\ge 0$을 만족하기만 하면 됩니다. 이는 어떤 입력에 대해서도 자명하게 성립합니다. 따라서 지금부터 $u^{\ast }$가 정의되었다고 가정하겠습니다.

 

어떤 승객 정점이 막 들어와서 아직 짝을 찾기 전에, $G$가 입력된 알고리즘과 $G-u$가 입력된 알고리즘에서 아직 짝지어지지 않은 택시 정점의 집합을 각각 $L_{\mathsf{exp}}$, $L_{\mathsf{exp}}^{\prime }$라고 하겠습니다. 이제부터 항상 $$L_{\mathsf{exp}}\supseteq L_{\mathsf{exp}}^{\prime }$$을 만족한다는 것을 보이도록 하겠습니다.

 

승객이 들어오는 순서에 따라 귀납적으로 보일 것입니다. 첫 번째 승객이 들어왔을 때는 $$L=L_{\mathsf{exp}}\supseteq L_{\mathsf{exp}}^{\prime }=L\setminus \{u\}$$이므로 바로 성립합니다. 임의의 승객 $v^{\prime }$이 들어왔을 때까지 명제가 성립한다고 가정하겠습니다. $G$가 입력된 알고리즘과 $G-u$가 입력된 알고리즘에서 각각 처리한 후에도 명제가 성립한다면 증명이 완료됩니다.

 

먼저 $G-u$가 입력된 알고리즘에서 $v^{\prime }$이 짝지어지지 못했다고 해보죠. 그런데 이때, 위 명제가 거짓이 되려면 $G$가 입력된 알고리즘에서 $v^{\prime }$이 $L_{\mathsf{exp}}\cap L_{\mathsf{exp}}^{\prime }=L_{\mathsf{exp}}^{\prime }$의 택시 정점 중 하나와 짝이 지어져야 합니다. 이는 $G-u$가 입력된 알고리즘에서 $v^{\prime }$에 짝을 지을 수 있는 택시 정점이 있었다는 의미이므로 모순이 됩니다.

 

이번에는 $G-u$가 입력된 알고리즘에서 $v^{\prime }$이 어떤 $u_1\in L_{\mathsf{exp}}^{\prime }$과 짝이 지어졌다고 합시다. 귀납 가정(induction hypothesis)에 의해 $u_1\in L_{\mathsf{exp}}$이고, 따라서 $G$가 입력된 알고리즘에서도 $v^{\prime }$이 들어왔을 때 $u_1$은 짝지어지지 않은 상태입니다. 그럼에도 명제가 거짓이 되려면 $G$가 입력된 알고리즘에서는 $u_1$과는 다른 $u_2$와 짝을 지어주어야 하며, 이때 $u_2\in L_{\mathsf{exp}}\cap L_{\mathsf{exp}}^{\prime }=L_{\mathsf{exp}}^{\prime }$을 만족해야 합니다. 이는 $u_2$가 $G-u$가 입력된 알고리즘에서도 $v^{\prime }$이 들어왔을 때 아직 짝이 지어지지 않은 상태라는 뜻입니다. 알고리즘 2는 가능한 작은 $y$ 값을 갖는 택시와 짝을 지어주므로 이 상황에서 두 입력에 대해 다르게 동작했다는 것은 모순입니다.

 

따라서 $G$가 입력된 알고리즘에서 $v$가 들어왔을 때, $u^{\ast }$는 반드시 짝이 지어지지 않은 상태입니다. 그러므로 $y^{\ast }$보다 크지 않은 $y$ 값을 갖는 정점과 짝이 지어질 것입니다. 앞의 정의에서 $g$는 단조 증가 함수라고 했으므로(성질 B), ${\beta }_v\ge 1-g(y^{\ast })$를 만족하게 됩니다. ■

 

정리 5와 6을 통해 우리는 적절한 분배 함수 $g$가 주어졌을 때, 임의의 간선 $(u,v)$에 대해, $$\mathbb{E}[{\alpha }_u+{\beta }_v\mid y_{-u}\text{ is fixed}]\ge {\int }_0^{y^{\ast }}g(y)dy+(1-g(y^{\ast }))$$임을 알 수 있습니다. 따라서 만약 $g$가 임의의 $\theta \in [0,1]$에 대해서 $${\int }_0^{\theta }g(y)dy+(1-g(\theta ))\ge \mathrm{\Gamma }$$를 만족함을 보인다면, 모든 증명이 완료됩니다.

 

가장 좋은 $\mathrm{\Gamma }$를 주는 $g$는 무엇일까요? 이는 $g(y)=e^{y-1}$로 잡으면 됩니다. 그러면 $g$는 성질 A, B, C를 모두 만족하면서 $\mathrm{\Gamma }=1-1/e$가 되는 것을 확인할 수 있습니다. 아래 그림은 이를 나타낸 것으로 빨간 실선은 $g(x)=e^{x-1}$을, 초록 실선은 $y={\int }_0^{x}g(y)dy+(1-g(x))$를 나타낸 것입니다.

마치며

이것으로 온라인 이분 매칭을 해결하는 $(1-1/e)$-경쟁 알고리즘인 랭킹 알고리즘에 대해서 알아 보았습니다. 과연 이보다 더 좋은 경쟁비를 갖는 알고리즘을 만들 수 있을까요? 안타깝지만 이 경쟁비가 최선이라는 사실이 잘 알려져 있습니다. 다음 번에는 해당 하한을 보이는 방법을 적어 볼까 합니다. 아직 좀 더 공부 중인데, 이것 저것 필요한 게 많더라고요. 너무 어렵지 않으면 정리해 보는 것도 좋겠다고 생각합니다.

 

온라인 이분 매칭은 조합론적 온라인 알고리즘 분야에서 가장 유명한 문제로 다양한 변종(variant)이 존재합니다. 게다가 최근 온라인 이분 매칭을 확장한 여러 흥미로운 결과도 많이 나왔습니다. 개인적으로도 온라인 매칭을 주로 연구하는 중인데, 재미있는 논문도 많이 있고 정리해 봄직한 주제도 좀 있습니다. 기회가 되면 최신 동향도 적어 보도록 하겠습니다.

 

궁금하신 점이 있으시거나, 글에 오류가 있으면 알려 주세요. 고맙습니다. :)

참조

[1] Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. "Randomized primal-dual analysis of ranking for online bipartite matching." In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pp. 101-107. Society for Industrial and Applied Mathematics, 2013.

각주

[ㄱ] 사실 $G$가 이분 그래프이면 $Z_{\mathrm{IP}}=Z_{\mathrm{P}}$도 만족합니다. 본문에서는 이 사실이 증명에 필요 없어서 생략하였습니다.

 

[ㄴ] $\mathrm{\forall }Y$, $\mathbb{E}[X\mid Y]\ge \mathrm{\Gamma }$이면, $$\mathbb{E}[X]=\sum _{\mathrm{\forall }Y}\mathbb{E}[X\mid Y]Pr[Y]\ge \sum _{\mathrm{\forall }Y}\mathrm{\Gamma }\cdot Pr[Y]=\mathrm{\Gamma }$$이기 때문입니다.