정의
게임의 참여자들의 이득의 합이 항상 0이면 그 게임을 영합게임, 또는 제로섬 게임(zero-sum game)이라 한다.
예시
2인 영합게임
영합게임에서 참여자의 수가 2명일 때, 참여자를 각각 라고 하자. 만약 가 택할 수 있는 전략의 수가 각각 m,n이면, 이 게임을 m×n직사각게임 또는 m×n게임이라 한다. 가 택하는 전략을 각각 라 하고, 이때 의 이득을 라고 하면, 다음 표
|
1
|
2
|
|
n
|
1
|
|
|
|
|
2
|
|
|
|
|
|
|
|
|
|
m
|
|
|
|
|
를 게임의 이득표(payoff table)이라고 한다. 그리고 행렬 를 게임의 이득행렬(payoff matrix)이라고 한다.
결정적 게임과 비결정적 게임
2인 영합게임에서 참여자들은 항상 최선의 전략을 사용하여 최대의 이득을 얻으려고 한다. 이때 각 참여자들은 상대방이 자신에게 가장 불리한 전략을 쓸 경우에 대비해 예상되는 손해를 줄이려고 행동한다고 가정한다. 그러면 는 이득행렬의 행의 최솟값 중에서 최댓값을 얻는 전략을 선택할 것이고, 반대로 는 이득행렬의 열의 최댓값 중에서 최솟값을 얻는 전략을 실행할 것이다. 따라서 미니맥스(minimax)와 맥시민(maximin)을 다음과 같이 정의할 수 있다: A의 i번째 행 의 최솟값을 라 하고, j번째 열 의 최댓값을 라고 하자. 그러면
이다.
결정적 게임
미니맥스와 맥시민이 같은 게임을 결정적 게임(strictly determined game)이라고 한다.
만약 참여자에게 전략 가 주어졌을 때 상대방의 전략에 상관없이 전략 a를 선택했을 때 전략 b보다 더 많은 이익을 얻는다고 하자. 그러면 a를 우월한 전략(dominant strategy), b를 열등한 전략(dominated strategy)이라고 한다. m×n게임의 이득표에서 열등한 전략을 소거하는 것을 축약(contraction)이라고 한다. 만약 축약된 게임이 결정적 게임이라면, 원래 게임도 결정적 게임이다.
예를 들어, 어떤 2인 영합게임의 이득행렬이 다음과 같이 주어졌다고 가정하자.
그러면 의 세 번째 전략은 첫 번째, 두 번째 전략보다 우월하다. 따라서 축약하면
이다. 따라서 이 게임은 는 첫 번째 전략을 선택하고 는 세 번째 전략을 선택하는 결정적 게임이다.
비결정적 게임
결정적 게임이 아닌 게임을 비결정적 게임(non-strictly determined game)이라고 한다. m×n게임에서 본래의 전략을 순수전략(pure strategy)이라 하고, 순수전략을 혼합하여 택하는 전략을 혼합전략(mixed strategy)이라고 하며, 혼합전략은 열벡터로 나타낼 수 있다. 이 전략 1,2,...,m을 확률 으로 택하는 혼합전략을 행렬 , 가 전략 1,2,...,n을 확률 으로 택하는 혼합전략을 행렬 라고 하자. 그러면
으로 나타낼 수 있으며, 이때 이 얻을 것으로 기대되는 이득, 즉 기대이득(expected payoff)은 이중선형형식(bilinear form)
으로 나타낼 수 있다.
의 혼합전략 에 대해 를 다음과 같이 정의하자.
그리고 이 되는 를 라고 하자. 이때 를 의 맥시민 전략(maximin strategy)이라고 한다.
의 혼합전략 에 대해 를 다음과 같이 정의하자.
그리고 이 되는 를 라고 하자. 이때 를 의 미니맥스 전략(minimax strategy)이라고 한다.
그러면 이고, 다음 식이 성립한다.
의 i,j번째 순수전략 를 다음과 같이 정의할 수 있다.
이때 는 크로네커 델타다. 그러면 다음 식이 성립한다.
같이 보기