행렬 게임

게임이론과 전략 : 권오헌. 윤태환 지음, 범한서적 주식회사, 2000

1 절  게임이론의 본질

2 절  우세와 안장점 (Dominate and Saddle Point)

3 절  혼합 전략 (Mixed Strategy)

4 절  단체법 (Simplex Method) 에 의한 해법

1 절  게임이론의 본질

게임이론은 합리적인 의사 결정자들 사이에서 일어나는 다툼 (conflict) 과 협력 (cooperation) 의 수학적 모델의 학문으로 정의될 수 있다. 이와 같이 다툼과 협력의 여러 가능성 하에서 둘 이상의 의사 결정자가 서로의 이익에 영향을 줄 결정을 해야 하는 상황을 분석하기 위하여 게임이론은 일반화된 수학적 기법을 제공한다.

게임은 적어도 둘 이상 사이의 의사 결정 상황으로서 게임의 참여자 (player), 참여자의 전략 (strategy), 의사 결정의 결과 (outcome), 결과의 수치적 가치인 소득 (payoff) 으로 구성된다.

구체적으로 게임의 참여자는 적어도 둘 이상으로 개인이 될 수도 있고 회사, 국가, 또는 생물체와 같은 보다 더 일반적인 실체가 될 수도 있다. 전략이란 각 참여자가 따르기로 택하는 행동의 과정을 말하며 유한 개가 되거나 또는 무한 개가 될 수 있다. 각 참여자에 의하여 선택된 전략들은 게임의 결과를 결정하며, 소득은 결정된 결과에 대하여 각 참여자에게 주어지는 수치를 말한다.

게임이론은 참여자가 어떻게 이성적으로 게임에 참여해야 하는가를 살피는 학문으로, 각 참여자는 가능하면 더 많은 소득을 자신에게 가져다 주는 결과로 게임을 끝내려고 한다. 즉 모든 참여자는 각자 자신에게 유리한 전략을 택하려고 하며, 전략의 선택이 결과에 영향을 미치므로 결과에 대하여 어느 정도의 조정력을 갖는다. 하지만 게임의 결과는 한 참여자의 선택에 의해서만 결정되는 것이 아니고, 다른 참여자의 선택에 의해 영향을 받게 되므로 다툼과 협력이 발생하게 된다.

일반적으로 다툼은 서로 다른 참여자들이 결과를 다르게 평가하기 때문에 발생한다. 한편 일부 혹은 모든 참여자들이 그들의 전략을 함께 조절하여 그들 모두에게 보다 나은 소득을 주는 결과를 얻을 수 있으므로 협력의 기회가 생긴다. 즉 다툼은 각 참여자가 자신에게 좋은 결과가 나오기를 원하므로 발생이 되고, 협력은 참여자 일부 혹은 모두가 전략의 선택을 함께 조절하여 그들 모두에게 보다 좋은 결과가 나오기를 원하므로 발생된다.

합리적인 결정은 다른 참여자들이 그들에게 유리한 결과를 만드는 전략을 택하려 한다는 것을 의식하고 자신에게 유리한 결과를 만드는 전략을 어떻게 택하느냐 하는 복잡한 개인적 결정을 포함한다. 또한 어떻게 협력하고 누구와 협력할 것인지에 대한 참여자들 간의 사회적 결정도 포함한다.

게임이론을 전개하고 기술하는 데는 크게 세 가지 어려움이 있다.

(1) 실생활에서의 게임은 매우 복잡하다. 참여자와 비참여자의 구분, 모든 전략들의 파악 및 분석, 주어진 결과에 부과되는 수치적 소득의 애매함 등이 그것이다. 우리는 실제 상황과 유사한 단순화된 모델을 세우고 분석하려고 한다. 이러한 모델의 분석은 본래의 상황에 대한 통찰력을 준다.

(2) 참여자들이 이성적인 결정을 한다는 것에 대한 부담이다. 다른 참여자들이 그들의 목표를 달성하기 위하여 최선의 논리적 분석을 한다고 가정하고 각 참여자는 자신의 목표를 달성하기 위한 최선의 논리적 분석을 한다. 즉 이성적인 참여자는 이성적인 상대방을 가정한다. 하지만 실제 상황에서 모든 참여자가 똑같이 이성적으로 행동하지는 않는다. 그렇지만 참여자들이 다툼과 협력의 상황에서 어느 정도로 이성적 행동을 하느냐 하는 문제는 그 자체가 흥미로울 뿐만 아니라 게임이론의 영역이 될 수가 있다.

(3) 게임이론 전개의 가장 큰 어려움으로 두 참여자의 이해가 완전하게 상충하지 않는 경우에는 그러한 게임에 대한 분석이 없다는 것이다. 게임이론이 제공하는 것은 다양한 흥미로운 예들, 분석, 제안, 그리고 상황에 대한 부분적인 기술이다.

우리가 다룰 상황을 이해하기 위하여 다음과 같은 간단한 경우를 살펴보자. 참여자는 행동이와 열심이 두 명이고, 행동이는 세 개의 전략 A, B, C 를 갖고 있고, 열심이는 두 개의 전략 A, B 를 갖고 있다고 하자. 그러므로 여섯 개의 서로 다른 결과가 생긴다.

