최소최대정리 : Mini-Max Theorem : 권오헌. 윤태환

Mini-Max Theorem

다음은 게임이론의 기본정리인 최소최대정리 (minimax theorem) 이다.

※ 정리 A.1

임의의 크기의 행렬게임은 해를 갖는다.

증명

임의의 크기의 행렬 에 대하여

를 보이면 충분하다. 여기서 과 은 각각 행동이와 열심이의 혼합전략이고, 는 게임의 값이다.

이 임의의 개의 수이고, 이 행동이의 혼합전략이라고 가정하자. 그러면 모든 에 대하여 적당한 가 존재하여

가 된다. 위 식을 로 곱하고, 에 대하여 모든 항을 더하면

가 되므로

가 된다.

한편 번째 순수전략을 택하면

가 된다. 그러므로

와

를 얻을 수 있다.

동치문제

와 가 다음과 같이 정의된다고 하자.

그러면 최소, 최대의 정의로부터 다음과 같은 두 개의 부등식을 얻는다.

모든 에 대하여

이제 첫 번째 부등식을 로 곱하여 에 대하여 모두 더하고, 두 번재 부등식을 로 곱하고 에 대하여 모두 더하면

가 된다.

이제

가 되는 한 쌍의 혼합전략 와 를 찾을 수 있다고 가정하자. 그러면

이므로

를 얻을 수 있다. 마찬가지로

를 얻을 수 있다.

최소최대정리는

를 의미하므로, 근본적으로 다음 문제와 동치이다.

다음 일곱 가지 조건을 만족하는, 성분이 각각 와 인 -성분 벡터 와 -성분 벡터 를 찾아라. 여기서 이고 이다.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

증명은 위의 일곱 가지 조건을 만족하는 와 를 찾는 것으로 이루어진다.

기저행렬 (basic matrix)

게임행렬 의 확대행렬을 다음과 같이 정의하자.

이 행렬은 개의 행과 개의 열을 갖는다. 의 첫 행을 으로 명명하고, 열들을 다음과 같이 명명하자.

여기서 는 -성분으로 1 을 갖고 나머지 성분은 모두 0 인 벡터이다. 더욱이, A 의 행들이

이 되도록 배열되었다고 가정하자.

의 개의 열을 택하면, 크기의 정방행렬 가 결정된다. 가 다음 세 가지 조건을 만족하면 를 기저행렬 (basic matrix) 이라고 한다.

B1. 가 의 첫 번째 열로 포함된다.

B2. 는 정칙행렬이다. 즉 는 역행렬 을 갖는다.

B3. 의 각 행은, 첫 번째 행을 제외하고, 처음으로 0 이 아닌 성분이 양수이다.

다음과 같은 행렬이 기저행렬의 한 예이다.

위 행렬은 정칙행렬이며 역행렬은

로 주어진다. 여기서 이다. 앞에서 으로 취했으므로 이 된다. 그러므로 의 모든 행은, 첫 행을 제외하고, 처음으로 영이 아닌 성분이 양수가 된다.

벡터들의 순서

기저행렬의 정의에서 조건 B3 는 벡터들의 영벡터와의 비교로 표현될 수 있다. 이후의 증명에서 임의의 두 벡터를 비교하는 것이 편리하다. 즉 두 개의 다른 벡터들이 주어질 때 큰 벡터를 택하는 규칙을 필요로 한다. 벡터들 간의 적당한 순서 관계를 다음과 같이 정의하자.

우선, 두 벡터의 상등을 정의한다.

두 벡터 와 가 같기 위해서는 임의의 에 대하여 이면 된다고 정의한다. 즉 와 가 같다는 것은 벡터 가 영벡터가 되는 것으로 로 표시한다. 이제 두 벡터 와 가 같지 않다고 가정하자. 그러면 벡터 는 최소한 영이 아닌 하나의 성분을 포함한다. 만일 의 처음으로 영이 아닌 성분이 양수이면, 가 보다 크다고 정의하고 라고 표현한다. 만일 의 처음으로 영이 아닌 성분이 음수이면, 가 보다 작다고 정의하고 라고 표현한다.

만일 기저벡터 의 역행렬의 행들이 으로 표시되면 조건 B3 는

에 대하여

을 의미한다.

벡터의 순서를 정하는 위의 방법에서 일련의 벡터들 중의 최소 벡터는 첫 번째 성분이 가장 작은 벡터가 된다. 만일 동률이 된다면 동률이 되는 벡터들의 두 번째 성분을 비교해야 한다. 등등.

최적기저행렬 (optimal basic matrix)

이 역행렬

을 갖는 기저행렬이라고 하자. 여기서 은 행벡터이고 는 열벡터이다. 그러면 가 단위행렬일 때

이므로

이 된다. 여기서 이다.

특히

이 된다. 이제 개의 스칼라곱

을 만든다고 가정하자. 에 대하여 이므로 개의 스칼라곱 중에서 최소한 개는 영이 된다. 만일 나머지 개의 스칼라곱이 영보다 크지 않다면 를 최적기저행렬 (optimal basic matrix) 이라고 정의한다. 나중에 보이겠지만 최적기저행렬은 참여자들의 최적혼합전략을 만든다. 즉 기저행렬 가

을 만족하면 는 최적기저행렬이 된다.

최적전략 (optimal strategy)

가 최적기저행렬이라고 하자. 의 0 행과 0 열의 성분이 다음과 같이 표시된다고 하자.

