게임이론과 알고리즘으로 풀어보는 실력지상주의(라노벨) 미니게임
라노벨 《실력지상주의 교실》(2학년 편 5권)에는 '만장일치 특별시험'이 등장한다. 안건은 "반에서 1명을 골라 퇴학시킬 것인가" — 반 전원이 익명으로 찬성 또는 반대를 투표해 만장일치를 이뤄야 하는데, 주인공을 퇴학시키려 하는 스파이 1명이 찬성표를 던져 이를 방해한다. 제한시간은 300분(30라운드), 한 라운드는 10분이다.
소설에서는 스파이를 투표로 잡아낼 방법을 찾지 못해, 찬성 몰표를 던진 뒤 게임과 별개로 사전에 확보해둔 근거를 동원해 퇴학당할 1명으로 스파이를 몰아간다. 하지만 그룹 분할 전략을 쓰면 투표만으로도 스파이를 잡을 수 있다. 30명 기준 평균 약 10라운드(100분), 97.7% 확률로 21라운드(210분) 안에 끝난다. 이 글에서는 그 전략을 게임이론으로 분석하고, 스파이가 최선을 다해 버틸 때 정확히 몇 라운드가 걸리는지 계산한다.
1. 게임 규칙
- 반 인원 N명이 익명투표로 반대 만장일치를 이뤄야 한다.
- 만장일치가 안 되면 재투표. 라운드 수에 제한이 있다.
- 스파이 1명이 찬성을 고수하여 만장일치를 방해한다.
- 스파이의 목표: 특정되거나 만장일치가 성립하기까지 최대한 많은 라운드를 버티는 것.
2. 리더의 검출 전략
리더는 반을 그룹 A, B 두 개로 나누고, 매 라운드 비밀리에 다음 중 하나를 지시한다:
| 지시 | A의 투표 | B의 투표 | 확률 |
|---|---|---|---|
| 반/반 | 반대 | 반대 | p |
| 찬/반 | 찬성 | 반대 | (1−p)/2 |
| 반/찬 | 반대 | 찬성 | (1−p)/2 |
- 반/반: 전원 반대를 지시한다. 만장일치가 성립하면 스파이가 순순히 반대를 눌렀다는 뜻이므로 게임 끝.
- 찬/반 또는 반/찬 (테스트): 한쪽에만 찬성을 지시한다. 찬성 표가 예상보다 1표 많으면 스파이가 반대 그룹에서 찬성을 눌렀다는 뜻 → 스파이의 그룹이 드러난다(검출).
한 번 검출될 때마다 후보가 절반으로 줄어든다. 30명이면 4번 걸리면 특정된다 (30 → 15 → 8 → 4 → 2).
3. 스파이의 딜레마
스파이는 자기 그룹의 지시만 알고, 상대 그룹의 지시는 모른다. 찬성 지시를 받으면 그대로 찬성을 눌러 자연스럽게 섞이면 된다. 문제는 반대 지시를 받았을 때:
- 반대를 누르면: 반/반 라운드였을 경우 만장일치가 성립하여 스파이가 진다.
- 찬성을 누르면: 테스트 라운드였을 경우 찬성 표가 1표 초과하여 검출된다.
매 라운드 "만장일치로 질 위험"과 "검출될 위험" 사이에서 도박을 해야 한다. 반대 지시를 받은 스파이가 확률 q로 반대, (1−q)로 찬성을 택한다고 하면:
| 사건 | 확률 | 결과 |
|---|---|---|
| 만장일치 | u = pq | 게임 종료 (스파이 패배) |
| 검출 | d = (1−p)(1−q)/2 | 후보군 절반 축소 |
| 무사건 | 1−u−d | 아무 일도 안 일어남 |
4. 수학적 분석
핵심 관찰
검출은 즉시 패배가 아니다. 30명 기준 스파이는 4번까지 검출을 허용할 수 있다. 이 여유분이 스파이의 전략 공간을 근본적으로 확장한다.
재귀식
남은 허용 검출 횟수가 j일 때, 양쪽 모두 최선을 다할 경우 스파이가 버틸 수 있는 기대 라운드 수를 V(j)라 하자 (게임이론에서 minimax 값이라 부르는 균형점이다).
매 라운드는 "현재 1라운드 소비 + 이후 기대값"으로 쓸 수 있다. 만장일치(확률 u)가 나면 게임이 끝나고(이후 0), 검출(확률 d)이 나면 여유가 1 줄어들고(이후 V(j−1)), 무사건(확률 1−u−d)이면 상태가 그대로다(이후 V(j)). 이를 식으로 쓰면:
V(j) = 1 + u·0 + d·V(j−1) + (1−u−d)·V(j)
우변의 V(j)를 좌변으로 이항하면:
V(j) = ⟨1 + d · V(j-1)⟩ ÷ ⟨u + d⟩
기저 조건은 V(0) = 0 (허용 검출이 0이면 다음 검출에서 바로 특정).
안장점
V(j)의 식은 p와 q에 대해 완전히 대칭이므로, 균형점에서 p* = q*가 성립한다. t = 1 − p, α = V(j−1)로 치환하고 미분하면 2차 방정식 α·t² + (3−α)·t − 2 = 0으로 귀결되며, 이를 재귀적으로 풀면:
| 남은 검출 j | 최적 q* = p* | 기대 생존 V(j) |
|---|---|---|
| 1 | 0.333 | 3.00 |
| 2 | 0.184 | 5.45 |
| 3 | 0.129 | 7.75 |
| 4 | 0.100 | 9.97 |
| 5 | 0.082 | 12.15 |
큰 j에 대해 V(j) ≈ 2j + 1로 수렴한다. j가 크면 양쪽 모두 p*, q* → 0이 되어 매 라운드 검출 확률이 약 1/2이 되고, 검출 1회당 평균 2라운드가 걸리기 때문이다.
5. 스파이의 최적 전략
스파이가 따라야 할 전략은 초반에는 과감하게, 후반에는 조심스럽게 접근하는 것이다.
| 남은 검출 j | 반대 지시 시 찬성 확률 |
|---|---|
| 4 (초기) | 90.0% |
| 3 | 87.1% |
| 2 | 81.6% |
| 1 (마지막) | 66.7% |
검출 여유가 많을 때는 거의 항상 찬성을 눌러 만장일치를 막고, 여유가 줄어들수록 반대 비율을 높여 검출을 피한다.
6. 변형: 리더가 스파이의 그룹을 아는 경우
첫 검출 이후 리더가 스파이의 그룹을 파악하면, 항상 스파이 그룹에 반대를 지시하는 테스트만 사용할 수 있다. 기존에는 스파이가 찬성 그룹에 속할 확률 1/2로 검출을 피할 수 있었지만, 이제 그 행운이 사라져 검출 확률이 2배가 된다.
N=30 기준, 스파이의 기대 생존이 9.97 → 5.89로 약 41% 감소한다.
7. 시뮬레이션 결과
200만 회 시뮬레이션으로 확인한 N=30에서의 생존 라운드 분포:
| 통계 | 값 |
|---|---|
| 평균 | 9.97 라운드 |
| 표준편차 | 4.46 라운드 |
| 중앙값 | 9 라운드 |
| 90% 구간 (P5~P95) | 4 ~ 18 라운드 |
| 97.7% 이내 (2σ 상한) | 21 라운드 |
| 99.85% 이내 (3σ 상한) | 28 라운드 |
분포는 8라운드 부근에서 피크를 찍고 오른쪽으로 긴 꼬리를 가지는 이산 phase-type 분포를 따른다.
8. 결론
소설 속 300분(30라운드) 제한 안에서, 그룹 분할 전략을 쓰면 스파이를 잡을 수 있었을까?
- 평균 약 10라운드(100분)이면 끝난다.
- 97.7%의 확률로 21라운드(210분) 안에 끝난다.
- 99.85%의 확률로도 28라운드(280분)로, 제한시간 내에 충분히 들어온다.
게다가 이 수치는 스파이가 게임이론적 최적 전략을 완벽하게 구사했을 때의 상한이다. 소설 설정상 스파이는 자기보신이 결코 사소한 요소가 아니기에, 이런 전략을 마주하면 차라리 반대표를 던져 만장일치에 협조하는 쪽으로 기울었을 가능성이 크다. 실제로는 훨씬 빠르게 끝났을 것이다.
소설 설정상 스파이를 잡아내는 위치에 있는 주인공은 중학생 때 이미 르벡적분까지 다 떼고 온 극한의 능력자(?)이다. 이런 전략을 생각해내지 못하는 건 캐릭터의 허점이자 작가의 실수라고 할 수 있다.