Impartial Combinatorial Games and the Nuclear Escalation Ladder

기술 요약: 공정한 조합 게임과 핵 에스컬레이션 사다리

문제 제기
본 논문은 허먼 칸(Herman Kahn)의 "에스컬레이션 사다리(escalation ladder)"—평화에서 핵 사용에 이르기까지 초강대국 간의 위기가 통제된 방식으로 격상되는 과정을 나타내는 은유—를 정식 모델링하는 문제를 다룬다. 기존의 에스컬레이션 관련 게임 이론 문헌(예: Schelling, Brams, Powell)은 카디널(cardinal) 또는 오디널(ordinal) 효용을 포함하는 고전적인 보수 기반 프레임워크에 의존하며, 이는 합리성과 공통 지식에 대한 강력한 가정을 내포하고 있다. 이러한 접근 방식은 순수하게 위치론적인 질문, 즉 특정 위기 상태와 차례가 된 플레이어가 주어졌을 때, 누가 구조적으로 다음 단계(잠재적으로 치명적인 단계)를 밟도록 강요받는가 하는 문제를 모호하게 만든다. 본 논문은 에스컬레이션 사다리를 **공정한 조합 게임(impartial combinatorial game)**으로 모델링함으로써, 카디널 보수를 버리고 승/패 및 차례의 구조에 집중하여, 누가 행동하도록 강요되는지에 대한 구조적 불변성을 분리해 낼 것을 제안한다.

방법론
저자는 에스컬레이션 사다리를 핵 사용 전까지 남은 거리로 재색인한다.

1. 재색인: 사다리에 $N+1$개의 단(rung)($0$부터$N$까지)이 있다면, 상태는$r = N - n$으로 재정의된다. 여기서$r$은 핵 사용 전까지 남은 단의 수를 나타낸다.
2. 게임 공식화: 이 변환은 사다리를 가장 분석하기 용이한 공정한 게임 클래스 중 하나인 **뺄셈 게임(subtraction game)**으로 변환한다.
   • 상태 공간: $\{0, 1, \dots, N\}$.
   • 수(Moves): $r \ge 1$인 상태에서, 플레이어는 $d \le r$을 만족하는 $d \in S = \{1, \dots, m\}$(여기서 $m$은 에스컬레이션 입도/granularity)를 선택하여 $r-d$로 이동한다.
   • 규칙(Convention): 이 게임은 미제르 규칙(misère convention) 하에 진행된다(즉, 종단 상태 $r=0$으로 이동하는 플레이어가 패배한다). 이는 핵 임계치를 먼저 넘는 것을 원치 않는다는 교리적 실재를 반영한다.
3. 다중 전역 확장: 동시 다발적인 전역(theater)의 경우, 이 게임은 독립적인 단일 사다리 게임들의 이접 합(disjunctive sum)으로 모델링된다.
4. 분석 도구: 본 논문은 일반적인 경기(normal play)를 위한 스프라그-그룬디(Sprague-Grundy) 정리와 미제르 경기(misère play)를 위한 미제르 쿼션트(misère quotients)(Plambeck 및 Siegel) 이론을 활용한다.

주요 기여 및 결과

1. 단일 사다리 안정성 (정리 4.1)
본 논문은 에스컬레이션 집합이 $S = \{1, \dots, m\}$인 단일 전역에 대해, P-포지션(이전 플레이어가 승리하는 위치, 즉 현재 차례의 플레이어가 구조적으로 패배하도록 강요되는 상태)의 집합이 다음과 같은 단순한 합동식(congruence)에 의해 지배됨을 증명한다:
$$P = \{ r \ge 0 : r \equiv 1 \pmod{m+1} \}$$

• 따라오는 정리(Corollary) 4.2: 현상 유지 상태($r=N$)가 P-포지션(개시자에게 첫 번째 에스컬레이션의 부담을 지움)이 될 필요충분조건은 $N \equiv 1 \pmod{m+1}$이다.
• 시사점: 안정성은 사다리의 길이 또는 입도에 따라 단조적이지 않다. 단을 추가하거나 단계 크기를 변경하는 것은 산술적 합동 클래스에 따라 현상 유지 상태를 안정과 불안정 사이에서 반전시킬 수 있으며, 이는 "옵션이 많을수록 더 안정적이다"라는 단순한 휴리스틱이 포착하지 못하는 미묘한 차이를 보여준다.

