Pandora's Box Problem

Introduction

 

필자가 게임을 하나 제안하겠다. 상품이 하나씩 들어있는 박스가 여러 개 있다. 당신은 박스들을 하나씩 개봉하고 개봉한 박스들 중에서 하나를 골라 그 안에 있는 상품을 가져갈 수 있다. 당신은 물론 가장 좋은 상품을 고르고 싶을 것이다. 어떻게 하면 가장 좋은 상품을 고를 수 있을까?

 

매우 간단하다! 모든 박스를 열어보고 그 중에서 가장 좋은 것을 고르면 되니까. 하지만 이 문제에 제약 조건이 붙어 있다. 각 박스마다 개봉 비용이 있어서 열 때마다 필자에게 개봉 비용을 내야 한다. 따라서 모든 박스를 다 열어보는 것은 좋지 않은 전략일 수 있다. 그러면 다음 전략을 생각해볼 수 있다. 박스가 가지고 있는 상품의 값어치와 박스의 개봉 비용의 차이가 가장 큰 박스를 열고 그 안의 상품을 가져가는 것이다! 하지만 추가적인 제약 조건이 있다. 박스를 열기 전까지 상품의 값어치를 알 수 없다. 대신 그 상품의 값어치의 확률 분포는 알 수 있다고 하자. 조금 더 수학적으로 표현하자면, 각 박스마다 분포가 있는 상황이고, 당신이 박스를 (비용을 내서) 개봉하면 그 분포에 따라 안에 들어있는 상품의 값어치가 결정되는 것이다.

 

이제는 어떤 전략을 취해야 할지 명확하지 않다. 박스가 가지고 있는 상품의 값어치의 "기대값"과 개봉 비용의 차이가 가장 큰 박스를 개봉하는 전략을 생각한다면 다음과 같은 문제가 생긴다. 가령 10이라는 비용을 내고 박스를 열었는데 0의 값어치를 얻을 수도 있다. 1979년에 이 문제를 처음 소개한 Weitzman이 Pandora's box라고 부른 이유가 바로 이것 때문이다.

박스를 개봉을 후회할 수도 있다.

 

Problem Setting

 

조금 더 형식적으로 문제를 정의하고자 한다. 박스가 $n$개가 있고 각 박스 $i$마다 개봉 비용 (cost) $c_i$가 있고, 각 박스마다 분포 $D_i$가 있다. 박스 $i$의 상품의 값어치 (value) $v_i$는 박스를 개봉하기 전에는 알 수 없고 박스를 개봉할 때 $D_i$에서 확률적으로 뽑힌다. 즉, $v_i$는 분포 $D_i$를 따른다. (추가적으로 상품의 값어치의 기댓값은 개봉 비용보다 작지 않다고 가정할 것이다. 그렇지 않은 박스가 있다면 빼놓고 생각할 것이다.) 우리가 하고 싶은 것은 박스들을 잘 골라서 개봉하고 개봉한 박스 중에서 가장 높은 값어치의 상품을 고르는 것이다. 수식으로 표현하면 다음과 같다.

$$ \max_{i:box~ i~opened}{v_i} - \sum_{i:box~i~opened}{c_i} $$

 

이 문제의 최적의 전략이 있다면 어떤 식일까?

 

처음에 개봉할 박스를 "어떻게 잘" 고르고, 열었을 때 관측하는 값에 따라 그 상품을 선택하거나 그 다음 박스를 "어떻게 잘" 고르고... 를 반복하는 것일 수 있다. 하지만 관측되는 상품의 값은 분포에 따라 매우 혹은 무수히 많을 수 있다. 그러면 전략의 형태는 어떤 식일까? "어떻게 잘" 범위를 지정하고 관측된 상품의 값어치가 해당 범위에 들어오면 어떤 행동을 하고 아니면 다른 행동을 하는 식일까?

 

꼬리에 꼬리를 물어 이렇게 생각하다보면 혹자는 이 문제에 대해 최적의 전략을 찾는 것은 computationally hard한 문제라고 추측하거나 혹은 전략이 존재할 수는 있지만 간결하고 축약된 형태로 적을 수는 없다고 생각할 수도 있다. 하지만 Weitzman은 1979년, Optimal search for the best alternative 이라는 논문에서 간단한 최적의 전략을 제시했다. 이 전략이 뭔지 알아보고자 한다.

 

Investment

 