(행동이, 열심이) = (A, A), (A, B), (B, A), (B, B), (C, A), (C, B).

행동이의 전략을 행으로 놓고, 열심이의 전략을 열로 놓고, 행렬의 각 성분을 대응하는 결과에 대한 (행동이의 소득, 열심이의 소득) 으로 놓으면 위 상황을 (3 × 2) 행렬로 나타낼 수 있다.

이 게임에서, 예를 들어, 행동이가 전략 A 를 택하고 열심이가 전략 A 를 택하면 결과는 (A, A) 가 되고, 이 때의 행동이의 소득은 2, 열심이의 소득은 -2 가 된다.

각 결과의 소득 (a, b) 에 대하여 a + b = 0 일 때 이 게임을 영합게임 (zero-sum game) 이라고 하며, 이런 경우에 행동이와 열심이의 이해는 완전히 상반되게 된다. 즉 영합게임은 두 참여자간의 순수한 다툼의 상황을 나타낸다. 영합게임인 경우에는

열심이의 소득 = -행동이의 소득

이므로 다음과 같이 행동이의 소득만을 나타낸 것으로 위 게임을 표현할 수 있다.

게임 2

물론 열심이의 소득을 나타내기 위해서는 부호가 반대로 대응하는 행렬을 생각하면 된다.

이제 위의 상황을 주의 깊게 살펴보자. 위의 6 개의 숫자 중에서 행동이는 제일 큰 수를 원하고, 열심이는 제일 작은 수를 원한다. 즉, 행동이는 10 을 얻을 수 있는 전략 C 를 선호하고, 열심이는 -5 를 행동이에게 줄 (열심이가 5 를 얻을 수 있는) 전략 A 를 선호한다. 이런 상황에서, 예를 들어, 열심이가 전략 B 를 택할 것이라는 희망하에 행동이가 전략 C 를 택한다고 가정하자. 이와 같은 것을 마찬가지로 알고 있는 열심이는 자신에게 유리하도록 전략 A 를 택하여 행동이에게는 -5 를 그리고 자신에게는 5 를 얻도록 할 것이다. 그러면, 이것을 예측한 행동이는 이 상황에서 자신에게 유리하도록 전략 A 를 택하여 자신에게는 2 가 생기고 열심이는 -2 가 되도록 할 것이다. 그러면, 다시 이것을 예측한 열심이는 이 상황에서 자신에게 유리하도록 전략 B 를 택하여 행동이에게는 -3 을 그리고 자신에게는 3 을 얻도록 할 것이다. 그러면, 다시 이것을 예측한 행동이는 이 상황에서 자신에게 유리하도록 전략 C 를 택하여 자신에게는 10 이 생기고 열심이는 -10 이 되도록 할 것이다. 이와 같은 상황을 계속 살펴보면 그림 1 과 같은 이동도표 (movement diagram) 를 얻는다.

그림 1  이동도표

위의 도표에서 행의 화살 방향은 열심이의 선택에 의한 것이므로 각 행에서 가장 작은 수로 향하고, 열의 화살 방향은 행동이의 선택에 의한 것이므로 각 열에서 가장 큰 수로 향한다. 위 게임에서는 화살표의 흐름이 멈추게 되는 멈춤점 (stopping point) 이 존재하지 않으며, 참여자들의 행동은 다음과 같은 일련의 추론 "그가 이렇게 할 것이라고 내가 생각한다는 것을 그가 생각하고, 그것을 내가 생각한다면 나는 이렇게 해야 한다" 에 따라 정해진다.

멈춤점이 존재하지 않는 상황에서의 전략 선택의 어려움은 나중에 배울 혼합 전략 (mixed strategy) 이라는 개념에 의하여 해결이 된다. 혼합전략은 2인 영합게임에서의 이성적인 행동을 완전히 분석해 준다. 또한 게임나무 (game tree) 를 배움으로써 전략의 개념을 보다 자세히 살펴보고, 효용이론 (utility theory) 을 배움으로써 소득의 개념을 보다 자세히 살펴본다.

다음 상황은 두 명의 참여자에 의한 게임으로 각 결과에 대한 양 참여자의 소득의 합이 영이 아닌 경우이다.

이 게임과 같이 각 결과에 대하여 양 참여자의 소득의 합이 반드시 영이 되지 않는 게임을 비영합게임 (nopnzero-sum game) 이라고 부른다. 행동이와 열심이가 모두 전략 A 를 택하여 소득 (1, 1) 을 얻는 것이 서로에게 차선책이자 최선책인듯하며, 가장 높은 총소득을 준다. 그러나 만약 열심이가 행동이는 A 를 택할 것이라고 예상한다면 열심이는 B 를 택하는 것이 더 유리할 것이다. 양 참여자가 이와 같이 추론하여 결정한다면 결과는 (-5, -5) 가 되어 양 참여자에게 최악의 결과가 나오게 된다.

