우월 전략

3. 수학적 설명

참가자 $i$를 제외한 나머지 참가자의 전략을 $s\_\{-i\}\; \backslash in\; S\_\{-i\}$라고 할 때, 참가자 $i$에 있어 다음의 조건이 만족될 경우 전략 $s^*\backslash in\; S\_i$는 나머지 전략 $s^\backslash prime\backslash in\; S\_i$에 대해 '''약한 우월전략'''이 된다.

:$\backslash forall\; s\_\{-i\}\backslash in\; S\_\{-i\}\backslash left[u\_i(s^*,s\_\{-i\})\backslash geq\; u\_i(s^\backslash prime,s\_\{-i\})\backslash right]$ (단, 부등호 $\backslash ge$가 아닌 $>$가 최소 한 번은 성립해야 함)

한편, 다음의 조건이 만족될 경우 전략 $s^*$는 나머지 전략 $s^\backslash prime$에 대해 '''강한 우월전략'''이 된다.

:$\backslash forall\; s\_\{-i\}\backslash in\; S\_\{-i\}\backslash left[u\_i(s^*,s\_\{-i\})>\; u\_i(s^\backslash prime,s\_\{-i\})\backslash right]$

다음은 플레이어의 집합을 $I$, 혼합 전략 공간을 $\backslash Theta\; =\; \backslash prod\_\{i\; \backslash in\; I\}\; \backslash Delta\_i$, 혼합 전략 보수 함수를 $u\_i\; :\; \backslash Theta\; \backslash to\; \backslash mathbb\{R\}\; \backslash quad\; (i\; \backslash in\; I)$ 로 한다. 또한, 전략 $x\_i\; \backslash in\; \backslash Delta\_i$ 와 전략 프로파일 $z\; \backslash in\; \backslash Theta$ 에 따라, 전략 프로파일 $(x\_i,\; z\_\{-i\})\; \backslash in\; \backslash Theta$ 는 플레이어 $i$ 가 전략 $x\_i$ 를 선택하고, 그 외 플레이어가 $z$ 에 따라 전략을 선택하는 전략 프로파일을 나타낸다.

; 지배 관계

: 전략 $x\_i,\; y\_i\; \backslash in\; \backslash Delta\_i$ 가 임의의 전략 프로파일 $z\; \backslash in\; \backslash Theta$ 에 대해 $u\_i(x\_i,\; z\_\{-i\})\; \backslash ge\; u\_i(y\_i,\; z\_\{-i\})$ 를 만족하고, 적어도 하나의 $z$ 에 대해서는 등호가 성립하지 않을 때(즉, $u\_i(x\_i,\; z\_\{-i\})\; >\; u\_i(y\_i,\; z\_\{-i\})$ 인 $z$가 존재할 때), "$x\_i$는 $y\_i$를 '''약지배'''한다"($x\_i$ weakly dominates $y\_i$)^[4], 또는 "$y\_i$는 $x\_i$에 '''약지배'''된다"($y\_i$ is weakly dominated by $x\_i$) 라고 한다.

: 전략 $x\_i,\; y\_i\; \backslash in\; \backslash Delta\_i$ 가 임의의 전략 프로파일 $z\; \backslash in\; \backslash Theta$ 에 대해 $u\_i(x\_i,\; z\_\{-i\})\; >\; u\_i(y\_i,\; z\_\{-i\})$ 를 만족할 때, "$x\_i$는 $y\_i$를 '''강지배'''한다"($x\_i$ strictly dominates $y\_i$)^[4]고 하며, 때로는 단순히 '''지배'''한다고도 부른다^[3]. 또는 "$y\_i$는 $x\_i$에 '''강지배'''된다"($y\_i$ is strictly dominated by $x\_i$) 라고 한다.

; 지배 전략

: 전략 $x\_i\; \backslash in\; \backslash Delta\_i$ 가 임의의 다른 전략 $y\_i\; \backslash in\; \backslash Delta\_i\; \backslash setminus\; \backslash \{x\_i\backslash \}$ 를 '''약지배'''할 때, $x\_i$ 를 '''약지배 전략''' (weakly dominant strategy)^[3]이라고 한다.

: 전략 $x\_i\; \backslash in\; \backslash Delta\_i$ 가 임의의 다른 전략 $y\_i\; \backslash in\; \backslash Delta\_i\; \backslash setminus\; \backslash \{x\_i\backslash \}$ 를 '''강지배'''할 때, $x\_i$ 를 '''강지배 전략''' (strictly dominant strategy)이라고 하며, 때로는 단순히 '''지배 전략'''이라고도 부른다^[3].