이 문제를 약간 다른 식으로 바라보고자 한다. 필자가 당신에게 한 가지 제안을 하도록 하겠다. 어떻게 보면 당신에게 투자를 한다고도 볼 수 있다. 이제부터 필자가 박스마다 개봉 비용을 없애주는 대신에, 상품의 값어치가 특정 값보다 크면 그 차이만큼을 필자가 가져가도록 하겠다. 즉, 각 박스 $i$마다 이 특정 값을 $\sigma_i$라고 한다면, 박스 $i$를 열었을 때 당신이 최대로 가져갈 수 있는 값어치는 $\min\{v_i,\sigma_i\}$인 것이고 필자가 가져가는 값어치는 $v_i - \min\{v_i,\sigma_i\}$인 것이다. 다르게 말하자면 $\sigma_i$는 당신이 가져갈 수 있는 값어치에 한도를 거는 것이다. 그래서 우리는 $\sigma_i$를 cap이라고 부를 것이고 당신이 가져가는 값어치를 capped value $\kappa_i$라고 부를 것이고 필자가 가져가는 양을 bonus $b_i$라고 부를 것이다.

제 제안이 마음에 드십니까?

 

당연히 cap이 얼만지, 즉 $\sigma_i$값에 따라 다를 것이다. 예를 들어 cap이 $0$이었다 하자. 그러면 당신은 $0$ 보다 더 많이 가져갈 수 없기에 제안이 마음에 들 수가 없다. 그렇다면 cap이 아주아주 큰 수라고 해 보자. 그러면 당신은 관측한 값어치에 관계없이 (거의) 전부를 가져갈 수 있다. (그렇기에 필자가 그런 제안을 할 이유가 없다.) 

 

cap의 값에 대해서 필자와 독자가 합의를 볼 수는 없을까? 가능하다! 개봉 비용이 있었을 때 필자가 받았을 비용의 기대값과, 개봉 비용을 없애고 한도를 걸었을 때 얻을 보너스의 기댓값이 같으면 된다. (그냥 값이 아니라 기댓값인 이유는 값어치 $v_i$가 확률적으로 정해지기 때문이다.) 그러면 필자 입장에서도, 독자 입장에서도 효용이 변하지 않기에 공평하다. 그래서 그러한 cap을 fair cap이라고 부르도록 하겠다. 수학적으로 적으면 다음과 같다. Fair cap $\sigma_i$는 다음 수식 보너스의 기대값과 개봉 비용을 같게끔 하는 cap, 즉,

$$ \mathbb{E}_{v_i\sim D_i}[b_i]=\mathbb{E}_{v_i\sim D_i}[v_i-\min\{v_i,\sigma_i\}] = c_i $$

을 만족하는 cap을 뜻한다. (이러한 fair cap은 항상 존재한다.)

 

Fair Cap Policy

 

뜬금없이 제안을 한 이유는 이것을 이용한 전략을 소개하기 위함이었다. 전략은 다음을 반복하는 것이다. 미개봉 박스 중 fair cap이 가장 큰 박스부터 개봉하고 상품의 값어치를 관측한다. 만약 현재까지 관측한 값어치의 최댓값이 아직 개봉하지 않은 모든 박스의 fair cap 보다 크면 관측한 값어치가 최대인 상품을 고른다.

 

다시 말하자면 다음과 같다. 일반성을 잃지 않고 박스가 fair cap이 감소하는 순으로 나열 되었다고 해보자. 즉 $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_n$을 만족한다. $1$번 박스를 열고 $v_1$을 관측한다. $2$번 박스를 열기 전에 $\sigma_2 \ge \max\{v_1\}$인지 체크한다. 만약 맞다면 $2$번 박스를 열고 $v_2$를 관측한다. $3$번 박스를 열기 전에 $\sigma_3 \ge \max\{v_1,v_2\}$인지 확인한다. 만약 맞다면 $3$번 박스를 열고 $v_3$를 관측한다. 이 과정을 계속 반복할 것이다. 그러다 만약 $i$번째 박스를 열기 전에 $\sigma_i < v_{i^*}:=\max{\{v_1,\dots,v_{i-1}\}}$였다면 그만 열고 $i^*$ 상품을 가져간다.

 