위의 예와 같은 게임에서는 양 참여자가 어떻게 상대방의 전략의 선택을 믿을 것인가 하는 신뢰의 문제가 발생된다. 이를 해결하기 위하여 상호간의 대화 (communication) 의 존재 여부 또는 제 3 의 중재자의 추천 (arbitrator's recommendation) 을 도입하여 분석을 시도해 볼 수 있다. 양 참여자가 대화를 한다면 둘 다 A 를 택하도록 동의할 수가 있다.

나중에 게임의 공평한 해결을 추천해 주는 중재자의 관점에서, 대화가 존재하는 경우의 다양한 관점에서 2 인 비영합게임을 다룰 것이다. 이것은 실험적 사회 심리학, 행동의 진화, 노사협상, 경제적 과점 등에 응용이 된다.

참여자가 두 명보다 많은 경우는 n 명게임 (n-person game) 이라 하며, 이 때는 참여자들 간의 연합 (coalition) 이 가능하므로 훨씬 더 복잡한 상황이 된다. n 명게임 (n > 2) 은 어떤 연합들이 형성되고 이들 각 연합이 소득을 어떻게 분배하느냐에 초점을 맞추게 된다.

2 절  우세와 안장점 (Dominate and Saddle Point)

행동이가 m 개의 전략을 갖고, 열심이는 n 개의 전략을 갖는 2인 영합게임은 mㆍn 개의 결과들 각각에 대하여 열심이로부터 행동이로의 소득을 성분으로 갖는 (m × n) 크기의 행렬로 나타낼 수 있다. 이러한 게임을 (m × n) 행렬게임 (matrix game) 이라 부른다. 이 경우에 행동이는 가장 큰 수를 갖고 있는 행을 택하려 하고, 열심이는 가장 작은 수를 갖고 있는 열을 택하려고 한다.

다음과 같은 행렬게임을 살펴보자.

게임 1

이 게임에서 행동이는 가장 큰 소득 16 을 원하며, 열심이는 행동이에게 가장 작은 소득을 주는 -20 을 원하게 된다. 그러면 실제 결과는 어떻게 나올까?

우선 두 번째 열에 있는 모든 숫자들이 세 번째 열에 있는 대응하는 숫자들보다 작거나 같기 때문에, 열심이 c 가 열심이 B 보다 열세하다 (dominated) 고 정의한다.

명백히 적당한 다른 전략보다 열세한 전략을 택하는 것은 결코 사리에 맞지 않다. 즉 우세한 전략을 택하는 것이 항상 좋은 결과를 초래하게 된다. 이와 같은 우세의 개념을 다음과 같이 일반화하여 정의할 수 있다.

우세의 원리는 일부 전략을 제거해 주지만 유용함은 극히 제한적이다. 위의 예에서, 행동이의 전략 중에는 어느 것도 서로 우세한 것이 없고, 열심이의 전략 A, B, D 중에서 어느 것도 다른 전략보다 우세하지 않다. 다만 열심이의 전략 B 가 C 보다 우세하다. 그러므로 이 원리를 이용하여 전략 선택을 더 제안할 수는 없다.

위의 게임을 실험적으로 반복해 보면 행동이 C 와 열심이 B 가 다른 어떤 전략보다도 많이 선택된다. 이유가 무엇일까? 한 가지 이유는 이들 전략이 행동이와 열심이에 대한 가장 조심스런 전략 (most cautious strategy) 이라는 것이다. 행동이가 C 를 택할 때 최소한 2 의 소득이 보장된다. 반면에 다른 전략의 선택은 전략 C 를 택할 때보다 손해를 볼 수도 있게 된다. 마찬가지로 열심이의 전략 B 도 2 보다 더 많이 손해를 보지 않는다는 것이 보장되고 다른 전략으로는 더 큰 손해를 볼 수가 있다.

하지만 행동이와 열심이가 조심스럽지 않다 할지라도 행동이 C 와 열심이 B 를 선택하는 합당한 이유가 있다. 다음과 같은 두 가지 이유를 살펴보자.

(1) (행동이 C, 열심이 B) 는 평형결과 (equilibrium outcome) 이다. 행동이가 C 를 택할 것이라고 열심이가 알거나 믿는다면 열심이는 B 로 대응하길 원하게 되며 행동이 C 도 열심이 B 에 대한 최상의 대응이 된다. 만일 양 참여자가 이들 전략을 택한다면 어떤 참여자도 다른 전략으로 이동할 동기가 없게 된다. 이것은 그림 1 과 같은 게임의 이동도표로 나타내어질 수 있다.

(2) 행동이는 C 를 택함으로써 최소한 소득 2 는 받게 될 것이라고 확신하게 된다. 열심이는 B 를 택함으로써 행동이가 소득 2 보다는 더 많이 받지는 못할 것이라는 것을 확신할 수 있다. 만약 행동이가 소득 2 보다도 작은 값을 받고 게임이 끝난다면 행동이는 C 를 택함으로써 보다 더 이득을 얻을 수가 있게 된다. 그리고 만약 행동이가 2 보다도 큰 값을 받고 게임이 끝난다면 열심이는 B 를 택함으로써 보다 더 이득을 볼 수가 있게 된다. 만일 양 참여자 평형 전략을 택하지 않으면 한쪽 참여자가 이득을 보게 됨을 서로가 알게 된다.

그림 1  이동도표

위의 두 가지 논의는 (행동이 C, 열심이 B) 를 이 게임의 합리적인 선택으로 규정해줄 만큼 설득력이 있다. (행동이 C, 열심이 B) 에서의 소득은 C 행에서의 가장 작은 수이며 동시에 B 열에서 가장 큰 수이다. 이러한 결과를 초래하는 전략은 서로에게 최상의 대응이며, 양 참여자가 이 값보다 더 나쁜 값을 주지 못하도록 보장해 준다.

한 행렬게임이 안장점을 갖고 있으면 안장점에 놓인 숫자가 바로 주어진 게임의 값이다. 왜냐하면, 안장점의 정의로부터 v 가 안장점에 놓인 숫자이면, v 는 그 행에서 가장 작은 수이므로 열심이가 그것에 해당하는 전략을 택하지 않을 이유가 없고, 또 v 는 그 열에서 가장 큰 수이므로 행동이도 그것에 해당하는 전략을 택하지 않을 이유가 없다. 하지만 행렬게임은 안장점을 갖지 않을 수도 있고 두 개 이상의 안장점을 가질 수도 있다. 다음 예를 살펴보자.

위 예에서 안장점은 둘 이상이 존재하게 되는데, 이들 안장점 사이에 밀접한 관계가 있다. 그들은 모두 같은 값을 갖게 되고 직사각형의 모서리에 나타나게 된다. 이러한 안장점들 사이의 관계는 다수의 안장점을 갖는 임의의 행렬게임에서 성립된다.

다음은 임의의 게임이 주어질 때 안장점이 존재하는지, 그리고 안장점이 존재하면 어떻게 구하는지를 살펴보자. 물론 행렬의 모든 성분에 대하여 각 성분이 속하는 행에서 가장 작고 그 열에서 가장 큰지를 조사할 수도 있다. 하지만 안장점 전략이 가장 조심스런 (소극적인) 전략이라는 개념에 의거하는 보다 효율적인 방법이 있다. 상대방의 존재를 의식한 가장 조심스런 전략은 다음과 같다. 행동이는 각 행에서 최소값을 구하여 이들 중에서 최대값을 정하고 (maximin), 열심이는 각 열에서 최대값을 구하여 이들 중에서 최소값을 정하여 (minimax), maximin = minimax 이면, 그 값이 바로 게임의 값이다.

이제 maximin 과 minimax 가 같은 경우를 살펴보자. 우선, 각 행에서 최소값을 갖는 성분을 택하고 그 중에서 가장 큰 값을 maximin 으로 놓는다. 마찬가지로 각 열에서 최대값을 갖는 성분을 택하고 그 중에서 가장 작은 값을 minimax 로 놓는다.

게임 3

위 게임에서 행동이의 maximin 과 열심이의 minimax 가 같은 결과는 (행동이 A, 열심이 C) 와 (행동이 C, 열심이 C) 의 두 결과로서, 안장점은 두 개이며 게임의 값은 2 임을 알 수 있다.

다음은 maximin 과 minimax 가 다른 경우이다.

게임 4

이 예에서는 maximin 과 minimax 의 값이 다르게 되어 안장점이 존재하지 않는다. 행동이는 최소한 0 을 얻으리라 확신할 수 있고 열심이는 행동이가 2 보다 더 많지 않은 값을 얻으리라 확신하게 된다. 하지만 0 과 2 사이의 공백이 생기게 된다. 그러므로 행동이의 maximin 전략 B 와 열심이의 minimax 전략 A 는 평형결과를 초래하지 못한다.

위와 같이 maximin 과 minimax 가 다른 값을 갖게 되어 안장점이 없는 경우 (두 참여자 모두 어느 한 가지 전략을 택할 수 없음) 는 다음 절에서 살필 혼합 전략을 이용할 수 있다. 

3 절  혼합 전략 (Mixed Strategy)

일부 행렬게임에서는 행 maximin 과 열 minimax 가 다른 숫자를 갖게 되어 안장점이 존재하지 않는 경우를 앞 절에서 살펴보았다. 예를 들어, 다음 게임을 살펴보자.

게임 1

이 게임에서는 안장점이 없으므로 두 참여자 모두 확신을 갖고 택할 한 개의 전략이 존재하지 않는다. 왜냐하면 한 참여자가 어떤 전략을 택한다면 다른 참여자가 선택한 전략을 이용할 수가 있기 때문이다. 그러므로 다른 대안으로, 임의의 숫자를 만들어내는 장치를 이용하여 전략을 섞어서 참여할 수 있다. 예를 들어, 열심이는 열심이 A 나 혹은 열심이 B 를 결정하기 위하여 동전을 던져 결정을 내릴 수가 있다.

참여자가 혼합전략을 이용할 때의 결과를 분석하기 위하여 기대값의 개념을 이용할 수 있다.

소득의 기대값은 가중평균값으로, 가중치는 각각의 확률이 된다. 만일 열심이가 위 게임에서 동전을 던지는 혼합전략을 이용한다면 확률 로 A 를 택하고 확률 로 B 를 택하게 된다. 그러므로 행동이가 A 를 택한다면 확률 로 소득 2 를 얻게 되고 확률 로 소득 -3 을 얻게 된다. 그러므로 행동이 A 에 대한 기대값은

이 된다. 마찬가지로 행동이 B 에 대한 기대값을 구하면

이 된다. 명백히 열심이가 혼합전략 를 행한다는 것을 행동이가 알거나 예측한다면 행동이는 B 를 택해야 한다. 이러한 추론은 다음과 같이 나타내어질 수 있다.

기대값의 원리 : 상대방이 주어진 혼합전략을 택한다는 것을 당신이 알고 있고 또한 당신이 무슨 선택을 하는지에 상관없이 상대방은 계속 그 혼합전략을 택한다는 것을 당신이 알고 있다면, 당신은 최대 기대값을 갖는 전략을 택해야 한다.

이제 열심이의 관점에서 상황을 살펴보자. 열심이가 혼합전략 를 이용하고 행동이가 이것을 예측한다면 행동이는 자신의 예측을 이용하여 전략 B 를 택하여 기대 소득 을 얻게 된다. 그렇다면 열심이가 다른 확률, 예를 들어 를 이용할 수가 있는데 이 때는 행동이가 어떤 전략을 택해야 할까? 열심이의 관점에서 이와 같은 혼합전략의 확률이 행동이가 열심이의 혼합전략을 이용하여 이득을 취할 수 없게 되는 적당한 확률의 선택일까? 아니면 열심이는 다른 어떤 혼합전략을 택해야 할까?

이것을 찾기 위하여 열심이가 확률 를 갖고 전략 A 를 택하고 확률 를 갖고 전략 B 를 택한다고 가정하자. 여기서는 는 0 과 1 사이의 적당한 수이다. 이 상황에서 행동이의 각 전략에 대한 기대값을 계산해 보자.

행동이의 A :

행동이의 B :

가 되어 , 일 때이다. 만일 열심이가 혼합전략 를 이용한다면 행동이가 어떤 전략을 택하든 상관없이

행동이의 A :

행동이의 B :

이므로 보다 많지 않은 소득을 행동이가 얻게 됨을 열심이는 확신할 수가 있다. 이 경우 열심이는 행동이에게 만큼의 소득을 준다.

열심이가 이러한 확률을 갖는 혼합전략을 실제로 어떻게 다루어야 할까? 몇 가지 제안을 해보자.

• 두 개의 동정을 던져서 둘 다 뒷면이 나오면 B 를 택한다.
• 잘 섞인 한 벌의 카드에서 한 장을 뽑아 스페이드면 B 를 택한다.
• A 가 적힌 세 장의 쪽지와 B 가 적힌 한 장의 종이 쪽지를 모자 속에 넣고 한 장을 끄집어낸다.
• 디지털 시계에서 현재의 초 (second) 가 4 로 나누어지면 B 를 택한다.
• 컴퓨터가 0 과 1 사이의 임의의 수를 만들 게 하여 0.75 보다 크면 B 를 택한다.

다음은 행동이의 관점에서 상황을 살펴보자. 확률 를 갖고 전략 A 를 택하고 확률 를 갖고 전략 B 를 택하는 혼합전략을 써서, 이것에 의해 열심이가 이득을 얻지 않도록 한다.

행동이의 A :

행동이의 B :

이제 이면 , 가 된다. 그러므로 만약 행동이가 와 의 혼합전략을 쓰면, 열심이가 무슨 전략을 사용할지라도

행동이의 A :

행동이의 B :

이 되어 행동이는 최소한 만큼의 소득은 보장된다.

이것을 방금 전의 열심이의 관점과 비교하면 안장점을 갖는 게임의 경우와 유사한 점을 찾을 수 있다. 행동이는 최소한 의 소득을 보장해주는 혼합전략을 갖게 되고 열심이는 행동이의 소득이 보다 많지 않을 것을 보장해 주는 혼합전략을 갖게 된다. 이를 종합하면 게임의 값은 이 되고, 행동이의 최적전략 (optimal strategy) 은 , 열심이의 최적전략은 가 된다.

모든 행렬게임은 순수전략이나 혹은 혼합전략으로서의 해를 갖게 된다. 이것은 게임이론의 기본정리인 최소최대정리 (minimax theorem) 로서 부록 A 의 증명을 참조하기 바란다.

다음은 안장점이 없는 (2 × 2) 게임에 대하여 혼합전략 해를 구하는 유용한 한 방법을 소개한다. 이 방법은 Williams (1986) 에 의해 도입된 것으로 아래 도표를 살펴보자.

행동이가 전략 A 를 택할지 전략 B 를 택할지를 정하기 위하여 행 성분의 차의 절대값을 이를 서로 바꾼 것을 자투리 (oddment) 로 놓는다. 마찬가지로 열심이가 전략 A 를 택할지 전략 B 를 택할지를 정하기 위하여 열 성분의 차의 절대값을 구하여 이를 서로 바꾼 것을 열의 자투리로 놓는다. 이와 같은 방법은 혼합전략의 정확한 확률을 만들 게 되며 (연습문제 1), 이 방법을 Williams 의 자투리 방법 (Williams' oddments method) 이라고 부른다. 최적혼합전략을 찾기 위하여 이러한 방법을 이용할 때 안장점의 존재 여부를 먼저 따져 보아야 한다. 안장점이 존재할 경우에는 이러한 방법이 최적전략을 만들지 못함을 보이는 예가 연습문제 2 에서 나온다.

다음은 행동이 또는 열심이가 두 개보다 많은 전략을 가진 경우를 살펴보자. 행동이가 두 개의 순수전략을 갖고 열심이가 개 의 전략을 갖는 게임이나, 행동이가 개 의 전략을 갖고 열심이가 두 개의 전략을 갖는 게임이 다음으로 가장 복잡한 경우가 된다. 만약 그러한 게임이 안장점을 갖지 않는다면 (2 × 2) 부분게임이 게임에 대한 해를 주는 지를 찾는 그래프식의 해법이 존재하며, 이 해법은 게임의 해가 무엇을 의미하는지를 기하학적인 관점에서 알려준다.

우선 열심이는 두 개, 행동이는 세 개의 전략을 가지는 경우를 살펴보자.

게임 2

위 게임은 maximin 과 minimax 가 다른값 0, 2 를 각각 갖게 되므로 안장점을 갖지 않는다.

그림 1a 에 있는 그래프를 살펴보자. 행동이의 각 전략에 대하여, 열심이가 전략 A 를 택하면 좌측 축위에 행동이의 소득을 표시하고, 열심이가 전략 B 를 택하면 우측 축위에 행동이의 소득을 표시한 후, 두 점을 선으로 연결한다. 만일 열심이가 임의의 에 대하여 혼합전략 () 를 택하면, 를 수평성분으로 갖는 위의 선분의 수직 성분이 행동이의 소득의 기대값을 주게 된다.

그림 1

행동이가 열심이의 혼합전략을 알거나 혹은 예측한다면, 행동이는 가장 좋은 대응을 함으로써 이득을 볼 수 있다. 이것은 각 점에서 최대값을 갖는 선분들을 연결한 그림에서의 위쪽 포락선 (upper envelope) 이 행동이에게 가장 좋은 전략임을 나타낸다. 한편 열심이는 행동이에게 대응하는 소득을 가능한 한 적게 주는 를 택하기를 원하므로 위쪽 포락선의 가장 아래에 놓인 점이 열심이에게 가장 좋은 대책임을 알 수 있다. 이 점은 행동이의 A 전략과 B 전략에 대한 각 선분의 교차점이다. 그러므로 위 게임은 다음과 같은 부분게임으로 축소된다.

행동이의 세 개의 전략 A, B, C 중에서 A 와 B 의 교차점을 구하기 위하여

의 해를 구하면 , 가 된다. 즉 행동이는 의 혼합전략을 택해야 하고, 열심이는 의 혼합전략을 택해야 한다. 다르게 표현하면, 행동이는 의 확률로 A 를 택하고, 의 확률로 B 를 택해야 하며, 결코 C 를 택해서는 안된다. 마찬가지로 열심이는 의 확률로 A 를 택하고, 의 확률로 B 를 택해야 한다.

이제 열심이의 혼합전략 에 대한 행동이의 기대값을 구해보자.

행동이의 전략 A :

행동이의 전략 B :

행동이의 전략 C : .

여기서 행동이의 전략 C 는 결코 택하게 되지 않을 것이므로 고려하지 않아도 된다.

다음은 행동이의 혼합전략 에 대한 열심이의 기대값을 구해보자.

행동이의 전략 A :

행동이의 전략 B : .

행동이의 모든 기대값은 보다 작거나 같게 되고, 열심이의 모든 기대값은 보다 크거나 같게 된다. 그러므로 열심이는 행동이가 보다 더 큰 값은 갖지 않는다는 것을 확신하게 되며, 행동이는 열심이가   보다 더 작은 값을 갖지는 못하리라 확신하게 된다. 따라서 주어진 게임의 값은 가 된다. 그림 1a 에서 이들 결과의 기하학적 해석이 가능하다. 위쪽 포락선에서 가장 낮은 점은 가 된다. 이 점의 수직 성분은 가 되어 게임의 값이 된다. 에서 행동이 C 에 대한 수직 성분은 게임의 값보다 낮은 가 되어 행동이 C 가 선택되지 않는 이유가 된다.

다음은 행동이가 두 개의 전략을 갖고 열심이가 개의 전략을 갖는 게임을 살펴보자. 다음과 같이 간단한 예가 주어진다고 하자.

게임 3

이 게임에 대한 그래프가 그림 1b 에서 주어진다. 열심이는 아래쪽 포락선에 있는 전략을 택하려고 할 것이고, 행동이는 아래쪽 포락선에서 가장 큰 값을 주는 점 를 택하려고 할 것이다. 이것은 열심이 A 와 열심이 C 를 포함한다. 최적혼합전략은

열심이 : ,     행동이 :

이 된다. 위 게임은 다음과 같은 부분게임으로 축소된다.

그러므로 행동이의 혼합전략은

.

열심이의 혼합전략은

가 된다.

이제 열심이의 혼합전략 에 대한 행동이의 기대값은 다음과 같다.

행동이의 전략 A :

행동이의 전략 B :

마찬가지로 행동이의 혼합전략 에 대하여 열심이의 각 전략에 대한 행동이의 기대값을 구하면 다음과 같다.

행동이의 전략 A :

행동이의 전략 B :

행동이의 전략 C :

행동이의 전략 D :

행동이의 전략 E : .

여기서 열심이는 B, D, E 를 결코 택하지 않을 것이므로 고려하지 않아도 된다. 따라서 주어진 게임의 값은 이 된다.

이제 두 참여자 모두 세 개 이상의 전략을 갖는 경우를 살펴보자. 결론적으로 그러한 게임에서도 게임의 해가 존재한다. 이러한 해의 존재를 입증하는 다음 정리는 von Neumann (1928) 에 의해 증명되었다.

이 정리의 증명은 부록 A 를 참조하기 바란다. 다음은 (3 × 3) 크기의 행렬게임의 해를 구해보자.

게임 4

이 게임은 안장점을 갖지 않으며, 어떤 우세한 전략도 존재하지 않는다. 열심이가 세 개의 전략 A, B, C 를 각각 의 확률로 임의대로 택한다고 가정하자. 그러면 이 경우 행동이의 기대값은 각각

행동이가 전략 A 를 택하는 경우 :

행동이가 전략 B 를 택하는 경우 :

행동이가 전략 C 를 택하는 경우 :

가 된다.

위의 세 경우의 값이 모두 같으면 행동이는 열심이의 혼합전략을 이용하여 이득을 취할 수가 없게 된다. 즉 열심이는 행동이가 열심이의 혼합전략을 이용할 수 없도록 혼합전략을 세워야 한다.

이므로

가 된다. 그러므로 열심이의 기대값을 동일화해주는 혼합전략은 가 되고, 위 행렬의 대칭성에 의하여, 행동이의 기대값을 동일화해 주는 전략도 가 된다. 이들 두 전략의 해가 되고 주어진 게임의 값은 이 된다. 위의 방법은 기대값의 동일화 방법 (method of equalizing expectations) 이라고 한다.

다음은 (4 × 4) 행렬게임의 해를 구해보자. 우선 안장점이 존재하는지를 확인을 한다. 안장점이 존재하면 게임의 해는 쉽게 구할 수 있다. 만일 안장점이 존재하지 않으면 행동이와 열심이의 전략들 중에서 우세한 전략이 존재하는지를 확인한다. 만일 존재하면 부분게임을 만들어 (4 × 4) 행렬게임보다 작은 크기의 행렬게임의 해를 구하는 방법을 이용하면 된다. 만일 안장점이 존재하지 않고 우세한 전략도 존재하지 않을 경우에는 기대값의 동일화 방법에 의하여 두 개의 삼원연립방정식의 해를 각각 구하면 된다.

(4 × 4) 게임보다 더 큰 크기의 행렬게임의 해를 구하기 위해서는 다음 절에서 다룰 선형계획법 (linear programming) 이라는 기법을 이용하는 것이 가장 효율적이다.

4 절  단체법 (Simplex Method) 에 의한 해법

선형계획법 문제 (linear programming problem) 는 선형 제약식을 만족하는 영 이상의 값을 갖는 변수들 이 주어질 때 선형함수

의 최대 혹은 최소를 구하는 문제이다. 여기서 제약식을 만족하는 () 을 가능해 (feasible solution) 라고 하고, 를 목적함수 (objective function) 라고 하며, 가 최대값 혹은 최소값을 갖도록 하는 점  () 을 최적해 (optimal solution) 라고 정의한다.

모든 최대 선형계획법 문제는 쌍대문제 (dual problem) 라 불리우는 대응되는 최소 선형계획법 문제와 관련이 있다. 역으로 모든 최소 선형계획법 문제는 쌍대라 불리우는 대응되는 최대 선형계획법 문제와 관련이 있다. 본래의 문제는 원문제 (primal problem) 라 불리운다. 예를 들어, 다음 문제들 각각은 서로가 쌍대가 된다.

(1) 최대화문제

Maximize

subject to

(2) 최소화문제

Maximize

subject to

목적함수의 계수들을 마지막 행으로 놓을 때, 위문제의 계수들은 다음과 같이 행렬 형태로 씌어질 수 있다.

(1) 최대화문제

(2) 최소화문제

위에서 쌍대문제의 계수행렬은 원문제의 계수행렬의 전치행렬 (transpose matrix) 임을 알 수 있다.

일반적으로 선형계획법 문제는 반드시 최적해를 갖지는 않는다. 다음 정리는 선형계획법의 기본정리이다.

앞의 최대 선형계획법 문제는 선형부등식이 아닌 선형등식만을 포함하는 다음 문제와 동치이다.

Maximize

subject to

여기서 변수 은 여유변수 (slack variable) 라 불리운다. 위 문제의 해를 구하기 위한 계산법으로 단체법 (simplex method) 이 있다. 단체법은 네 개의 단계로 이루어진다.

단계 1. 초기 단체표를 만든다.

단계 2. 단체표에서 추축 성분을 찾는다.

단계 3. 추축을 갖는 단체표로부터 새로운 단체표를 만든다.

단계 4. 최종 단체표를 얻을 때까지 단계 2 와 단계 3 을 반복한다.

위의 각 단계를 살펴보자. 우선 단계 1 에서의 초기 단체표를 만들어 본다. 위에서 주어진 최대 선형계획법 문제의 초기 단체표는 다음과 같다.

위 표의 첫 번째에서 번째까지의 행은 문제 (1.4.1) 에 있는 선형등식들의 계수들이고, 마지막 행은 문제 (1.4.1) 에 있는 목적함수의 계수들에 -1 을 곱한 값들이다. 비여유변수 (non-slack variable) 의 열들을 로 이름 붙여진다. 마지막 행에서 마지막 성분을 제외한 나머지 성분은 지시기 (indicator) 라고 정의한다. 마지막 행의 마지막 성분은 목적함수의 원점에서의 값을 뜻한다.

단계 2 에서의 추축 성분은 다음과 같이 구한다. 음의 지시기를 갖는 임의의 열 를 택해서, 이 열에 있는 각 양의 성분으로 마지막 열에 대응하는 성분을 나눈다. 이 때 가장 작은 몫을 갖는 의 성분이 추축 (pivot) 이 된다. 추축이 속하는 열은 추축열 (pivotal column), 추축이 속하는 행은 추축행 (pivotal row) 이라고 정의한다. 만일 단체표가 음의 지시기를 갖지 않는다면 추축은 없게 되며 그 때의 단체표가 최종 단체표가 된다.

단계 3 은 추축을 갖는 단체표로부터 새로운 단체표를 만드는 과정이다. 새로운 단체표는 행렬의 기본행연산 (elementary row operation) 을 통하여 추축 성분을 1 로, 추축열의 나머지 성분을 0 으로 만들면 된다. 이 때 추축이 번째 행과 번째 열에 있다면 새로운 단체표에서의 번째 행을 행이라고 이름 붙인다.

단계 4 를 거쳐 음의 지시기를 갖지 않은 다음 표와 같은 최종 단체표를 얻는다고 가정하자.

위 표에서 는 의 최대값이 되며, 쌍대정리에 의해, 의 최소값이 되기도 한다. 최대 문제의 최적해는 다음과 같이 구한다. 적당한 행이 라고 이름 붙여지면 그 행의 마지막 성분을 로 놓고, 어떤 행도 라고 이름 붙여지지 않으면 를 0 으로 놓는다. 이 때의 () 이 최대 문제의 최적해가 된다. 최소 문제의 최적해는 () 이 된다.

초기 단체표는 다음과 같다.

위 표에서 추축열을 2 열로 놓으면 추축 성분은 3 행 2 열의 3 이 된다. 기본행연산을 통하여 다음과 같은 새로운 단체표를 얻는다.

위 표에서 추축열을 1 열로 놓으면 추축 성분은 2 행 1 열의 이 된다. 기본행연산을 통하여 다음과 같은 새로운 단체표를 얻을 수 있다.

위 표에서 추축열을 5 열로 놓으면 추축 성분은 1 행 5 열의 3 이 된다. 기본행연산을 통하여 다음과 같은 새로운 단체표를 얻을 수 있다.

위 단체표는 음의 지시기를 갖지 않으므로 최종 단체표가 된다. 위에서 7 과 2 가 각각 과 로 이름 붙여진 행의 마지막 성분이기 때문에 최적해는 P = (7, 2) 가 된다. 의 최대값은 310 이 된다.

초기 단체표는 다음과 같다.

위 표에서 추축열을 2 열로 놓으면 추축 성분은 2 행 2 열의 2 가 된다. 기본행연산을 통하여 다음과 같은 새로운 단체표를 얻을 수 있다.

위 표에서 추축열을 1 열로 놓으면 추축 성분은 1 행 1 열의 4 가 된다. 기본행연산을 통하여 다음과 같은 새로운 단체표를 얻을 수 있다.

위 단체표는 음의 지시기를 갖지 않으므로 최종 단계표가 된다. 최적해는 Q = (1, 5) 이고, 목적함수  의 최소값은 13 이 된다.

이제 단체법을 이용하여 큰 크기의 행렬게임의 해를 구해보자. 단체법을 적용하기 위해서는 행렬게임의 소득행렬이 안장점을 갖지 않으며, 행동이와 열심이 모두가 열세한 전략들을 갖지 않는다고 가정해야 한다. 해를 구하기 위한 첫 번째 단계는 행렬의 모든 성분을 양의 수로 만드는 것이다. 적당히 큰 수  를 더하여 모든 성분이 양의 값을 갖는 다음 행렬게임을 만든다.

두 번째 단계는 다음과 같은 최대 선형계획법 문제의 해를 구하는 것이다.

Maximize

subject to

.

위 문제에 대응하는 단체표는 다음과 같다.

위 단체표에 단체법을 적용하면 최대문제의 최적해 , 쌍대최소문제의 최적해 , 최대값 혹은 쌍대문제의 최소값 를 구할 수 있다. 그러면 행동이의 최적혼합전략은

즉,

이 되고, 열심이의 최적혼합전략은

즉,

이 되며, 게임의 값은

가 된다.

초기 단계표는 다음과 같다.

위 표에서 추축열을 3 열로 놓으면 추축 성분은 3 행 3 열의 2 가 된다. 기본행연산을 통하여 다음과 같은 새로운 단체표를 얻을 수 있다.

위 표에서 추축열을 1 열로 놓으면 추축 성분은 1 행 1 열의 이 된다. 기본행연산을 통하여 다음과 같은 새로운 단체표를 얻을 수 있다.

위 표에서 추축열을 2 열로 놓으면 추축 성분은 2 행 2 열의 가 된다. 기본행연산을 통하여 다음과 같은 단체표를 얻을 수 있다.

위 표에서 , , 이 된다. 그러므로 행동이의 최적혼합전략은

즉,

가 되고, 열심이의 최적혼합전략은

즉,

가 되며, 게임의 값은

가 된다.