; 지배되는 전략

: 전략 $x\_i\; \backslash in\; \backslash Delta\_i$ 가 어떤 다른 전략 $y\_i\; \backslash in\; \backslash Delta\_i$ 에 '''약지배'''될 때, $x\_i$ 를 '''약지배되는 전략''' (weakly dominated strategy)이라고 한다.

: 전략 $x\_i\; \backslash in\; \backslash Delta\_i$ 가 어떤 다른 전략 $y\_i\; \backslash in\; \backslash Delta\_i$ 에 '''강지배'''될 때, $x\_i$ 를 '''강지배되는 전략''' (strictly dominated strategy)이라고 한다.

4. 용어 (Terminology)

우월전략에는 '''강한 우월전략'''과 '''약한 우월전략'''이 있다. 게임의 한 참가자에게 전략 A와 전략 B가 존재한다고 가정해 보자.

플레이어는 두 가지 전략 A와 B를 비교하여 어느 쪽이 더 나은지 판단할 수 있으며, 그 결과는 다음과 같이 분류된다.

• B가 A를 '''엄격하게 지배'''(>)한다: 다른 플레이어가 어떤 전략을 선택하든, B를 선택하는 것이 항상 A를 선택하는 것보다 더 나은 결과를 가져온다. 이는 전략 B가 A에 대한 '''강한 우월전략'''임을 의미한다.
• B가 A를 '''약하게 지배'''(≥)한다: 다른 플레이어가 어떤 전략을 선택하든, B를 선택하는 것이 항상 A를 선택하는 것만큼 좋은 결과를 가져오며, B가 A보다 더 나은 결과를 가져오는 상대방의 행동(전략)이 적어도 하나 이상 존재한다.^[1] 이는 전략 B가 A에 대한 '''약한 우월전략'''임을 의미한다. (참고로, B가 A를 엄격하게 지배한다면, B는 A를 약하게도 지배한다.)
• B는 A에 의해 '''약하게 지배'''된다: B가 A보다 더 나쁜 결과를 가져오는 상대방의 행동이 적어도 하나 있고, 다른 모든 상대방의 행동은 B에게 A와 동일한 보상을 제공한다. (즉, 전략 A가 B를 약하게 지배하는 경우이다.)
• B는 A에 의해 '''엄격하게 지배'''된다: 다른 플레이어가 어떤 전략을 선택하든, B를 선택하는 것은 항상 A를 선택하는 것보다 더 나쁜 결과를 가져온다. (즉, 전략 A가 B를 엄격하게 지배하는 경우이다.)
• A와 B는 서로를 지배하지 않는다: B와 A는 동등하지 않으며, 서로 지배하거나 지배받지 않는다. 상대방의 전략 선택에 따라 A가 더 나을 수도, B가 더 나을 수도 있다. 예를 들어, 가위바위보에서 B가 "바위"이고 A가 "가위"인 경우가 해당된다.

• 전략 B가 '''엄격하게 우세'''하다면, 이는 전략 B가 다른 모든 가능한 전략을 '''엄격하게 지배'''한다는 의미이다. 즉, '''강지배 전략'''이다.^[3]
• 전략 B가 '''약하게 우세'''하다면, 이는 전략 B가 다른 모든 가능한 전략을 '''약하게 지배'''한다는 의미이다. 즉, '''약지배 전략'''이다.^[3]
• 전략 B가 '''엄격하게 지배'''된다면, B를 엄격하게 지배하는 다른 전략이 존재한다는 의미이다. 즉, '''강지배되는 전략'''이다.
• 전략 B가 '''약하게 지배'''된다면, B를 약하게 지배하는 다른 전략이 존재한다는 의미이다. 즉, '''약지배되는 전략'''이다.

• '''전략''': 게임에서 플레이어가 모든 가능한 상황(정보 집합)에 대비하여 어떤 행동을 취할지 미리 정해 놓은 완전한 계획을 의미한다. 즉, 플레이어가 마주칠 수 있는 모든 결정 지점에서 어떤 선택을 할지를 명시한다.^[2]
• '''합리성''': 각 플레이어가 자신의 선호도에 따라 가장 유리한 결과(가장 높은 보상 또는 효용)를 얻기 위해 행동한다는 기본 가정을 말한다. 이는 단순히 금전적 이익뿐만 아니라, 노력 최소화, 정의 추구 등 다양한 형태의 보상을 포함할 수 있다. 합리적인 플레이어는 가능한 결과들을 자신의 선호 순서에 따라 평가하고, 가장 만족스러운 결과를 가져올 행동을 선택한다.^[2]
• '''공통 지식''': 모든 플레이어가 게임의 규칙, 가능한 전략, 각 전략에 따른 보상을 알고 있을 뿐만 아니라, 다른 모든 플레이어들도 이 사실을 알고 있다는 것을 서로 아는 상태를 의미한다. 이는 플레이어들이 상대방의 합리적인 행동을 예측하고 자신의 전략을 결정하는 데 중요한 전제가 된다.^[2]