직관적으로 말하자면 이 전략은 개봉 비용을 없앤 버전에서 가장 가치있는 박스부터 개봉하는데 언제까지 하냐면, 더 이상 얻을 것이 없다고 기대하는 순간까지 여는 것이다. 이 전략의 특이한 점은 관측된 값에 따라 개봉할 박스의 순서가 바뀌지 않는 다는 것이다. 처음에 관측된 값에 따라 개봉할 박스를 달리 해야 하지 않을까?라는 추측과 반대되기 때문에 흥미롭기도 하다.

 

Theorem. Fair Cap Policy is Optimal!

 

이 전략이 흥미로운 진짜 이유는 이것이 최적의 전략이라는 점이다. 증명은 다음과 같다. 임의의 전략으로 얻을 수 있는 값어치의 상한선이 있는데, fair cap policy를 적용하면 그 상한선을 정확히 얻을 수 있다.

 

따라서 임의의 전략이 얻을 수 있는 값어치의 상한선을 먼저 구해보겠다. 그 전에 두 가지 종류의 확률 변수 $I$와 $A$를 정의하고 가겠다. (임의로 정한) 전략이 $i$번째 박스를 개봉했다면 $I_i=1$이고 아니면 $0$이다. 그리고 그 전략이 $i$번째 박스의 상품을 선택하기로 했다면 $A_i=1$이고 아니면 $0$이다. (확률 변수인 이유는 전략 자체가 확률적으로 개봉할지 말지, 받아들일지 말지를 결정해서 일수도 있기 때문이다. 가령 이제까지의 개봉된 값어치에 의존해서 다음 개봉할 박스를 확률적으로 고른다던지 등이 예시가 될 수 있겠다.)

 

임의의 전략을 하나 골라서 그것을 $\pi$라고 하겠다. 그리고 전략 $\pi$로 얻을 수 있는 값어치의 기댓값을 $V(\pi)$라고 하자. 그러면 정의에 따라 다음과 같이 적을 수 있다.

$$ V(\pi)=\mathbb{E}\left[ \sum_i{A_i v_i}-\sum_i{I_i c_i} \right]$$

여기서 expectation은 policy에서의 randomness와 value의 randomness 모두를 포함하고 있다. 즉 $v_i$는 $D_i$를 따르고  $I$와 $A$는 policy의 randomness를 따를 수 있다. 이제 $v_i$를 $\kappa_i+b_i$로 표현해 보자. 이때 $\kappa_i$와 $b_i$는 각각 fair cap에 의해 정해지는 capped value와 bonus로 생각할 것이다.

$$ \mathbb{E}\left[ \sum_i{A_i v_i}-\sum_i{I_i c_i} \right] = \sum_i{\left(\mathbb{E}[A_i \kappa_i]+\mathbb{E}[A_i b_i]-\mathbb{E}[I_i]c_i\right)}$$

이때 $c_i$는 fair cap의 정의에 따라 $\mathbb{E}[b_i]$와 같고, $b_i$는 $D_i$에 의해 뽑힌 숫자 $v_i$에 의해서만 결정되지만 $I_i$는 개봉하기 전에는 알 수 없는 값인 $v_i$에 영향을 받을 수 없다. 따라서,

$$\mathbb{E}[I_i] c_i=\mathbb{E}[I_i]\mathbb{E}[b_i]=\mathbb{E}[I_i b_i]$$라고 쓸 수 있다. 따라서

$$\sum_i{\left(\mathbb{E}[A_i \kappa_i]+\mathbb{E}[A_i b_i]-\mathbb{E}[I_i]c_i\right)}=\sum_i{\left(\mathbb{E}[A_i \kappa_i]+\mathbb{E}[A_i b_i]-\mathbb{E}[I_i b_i]\right)}$$라고 쓸 수 있고, 이를 추가적으로 정리하면

$$V(\pi)=\sum_i{\mathbb{E}\left[A_i \kappa_i - (I_i-A_i)b_i\right]} \le \sum_i{\mathbb{E}\left[A_i \kappa_i\right]}\le\mathbb{E}\left[\max_i{\kappa_i}\right]$$ 인 것이다. 첫 번째 부등식이 성립하는 이유는 박스를 개봉해야지 상품을 선택할 수 있어서 $I_i-A_i$는 음수가 될 수 없기 때문이다.

 

이제 fair cap policy $\pi^*$는 위의 부등식을 등식으로 성립함을 보일 것이다. 그러면 다음 두 가지를 보이면 된다. Fair cap policy에서는 모든 박스 $i$에 대해 $(I_i-A_i)b_i$가 항상 $0$이라는 것과 항상 capped value가 가장 큰 박스의 상품이 선택된다는 것이다. (그러면 위의 두 부등식이 등식으로 성립한다.)

 