그러면 행동이의 최적혼합전략 는 행 로부터

으로 놓음으로써 얻어진다. 열심이의 최적혼합전략 는 열 로부터

으로 놓음으로써 얻어진다.

이제 와 가 앞서 기술한 일곱 가지 조건 (1)-(7) 을 만족함을 보임으로써 와 가 최적혼합전략임을 증명한다.

최적기저벡터가 주어진다고 가정하고 의 다른 값들에 대하여 곱 를 만들어 보자.

만일 이면

가 되므로 조건 (2) 가 만족된다.

만일 이면

가 되므로 조건 (3) 이 만족된다.

만일 이면

이 되므로 조건 (1) 이 만족된다.

는 기저행렬이므로

이 된다. 특히 각 의 첫 번째 성분은 영보다 크거나 같게 된다. 그런데 각 의 첫 번째 성분은 이므로 (4) 가 만족된다.

이므로

가 된다. 이 행렬 방정식으로부터 개의 변수 으로 이루어진 개의 선형 방정식을 얻는다.

각 의 첫 번째 성분은 에 대하여 1 이 되고 그렇지 않으면 0 이 되므로, 이들 방정식의 첫 번째는

이 된다. 그러므로 (5) 가 만족된다. 나머지 개의 방정식은 다음과 같이 씌어질 수 있다.

여기서 이다. 그러므로

이 되므로 (6) 이 만족된다. 마지막으로 와 은 둘 다 의 같은 원소에 의하여 정의되므로 조건 (7) 이 만족된다.

최적기저행렬의 구성

최적전략을 찾는 문제는 이제 최적기저행렬을 만드는 문제로 줄어들었다. 최적기저행렬의 역행렬이 최적전략을 줄 것이다. 최적기저행렬과 그것의 역행렬을 만드는 반복적인 과정을 기술해 보자.

반복적인 과정은 적당한 기저행렬, 예를 들어 앞에서의 를 가지고 시작한다. 가 최적이 아니면 로부터 단지 하나의 열만 바꾼 새로운 기저행렬 을 만든다. 더욱이, 이 의 역행렬 의 0 번째 행이라면, 은 다음과 같은 성질

을 갖도록 한다. 만일 이 최적이 아니면, 에 대하여 앞의 알고리즘을 반복한다. 등등.

이 과정은 일련의 기저행렬들을 만든다. 하지만 로부터 어떤 기저행렬도 반복될 수는 없다. 더욱이, 기저행렬들의 수는 확대행렬 의 개의 열에서 개의 열을 택하는 방법의 수를 초과할 수는 없다. 그러므로 최적기저행렬에 도달했을 때 이 과정을 마치면 된다.

기저행렬 가 최적이 아니라고 가정하자. 그러면 에 있는 적당한 가 존재하여 이 된다. 로부터 을 만들기 위하여 의 한 열을 로 바꾼다. 여기서 는 조건

에 의하여 결정된다. 의 선택이 유일하지 않는 경우에는 가장 작은 지수를 갖는 를 택한다.

다음은 방정식 를 만족하는 열벡터 을 계산해 보자. 그러면

이 된다. 특히

이 된다. 더욱이 영이 아닌 적당한 다른 에 대하여 이 된다. 왜냐하면, 만약 그렇지 않다고 가정한다면, 즉 이라고 한다면, 다음과 같은 관계

로부터

가 따른다. 그러므로 열 는 의 개의 열들의 양의 선형조합으로 씌어질 수 있다. 하지만 의 정의로부터 는 다른 열들의 양의 선형조합으로 씌어질 수가 없으므로 모순이 된다.

이제

이 되는 열 을 에서 제거한다. 그러면

이 된다.

우리는 에서 열 를 제거하고 열 를 추가함으로써 을 만들었다. 이제 이 기저행렬임을 보이는 것이 남아있고, 이를 위하여 에서 을 만들어 보자.

의 행들이 에 대하여 으로 표시된다고 하자. 그러면 와 로부터

라고 놓음으로써 을 얻을 수 있다. 이제 행렬 이 위와 같이 정의된다고 하고 를 증명하자.

첫째로 이고 이면

이 된다. 둘째로 이고 이면

이 된다.

셋째로 이고 이면

이 된다.

마지막으로 이고 이면

이 된다.

그러므로 가 된다.

가 기저행렬이라는 증명을 마치기 위하여 에 대하여 을 보일 필요가 있다. 만일 일 때는 이고 이다. 그러므로

이 된다. 만일 이고 일 때는

이 되고, 만일 이고 일 때는 앞의 정의에 의하여 역시

이 된다. 그러므로 은 기저행렬이다.

마지막으로 어떤 기저행렬도 이 과정에서 반복될 수 없음을 보여야 한다. 이를 위하여 이 만족됨을 보이면 충분하다. 이것은 가 특이행렬의 행이므로 최소한 영이 아닌 하나의 성분을 포함해야 하고 그것은 양수라는 사실로부터 따른다. 이고 이므로

이 된다.

이 에서 제거된 열이라면

이 된다. 또한

이 된다. 그러므로 개의 열 중에서는 최소한 개의 열은 성질 을 갖는다. 이것은 앞 단계에서 이 성질을 갖는 최소한 개의 열과 비교된다. 더욱이, 다음 반복에서 기저벡터에 대한 후보 가 을 만족해야 하므로 은 기저벡터로 돌아올 수 없다. 이로써 정리가 증명된다.