【ゲーム理論】第2回 - 零和ゲームと混合戦略、相関戦略について解説

# はじめに
**マルチエージェントインタラクションとゲーム理論**(Multi-agent Interaction and Games, MAIG)について学習したので、備忘録も兼ねて同分野の基礎について解説します。一部の専門用語については他の文献と訳出の齟齬があるかもしれませんがあしからず。記事の内容に誤りを発見した際はご指摘ください。

第2回となる本稿では、まず**零和（ゼロサム）ゲーム**を扱います。その後、前回扱った戦略を発展させた**混合戦略と相関戦略**、さらには**ミニマックス戦略とマックスミニ戦略、ミニマックス・リグレット**について説明します。

前回 ▶ [【ゲーム理論】第1回 - ナッシュ均衡とパレート最適について解説](https://qiita.com/inoz/items/b5cf3cb363e0eb57d811)
次回 ▶ 【ゲーム理論】第3回 - 展開型ゲームについて解説（執筆中）

<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/47816087-892e-8d87-5a6d-bf7ade3871f8.jpeg">

# 零和ゲームとは
チェスやポーカーのように、**片方が勝つと片方が負ける**という仕組みになっている2人のプレイヤーによるゲームのことを**零和ゲーム**といいます。英語のまま「**ゼロサムゲーム**」と呼ばれることも多いです。

零和ゲームの例として、**プレイヤー1が偶数か奇数のどちらかの数字を思い浮かべ、プレイヤー2がそれが偶数であるか奇数であるかを予測する**、という零和ゲームを考えましょう。プレイヤー2が正しく予測できればプレイヤー2の効用は $1$ 、プレイヤー2が誤った予測をした場合のプレイヤー2の効用は $-1$ です。零和ゲームなので、予測が当たった場合のプレイヤー1の効用は $-1$ 、外れた場合のプレイヤー1の効用は $1$ となります。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/11e7e003-d0e0-acc5-e68a-7a015b28bd06.png">

繰り返しになりますが、零和ゲームの場合、**プレイヤー1の効用とプレイヤー2の効用の和は常に $0$ となります**。そのため表によってゲームを表す際は、プレイヤー1の効用のみを表記すれば二人の効用を特定するのには十分です。したがって、例えば以下のように**表記を簡略化**することができます。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/aa5ceebb-489a-cc6a-71d9-ebdd90fc7561.png">

# 混合戦略
前回の記事で扱った戦略は、いずれも「**とり得る行動の中からどれか1つを選ぶ**」という**決定的なもの**でした。このように、一つだけの行動を選択する戦略のことを「**純粋戦略**」と呼びます。

しかし、戦略では必ずしも同じ行動を毎回取らなければならないというわけではありません。コインの裏表のような**偶然の要素に従う戦略**について考えてみましょう。

## 混合戦略とは
**実際に取る行動を確率的に決めるような戦略**のことを、**混合戦略**といいます。もう少し正確に言えば、混合戦略とは**取りうる行動に対して定義される確率分布に従ってプレイヤーが行動を選択するような戦略**のことです。

$n$ 人のプレイヤーが参加する標準形ゲーム $(N,\\,A,\\,u)$ に対して混合戦略を $s=(s_1,\\,s_2,\\,\cdots,\\,s_n)$ と定義します。$s_i:\\,A_i\mapsto \[0,\\,1\]$ は任意の $i$ に対して
$$
\sum_{a\in A_i}s_i\\,(a)=1
$$
を満たす、「**$i$ 番目のプレイヤーがある行動を取る確率を与える関数**」です。

このとき、混合戦略 $s$ についてのプレイヤー $i$ の**期待効用**（効用の期待値）は以下のように表すことができます。

$$
u_i(s)=\sum_{a\\in A}u_i\\,(a)\prod_{j=1}^{n}s_j\\,(a_j)
$$

$a$はプレイヤー全員の行動の組 $(a_1,\\,a_2,\\,\cdots,\\,a_n)$ であったことを思い出せば、飲み込みやすい式なのではないでしょうか。

## 混合戦略におけるナッシュ均衡
零和ゲームの章で紹介した「**数当てゲーム**」をもう一度見てみましょう。前回扱った純粋戦略のみを考えた場合、このゲームにナッシュ均衡は存在するでしょうか。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/85a849a2-fb99-7f11-522b-cc89b9dbcd11.png">

例えばプレイヤー1が偶数、プレイヤー2が偶数をそれぞれ選ぶ状況はナッシュ均衡になるでしょうか。プレイヤー1にとっては、プレイヤー2が偶数を選ぶとわかっている状況のもとでは奇数を選択したほうが効用が高いです。ではプレイヤー1が奇数、プレイヤー2が偶数を選ぶ場合はどうかというと、今度はプレイヤー2にとっては奇数を選んだほうが効用が高くなります。同様に一つ一つ確かめてみればわかりますが、**明らかにこのゲームに純粋戦略のナッシュ均衡は存在しません**ね。

**混合戦略を用いた均衡**について考えてみましょう。プレイヤー1が偶数を選択する確率を $p_e$、奇数を選択する確率を $p_o$ と表します。同様に、プレイヤー2が偶数を選択する確率を $q_e$ 、奇数を選択する確率を $q_o$ と表します。また、表記の簡略化のため「偶数を選択する」という行動を $e$ 、「奇数を選択する」という行動を $o$ と表しましょう。

$p_e,\\,p_o,\\,q_e,\\,q_o$ に従う戦略がナッシュ均衡となるとき、プレイヤー1にとって「**自身が偶数を選択したときの期待効用」と「自身が奇数を選択したときの期待効用」は等しくなる必要があります**[^1]。ゆえに、以下の式が成り立ちます。左辺が「プレイヤー1が偶数を選択したときのプレイヤー1の期待効用」、右辺が「プレイヤー1が奇数を選択したときのプレイヤー1の期待効用」です。
$$
\begin{align}
-1\cdot q_e+1\cdot q_o=1\cdot q_e+-1\cdot q_o\tag{1}
\end{align}
$$

同様に、プレイヤー2にとって「**自身が偶数を選択したときの期待効用」と「自身が奇数を選択したときの期待効用」は等しくなる必要があります**。よって先ほどと同様に、以下の式が成り立ちます。
$$
\begin{align}
1\cdot p_e+-1\cdot p_o=-1\cdot p_e+-1\cdot p_o\tag{2}
\end{align}
$$

また、プレイヤー1とプレイヤー2はそれぞれ偶数か奇数のどちらかを必ず選択するので、$p_e,\\,p_o,\\,q_e,\\,q_o$ は以下の式を満たします。
$$
\begin{align}
p_e+p_o=1\tag{3}\\\\
q_e+q_0=1\tag{4}
\end{align}
$$

以上の(1)〜(4)式を連立すると、**混合戦略におけるナッシュ均衡**を与える$p_e,\\,p_o,\\,q_e,\\,q_o$ は
$$
p_e=p_o=q_e=q_o=\frac{1}{2}
$$
と求まります。つまり、**両者がそれぞれ等確率でランダムに奇数か偶数を選択するような戦略**が、数字当てゲームにおけるナッシュ均衡です。

## 混合戦略の性質
**混合戦略におけるナッシュ均衡の別の例**を見てみましょう。プレイヤー1とプレイヤー2がサッカーをするか野球をするかを決める、下表のようなゲームを考えます。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/e1f6440f-e71f-559f-e2ad-70e305db184a.png">

プレイヤー1はサッカーの方が好きですが、プレイヤー2は野球のほうが好きです。ただし二人の希望が食い違うとどちらも効用は $0$ になってしまう、というようなシチュエーションです。このゲームにおける**純粋戦略のナッシュ均衡は、下図で黄色く示した2マス**ですね。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/197d58ad-7be2-1b57-0c0b-b4bacabc38de.png">

さて、**混合戦略におけるナッシュ均衡**を求めてみましょう。プレイヤー1がサッカーを選ぶ確率を $p_s$、野球を選ぶ確率を $p_b$、プレイヤー2がサッカーを選ぶ確率を $q_s$、野球を選ぶ確率を $q_b$とそれぞれ表します。数字当てゲームの際と同様に立式すると、

$$
\begin{align}
\begin{cases}
&p_b+p_s=1\\\\
&q_b+q_s=1\\\\
&1\cdot p_s+0\cdot p_b=0\cdot p_s+2\cdot p_b\\\\
&2\cdot q_s+0\cdot q_b=0\cdot q_s+1\cdot q_b\\\\
\end{cases}
\end{align}
$$

と立式できます。これらを連立すると、

$$
\begin{align}
p_b=q_s=\dfrac{1}{3}\\\\
p_s=q_b=\dfrac{2}{3}
\end{align}
$$

が得られます。これが**混合戦略におけるナッシュ均衡**です。さて、この**ナッシュ均衡における期待効用**はいくらでしょうか。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/a0b60f96-3bd7-80f1-852f-27e4ecf7a268.png">

求まった混合戦略におけるナッシュ均衡に従った際、**それぞれの行動の組が実現する確率は上表の通り**となります。したがって、プレイヤー1の期待効用は

$$
2\cdot\dfrac{2}{9}+0\cdot\dfrac{1}{9}+0\cdot\dfrac{4}{9}+1\cdot\dfrac{2}{9}=\dfrac{2}{3}
$$

です。同様にプレイヤー2の期待効用も $2\\,/\\,3$ となります。一方、**純粋戦略のナッシュ均衡における効用は悪くても $1$ です**。純粋戦略における $2$ つのナッシュ均衡はどちらも、**混合戦略におけるナッシュ均衡をパレート支配**しています。

**純粋戦略におけるナッシュ均衡は、混合戦略におけるナッシュ均衡をパレート支配することがあります**。ただし、必ずしもそうなるというわけではなく、混合戦略におけるナッシュ均衡が純粋戦略におけるナッシュ均衡をパレート支配する場合もあります。

# 相関戦略
混合戦略では両者が独立した偶然によって行動を選択していました。それでは、両者が**独立でない偶然の要素に従って行動を選択するような場合**はどうでしょうか。ここでは、**両者が1つの偶然の要素に従って行動するという相関戦略の概念**について説明します。

## 相関戦略とは
相関戦略とは、複数のプレイヤーが「**共通して観察できる偶然の結果**」に基づいて行動を決定するような戦略のことです。先述した数当てゲームにおける例を考えてみます。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/85a849a2-fb99-7f11-522b-cc89b9dbcd11.png">

二人が行動を選択する前に**一枚のコインを投げる**とします。相関戦略の例としては、
- **コインの表**が出た場合、プレイヤー1は偶数を、プレイヤー2は奇数を選択する
- **コインの裏**が出た場合、プレイヤー1は奇数を、プレイヤー2は偶数を選択する

といったものが考えられます。

## 相関均衡
**ある一つの偶然の要素**に基づいた**一定のルールに従ってそれぞれのプレイヤーが行動を選択する**場合を考えます。すべてのプレイヤーについて、**他の任意のルールに従ったとき以上の期待効用が得られる**場合、それは**相関均衡**であるといいます。

もう少し正確に定義しましょう。**$n$ 人のプレイヤーを持つ標準形ゲーム** $G=(N,\\,A,\\,u)$ を考えます。集合 $D_i$ を集めたタプル $D$ を $D=(D_1,\\,D_2,\\,\cdots,\\,D_n)$ とし、$d_i\in D_i$ であるとします。また、**$\pi$ を $D$ 上の確率分布**とします。また、$\sigma=(\sigma_1,\\,\sigma_2,\\,\cdots,\\,\sigma_n)$ を $\sigma_i:\\,D_i\mapsto A_i$ なる写像のタプルとします。このとき、任意のプレイヤー $i$ と$\sigma'_i:\\,D_i\mapsto A_i$ なる任意の写像 $\sigma'_i$ に対して、

$$
\begin{align}
&\sum_{d\in D}\pi(d)\\, u_i(\sigma_1(d_1),\\,\\cdots,\\,\sigma_i(d_i),\\,\cdots,\\,\sigma_n(d_n))\\geq \\\\
&\sum_{d\in D}\pi(d)\\, u_i(\sigma_1(d_1),\\,\\cdots,\\,\sigma'_i(d_i),\\,\cdots,\\,\sigma_n(d_n))
\end{align}
$$

が成立するとき、**タプル $(D,\\,\pi,\\,\sigma)$ は相関均衡である**、といいます。この数式だけでは意味が取りにくいかもしれません。噛み砕いて説明すると、

- 全員に共通する確率分布 $\pi$ にしたがって集合 $D_i$ の中からそれぞれランダムな要素を選び、**それぞれのプレイヤーは一定のルールに従って、与えられた $d_i$ を基に行動を決める**
- **今よりも良いルールが誰にも存在しないとき、相関均衡**である

ということです。以下の例を見てさらに理解を深めましょう。

## 相関均衡の例
例えば、先程も登場した**野球かサッカーを選択するゲームにおける相関均衡の例**としては、

- **コイントスで表**が出たらプレイヤー1とプレイヤー2は**共にサッカー**を選択する
- **コイントスで裏**が出たらプレイヤー1とプレイヤー2は**共に野球**を選択する

が挙げられます。
<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/4017770e-41af-6d1b-e96a-3f8f351b492d.png">

先程の数式に当てはめてみましょう。**2人のプレイヤー**がいるため $N=\{1,\\,2\}$ となります。サッカーを $S$、野球を $B$ でそれぞれ表すと、**行動**は $A_1=A_2={S,\\,B}$ です。

**コインの表を $H$、コインの裏を $T$** とそれぞれ表すと、$D_1=D_2={H,\\,T}$ です。また、コイントスに用いるコインは表裏がそれぞれ $1\\,/\\,2$ の確率で出るとします。このとき、$\pi(H,\\,H)=\pi(T,\\,T)=1\\,/\\,2$です。$\pi(H,\\,T)$ と $\pi(T,\\,H)$ は1枚のコインの表と裏が同時に出ることを意味しているため、どちらも $0$ です。

**コイントスで表**が出た場合、プレイヤー1とプレイヤー2は**どちらもサッカーを選択する**ため、$\sigma_1(H,\\,H)=\sigma_2(H,\\,H)=S$ となります。**裏が出た場合は共に野球を選択する**ため、同様に $\sigma_1(T,\\,T)=\sigma_2(T,\\,T)=S$ です。相関均衡の定義式が理解できなかった場合は、以上の例と照らし合わせながら確認すると意味が分かるはずです。

## 相関均衡の性質
先述した**相関均衡における期待効用**を計算してみましょう。コインは表裏がそれぞれ $1\\,/\\,2$ の確率で出ると仮定したため、**プレイヤー1の期待効用**は
$$
2\cdot\dfrac{1}{2}+1\cdot\dfrac{1}{2}=\dfrac{3}{2}
$$
となります。**プレイヤー2の期待効用**も、同様に計算すると $3\\,/\\,2$ と求まります。混合戦略のナッシュ均衡における両者の期待効用はそれぞれ $2\\,/\\,3$ であったため、**相関均衡の期待効用のほうが高くなっています**ね。

相関均衡は、**ナッシュ均衡を一般化した概念**であることが知られています。すなわち、ナッシュ均衡が存在する場合、それに対応する相関戦略が存在します[^2]。

# 種々の戦略
ここまで紹介してきたナッシュ均衡などは、どれも**互いのプレイヤーが合理的な選択をするという仮定**に基づいたものでした。ここからは相手が非合理的な選択をしうる場合にも有効な、**マックスミニ戦略とミニマックス戦略、ミニマックス・リグレット**について説明します。

## マックスミニ戦略
マックスミニ戦略は、**自身の獲得しうる利得の最小値を最大化する戦略**です。純粋戦略におけるマックスミニ戦略を考えてみます。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/3856108e-2d54-7610-b6c9-31040f6c7ff1.png">

上表のようなゲームを考えましょう。まずは**プレイヤー1が行動 $A$ を選択する場合**について考えます。このとき、プレイヤー2が $A$ を選択した場合の効用は $3$、プレイヤー2が $B$ を選択した場合の効用は $2$ です。したがって、**プレイヤー1が行動 $A$ を選択する場合の最小効用は $2$** となります。同様に、**プレイヤー1が行動 $B$ を選択する場合の最小効用は $1$** です。これらを上図では赤枠で示しています。

両者を比較すると、**プレイヤー1の最小効用が高くなる行動は $A$** であることがわかりますね。したがって、**プレイヤー1が最小効用を最大化しようとする場合、選択する行動は $A$** となります。これがマックスミニ戦略です。なお、マックスミニ戦略を取る際、考えられる効用の最小値のことを「**マックスミニ値**」と呼びます。先程の例の場合、プレイヤー1にとってのマックスミニ値は $2$ です。

### 混合マックスミニ戦略
**混合戦略**についても**マックスミニ戦略**を考えることができます。再び、**サッカーか野球を選択するゲーム**について考えてみましょう。プレイヤー1がサッカーを選択する確率を $p_S$、プレイヤー2がサッカーを選択する確率を $q_S$ とします。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/bdae9c31-2954-7488-162b-c116fe35be88.png">

このとき、プレイヤー1の**期待効用**は
$$
\begin{align}
&2\cdot p_S q_S+1\cdot (1-p_S)(1-q_S)\\\\
&=3p_S q_S-p_S-q_S+1\\\\
&=(3p_S-1)q_S-p_S+1
\end{align}
$$
と表すことができます。このとき**マックスミニ戦略**を与える $p_S$ は
$$
\arg\max_{p_S\in[0,\\,1]}\[\min_{q_S\in[0,\\,1]}\\{(3p_S-1)q_S-p_S+1\\}\]
$$
と表せますね。具体的に $q_s\in [0,\\,1]$ を計算すると、
$$
\begin{cases}
&q_s=0\quad&\left(\dfrac{1}{3}\leq p_S\leq 1\right)\\\\
&q_s=1\quad&\left(0\leq p_S\leq \dfrac{1}{3}\right)
\end{cases}
$$
となります。このとき**プレイヤー1の期待効用**は以下の通りです。
$$
\begin{cases}
&-p_S+1\quad&\left(\dfrac{1}{3}\leq p_S\leq 1\right)\\\\
&2p_S\quad&\left(0\leq p_S\leq \dfrac{1}{3}\right)
\end{cases}
$$
ゆえに**以下のグラフ**から、このときの**プレイヤー1の期待効用の最大値**は $p_S=1\\,/\\,3$ のときの $2\\,/\\,3$ と求まります。横軸に $p_S$、縦軸に期待効用 $E_1$ を取っています。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/70d6c552-3770-f09e-c195-42fd0b35f671.png">


## ミニマックス戦略
ミニマックス戦略は、マックスミニ戦略とは反対に「**相手が得る利得の最大値を最小化する**」戦略です。この場合、**自分の利得は度外視**して、**相手の最大利得を最小化することのみを考えます**。

例えば下表に示すゲームを考えましょう。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/0d66002f-9402-3e3a-fdd9-0831b19393ef.png">

**プレイヤー1の視点**に立ちます。もし**自分が行動 $A$ を選択した場合、プレイヤー2の最大効用は $4$** です。もし**自分が行動 $B$ を選択した場合、プレイヤー2の最大効用は $3$** です。表ではそれぞれ赤枠で示しています。**プレイヤー1は相手の最大効用を最小化したい**ため、ミニマックス戦略を採用する場合、**プレイヤー1は行動 $B$ を選ぶ**ことになります。

なお、マックスミニ戦略と同様に、**ミニマックス戦略についても混合戦略**を考えることができます。

**有限な二人零和ゲーム**においてはどちらのプレイヤーに対しても、**ミニマックス戦略において得られる戦略とマックスミニ戦略において得られる戦略が一致**します。これは、1928年にノイマンによって証明された「**ミニマックス定理**」として知られています。

## ミニマックス・リグレット
本稿の最後に、**ミニマックス・リグレット戦略**について紹介します。ミニマックス・リグレットは、**最も悪いケースの損失**（正確には後述するリグレット）**を最小化する戦略**です。最も悪いケースの利得を最大化するマックスミニ戦略と似ていますが、一般にはマックスミニ戦略と異なる戦略が得られます。

### リグレットとは
ミニマックス・リグレット戦略の解説に入る前に、**リグレット**（後悔）について説明します。リグレットとは、自分以外のプレイヤーの行動が同じときに、**自分が得られたであろう効用の最大値との差**のことです。これだけだとやや分かりにくいので、具体例で説明します。

例えば、マックスミニ戦略の際にも登場した以下のゲームおいて、**プレイヤー1とプレイヤー2がそれぞれ $B$ を選んだ**とします。この場合の**プレイヤー1のリグレット**について考えてみましょう。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/64eb6ecc-7db0-2447-46b0-0c8ca17cd108.png">

プレイヤー2が $B$ を選択する場合、**プレイヤー1にとって最適な行動は $A$** です。もしプレイヤー1が $B$ ではなく $A$ を選択していれば、**プレイヤー1は効用 $2$** を得ることができました。しかし、プレイヤー1は $B$ を選択してしまったので、**実際に得た効用は $1$** です。ゆえに、このときの**リグレット**は $2-1=1$ となります。

数式で表してみましょう。**プレイヤー $i$ が取った行動**を $a_i$、**プレイヤー$i$　以外が取った行動**を $a_{-i}$ で表します。このとき、**プレイヤー $i$ のリグレット**は以下の式で表すことができます。
$$
\[\max_{a'\_i\in A_i}u_i(a'\_i,\\,a_{-i})\]-u_i(a_i,\\,a_{-i})
$$

### 最大リグレットとは
**プレイヤー $i$ にとっての最大リグレット**とは、**プレイヤー $i$ が行動 $a_i$ を取るとき**、プレイヤー $i$ 以外が取るすべての行動の中での**リグレットの最大値**を指します。こちらも例を見てみましょう。**プレイヤー1が $A$ を選ぶ**とします。

<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/d39f965f-8c08-53fd-3d4a-5dc5781fa4ea.png">

プレイヤー2が $A$ を選ぶとき、プレイヤー1の効用は $3$、プレイヤー2が $B$ を選ぶとき、プレイヤー1の効用は $2$ となります。ゆえに、$(A,\\,A)$ のリグレットは $3-3=0$、$(A,\\,B)$ のリグレットは $3-2=1$ です。したがって、**プレイヤー1が $A$ を選ぶ際の最大リグレットは $1$** となります。

同様に、**プレイヤー1が $B$ を選ぶ**とします。
<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/542b75cc-362d-739e-3614-f481483de0e9.png">
プレイヤー2が $A$ を選ぶとき、プレイヤー1の効用は $5$ です。プレイヤー2が $B$ を選ぶとき、プレイヤー2の効用は $1$ です。ゆえに、$(B,\\,A)$ のリグレットは $5-5=0$、$(B,\\,B)$ のリグレットは $5-1=4$ となり、**プレイヤー1が $B$ を選ぶ場合の最大リグレットは $4$** となります。

$i$ 番目のプレイヤーが行動 $a_i$ を取るときの最大リグレットは、**先程定義したリグレットの最大値**となるため、以下のように表すことができます。
$$
\max_{a'\_{-i}\in A_{-i}}\left(\[\max_{a'\_i\in A_i}u_i(a'\_i,\\,a_{-i})\]-u_i(a_i,\\,a_{-i})\right)
$$

### ミニマックス・リグレットとは
ミニマックス・リグレットとは、**最大リグレットを最小化する戦略**のことです。

先程求めた通り、プレイヤー$1$ にとって **$A$ を選択した際の最大リグレットは $1$、$B$ を選択した際の最大リグレットは $4$** でした。ミニマックス・リグレットにおいてはこの最大リグレットが最小となる行動を選択するため、プレイヤー1は行動 $A$ を選択します。**起こりうる後悔の小さい行動を選択する**、という方針ですね。
<img width="600" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/d99c56bd-96bc-3817-ee59-b13ff6fd1549.png">

プレイヤー$i$ は自身がとり得る行動の中で、**最大リグレットが最小となるような行動**を取ります。そのため、ミニマックス・リグレットにおいてプレイヤー $i$ が取る行動を数式で表すと以下のようになります。

$$
\underset{a_i\in A_i}{\rm{argmin}}\\,\left[\max_{a'\_{-i}\in A_{-i}}\left(\[\max_{a'\_i\in A_i}u_i(a'\_i,\\,a_{-i})\]-u_i(a_i,\\,a_{-i})\right)\right]
$$

# おわりに
**零和ゲームや混合戦略、相関戦略**について扱いました。また、種々の戦略として**マックスミニ戦略やミニマックス戦略、さらにはミニマックス・リグレット**について紹介しました。ゲーム理論独特の考え方が多く感じるかもしれませんが、これらはいずれもゲームにおける戦略を考える上で重要な概念です。次回は**展開型ゲーム**について扱っていきます。

### 訳出について
専門用語は、[Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%B2%E3%83%BC%E3%83%A0%E7%90%86%E8%AB%96)を参考に以下のように訳出しています。
| 日本語 | 英語 |
| :-: | :-: |
| 零和ゲーム | Zero-sum Game |
| 期待効用 | Expected Utility |
| 純粋戦略 | Pure Strategy |
| 混合戦略 | Mixed Strategy |
| 相関戦略 | Correlated Strategy |
| マックスミニ戦略 | Maxmin Strategy |
| マックスミニ値 | Maxmin Value |
| 混合マックスミニ戦略 | Mixed Maxmin Strategy |
| ミニマックス戦略 | Minmax Strategy |
| リグレット | Regret |
| ミニマックス・リグレット | Minmax Regret |

## 参考文献
1. Yoav Shoham and Kevin Leyton-Brown, "Multi-Agent Systems", Cambridge University Press(2009)
2. Wikipedia, "ゲーム理論", https://ja.wikipedia.org/wiki/%E3%82%B2%E3%83%BC%E3%83%A0%E7%90%86%E8%AB%96, 最終閲覧2022/11/08
3. 画像素材: Unsplash, https://unsplash.com/ja, 最終閲覧2022/11/02

なお、内容の説明にはLeibniz Universität HannoverのDaniel Kudenko先生の講義を参考にしています。

[^1]: 等しくなければ、より期待効用が高い方へ $p_e,\\,p_o$ を調整することができてしまいます。
[^2]: 相関戦略が存在する場合でも、それに対応するナッシュ均衡が存在するとは限りません。