게임이론 - (5) 혼합전략과 행동전략

이번 글에서는 혼합전략과 행동전략을 설명하겠습니다.
두 개념은 비슷한 점이 있으므로, 편의상 같이 설명하겠습니다.

1. 혼합전략과 행동전략의 개념

혼합전략은 (전략형 게임에서) 각 경기자가 선택할 수 있는 전략 위에 주어진 확률분포입니다.
앞선 글에서 전략형 게임의 구성요소로서 전략을 소개했었습니다.
각 경기자가 가지고 있는, 기본 구성요소로서의 전략을 순수전략이라고 합니다.
혼합전략은 각 순수전략을 특정 확률로 선택하는 전략입니다.

경기자 $i$의 혼합전략은 보통 $\sigma _i$ 로 표기합니다.
혼합전략은 $\sigma _i : S_i \rightarrow [0,1]$인 함수로 생각할 수 있습니다.
여기서 $S_i$는 경기자 $i$의 순수전략입니다.
경기자 $i$가 혼합전략 $\sigma _i$를 사용할 경우 순수전략 $s^i_k$를
$\sigma _i(s^i_k)$의 확률로 사용한다고 생각합니다.

행동전략은 전개형 게임에서의 개념입니다.
혼합전략과 비슷한 개념입니다만, 각 정보집합에서 선택 가능한 행동집합 위에서 정의된다는 점이 다릅니다.
전개형 게임에서 경기자 $i$의 정보집합 $\left \{ h^i_k \right \}_{k\in K^i}$를 생각하겠습니다.
이때 각 정보집합에서 선택할 수 있는 행동집합 $\left \{ A^i_k \right \}_{k\in K^i}$ 가 존재합니다.
경기자 $i$의 행동전략은 $\pi _i : \bigcup_{k \in K^i} A^i_k \rightarrow  [0,1]$인 함수입니다.
경기자 $i$가 혼합전략 $\pi _i$를 사용할 경우 
정보집합 $h^i_k$에서는 행동 $a^i_k \in A^i_k$를
$\pi _i(a^i_k)$의 확률로 사용한다고 생각합니다.

2. 혼합전략과 행동전략의 조건

이들 전략은 기본적으로 확률분포입니다.
따라서 혼합전략의 경우 아래 조건을 충족시킵니다.
$\sum_{s^i_k \in S_i} \sigma_i(s^i_k) = 1$ for all $i \in I$
$S_i$가 비가산집합이라면 확률밀도함수의 적분이 1이 되면 됩니다.

행동전략 역시 마찬가지입니다.
다만 행동전략은 모든 행동에 대해서 확률을 합하는 것이 아닙니다.
각 정보집합에서 선택할 수 있는 확률을 합해야 합니다.
$\sum_{a^i_k \in A^i_k} \pi_i(a^i_k) = 1$ for all $i \in I$ , $k \in K^i$
행동전략 또한 $A^i_k$가 비가산집합이라면 확률밀도함수의 적분이 1이 되면 됩니다.

3. 혼합전략 개념을 도입한 이유

앞선 여러 글에서 언급했듯이 쿤의 정리는 완전기억게임에서는
임의의 혼합전략에 대응되는 행동전략이 존재한다는 것입니다.
사실 게임이론에서 다루는 게임들은 대부분 완전기억게임입니다.

그러면 혼합전략의 개념을 왜 굳이 도입했는가?라는 질문을 할 수 있습니다.
그 이유는 뒤의 이어지는 글에서 자세히 서술할 내쉬균형과 밀접한 관련이 있습니다.
내쉬균형은 다른 경기자들의 전략에 대해
각 경기자가 나름대로 최적대응(best response)을 선택한 상황을 의미합니다.

임의의 전략형 게임에서 순수전략 내쉬균형은 존재하지 않을 수도 있습니다.
그러나 혼합전략 내쉬균형은 항상 존재합니다.
이는 카쿠타니의 고정점 정리(Kakutani's fixed point theorem)를 사용해서 쉽게 증명할 수 있습니다.

단, 여기에서의 전략형 게임은 유한 전략형 게임을 의미합니다.
다시 말해 1) 경기자 수가 유한하고 2) 각 경기자가 선택할 수 있는 순수전략의 수도 유한해야 합니다.
이 두 조건 중 하나라도 교란되면 혼합전략 내쉬균형이 존재하지 않을 수도 있습니다.
물론 위 조건이 교란되어도 혼합전략 내쉬균형이 존재할 수도 있습니다.
예컨대, 전략집합이 실수 집합의 부분집합으로서 비가산집합이라고 해보겠습니다.
이때 모든 경기자의 보수함수가 각자의 전략에 대해서 연속이고 전략집합이 컴팩트하면(유계이고 폐집합이면)
항상 혼합전략 내쉬균형이 존재합니다.
자세한 논의는 후술할 내쉬균형에서 다루겠습니다.