통계적으로 최적의 소개팅 횟수 생각해보기 (비서 문제)

비서 문제(Secretary Problem)는 알려진 수의 대상들 중에서 가장 뛰어난 대상을 순차적으로 선택할 때 성공 확률을 최대화하는 최적 정지(Optimal Stopping) 문제의 고전적인 사례이다. 이 문제는 다양한 현실의 순차적 의사결정 상황에 적용될 수 있다.

 

1. 비서 문제의 정의

비서 문제는 다음과 같은 조건을 갖는다.

• n명의 후보자가 존재하며, n 값은 사전에 알려져 있다.
• 후보자들은 무작위 순서로 한 명씩 순차적으로 등장한다.
• 각 후보자가 등장할 때마다 그 자리에서 즉시 '선택(채용)'하거나 '거절'해야 한다.
• 한 번 거절된 후보자는 다시 선택할 수 없다.
• 현재 등장한 후보자에 대해 알 수 있는 정보는 현재까지 등장한 후보자들 중 그의 상대적인 순위뿐이다. 전체 n명 중 그의 절대적인 순위는 알 수 없다.
• 목표는 가장 뛰어난 단 한 명의 후보자를 선택할 확률을 최대화하는 것이다.

사람을 고용해야하는 입장에서 전체 몇명이 들어올지는 알지만 이 사람들의 평균적인 역량을 알 수 없기 때문에, 최소 몇명 이상은 거절을 염두해두고 평가를 해야할 것이다. 그리고 거절한 후보자는 다시 못보고 채용 이후에는 변경하지 못하다보니 매번 매번이 고민의 연속이어야 한다.

 

이러한 사례는 사실 현실에서 흔한데, 제목에 기재한 것처럼 소개팅이 될 수도 있고, 여러 회사에 순차적으로 면접을 보며 오퍼를 수용할지 기다릴지 결정하는 문제가 될 수도 있고, 집을 돌아보며 부동산을 구매해야하는 문제일 수도 있다. 물론, 과거에 만났던 사람을 다시 만날수도 있고, 회사의 오퍼는 시간을 조율할 수 있으니까, 현실의 제약은 이런 문제보다는 조금 더 완화되어 있을 것이다. 그럼에도 이러한 문제는 우리에게 큰 영감을 주니 한번 살펴보도록 하자.

 

2. 최적의 전략

비서 문제의 최적 전략은 '관찰 후 선택(Look, Then Leap)' 방식이다.

1. 관찰 단계: 처음 k명의 후보자는 무조건 거절한다. 이들은 단지 이후에 나타날 후보자들의 평가 기준을 설정하는 데 사용될 뿐이다.
2. 선택 단계: k+1번째 후보자부터는, 이전 관찰 단계(처음 k명)에서 만났던 모든 후보자들보다 상대적으로 더 뛰어난 첫 번째 후보자를 만나는 즉시 그를 선택한다.
3. 만약 마지막 n번째 후보자까지 관찰 단계보다 뛰어난 후보자가 나타나지 않았다면, 마지막 n번째 후보자를 선택한다.

 

3. 최적 관찰 비용 & 최대 성공 확률

여기서는 밸런스가 매우 중요한데, 물론 전체를 관찰할 수 있다면 최적의 사람을 뽑을 수 있겠지만, 그런 경우에는 이미 거절한 사람 중에 더 뛰어난 사람이 섞여있을테니 어느 수준에서 관찰을 멈추어야 한다. 그렇다면 몇 명까지 관찰해야 할까?

 

최적의 성공 확률을 달성하는 관찰 대상의 수 k는 전체 후보자 수 n에 따라 결정된다. n이 충분히 클 때, 최적의 k는 대략 n/e이며, 이때 가장 뛰어난 후보자를 선택할 확률은 약 1/e≈0.368 (약 36.8%, 즉 약 37%)로 최대가 된다. 자연로그의 밑 e≈2.718이다.

이는 즉, 전체 후보자의 약 37%는 탐색 기간으로 사용하고, 이후부터는 탐색 기간의 최고보다 나은 첫 후보를 선택하는 전략이 가장 높은 확률(약 37%)로 전체 최고 후보를 선택할 수 있음을 의미한다.

 

4. 증명

주어진 전략(첫 k명 거절 후, k명보다 우월한 첫 후보 선택)을 따랐을 때, 전체 n명 중 최고의 후보자를 선택할 확률을 P(성공∣k)라고 하자.

최고의 후보자가 j번째에 등장했을 때 (단, j>k), 이 전략이 성공하기 위해서는 다음 두 가지 조건이 만족되어야 한다.

1. 최고의 후보자가 j번째에 등장한다. (확률 1/n)
2. 첫 j−1명의 후보자들 중에서 가장 뛰어난 후보자가 첫 k명 안에 존재한다. (그래야 j번째 후보자가 k명보다 우월한 첫 후보가 될 수 있다. 조건부 확률 k/(j−1))

따라서, 최고의 후보자가 j번째에 등장했을 때 전략이 성공할 조건부 확률은 k/(j−1)​이다.

 

$$ P(\text{성공} | k) = \frac{k}{n} \sum_{j=k+1}^{n} \frac{1}{j-1} $$

$n$이 충분히 클 때, 합은 적분으로 근사된다:

$$ \sum_{j=k+1}^{n} \frac{1}{j-1} \approx \int_{k}^{n} \frac{1}{x} dx = \ln\left(\frac{n}{k}\right) $$

따라서 성공 확률 근사치는:

$$ P(\text{성공} | k) \approx \frac{k}{n} \ln\left(\frac{n}{k}\right) $$

$\frac{k}{n} = x$ 로 치환하면, 최대화할 함수는 $f(x) = -x \ln x$ 이다.

 

미분값:

$$ \frac{d}{dx}(-x \ln x) = -(\ln x + 1) $$

 

최대값은 $\frac{d}{dx}f(x) = 0$ 일 때 발생하므로, $\ln x + 1 = 0 \implies \ln x = -1 \implies x = e^{-1} = \frac{1}{e}$ 이다. 최적의 관찰 비율은 $k/n \approx 1/e$ 이다.

이때 최대 성공 확률은:

$$ P_{\max} \approx f(1/e) = -\frac{1}{e} \ln\left(\frac{1}{e}\right) = -\frac{1}{e}(-1) = \frac{1}{e} $$

$$ \frac{1}{e} \approx 0.368 $$

 

5. 실제 적용 시사점

 

비서 문제의 분석 결과는 현실의 순차적 의사결정에서 고려할 점을 시사한다.

• 정보 탐색의 중요성: 초기에 일정 기간 동안 후보들을 관찰하여 평가 기준을 설정하는 과정이 필요하다.
• 결정 시점의 중요성: 탐색 후 기준을 만족하는 후보가 나타났을 때 결정을 미루면 최적의 기회를 놓칠 수 있다.
• 균형: 초기 관찰 기간과 이후의 빠른 결정 사이의 균형이 중요하며, 수학적으로는 전체의 약 37%를 탐색 기준으로 삼는 것이 최적 확률을 제공한다.
• 현실 문제에서는 n이 불확실하고 평가 기준이 상대적이지 않을 수 있지만, 비서 문제는 순차적 선택 상황에서 탐색-실행 트레이드오프에 대한 중요한 수학적 통찰을 제공한다.

만약 앞으로 내가 10번의 소개팅의 기회가 있다고 한다면, 3~4명 정도는 거절을 염두해두고 관찰을 하고, 그 이후부터는 결정을 해야 함을 의미한다.