강열등전략의 반복 소거

절대 쓰지 않을 전략을 하나씩 지워나가는 과정을 본다. 라운드 슬라이더를 밀며 순서대로 소거한다.

어떤 전략이 다른 전략보다 항상 나쁘면 합리적 경기자는 쓰지 않는다. 그 전략을 지우면 표가 작아진다. 작아진 표에서는 또 다른 나쁜 전략이 드러난다. 이 씬에서는 C와 M과 D가 차례로 사라지고 U만 남는다.

예를 들면, 🏪 가게에 🍬 사탕이 세 종류 있다고 하자. 한 종류는 다른 종류보다 항상 작고 맛도 없다. 그런 사탕은 아무도 고르지 않으니 진열대에서 빼도 된다. 빼고 나면 또 항상 손해인 사탕이 눈에 띈다. 이렇게 지워나가면 마지막 선택이 남는다.

si′ strictly dominates si  ⟺  ui(si′,s−i)>ui(si,s−i)    ∀s−is_i' \text{ strictly dominates } s_i \iff u_i(s_i', s_{-i}) > u_i(s_i, s_{-i}) \;\; \forall s_{-i}

이 씬이 포함된 학습 경로

예제

3×33 \times 3 게임에서 강열등전략 소거를 3라운드까지 수행하고, 각 라운드에서 무엇이 왜 제거되는지 밝혀라.

LCRU(4,3)(5,1)(6,2)M(2,1)(8,4)(3,6)D(3,0)(9,6)(2,8)\begin{matrix} & L & C & R \\ U & (4,3) & (5,1) & (6,2) \\ M & (2,1) & (8,4) & (3,6) \\ D & (3,0) & (9,6) & (2,8) \end{matrix}
3라운드 후 — P1은 UU만 남고 P2는 LL을 택한다.
증명 보기

  1. 라운드 1: P2의 보수만 보면 CC 열 (1,4,6)(1, 4, 6) vs RR 열 (2,6,8)(2, 6, 8) — 모든 행에서 RR이 크므로 RR이 CC를 강우월한다. CC 제거.

  2. 라운드 2 ({L,R}\{L,R\} 하에서): P1의 MM 행 (2,3)(2,3) vs UU 행 (4,6)(4,6) — UU가 강우월한다. MM 제거.

    라운드 3: DD 행 (3,2)(3,2) vs UU 행 (4,6)(4,6) — 다시 UU가 강우월한다. DD 제거.

  3. P1에게는 UU만 남았다.

    P2는 UU에 대해 LL(보수 33)과 RR(보수 22) 중 LL을 택한다.

    최종 결과 (U,L)=(4,3)(U, L) = (4, 3) — 내쉬 균형이기도 하다(일방적 이탈이 손해).

강열등전략 소거는 내쉬 균형을 절대 제거하지 않음을 증명하라.

소거 완료 상태 — 균형 (U,L)(U, L)은 살아남았다.
증명 보기

  1. si′s_i'가 sis_i를 강우월한다는 것은 모든 s−is_{-i}에 대해 ui(si′,s−i)>ui(si,s−i)u_i(s_i', s_{-i}) > u_i(s_i, s_{-i})라는 뜻이다. 내쉬 균형 s∗s^*에서 si∗s_i^*가 강열등전략이라면, si′s_i'로 바꾸면 상대 전략 s−i∗s_{-i}^*에 대해 보수가 엄격히 올라가므로 s∗s^*는 균형일 수 없다 — 모순.

  2. 따라서 첫 라운드에서 제거되는 전략은 어떤 내쉬 균형의 구성요소도 될 수 없다.

    제거 후 남은 "축소 게임"에서도 같은 논증이 적용되므로, 귀납적으로 모든 라운드의 소거가 내쉬 균형을 보존한다.

    즉 IEDS의 결과 집합은 항상 모든 내쉬 균형을 포함한다.

8. 게임이론