스키 대여 문제의 경쟁비 하한 (Lower Bound of Competitive Ratio for Ski Rental)

Photo by Andrés Canchón on Unsplash

스키 대여 문제(ski rental problem)는 대표적인 온라인 문제(online problem) 중 하나입니다. 이 문제에서는 스키장이 언제 폐장할지 모르는 상황에서 우리는 매일 스키를 대여하거나 구매해야 합니다. 한번 스키를 구매하면 이후 계속 사용할 수 있지만 대여를 하면 당일만 사용할 수 있습니다. 이 문제의 목표는 최소의 비용으로 폐장할 때까지 스키를 타는 방법을 찾는 것입니다.

 

이전 글에서는 이 문제를 결정론적(deterministic)으로 해결하는 2-경쟁 알고리즘(competitive algorithm)이 존재하고, 해당 경쟁비가 결정론적 알고리즘으로서는 이룰 수 있는 최선의 결과라는 것을 보였습니다.

2020/03/15 - [온라인 알고리즘/Ski rental] - [스키 대여 문제 / Ski Rental Problem] 문제 정의 & Break-Even Algorithm

[스키 대여 문제 / Ski Rental Problem] 문제 정의 & Break-Even Algorithm

반면, 동일한 입력에 대해서도 매 시행마다 결과가 달라질 수 있는 랜덤 알고리즘(randomized algorithm)을 사용하면 이보다 좋은 \(\frac{e}{e-1} \approx 1.582 \)의 경쟁비를 얻을 수 있었습니다.

2020/03/16 - [온라인 알고리즘/Ski rental] - [스키 대여 문제 / Ski Rental Problem] 선형 계획법을 이용한 Randomized Algorithm

[스키 대여 문제 / Ski Rental Problem] 선형 계획법을 이용한 Randomized Algorithm

그러면 다음과 같은 질문이 자연스럽게 따라옵니다.

과연 \(\frac{e}{e-1}\)보다 좋은 경쟁비를 갖는 알고리즘을 만들 수 있을까?

흥미롭게도 위 질문에 대한 정답은 "불가능하다"는 것입니다. 좀더 엄밀히 말하면 이 글에서는 다음의 정리를 증명합니다.

정리 1. 스키 대여 문제의 경쟁비 하한

---

스키 대여 문제를 경쟁적으로 해결하는 (랜덤 알고리즘을 포함하는) 어떤 알고리즘도 임의의 무지각형 상대방(oblivious adversary)을 상대로 \( \frac{e}{e-1} \)보다 좋은 경쟁비를 얻을 수 없다.

이 글은 온라인 알고리즘(online algorithm) 및 경쟁성 분석(competitive analysis)에 대한 내용을 숙지하고 있다는 전제 아래 작성되었습니다. 이 내용에 익숙하지 않으시면 다음 포스트를 참조하시기 바랍니다.

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

온라인 알고리즘 (Online Algorithm)

문제 정의

스키 대여 문제를 빠르게 정의하고 넘어가겠습니다. 매일 아침 우리는 스키를 대여하거나 구매할 수 있습니다. 스키를 대여하면 그날 하루 사용할 수 있고 가격은 $1입니다. 스키를 구매하면 그날부터 계속 사용할 수 있으며 가격은 $B입니다. 분석의 편의를 위해 B는 항상 정수라고 가정하겠습니다. 첫째 날은 스키장이 항상 개장하지만, 매번 다음날 스키장이 열지 닫을지는 알 수 없습니다. 우리의 목표는 최소의 비용으로 스키장이 개장하는 모든 날 스키를 타는 것입니다.

 

만약 스키장이 언제 닫을지 안다면 이 문제는 매우 쉽게 해결됩니다. 만약 \(B\) 번째 날 전에 폐장한다면 스키를 매일 대여하는 것이 최적의 방법이며, 그 이후에 폐장한다면 첫날 스키를 구매하는 것이 이득입니다. 하지만 언제 폐장할지 모르기에 첫날에 구매할지 계속 대여할지 속단할 수 없으며, 이런 까닭에 이 문제가 어려워집니다.

스키 대여 문제를 해결하는 알고리즘의 성질