1. $(I_i-A_i)b_i=0$

만약 $I_i=0$이거나 $b_i=0$이면 자명하게 성립한다. 따라서 $I_i=1$이면서 $b_i>0$인 경우만 고려하겠다. $I_i=1$은 어떤 상황인가? 우선 박스 $i$를 개봉한 상황이고 이것은 $\sigma_i \ge \max\{v_1,\dots,v_{i-1}\}$인 상황이다. 그럼 $b_i>0$은 어떤 상황인가? 이는 $v_i > \sigma_i $가 성립함을 뜻한다. 이 수식과 $\sigma_i \ge \sigma_{i+1}$과 결합하면 $i+1$번째 박스는 개봉하지 않을 것임을 알 수 있다. 즉, $i$번째 박스가 마지막으로 개봉한 박스라는 것이다. 더 이상 선택되는 박스가 없으므로 이제까지 관측된 값어치의 대소 관계만 따져보면 된다. 수식에 따라서 $v_i > \sigma_i \ge \max\{v_1,\dots,v_{i-1}\}$이기 때문에 $v_i$가 가장 높은 값어치를 갖는다. 가장 비싼 값어치를 선택하는 규칙에 따라 따라서 $A_i=1$이 성립한다.

 

2. 항상 모든 상품 중 capped value가 가장 큰 상품이 선택된다.

$i^*$를 선택된 상품을 담았던 박스의 번호라고 하자. 우리가 보일 것은 모든 $i$에 대해 $\kappa_i \le \kappa_{i^*}$이다. 우리는 이를 $i$가 개봉된 박스인지 아닌지로 나누어서 증명할 것이다. 

 

(증명에 쓰이는 성질들을 미리 적어두었다.)

(a) 정의에 따라 $\kappa_i = \min\{v_i,\sigma_i\}$

(b) $v_{i^*}$는 개봉된 상품 중에서 값어치가 가장 높은 것

(c) 미개봉 박스의 cap value $\le$ 개봉 박스의 cap value

(d) 마지막으로 개봉한 박스의 cap value $\ge$ 이 박스를 개봉하기 전의 최대 값어치

(e) 미개봉 박스의 cap value $\le$ 선택된 (최고) 상품의 값어치

 

2-1) 박스 $i$가 개봉된 박스인 경우

2-1-1) $v_{i^*} \le \sigma_{i^*}$인 경우, 즉 $\kappa_{i^*}=v_{i^*}$인 경우. (성질 (a)과 (b) 때문에 다음 부등식 성립)

$$\kappa_i \le v_i \le v_{i^*} = \kappa_{i^*}$$ 

2-1-2) $v_{i^*} > \sigma_{i^*}$인 경우, 즉 $\kappa_{i^*}=\sigma_{i^*}$인 경우. 이 경우는 $i^*$번째 박스가 마지막으로 개봉된 박스라는 것을 뜻한다. (성질 (a)과 (d) 때문에 다음 부등식 성립)

$$\kappa_i \le v_i \le \sigma_{i^*} =\kappa_{i^*}$$ 

 

2-2) 박스 $i$가 미개봉 박스인 경우

2-2-1) $v_{i^*} \le \sigma_{i^*}$인 경우, 즉 $\kappa_{i^*}=v_{i^*}$인 경우. (성질 (a), (e) 때문에 다음 부등식 성립)

$$\kappa_i \le \sigma_i \le v_{i^*} = \kappa_{i^*}$$ 

2-2-2) $v_{i^*} > \sigma_{i^*}$인 경우, 즉 $\kappa_{i^*}=\sigma_{i^*}$인 경우. (성질 (a), (c) 때문에 다음 부등식 성립)

$$\kappa_i \le \sigma_i \le \sigma_{i^*} = \kappa_{i^*}$$ 

 

따라서 모든 $i$에 대해 $\kappa_i \le \kappa_{i^*}$가 성립하고 이로서 증명이 마무리된다.

 

---

참고

https://tcs.cs.uni-bonn.de/lib/exe/fetch.php?media=teaching:ss20:vl-aau:lecturenotes09.pdf 

https://bowaggoner.com/blog/2018/07-20-pandoras-box/