ゲーム理論入門/(2)ミニ・マックス定理

ゼロ和2人ゲームとミニ・マックス定理

ゼロ和2人ゲーム
2人のプレイヤーが互いに勝ち負けを争うゲーム

 → フォン・ノイマンによる回答(1928年)=ミニ・マックス定理

  • ミニ・マックス戦略=最大損失を最小化する戦略
  • マックス・ミニ戦略=最小利得を最大化する戦略

  両者の戦略は同じ結果をもたらす


例) じゃんけん

   G = グー、T = チョキ、P = パー と表記すると
    必ずP(orG orT)を出す戦略 = 純粋戦略
    ある確率pでGを出し、確率qでTを、確率rでPを出す戦略 = 混合戦略
     (この混合戦略を(p, q, r)と表記する)

<プレイヤー1が純粋戦略、プレイヤー2が混合戦略を取った場合>

プレイヤー2の混合戦略を(p, q, r)とすると、プレイヤー1の利得表は以下の通り。

    プレイヤ
ー2
(=混合 戦略 )
    確率p 確率q 確率r
    G T P   プレイヤー1利得
プレイヤー1 G    0    1   −1        q-r
(=純粋戦略)  T   −1    0    1        -p+r
  P    1   −1    0        p-q
<プレイヤー1が(1/3, 1/3, 1/3)という混合戦略を取った場合>

プレイヤー1の利得は常に(=プレイヤー2の戦略に関わらず)ゼロ。
( ∵ 1/3(q-r) + 1/3(-p+r) + 1/3(p-q) = 0 )

<プレイヤー1が(1/3, 1/3, 1/3)以外の混合戦略を取った場合>

プレイヤー1が(p’, q’, r’)≠(1/3, 1/3, 1/3)という混合戦略を取れば、p’, q’, r’のいずれかは必ず1/3より大きくなる。今、p’が3つの確率の中で最大とすると、プレイヤー2は(0,0,1)という純粋戦略を取ればp’-q’≧0の利得を得ることができる。これはそのままプレイヤー1の損失となる。 → プレイヤー1の損失 = -p’+q’≦0

この時、プレイヤー1は(1/3, 1/3, 1/3)を取った場合の利得(=ゼロ)を確保することができない。従って、プレイヤー1が最小利得を最大化するマックス・ミニ戦略は混合戦略(1/3, 1/3, 1/3)。
同時に、この損失は、プレイヤー1が(1/3, 1/3, 1/3)を取った場合の損失(=ゼロ)を下回る。従って、プレイヤー1が最大損失を最小化するミニ・マックス戦略もやはり混合戦略(1/3, 1/3, 1/3)。


上記の話ではプレイヤー1とプレイヤー2は対称的なので、プレイヤー2についても同様の結果が成り立つ。