• '''지배 관계'''
• '''약지배''': 전략 ''x''_''i'', ''y''_''i'' ∈ Δ_''i'' 가 모든 상대방 전략 프로파일 ''z'' ∈ Θ 에 대해 ''u''_''i'' (''x''_''i'', ''z''_−''i'') ≥ ''u''_''i'' (''y''_''i'', ''z''_−''i'') 를 만족하고, 적어도 하나의 ''z'' 에 대해서는 등호가 성립하지 않을 때(즉, ''u''_''i'' (''x''_''i'', ''z''_−''i'') > ''u''_''i'' (''y''_''i'', ''z''_−''i'')), "''x''_''i'' 는 ''y''_''i'' 를 '''약지배'''한다" 또는 "''y''_''i'' 는 ''x''_''i'' 에 '''약지배'''된다"고 한다.^[4]
• '''강지배''': 전략 ''x''_''i'', ''y''_''i'' ∈ Δ_''i'' 가 모든 상대방 전략 프로파일 ''z'' ∈ Θ 에 대해 ''u''_''i'' (''x''_''i'', ''z''_−''i'') > ''u''_''i'' (''y''_''i'', ''z''_−''i'') 를 만족할 때, "''x''_''i'' 는 ''y''_''i'' 를 '''강지배'''한다" 또는 "''y''_''i'' 는 ''x''_''i'' 에 '''강지배'''된다"고 한다.^[4][3] (단순히 '지배한다'고도 한다.)

• '''지배 전략'''
• '''약지배 전략''': 전략 ''x''_''i'' ∈ Δ_''i'' 가 자신을 제외한 다른 모든 전략 ''y''_''i'' ∈ Δ_''i'' \ {''x''_''i''} 를 '''약지배'''할 때, ''x''_''i'' 를 '''약지배 전략'''이라고 한다.^[3]
• '''강지배 전략''': 전략 ''x''_''i'' ∈ Δ_''i'' 가 자신을 제외한 다른 모든 전략 ''y''_''i'' ∈ Δ_''i'' \ {''x''_''i''} 를 '''강지배'''할 때, ''x''_''i'' 를 '''강지배 전략'''이라고 한다.^[3] (단순히 '지배 전략'이라고도 한다.)

• '''지배되는 전략'''
• '''약지배되는 전략''': 전략 ''x''_''i'' ∈ Δ_''i'' 가 어떤 다른 전략 ''y''_''i'' ∈ Δ_''i'' 에 '''약지배'''될 때, ''x''_''i'' 를 '''약지배되는 전략'''이라고 한다.
• '''강지배되는 전략''': 전략 ''x''_''i'' ∈ Δ_''i'' 가 어떤 다른 전략 ''y''_''i'' ∈ Δ_''i'' 에 '''강지배'''될 때, ''x''_''i'' 를 '''강지배되는 전략'''이라고 한다.

5. 우월전략과 내쉬 균형

게임에서 한 플레이어에게 '''강한 우월 전략'''(strictly dominant strategy)이 존재하면, 그 플레이어는 합리적으로 그 전략을 선택한다. 왜냐하면 다른 어떤 전략을 선택하더라도 우월 전략보다 더 나은 결과를 얻을 수 없기 때문이다.^[4] 따라서 강한 우월 전략을 가진 플레이어는 게임의 모든 내쉬 균형에서 반드시 그 우월 전략을 사용한다.

만약 게임에 참여하는 모든 플레이어가 각자 강한 우월 전략을 가지고 있다면, 이 전략들의 조합으로 이루어진 결과는 '''우월 전략 균형'''(dominant strategy equilibrium)이라고 불린다.^[3] 우월 전략 균형은 유일한 내쉬 균형이 된다. 모든 플레이어가 합리적이라면 이 균형이 실현될 것으로 예상할 수 있다.