2. 일반 경기 하의 다중 전역 안정성 (정리 5.2)
마지막 플레이어가 승리하는 일반 경기 규칙(normal-play convention) 하에서, $k$개의 독립적인 전역의 결합 안정성은 각 구성 요소의 그룬디 값(Grundy values)의 **님-합(Nim-sum, 비트 단위 XOR)**에 의해 결정된다:
$$\bigoplus_{i=1}^k (r_i \pmod{m_i + 1}) = 0$$

• 결과: 결합 안정성은 개별 전역의 합이 아니며, 가장 위험한 단일 전역에 의해 지배되지도 않는다. 이는 모든 전역의 에스컬레이션 거리에 대한 비선형 함수이다.

3. 미제르 경기 하의 다중 전역 안정성 (정리 6.3)
본 논문은 님-합의 축소가 교리적으로 충실한 미제르 규칙 하에서는 실패함을 입증한다.

• 반례: $S=\{1, 2\}$인 상태 $(1, 1)$은 님-합이 0(P-포지션을 예측함)이지만, 역방향 귀납법(backward induction)을 통해 실제로는 N-포지션임을 알 수 있다.
• 미제르 쿼션트: 본 논문은 님-합의 대체제로 미제르 쿼션트를 도입한다. 두 단계 에스컬레이션($S=\{1, 2\}$)의 구체적인 경우, 미제르 쿼션트는 다음과 같은 6차 가환 모노이드(order-six commutative monoid)로 증명된다:
  $$Q = \langle a, b \mid a^2 = 1, b^3 = b \rangle$$
  여기서 패배 집합은 $P = \{a, b^2\}$이다. 이 구조는 다중 전역 안정성이 단순한 균형 휴리스틱(예: 거리 맞추기)이 실패할 수 있음을 의미하는, 비자명한 항등원(idempotents)을 가진 모노이드에 의해 지배됨을 시사한다.

4. 확장 및 한계

• 비연속 집합: 비연속적인 에스컬레이션 집합(예: $S=\{1, 3\}$)의 경우, 단순한 나머지 연산 공식은 상실되지만, 게임은 여전히 주기성을 유지한다.
• 삼극 에스컬레이션: 본 논문은 3인 공정 게임 이론에는 스프라그-그룬디 대응물이 없음을 언급한다. 결과는 연합 역학에 따라 달라지며, 단일 님-합 불변량은 존재하지 않는다. 이는 삼극 에스컬레이션이 양극 체제보다 질적으로 분석하기 어려움을 시사한다.
• 탈에스컬레이션(De-escalation): 사다리를 내려가는 움직임을 허용하면 루프(loopy) 게임이 되어, 유한 스프라그-그룬디 이론의 범위를 벗어나게 된다.

의의 및 주장
본 논문은 공정한 조합 게임 이론(특히 스프라그-그룬디 및 미제르 분석)을 핵 에스컬레이션 사다리에 적용한 첫 사례라고 주장한다.

• 구조적 통찰: 본 논문은 효용이나 보수 구조와 무관하게 성립하는 폐쇄형 구조적 불변량(합동식 및 님-합)을 제공한다.
• 상보성: 저자들은 이 모델을 고전적 억제 이론을 대체하는 것이 아니라, 보수 기반 모델에서 흔히 암묵적으로 남겨지는 "위치론적" 구조를 분리해 내는 상보적인 렌즈로 규정한다.
• 겸허함: 본 논문은 한계를 명시적으로 인정한다: 에스컬레이션 집합 $S$는 특정 교리로부터 도출되는 것이 아니라 가정된 것이며, 모델은 선호의 강도나 인간적 요인을 무시한다. 또한, $m \ge 3$이거나 비연속적인 집합에 대한 미제르 다중 전역 이론은 미완성 상태이다. 주요 기여는 누가 먼저 행동하도록 강요받는지를 결정하는 산술적 불변량을 식별한 데 있다.