이 문제를 경쟁적으로 해결하는 알고리즘은 어떤 방식으로 동작할까요? 매일 특정한 확률로 스키를 구매하거나 구매하지 않을 것입니다. 게다가 만약 구매하지 않는다면 반드시 스키를 대여해야 합니다. 이를 통해서 매 \(t\) 번째 날이 끝날 때 알고리즘의 비용의 기댓값을 다음과 같은 식으로 표현할 수 있게 됩니다.

정리 2. 알고리즘의 비용의 기댓값

---

어떤 랜덤 알고리즘이 매 \(i\) 번째 날 이전에 스키를 구매할 확률을 \(p_i\)라고 하자. 그러면 \(t\) 번째 날이 끝날 때 알고리즘이 출력하는 답의 비용의 기댓값은 \[ p_t B + \sum_{i = 1}^t (1 - p_i) \]이다.

[증명] 직관적으로 설명하자면, \(t\) 번째 날 이전에 스키를 구매할 확률이 \(p_t\)이므로 그 기댓값은 \(p_t B\)가 되며, 반대로 스키를 구매하지 않으면 반드시 대여를 해야 하므로 매 \(i \leq t\) 번째 날 스키를 대여할 확률은 \( 1-p_i \)가 됩니다. 이를 모두 더한 값이 비용의 기댓값이 됩니다.

 

좀더 상세한 증명은 다음과 같습니다. 정확히 \(i\) 번째 날에 스키를 구매할 확률은 \( p_i - p_{i - 1} \)로 표현됩니다. (단, \(p_0 = 0\)이라고 하겠습니다.) 또한, 정확히 \(i\)번째 날에 스키를 구매했다는 뜻은 전날까지는 계속 스키를 대여했다는 의미이므로 \( B + (i - 1) \)의 비용이 발생하게 됩니다. 마지막으로 \(t\) 번째 날까지 스키를 구매하지 않았다면 비용은 정확히 \(t\)가 발생하며, 그 확률은 \(1 - p_t\)입니다. 따라서 이를 정리하면

\[ \begin{array}{l} \displaystyle \sum_{i = 1}^t (p_i - p_{i - 1})(B + (i - 1)) + (1 - p_t)t \\ \displaystyle = \sum_{i = 1}^t (p_i - p_{i - 1})B + (t - 1)p_t - \sum_{i = 1}^{t - 1} p_i + t - tp_t \\ \displaystyle = p_t B + \sum_{i = 1}^t (1 - p_i) \end{array}\]

와 같습니다. ■

 

이 글의 목표는 어떤 알고리즘도, 심지어는 랜덤 알고리즘도 포함해서 \(\frac{e}{e-1}\)보다 좋은 경쟁비를 가질 수 없다는 것을 보이는 것입니다. 이를 분석하는 것이 쉽지 않은 이유는 상상할 수 있는 모든 알고리즘을 상정하는 것부터 쉽지 않기 때문입니다. 따라서 일반성을 잃지 않고 고려할 알고리즘의 폭을 줄일 수 있다면 우리에게 큰 도움이 될 것입니다. 다음 정리는 \(B\) 번째 날 이전에는 반드시 스키를 구매하는 알고리즘만 고려해도 괜찮다는 것을 알려줍니다.

정리 3. 고려할 알고리즘의 특징

---

스키 대여 문제를 \(\rho\)의 경쟁비로 해결하는 어떤 (랜덤) 알고리즘 \(\mathcal{A}\)가 주어졌을 때, 그보다 나쁘지 않은 경쟁비로 \(B\) 번째 날 이전에는 반드시 스키를 구매하는 (랜덤) 알고리즘 \(\mathcal{B}\)를 만들 수 있다.

[증명] 먼저 \(\mathcal{A}\)가 \(i\) 번째 날 이전에 구매할 확률을 \(p_i\)라고 하겠습니다. 만약 \(p_B = 1\)이라면, 이미 \(\mathcal{A}\)가 \(B\) 번째 날 이전에는 반드시 스키를 구매한다는 의미이므로 \(\mathcal{A}\)를 \( \mathcal{B} \)로 두면 됩니다.

 