그러나 우월 전략 균형이나 내쉬 균형이 반드시 파레토 효율적인 것은 아니다. 즉, 모든 플레이어에게 더 나은 결과를 가져다주는 다른 결과(비-균형 결과)가 존재할 수 있음에도 불구하고, 합리적인 플레이어들이 내쉬 균형에 도달하는 경우가 있다. 죄수의 딜레마는 파레토 비효율적인 우월 전략 균형의 대표적인 예시다.

오른쪽 표(예시 1)에서 각 플레이어에게 전략 A는 전략 B에 대해 강한 우월 전략이다. 상대방이 어떤 전략을 선택하든, 자신은 B보다 A를 선택하는 것이 항상 더 높은 보수를 얻는다 (상대가 A일 때 3 > 1, 상대가 B일 때 8 > 6). 따라서 (A, A)는 유일한 우월 전략 균형이자 내쉬 균형이다. 이 균형에서 두 플레이어는 각각 3의 보수를 얻는다. 하지만 두 플레이어 모두 전략 B를 선택하는 (B, B)의 경우, 각각 6의 보수를 얻어 (A, A)보다 더 높은 보수를 얻을 수 있다. 즉, 내쉬 균형 (A, A)는 파레토 효율적이지 않다. 그럼에도 불구하고 각 플레이어는 상대방이 B를 선택할 것이라는 보장이 없다면, 자신이 먼저 B로 바꿀 유인이 없다 (상대가 A를 유지하면 자신은 1만 얻게 되므로).

강하게 열등한 전략(strictly dominated strategy)은 내쉬 균형의 일부가 될 수 없다. 합리적인 플레이어는 강하게 열등한 전략을 선택하지 않기 때문이다. 반면, '''약하게 열등한 전략'''(weakly dominated strategy)은 내쉬 균형의 일부가 될 수 있다. 약하게 우월한 전략(weakly dominant strategy)은 다른 모든 전략에 비해 같거나 더 나은 결과를 가져오며, 적어도 하나의 경우에서는 더 나은 결과를 가져오는 전략이다. 반대로 약하게 열등한 전략은 다른 전략에 비해 같거나 더 나쁜 결과를 가져오며, 적어도 하나의 경우에서는 더 나쁜 결과를 가져오는 전략이다.

오른쪽 표(예시 2)를 보자. 각 플레이어에게 전략 C는 전략 D에 대해 약하게 우월하다. 만약 상대방이 C를 선택하면, C를 선택하면 1을 얻고 D를 선택하면 0을 얻는다 (C가 더 낫다). 만약 상대방이 D를 선택하면, C를 선택하면 0을 얻고 D를 선택해도 0을 얻는다 (C와 D가 같다). 따라서 C는 D보다 결코 나쁘지 않고, 어떤 경우에는 더 낫기 때문에 약하게 우월하다. 반대로 D는 C에 대해 약하게 열등하다. 이 게임에는 두 개의 내쉬 균형이 존재한다: (C, C)와 (D, D). (C, C)는 내쉬 균형이다. 어느 플레이어도 일방적으로 D로 바꾸면 보수가 1에서 0으로 감소하므로 이탈할 유인이 없다. (D, D) 역시 내쉬 균형이다. 어느 플레이어도 일방적으로 C로 바꾸더라도 보수가 0으로 동일하므로 이탈할 유인이 없다. 이처럼 약하게 열등한 전략 D가 포함된 (D, D)도 내쉬 균형이 될 수 있다.

어떤 전략 프로파일에 대해 최적 반응이 되는 전략은 강하게 지배되지 않으므로 내쉬 균형을 이루는 전략은 모두 강하게 지배되지 않는다. 특히 완전 혼합 전략으로만 구성된 전략 프로파일에 대한 최적 반응이 되는 전략은 약하게 지배되지 않으며, 또한 약하게 지배되지 않는 전략으로만 구성된 내쉬 균형 (지배되지 않는 내쉬 균형)은 어떤 전략형 게임에도 반드시 존재한다는 것이 알려져 있다.

6. 강하게 지배되는 전략의 반복적 제거

게임 이론에서 '''강우월 전략의 반복적 제거'''(Iterated Elimination of Strictly Dominated Strategies, '''IESDS''')^[5]는 게임의 해를 찾는 기본적인 방법 중 하나이다. 이 방법은 게임에 참여하는 플레이어들이 합리적이라고 가정하고, 합리적인 플레이어라면 절대로 선택하지 않을 강하게 지배되는 전략(strictly dominated strategy)을 단계적으로 제거해 나가는 과정이다.

과정은 다음과 같다.

1. 각 플레이어의 전략 중에서 다른 어떤 전략보다 항상 나쁜 결과를 가져오는 '강하게 지배되는 전략'을 찾는다.

