게임은 경기자들이 동시에 전략에 따른 행동을 하는 동시 게임과 순차적으로 하는 순차적 게임으로 나뉘며, 이를 정규형(normal form)이나 확장형(extensive form)으로 나타낼 수 있습니다. 정규형은 이전 글들에서 소개한 것처럼 보수행렬을 통해 표현하는 방법입니다. 일반적으로 N명의 경기자가 있다고 하고 이 집합을 I={1,2, ..., N}라고 합시다. 각 경기자 i는 K개의 전략으로 이루어진 전략 집합 Si={1,2, ..., K}를 갖습니다. N명의 경기자가 자신의 전략 집합 중 하나씩 제시하고 그 결과로 각 경기자에게 보수가 돌아갑니다. 각 경기자가 하나씩 제시한 전략들로 만든 벡터를 전략쌍 s라고 하며, 가능한 모든 전략쌍의 집합, 즉 전략 집합들의 데카르트 곱(cartesian product)을 전략공간 S라 부릅니다.
$$s_i\in S_i,\ s= (s_1,s_2,\cdots, s_N),\ S= \times_{i\in I} S_i$$
또한 S의 각 원소에 대응하는 각 경기자의 보수는 실수(real number)로 주어집니다. 경기자 i의 보수는 πi로 나타냅니다. 이렇게 정의된 정규형 게임을 간단히 다음처럼 나타냅니다.
$$G=[I,\{S_i\}_{i\in I},\{\pi_i\}_{i\in I}]$$
이제 강우월 전략(strictly dominant strategy)을 정의합니다.
$$\pi_i(s_i,s_{-i})>\pi_i(s'_i,s_{-i})\ \forall s_{-i}\in S_{-i}$$
첨자 -i는 "경기자 i를 제외"한 나머지 경기자들만의 전략쌍을 뜻합니다.
$$s_{-i}=(s_1,\cdots,s_{i-1},s_{i+1},\cdots,s_N)$$
i를 제외한 다른 경기자들이 어떤 전략쌍을 택하든 거기에 i의 전략 중 s'i로 대응할 때보다 si로 대응할 때 언제나 더 높은 보수를 준다면 전략 si는 전략 s'i에 비해 강우월 전략이 됩니다. 이때 s'i는 강열등 전략입니다. 위 부등식에서 '크다'라는 부등호를 '크거나 같다'로 바꾸면 약우월 전략(weakly dominant strategy)의 정의가 됩니다.
경기자 i의 최적대응(best response)은 i를 제외한 나머지 경기자들의 전략쌍 s-i에 대응하여 가장 높은 보수를 주는 i의 전략들의 집합입니다.
$$BR_i(s_{-i})=\{s_i\in S_i|\pi_i(s_i,s_{-i})\geq \pi_i(s'_i,s_{-i}),\ \forall s'_i\in S_i\}$$
다음으로 내쉬균형(Nash equilibrium)의 정의입니다. 모든 i에 대해 그들의 모든 전략 si에 대해 다음 조건을 만족시키는 전략쌍 s*를 내쉬균형이라고 부릅니다.
$$\pi_i(s^*_1,\cdots,s^*_{i-1},s^*_i,s^*_{i+1},\cdots,s^*_N)\geq \pi_i(s^*_1,\cdots,s^*_{i-1},s_i,s^*_{i+1},\cdots,s^*_N)$$
경기자들이 일단 내쉬균형에 도달했다면 다른 전략으로 바꿀 유인이 없기 때문에 '균형'이라고 합니다. 내쉬균형의 집합을 SNE로 씁니다.
어떤 게임에서 내쉬균형을 찾는 일은 매우 중요하며 반복적으로 강열등 전략을 제거함으로써 내쉬균형을 찾을 수 있습니다. 그렇게 찾은 내쉬균형이 1개라면 각 경기자들은 그 균형을 이루는 전략들을 선택할 것이라고 예측할 수 있습니다. 그런데 2개 이상이라면 경기자들이 어느 쪽을 선택할지 알 수 없지요. 특히 내쉬균형 중 다소 비합리적으로 보이는 균형을 배제하는 방법들도 제시되었는데, '손떨림으로부터 완전한 균형(trembling hand perfect equilibrium)'이 그 중 하나입니다. 균형 전략을 제시하려다 실수로 다른 전략을 선택할 확률 ε을 고려할 때에도 그 균형 전략이 여전히 우월하다면 완전한 균형이 되며, 아니라면 아닌 겁니다.
지금까지는 순수전략(pure strategy)만을 다루었는데 이제 혼합전략(mixed strategy)을 정의합니다. 경기자 i가 자신의 전략 중 k번째 전략을 선택할 확률을 σik로 쓰면, 이 확률들의 집합, 즉 순수전략들에 대한 확률분포가 혼합전략입니다.
$$\sigma_i=(\sigma_{i1},\cdots,\sigma_{iK}),\ \sum_{k=1}^K\sigma_{ik}=1,\ 0\leq \sigma_{ik}\leq 1$$
경기자 i의 혼합전략의 집합은 다음처럼 쓸 수도 있습니다.
$$\Delta_i=\left\{\sigma_i\in R^K_+\Big|\sum_{k=1}^K\sigma_{ik}=1\right\}$$
R+는 음이 아닌 실수의 집합이고, 위첨자 K는 K차원 실수 공간임을 뜻합니다. 경기자 i의 모든 σik가 양수인 경우를 완전 혼합전략(completely mixed strategy)이라 부릅니다. 혼합전략을 이용해 순수전략을 나타낼 수도 있습니다. 예를 들어 1번 순수전략은 아래 왼쪽과 같고, 순수전략들을 이용해 혼합전략을 다시 나타내면 아래 오른쪽이 됩니다.
$$h^1=(1,0,\cdots,0),\ \sigma_i=\sum_{k=1}^K h^k\sigma_{ik}$$
혼합전략공간은 Θ로 표시합니다.
$$\sigma=(\sigma_1,\cdots,\sigma_N)\in \Theta=\times_{i\in I}\Delta_i$$
이제 경기자 i의 보수 ui는 다음처럼 얻어집니다.
$$u_i(\sigma)=\sum_{k_1=1}^K\cdots \sum_{k_N=1}^K \sigma_{1k_1}\cdots \sigma_{Nk_N}\pi_i(k_1,\cdots, k_N)$$
강우월 전략을 다시 정의합니다.
$$u_i(\sigma_i,\sigma_{-i})>u_i(\sigma'_i,\sigma_{-i})\ \forall \sigma_{-i}\in \Delta_{-i}$$
위 조건이 만족될 때 σ'i보다 σi가 강우월하다고 하고, 위 부등호가 '크거나 같다'로 바뀌면 약우월 전략의 정의가 됩니다. 다음으로 상대 경기자들이 혼합전략을 쓸 때 그에 대한 순수전략 최적대응을 정의합니다.
$$BR^s_i(\sigma_{-i})=\{k\in S_i|u_i(h^k_i,\sigma_{-i})\geq u_i(h^j_i,\sigma_{-i}),\ \forall j\in S_i\}$$
상대 경기자들이 혼합전략을 쓸 때 그에 대한 혼합전략 최적대응도 다음처럼 정의됩니다.
$$BR^m_i(\sigma_{-i})=\{\sigma_i\in \Delta_i|u_i(\sigma_i,\sigma_{-i})\geq u_i(\sigma'_i,\sigma_{-i}),\ \forall \sigma'_i\in \Delta_i\}$$
모든 i에 대해 그들의 모든 혼합전략 σi에 대해 다음 조건을 만족시키는 전략쌍 σ*를 혼합전략 내쉬균형이라고 부릅니다.
$$u_i(\sigma^*_1,\cdots,\sigma^*_{i-1},\sigma^*_i,\sigma^*_{i+1},\cdots,\sigma^*_N)\geq u_i(\sigma^*_1,\cdots,\sigma^*_{i-1},\sigma_i,\sigma^*_{i+1},\cdots,\sigma^*_N)$$
중간중간 뛰어넘으면서 여기까지 왔네요. 125쪽부터 시작하는 제5장 제목은 '게임이론과 합리성'입니다. 게임이론의 균형을 찾기 위해 경기자들에게 요구되는 합리성은 어느 정도인가?라는 질문을 던지고 있습니다. 각 경기자는 자신과 상대방의 행동의 결과 어떤 보수가 주어질지에 대해 모두 알고 있으며, 또한 그 보수들을 비교하여 가장 높은 보수를 주는 전략을 선택하는 합리성을 지니고 있다는 가정이 필요합니다. 덧붙여 자신의 보수뿐 아니라 상대방의 보수도 알고 있어야 하며, 상대 경기자 역시 합리적이라고 가정할 필요가 있을 때도 있으며 이를 '초합리성'이라 부른답니다.
앞에서 잠깐 말했던 '강열등 전략의 반복적 제거'를 위해서는 경우에 따라 "상대방이 합리적이라는 사실을 자신이 알고 있다는 사실을 상대방이 알고 있다는 사실을 자신이 알고 있을 것"(136쪽)이라는 가정이 필요하기도 합니다. 뭐 자세한 건 책을 보세요;;; 제1부 마지막에서는 진화적 게임이론과 합리성의 관계를 소개하고 있는데요, 사실 이 얘기를 원래 하고 싶었는데 다음 글에서 해야겠습니다.
