승부차기의 순간을 상상해 봅시다. 키커는 좌측이나 우측으로 공을 찰 수 있고, 키퍼는 반대로 좌측이나 우측으로 몸을 날릴 수 있습니다.(당연히 보는 방향에 따라 좌우가 바뀌지만, 키커의 왼쪽과 키퍼의 왼쪽이 같은 방향이라고 가정하겠습니다.) 만약 키커가 공을 찬 방향과 키퍼가 몸을 날린 방향이 다르다면, 키커는 1점을 얻습니다. 반대로 키커가 공을 찬 방향과 키퍼가 몸을 날린 방향이 동일하다면, 키커는 아무런 점수를 얻지 못합니다. 즉 다음과 같은 행렬을 생각해 볼 수 있겠죠.
| 키커 왼쪽 | 키커 오른쪽 | |
| 키퍼 왼쪽 | 0 | 1 |
| 키퍼 오른쪽 | 1 | 0 |
키커의 목표는 당연히 골을 넣어 점수를 얻는 것이며, 반대로 키퍼의 목표는 공을 막아 점수를 지켜내는 것입니다. 과연 키커와 키퍼가 공을 어떻게 차고 막아야 각자에게 이득이 될 수 있을까요? 먼저 키커의 입장에서 생각을 해 봤을 때, 한 쪽 방향으로만 공을 차는 것은 그렇게 좋지 않은 선택이 됩니다. 예를 들어, 키커가 항상 왼쪽으로 공을 찬다고 해보죠. 그러면 키퍼는 왼쪽으로 몸을 날리는 것만으로 항상 점수를 지켜낼 수 있습니다. 반대의 경우도 마찬가지입니다. 만약 키퍼가 항상 왼쪽으로만 몸을 날린다면, 키커가 오른쪽으로 공을 차는 것만으로 항상 점수를 따낼 수 있습니다.
따라서 키커도, 키퍼도 "확률적으로 혼합된 전략"을 구사해야 합니다. 즉 키커든 키퍼든 일정 확률로는 왼쪽을 선택하고, 또 다른 확률로는 오른쪽을 선택하는 것이죠. 그러면 아무래도 서로가 어떻게 움직일지 가늠이 잡히지 않을테니, 키커의 입장에서는 골을 넣을 것을, 반대로 키퍼의 입장에서는 공을 막을 것을 서로 기대할 수 있게 됩니다. 그러면 다음과 같은 의문점이 자연스레(?) 떠오르실 겁니다.
- 키커와 키퍼가 모두 확률적으로 혼합된 전략을 구사할 수 있을 때, 키커의 입장에서 자신이 얻을 것으로 기대되는 점수의 최댓값과, 반대로 키퍼의 입장에서 키커가 얻을 것으로 기대되는 점수의 최솟값의 크기가 같을 것인가, 다를 것인가?
- (같든지 다르든지 간에) 각자 어떤 전략을 구사해야 각자가 원하는 기댓값을 얻을 수 있을 것이며, 이 전략을 "효율적으로" 계산할 수 있겠는가?
미리 답을 말씀드리자면, 이러한 형태의 문제에서는 두 값이 항상 동일하며, 각각의 전략을 효율적으로 구할 수 있습니다. 위 예시에서는 키커와 키퍼가 모두 절반의 확률로 왼쪽으로, 그리고 나머지 절반의 확률로 오른쪽으로 가는 전략이 해당 기댓값을 구하는 한가지 (그리고 이 예시에서는 유일한) 전략입니다.
2인 제로섬 게임
이러한 형태의 문제는 2인 제로섬 게임(two-player zero-sum game)이라고 불립니다. 엄밀한 정의는 다음과 같습니다. 이름에서 쉽게 알 수 있듯이 이 게임에는 두 명의 선수가 있으며, 각각 선수 1, 선수 2로 칭하겠습니다. 선수 1에게는 총 \(m\) 개의 전략이 있고, 선수 2는 총 \(n\) 개의 전략을 갖습니다. 또한, \( m \times n \) 행렬 \( A \in \mathbb{R}^{m \times n} \)이 주어지며, 이 행렬의 각 \(i\) 행 \(j\) 열의 원소 \( a_{i, j} \)는 선수 1이 전략 \(i\)를 취하고 선수 2가 전략 \(j\)를 선정했을 때 선수 1이 얻는 점수를 나타냅니다. 당연히 선수 1의 목표는 최대한 많은 점수를 얻는 것이며, 반대로 선수 2의 목표는 선수 1이 최소한의 점수를 얻도록 하는 것입니다.
예를 들어, 위 승부차기 선수 1과 선수 2 각각 두 가지의 전략이 주어지고(이때, 둘 다 1은 왼쪽, 2는 오른쪽), 선수 1이 얻는 점수를 나타내는 행렬은 \[ A = \left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right] \]로 표현할 수 있겠습니다.
두 선수는 모두 확률적으로 혼합된 전략을 선택할 수 있습니다. 자세히 말하자면, 선수 1의 전략은 \(x \in \mathbb{R}^m_+\)로 표현될 수 있는데, 이때 이 벡터의 \(i\) 번째 원소 \(x_i\)는 선수 1이 전략 \(i\)를 취하는 확률이 되겠습니다. 똑같이 선수 2의 전략은 \( y \in \mathbb{R}^m_+ \)로 표현될 수 있으며, 이때 이 벡터의 \(j\) 번째 원소 \( y_j \)는 선수 2가 전략 \(j\)를 선택하는 확률입니다. 당연히 \( x, y \)는 확률 분포를 이루어야 하므로, \[ \sum_{i = 1}^m x_i = 1 \text{, } \sum_{j = 1}^n y_j = 1 \tag{1} \]을 만족해야 합니다. 각 선수가 자신의 전략 \(x\)와 \(y\)를 각각 정했을 때, 선수 1이 얻는 점수의 기댓값은 \[ x^\intercal A y = \sum_{i = 1}^m \sum_{j = 1}^n a_{i, j} x_i y_j \]로 표현됩니다.
이제 선수들의 목표를 좀더 구체적으로 적어보도록 하죠. 먼저 선수 1의 목표는 선수 2가 어떤 전략을 가지고 오든지 간에 최대의 기댓값을 얻을 수 있는 전략을 구하는 것입니다. 다시 말해, \[ \max_{x} \min_{y} x^\intercal A y \tag{2} \]를 이루는 \(x\)를 찾는 것이죠. 반대로 선수 2의 목표는 선수 1이 어떤 전략을 취하든 선수 1의 점수를 최소화하도록 기대할 수 있는 전략을 얻는 것으로, \[ \min_{y} \max_{x} x^\intercal A y \tag{3} \]를 만족하는 \(y\)를 구하는 것입니다. 둘의 의미는 완전히 다릅니다. 전자는 선수 1이 어떤 전략 \(x\)를 선택했을 때, 선수 2는 그것을 최대한 망가뜨리는 \(y\)를 고르는데, 그럼에도 \(x^\intercal A y\)의 값을 최대로 만드는 \(x\)를 의미합니다. 반대로 후자는 선수 2가 먼저 어떤 전략 \(y\)를 선택하고, 선수 1은 이를 최대한 망치는 \(x\)를 고르게 되는데, 그래도 \(x^\intercal A y\)의 값이 최소가 되는 \(y\)를 나타냅니다.
폰 노이만의 최소 최대 정리
그러면 서론에서 제시한 두 질문 중 첫 번째를 다음과 같이 다시 적을 수 있습니다.
- 2인 제로섬 게임이 주어졌을 때, 식 2의 값과 식 3의 값은 같은가?
그리고 이는 항상 동일하다는 것이 잘 알려져 있습니다.
정리 1. von Neumann's minimax theorem
임의의 2인 제로섬 게임은 \[ v := \max_{x} \min_{y} x^\intercal A y = \min_{y} \max_{x} x^\intercal A y \]를 만족한다. 이때, \(v\)를 게임의 값(value)이라고 부른다.
네, 폰 노이만이 "그" 폰 노이만이 맞습니다. 많은 사람들은 이 정리가 게임 이론이라는 거대한 학문의 주춧돌이라고 평가를 하더군요.(역시, 대단한 분입니다.) 이 정리는 매우 유명하고 다양한 증명 방법이 알려져 있지만, 이 글에서는 선형 계획법의 쌍대성(duality)를 이용하여 증명하고자 합니다. 혹시나 쌍대성에 관해 아직 잘 모르신다면, 다음 글을 참조하세요.
2019/07/15 - [수학적 도구/Linear programming] - [선형 계획법] 쌍대성(Duality)
[선형 계획법] 쌍대성(Duality)
Linear programming은 최적화 분야에서 잘 알려지고 연구되었으며 실제로도 많이 응용되는 기법입니다. 줄여서 LP라고도 하며, 우리말로는 선형계획법으로 불립니다. 이름이 뭔가 멋들어져서 괜스레
gazelle-and-cs.tistory.com
아래 증명에서는 다음 기호들이 사용됩니다. 어떤 행렬 \(A \in \mathbb{R}^{m \times n}\)이 주어졌을 때, \(i\) 번째 행을 \(a_i^\intercal \in \mathbb{R}^{1 \times n} \), \(j\) 번째 열을 \( A_j \in \mathbb{R}^{m \times 1} \)으로 표현하겠습니다.
[증명] 먼저 식 2를 살펴보죠. \(x\)가 정해졌을 때, \( u^\intercal := x^\intercal A \in \mathbb{R}^{1 \times n} \)으로 정의하면, 선수 2의 목표는 \( u^\intercal y \)의 값을 최소화하는 \(y\)를 찾는 것입니다. 그런데 \(y\)는 확률 분포이기 때문에 어떤 \(y\)를 가지고 와도 \[ u^\intercal y \geq \min_{j = 1, \cdots, n} (u^\intercal)_j \]를 만족할 수 밖에 없습니다. 반대로 \(u^\intercal\)의 가장 작은 원소의 인덱스를 \(j^\star\)라고 했을 때(여러 개가 있는 경우에는 아무거나 고름), \[ y_j = \left\{ \begin{array}{ll} 1, & j = j^\star, \\ 0, & \text{otherwise} \end{array} \right. \]의 원소를 갖는 \(y\)에 대해 \( u^\intercal y = (u^\intercal)_{j^\star} \)이 됩니다. 이를 종합하면 \[ \min_{y} u^\intercal y = \min_{j = 1, \cdots, n} (u^\intercal)_j = \min_{j = 1, \cdots, n} x^\intercal A_j \tag{4} \]라는 사실을 얻을 수 있습니다.
비슷한 방식을 식 3에도 적용할 수 있습니다. \(y\)가 정해졌을 때, \( w := Ay \in \mathbb{R}^{m \times 1} \)으로 정의하면 선수 1의 목표는 \( x^\intercal w \)를 최대화하는 \(x\)를 찾는 것입니다. 똑같이 \(x\)가 확률 분포라는 사실을 통해 우리는 \[ \max_{x} x^\intercal w = \max_{i = 1, \cdots, m} w_i = \max_{i = 1, \cdots, m} a^\intercal_i y \tag{5} \]를 이끌어낼 수 있습니다.
식 2와 3에 각각 식 4와 5를 대입하면, 각 선수들의 목표를 다음과 같이 다시 쓸 수 있습니다.
\[ \max_{x} \min_{y} x^\intercal A y = \max_{x} \min_{j = 1, \cdots, n} x^\intercal A_j \tag{6} \]
\[ \min_{y} \max_{x} x^\intercal A y = \min_{y} \max_{i = 1, \cdots, m} a^\intercal_i y \tag{7} \]
놀랍게도 식 6과 7은 선형 계획법으로 표현할 수 있습니다. 더욱 놀라운 점은 서로 원-쌍대(primal-dual) 관계에 있다는 사실입니다. 이를 보이면 strong duality에 의하여 정리의 등식이 성립한다는 것을 증명하게 됩니다. 따라서 남은 증명 과정은 다음과 같습니다. 먼저 식 6을 표현하는 LP를 하나 만든 후, 그것의 dual program을 구하겠습니다. 그러고는 그렇게 만들어진 LP가 식 7을 표현하는 LP라는 것을 보이도록 하겠습니다.
식 6을 표현하는 LP를 만들어 봅시다. 먼저 변수는 \(x \in \mathbb{R}^m_+\)입니다. \(x\)가 확률 변수라는 조건은 모든 \(i = 1, \cdots, m\)에 대해 \(x_i \geq 0\)이라는 조건과 함께 식 1의 \( \sum_{i = 1}^m x_i = 1 \)로 표현할 수 있습니다. 남은 것은 \( \min_{j = 1, \cdots, n} x^\intercal A_j \)의 최댓값을 구하는 것입니다. 이는 최솟값을 나타내는 변수 \(s\)를 두고 대신 모든 \( j = 1, \cdots, n \)에 대해 \( x^\intercal A_j \geq s \)를 만족하도록 만들면 됩니다. 이때, \( x^\intercal A_j = \sum_{i = 1}^m a_{i, j} x_i \)이므로 이 조건은 선형 부등식입니다. 참고로 \(s\)는 \(A\)가 양수든 음수든 아무 값이나 가질 수 있었기 때문에 부호의 제약은 없겠습니다. 이를 정리하면 다음과 같은 LP를 구성할 수 있습니다.
\[ \begin{array}{lrll} \text{maximize} & s && \\ \text{subject to} & \displaystyle s - \sum_{i = 1}^m a_{i, j} x_i & \leq 0, & \forall j = 1, \cdots, n, \\ & \displaystyle \sum_{i = 1}^m x_i & = 1, & \\ & x_i & \geq 0, & \forall i = 1, \cdots, m. \end{array} \]
여기서 첫 번째 제약 조건은 \( \sum_{i = 1}^m a_{i, j} x_i \geq s \)에서 좌변을 몽땅 우변으로 넘긴 것입니다. 이는 다음 단계에서 큰 도움이 됩니다.
이제 위 LP의 dual program을 구해보도록 하겠습니다. 첫 번째 제약 조건에 해당하는 변수를 \(y_j\)라고 하고, 두 번째 제약 조건에 해당하는 변수를 \(t\)라고 하겠습니다. 위 LP는 maximization problem이므로, 그 dual의 목표는 제약 조건들을 잘 조합하여 적절한 상한을 주는 것이 됩니다. 다시 말해, \[ s \leq \sum_{j = 1}^n y_j \cdot \left[ s - \sum_{i = 1}^m a_{i, j} x_i \right] + t \cdot \sum_{i = 1}^m x_i = s \cdot \sum_{j = 1}^n y_j + \sum_{i = 1}^m x_j \left[ t - \sum_{j = 1}^n a_{i, j} y_j \right] \tag{8} \]를 만족하게 만드는 것이죠. \(s\)는 양수 음수 모두 가질 수 있으므로 \( \sum_{j = 1}^n y_j = 1 \)을 만족해야 합니다. 또한, \( x_j \geq 0 \)이기 때문에 \( t - \sum_{j = 1}^n a_{i, j} y_j \geq 0 \)도 이끌어낼 수 있습니다.
또한 dual program을 만들기 위해서는 식 8의 중간 식에 primal constraint를 다음과 같이 적용해주어야 합니다. \[ \sum_{j = 1}^n y_j \cdot \left[ s - \sum_{i = 1}^m a_{i, j} x_i \right] + t \cdot \sum_{i = 1}^m x_i \leq \sum_{j = 1}^n 0 \cdot y_j + t \tag{9} \] 첫 번째 제약 조건에 의해 \( y_j \geq 0 \)이라는 부호 조건을 가져야 하며, 두 번째 제약 조건은 등식이므로 \(t\)는 아무 부호를 가져도 괜찮습니다.
그렇게 되면 식 8과 함께 식 9의 우변이 원래 LP가 갖는 모든 목적 함수 값의 상한을 이룬다는 사실을 얻을 수 있게 되고, 우리의 목표는 그러한 상한 중 가장 값이 작은 것을 찾는 것이 됩니다. 이를 정리하면 다음 LP가 됩니다.
\[ \begin{array}{lrll} \text{minimize} & t && \\ \text{subject to} & \displaystyle t - \sum_{j = 1}^n a_{i, j} y_j & \geq 0, & \forall i = 1, \cdots, m, \\ & \displaystyle \sum_{j = 1}^n y_j & = 1, & \\ &y_j & \geq 0, & \forall j = 1, \cdots, n. \end{array} \]
이 LP의 첫 번째 제약 조건을 다시 쓰면 모든 \(i = 1, \cdots, m\)에 대해 \( \sum_{j = 1}^n a_{i, j} y_j \geq t \)가 됩니다. 여기서 재밌는 사실은 \( \sum_{j = 1}^n a_{i, j} y_j = a^\intercal_i y \)라는 점이죠. 따라서 이 LP가 식 7과 동일하다는 것은 쉽게 보일 수 있습니다. 이를 통해 앞서 설명한 대로 식 7을 표현하는 LP와 식 8을 표현하는 LP가 primal-dual 관계가 성립하고, strong duality에 의해 두 값은 동일하다는 점을 알 수 있습니다. □
마치며
이번 글에서는 2인 제로섬 게임(two-player zero-sum game)에 대해서 알아보았습니다. 특히 (선수 2의 전략이 무엇이든지) 선수 1이 최대로 기대할 수 있는 점수나 (선수 1의 전략이 어떤 것이든) 선수 2가 선수 1이 얻는 점수를 최소로 할 때 기대할 수 있는 점수는 동일하다는 최소 최대 정리(minimax theorem)을 보였습니다. 여러 증명 방법이 존재하지만, 이번에는 LP duality를 활용하여 이를 증명하였습니다.
LP duality를 이용한 증명이 좋은 점 중 하나는 서론의 두 번째 질문에 대한 답을 줄 수 있다는 것입니다. 증명에서 사용된 primal program과 dual program을 각각 풀어서 얻는 \(x\)와 \(y\)가 곧 각자에게 있어 "최적"의 전략이 됩니다. 또한 LP를 변수의 개수와 제약 조건의 수의 다항 시간에 풀 수 있다는 사실은 잘 알려져 있습니다. Primal(dual) program의 변수는 \(m + 1\)(\(n + 1\)) 개이고, 제약 조건의 개수는 둘 다 \( m + n + 1\) 개입니다. 따라서 \( m \)과 \( n \)의 다항 시간에 이 LP를 해결할 수 있습니다. 따라서 최적의 전략을 구하는 효율적인 알고리즘도 존재한다는 것을 함께 이끌어낼 수 있습니다.
참고로 "최적"의 전략은 다음과 같이 해석할 수도 있습니다. 선수 1의 입장에서 선수 2가 전략을 바꾸지 않는 한 선수 1도 전략을 바꿀 인센티브가 없습니다. 반대로, 선수 2의 입장에서도 선수 1이 자신의 전략을 수정하지 않는 이상 선수 2가 자기 스스로 전략을 바꿀 이유가 없습니다. 누구든 그렇게 하면 자신에게 손해가 되기 때문이죠. 이러한 평형점을 우리는 내쉬 평형(Nash equilibrium)이라고 부릅니다. 이 개념을 사용하여 이번 시간에 알아본 것을 다시 적어 보면 다음과 같습니다.
- 2인 제로섬 게임에는 내쉬 평형이 최소한 하나는 존재하며, 여러 개가 있을 경우 그것들이 이루는 게임의 값은 모두 동일하다.
- 또한, 2인 제로섬 게임에서는 내쉬 평형을 전략의 총 개수의 다항 시간에 찾을 수 있다.
제로섬 게임은 선수 1의 이득이 곧장 선수 2의 손해로 이어지기 때문에 서로 정확히 반대의 동기를 갖고 있었습니다. 하지만 모든 게임이 항상 그런 것만은 아닙니다. 가장 유명한 비제로섬 게임 중 하나는 죄수의 딜레마(prisoner's dillema)입니다. 이러한 게임에서는 각 선수마다 각자의 점수 행렬을 갖게 되고, 각자는 최대의 점수를 얻도록 전략을 구사해야 합니다. 이때는 내쉬 평형이 존재할까요? 이를 쉽게 구할 수 있을까요? 이에 관한 내용은 다음에 다루어 보도록 하겠습니다.
글 내용에 부족한 점이 있거나, 궁금하신 사항이 있으시면 알려주시기 바랍니다. 읽어 주셔서 고맙습니다.
참조
[1] 전체적인 내용 : https://courses.cs.washington.edu/courses/cse521/16sp/521-lecture-16.pdf
'알고리즘 & 게임 이론 > Game theory' 카테고리의 다른 글
| 우월 전략 균형 & 내쉬 균형 (Dominant Strategy Equilibrium & Nash Equilibrium) (3) | 2022.11.15 |
|---|