2. 합리적인 플레이어는 이런 전략을 사용하지 않을 것이므로, 해당 전략들을 모든 플레이어의 선택 가능성에서 제외한다. 이로 인해 게임의 규모가 작아진다.

3. 이전에는 지배되지 않았던 전략이라도 작아진 새로운 게임에서는 지배되는 전략이 될 수 있다. 따라서 작아진 게임에서 다시 강하게 지배되는 전략이 있는지 확인한다.

4. 더 이상 제거할 강하게 지배되는 전략이 없을 때까지 이 과정을 반복한다.

이러한 반복 제거 과정이 유효하려면, 게임에 참여하는 모든 플레이어가 합리적일 뿐만 아니라, "다른 모든 플레이어도 합리적이다"라는 사실을 알고, "다른 모든 플레이어가 내가 합리적이라는 것을 안다는 사실을 안다"는 식으로 서로의 합리성에 대한 믿음이 공통 지식(common knowledge)이 되어야 한다. 즉, 합리성에 대한 가정이 무한히 이어져야 한다는 것이다 (Aumann, 1976 참고).

만약 게임이 유한 게임이라면, 이 반복 제거 과정은 언젠가 멈추게 된다. 이때까지 제거되지 않고 남은 전략들을 '''반복적으로 강우월되지 않는 전략'''(not iteratively strictly dominated)^[4]이라고 부른다. 만약 이 과정을 통해 각 플레이어에게 단 하나의 전략만 남게 된다면, 그 게임은 '''강우월에 의해 풀린다'''(strictly dominance solvable)^[4]고 하며, 때로는 단순히 '''지배에 의해 풀린다'''(dominance solvable)라고 부르기도 한다^[3]. 이 반복 제거의 결과는 어떤 플레이어의 전략부터 제거하든, 또는 한 번에 여러 전략을 제거하든 순서에 상관없이 항상 동일하게 나타난다.^[3][4][7]

참고로, '강하게' 지배되는 전략 대신 '약하게' 지배되는 전략(weakly dominated strategy)을 제거하는 방법도 생각해 볼 수 있다. 하지만 약우월 전략 제거는 제거 순서에 따라 최종 결과가 달라질 수 있으며, 중요한 해인 내쉬 균형 중 일부가 제거될 수도 있다는 문제점이 있다.^[3][8]

IESDS는 기본적으로 순수 전략만을 대상으로 제거를 진행하지만^[6], 순수 전략만을 고려하는 것에는 한계가 있을 수 있다.

6. 1. 강우월 전략 반복 제거의 한계

이 게임에서 플레이어 B의 순수 전략인 b₁, b₂, b₃ 사이에는 서로를 강우월하는 관계가 없다. 어떤 순수 전략도 다른 순수 전략보다 항상 더 나은 결과를 보장하지 않기 때문이다.

그러나 플레이어 B가 b₁과 b₃를 각각 50%의 확률로 선택하는 혼합 전략을 사용한다고 가정해보자. 이 혼합 전략을 사용했을 때 플레이어 B가 얻는 기대 보수는 다음과 같다.

• 플레이어 A가 a₁을 선택할 경우: (b₁ 선택 시 보수 3 × 0.5) + (b₃ 선택 시 보수 0 × 0.5) = 1.5
• 플레이어 A가 a₂을 선택할 경우: (b₁ 선택 시 보수 0 × 0.5) + (b₃ 선택 시 보수 5 × 0.5) = 2.5

7. 최적 반응 및 내쉬 균형과의 관련

어떤 전략 프로파일에 대해 최적 반응이 되는 전략은 강하게 지배되지 않으므로 내쉬 균형을 이루는 전략은 모두 강하게 지배되지 않는다. 특히 완전 혼합 전략으로만 구성된 전략 프로파일에 대한 최적 반응이 되는 전략은 약하게 지배되지 않으며, 또한 약하게 지배되지 않는 전략으로만 구성된 내쉬 균형 (지배되지 않는 내쉬 균형)은 어떤 전략형 게임에도 반드시 존재한다는 것이 알려져 있다^[4].

참조

_[1] 논문 Essentials of Game Theory: A Concise Multidisciplinary Introduction 2008-01
_[2] 서적 Strategy: An Introduction to Game Theory 2013-05-09
_[3] 서적 ゼミナール ゲーム理論入門 日本経済新聞出版 2008-04-07
_[4] 서적 進化ゲームの理論 文化書房博文社 1998-03-31
_[5] 문서
_[6] 문서
_[7] 문서
_[8] 문서