따라서 남은 경우는 \( p_B < 1 \)일 때입니다. 이번에는 매 \(i\) 마다 새로운 확률 \(p'_i\)를 다음과 같이 정의하겠습니다. \[ p'_i = \left\{ \begin{array}{ll} p_i, & \text{ if } i < B, \\ 1, & \text{ otherwise.}\end{array} \right. \] 그러고는 \( \mathcal{B} \)가 \(i\) 번째 날 이전에 스키를 구매할 확률이 \( p'_i \)가 되도록 \(\mathcal{B}\)를 만들겠습니다. 이는 다음과 같이 만들 수 있습니다. \(\alpha\)를 \([0, 1)\)에서 균등한 확률(uniformly at random)로 하나 뽑습니다. 만약 \( \alpha \in [p'_{i - 1}, p'_i) \)에 속하면 \(\mathcal{B}\)는 \(i\) 번째 날에 스키를 구매하고 그 전날까지는 대여하도록 만들면 됩니다.

 

\(\mathcal{B} \)가 동작하는 것을 살펴 보면 \(B\) 번째 날이 오기 전까지는 \( \mathcal{A}\)와 "확률적으로" 동일하게 수행하다가 \(B\) 번째 날에는 그때까지 스키를 사지 않았다면 그냥 사버린다는 것을 확인할 수 있습니다. 이제 이렇게 얻은 \( \mathcal{B} \)의 경쟁비가 \( \mathcal{A} \)보다 나쁘지 않다는 것을 보이도록 하겠습니다. 먼저 \(B\) 번째 날 전까지는 \( \mathcal{A} \)와 \( \mathcal{B} \)가 확률적으로 동일하게 동작하므로 \(\mathcal{A}\)와 \(\mathcal{B}\)의 비용의 기댓값이 서로 같습니다. 따라서 \(B\) 번째 날 이전에 폐장한다면 \( \mathcal{B} \)도 여전히 \(\rho\)의 경쟁비를 가질 것입니다.

 

이제 스키장이 \(B\) 번째 날 이후에 폐장한다고 하죠. 우리는 언젠가는 \( \mathcal{A} \)가 스키를 반드시 구매한다고 가정할 수 있습니다. 그렇지 않다면 스키장이 폐장하지 않는 입력에 대해서는 그 비용이 무한정 커지기 때문입니다. 그때를 \(t > B\) 번째 날이라고 하겠습니다. 즉, \( p_t = 1 \)이 됩니다.^[ㄱ] \(\mathcal{A}\)가 \( \rho \)-경쟁 알고리즘이라는 사실과 정리 2에 의해, 어떤 음이 아닌 상수 \(c\)에 대해 \[ B + \sum_{i = 1}^t (1 - p_i) \leq \rho B + c \tag{1} \]가 만족하게 됩니다.

 

\(  \mathcal{B} \)는 \(B\) 번째 날에는 반드시 스키를 구매하기 때문에 \( B \) 번째 날 이후에 폐장되는 경우에는 그 비용의 기댓값이 항상 \[ B + \sum_{i = 1}^{B - 1} (1 - p'_i) = B + \sum_{i - 1}^{B-1}(1 - p_i) \tag{2} \]이 됩니다. 여기서 등식은 \( i < B \)에 대해, \( p'_i = p_i \)라고 하였으므로 성립합니다. 각 \( p_i \)는 모두 확률이기 때문에 반드시 0과 1 사이의 값입니다. 그러므로 식 2가 식 1의 좌변보다 크지 않다는 것을 쉽게 확인할 수 있습니다. 따라서 \(\mathcal{B}\)는 \( \mathcal{A} \)보다 나쁘지 않은 경쟁비를 가집니다. ■

 

위 증명에서 \(\mathcal{B}\)를 만드는 방법은 이전 글에서 더 자세히 설명하였으니 궁금하신 분들은 다음 글의 알고리즘 3을 참조하세요.

2020/03/16 - [온라인 알고리즘/Ski rental] - [스키 대여 문제 / Ski Rental Problem] 선형 계획법을 이용한 Randomized Algorithm

[스키 대여 문제 / Ski Rental Problem] 선형 계획법을 이용한 Randomized Algorithm

경쟁비의 하한 구하기

이제 정리 1을 증명해 보도록 합시다. 정리 3을 통해 우리는 \(B\) 번째 날 이전에는 반드시 스키를 구매하는 알고리즘만 고려해도 괜찮다는 것을 보였습니다. 이 중 아무 알고리즘 하나를 가지고 오도록 하겠습니다. 위에서 하던 것과 비슷하게, 이 알고리즘이 \(i\) 번째 날 이전에 스키를 구매할 확률을 \(p_i\)라고 하겠습니다. \(p_i\)들은 일종의 누적 확률(cumulative probability)이므로, \[ 0 \leq p_1 \leq p_2 \leq \cdots \leq p_B = 1 \tag{3} \]이 성립합니다.

 

우리의 목표는 이 알고리즘이 임의의 무지각형 상대방에 대항하여 \( \rho \)의 경쟁비를 가질 때, 가능한 \( \rho \)의 하한(lower bound)을 찾는 것입니다. 이를 위해서 먼저 상수 \(c\)를 하나 고정하고, 총 \(B\) 개의 무지각형 상대방을 다음과 같이 가지고 오겠습니다. 첫 번째는 첫날만 스키장을 개장하고 다음날 바로 폐장하는 상대방입니다. 정리 2에 의해, 알고리즘은 \[ p_1 B + (1 - p_1) \leq \rho + c \]를 만족해야 합니다. 두 번째는 둘째 날까지 개장하는 상대방입니다. 그러면 비슷한 논의로 \[ p_2 B + (1 - p_1) + (1 - p_2) \leq 2\rho + c \]를 만족해야 합니다. 이제 규칙을 찾으셨으리라 생각합니다. 바로 \(t = 1, \cdots, B\) 번째 무지각형 상대방은 \(t\) 번째 날까지 스키장을 개장하도록 만드는 것입니다. 그러면, 우리가 고려하는 알고리즘은 \[ p_t B + \sum_{i = 1}^t (1 - p_t) \leq \rho t + c \tag{4} \]를 반드시 만족해야 합니다.

 

따라서 식 3과 4를 모두 만족하는 \(\rho\) 중에서 가장 작은 값을 찾는다면, 우리는 어떤 랜덤 알고리즘도 그보다 좋은 경쟁비를 가질 수 없다고 결론을 지을 수 있습니다. 일단 식 3은 고려하지 말고 식 4에만 집중해 봅시다. 각 식에서 \(\rho\)는 우변에 있으므로 부등식이 등식이 될 때가 가장 작은 \(\rho\)를 이루게 될 때일 것입니다. 따라서 모든 \(t = 1, \cdots, B\)에 대해, \[ p_t B + \sum_{i = 1}^t (1 - p_i) = \rho t + c \]가 될 때의 \( \rho \)와 \(p_i\)를 구해보도록 하겠습니다. 먼저 \(t = 1\)일 때는 \( p_1 B + (1 - p_1) = \rho + c \)이므로, 이를 \(p_1\)에 대해 정리하면 \[ p_1 = \frac{\rho - 1 + c}{B - 1}  \tag{5} \]이 됩니다.

 

다음으로 모든 \(t = 2, \cdots, B\)에 대해서는 \( p_t B + \sum_{i = 1}^t (1 - p_t) = \rho t + c \)가 성립합니다. 이 때, \(t - 1\)에 대해서도 \(p_{t - 1}B + \sum_{i = 1}^{t - 1} (1 - p_i) = \rho (t - 1) + c \)가 성립하므로, 좌변을 \[ \begin{array}{l} p_t B + \sum_{i = 1}^t (1 - p_i) \\ = p_t B + (1 - p_t) + \sum_{i = 1}^{t - 1}(1 - p_i) \\ = p_t B + (1 - p_t) + \rho  (t - 1) + c - p_{t-1} B\end{array} \]와 같이 다시 쓸 수 있고, 이를 다시 식에 대입한 후 정리하면 \[ p_t = \frac{B}{B - 1} p_{t - 1} + \frac{\rho - 1}{B - 1} \]의 점화식을 얻을 수 있습니다. 여기서 \( a := \frac{B}{B - 1}, b := \frac{\rho - 1}{B - 1} \)로 두면 \( p_t = a p_{t - 1} + b \) 형식으로 정리가 되며, 이를 닫힌 형태(closed form)로 표현하면, \[ p_t = a^{t - 1} p_1 + b \frac{a^{t - 1} - 1}{a - 1} \]이 됩니다. 이렇게 구한 \(p_t\)는 식 3에서 등식을 제외한 부분을 모두 만족한다는 것을 쉽게 보일 수 있습니다.

 

이제 남은 것은 식 3의 \(p_B = 1\)을 이용하는 것입니다. 앞에서 \(t = B\)를 대입하면, \[ p_B = \left( \frac{B}{B - 1} \right)^{B - 1} + \left( \frac{\rho - 1}{B - 1} \right) \frac{\left(\frac{B}{B - 1}\right)^{B - 1} - 1}{\frac{B}{B - 1} - 1} \]이 된다는 것을 알 수 있습니다. 이번에는 \(e_B := \left( \frac{B}{B - 1} \right)^{B - 1}\)로 두겠습니다. 그러면 위 식을 \[ p_B = e_B p_1 + (\rho - 1)(e_B - 1) \]으로 정리할 수 있고, 여기에 앞에서 구한 식 5를 대입하면 \[ p_B = e_B \left( \frac{\rho - 1}{B - 1} + \frac{c}{B - 1}\right) + (\rho - 1)(e_B - 1) = 1\]과 같이 정리할 수 있습니다. 따라서 이를 \(\rho\)에 대해 정리하면, \[ \rho = 1 + \frac{1 - \frac{e_B c}{B - 1}}{e_B - 1 + \frac{e_B}{B - 1}} \]이 된다는 것을 이끌어낼 수 있습니다. 임의의 \(B\)에 대해서 모두 성립해야 하므로, \( B \to \infty \)일 때, \( e_B \to e \)이며 결과적으로 \( \rho \to 1 + \frac{1}{e - 1} = \frac{e}{e - 1} \)이 된다는 것도 알 수 있습니다.

마치며

이것으로 스키 대여 문제를 경쟁적으로 해결하는 알고리즘은 (랜덤 알고리즘이라고 할지라도) \(\frac{e}{e - 1}\)보다 좋은 경쟁비를 가질 수 없음을 증명하였습니다. 이전 포스트에서 동일한 경쟁비를 갖는 알고리즘을 제시하였으므로 그 알고리즘은 최적의(optimal) 알고리즘이라는 것을 알 수 있습니다. 이 글을 끝으로 스키 대여 문제는 마무리를 지을 수 있을 것 같군요.

 

랜덤 온라인 알고리즘의 경쟁비 하한을 분석한 것은 이 글이 처음인 것 같습니다. 위 글에서도 확인할 수 있다시피 랜덤 알고리즘의 경쟁비의 하한을 구하는 것은 결정론적 알고리즘의 하한을 구하는 것보다 훨씬 복잡합니다. 적응형 상대방(adaptive adversary)이 아닌 무지각형 상대방을 상정해야 하기 때문이죠. 그렇지만 복잡한 만큼 흥미로운 주제라는 것도 부인할 수 없겠습니다.

 

궁금한 점이 있으시거나, 글 내용에 오류가 있는 경우에는 알려 주시기 바랍니다. 긴 글 읽어 주셔서 고맙습니다. 

참조

[1] Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan Owicki. "Competitive randomized algorithms for nonuniform problems." Algorithmica 11, no. 6 (1994): 542-571.

각주

[ㄱ] 사실 \( p_t = 1 \)을 만족하는 \(t\)가 없을 수도 있습니다. 즉, 모든 \(t\)에 대해서 \( p_t < 1 \)일 수는 있는 것이죠. 따라서 좀 더 올바른 증명은 \( \lim_{t \to \infty} p_t = 1 \)이라는 사실을 보이는 것입니다. 그렇지 않다면 \( \sum_{i = 1}^t (1 - p_i) \)가 수렴하지 않을 것이고, 그러므로 \(\rho B + c\)에 들어오지 못하게 됩니다. 따라서, \(\mathcal{B}\)의 비용의 기댓값은 \[ B + \sum_{i = 1}^{B - 1} (1 - p'_i) \leq \lim_{t \to \infty} \left[ p_t B + \sum_{i = 1}^t (1 - p_i) \right] \leq \rho B + c  \]을 넘지 못합니다.