# じゃんけんの話

これは[数学物理 Advent Calender 2022](https://adventar.org/calendars/8175)の8日目の記事です。

---

## 導入
多くの人はじゃんけんをした経験があるでしょう。
「じゃん、けん、ぽん」の掛け声とともに、参加者のそれぞれがグー、チョキ、パーの手の中から一つを選んで出し、出された手の組み合わせによって勝敗(あるいは引き分け)が決まります。

三人以上でおこなうじゃんけんも魅力的ですが、今回は二人でおこなう場合について考えましょう。

グーはチョキに勝ち、チョキはパーに勝ち、パーはグーに勝ちます。最強の手はありません。三つの手の立場は完全に平等なのです。
だからといって、たとえば、必ずグーを出すというやり方はうまくありません。必ずグーを出すという戦略をとる人は、その戦略が相手に知られてしまうと、常に相手にパーを出されて負けてしまいます。戦略の弱みにつけこまれて(裏をかかれて)しまうのです。
では、じゃんけんで勝つには、どのような戦略をとるのがよいのでしょうか？

## ゲーム理論の言葉で
ゲーム理論を使いましょう。
常にある決まった手を出すという戦略は**純粋戦略**と呼ばれます。じゃんけんには3種類の純粋戦略が存在します。すなわち、
- 常にグーを出す
- 常にチョキを出す
- 常にパーを出す

の三つです。また、あなたが純粋戦略 $s_1$ を、相手が純粋戦略 $s_2$ をとったときの利得関数を
\begin{align*}
f(s_1,s_2)=\begin{cases}
1&\text{あなたの勝ちのとき}\\
-1&\text{あなたの負けのとき}\\
0&\text{引き分けのとき}
\end{cases}
\end{align*}と置きます。

実際にじゃんけんをするときに純粋戦略をとる人は稀です。自分の出す手をランダムに決めたくなるかもしれません。たとえば、「確率 $1/4$ でグーを、確率 $1/4$ でチョキを、確率 $1/2$ でパーを出す」のように。このような、ある確率分布にしたがって自分の出す手を選ぶ戦略を**混合戦略**と呼びます。じゃんけんの混合戦略 $q$ は、グーを出す確率 $p_\text{グー}$、チョキを出す確率 $p_\text{チョキ}$、パーを出す確率 $p_\text{パー}$ の三つ組
\begin{align*}
&q=(p_\text{グー},p_\text{チョキ},p_\text{パー}),\\
&p_\text{グー},p_\text{チョキ},p_\text{パー}\ge0,\quad p_\text{グー}+p_\text{チョキ}+p_\text{パー}=1,
\end{align*}で指定されます。混合戦略の全体を $Q$ と書きます。
また、あなたが混合戦略 $q_1$ を、相手が混合戦略 $q_2$ をとったときの利得関数の期待値を $F(q_1,q_2)$ と書きます。
以下では、単に戦略といえば混合戦略のことを指すものとします。

相手のとる戦略 $q_2$ が既知のとき、あなたは $F(q_1,q_2)$ を最大化するような戦略 $q_1$ を取るのが(ある意味で)最適です。このような $q_1$ を $q_2$ に対する最適応答といい、その全体を
\begin{align*}
B_1(q_2)=\{q_1^*\in Q\mid F(q_1^*,q_2)=\max_{q_1\in Q}F(q_1,q_2)\}
\end{align*}と書きます。
同様に、$q_1$に対する(相手の)最適応答の全体を
\begin{align*}
B_2(q_1)
&=\{q_2^*\in Q\mid -F(q_1,q_2^*)=\max_{q_2\in Q}(-F(q_1,q_2))\}\\
&=\{q_2^*\in Q\mid F(q_1,q_2^*)=\min_{q_2\in Q}F(q_1,q_2)\}
\end{align*}と書きます[^1]。あなたの勝ちは相手の負けを、あなたの負けは相手の勝ちを意味するので、相手の視点での利得関数は $-f$ であって、その期待値は $-F$ と表されることに注意してください。
[^1]: 今の場合は $B_1=B_2$ になりますが、後の議論を見やすくするために敢えて記号を分けて書いています。

実際には、あなたには相手のとる戦略は分からず、相手にはあなたのとる戦略は分かりません。仮に、
- あなたは「相手が戦略 $q_2^{(0)}$ を取る」と予測し、
- 相手は「あなたが戦略 $q_1^{(0)}$ を取る」と予測した

としましょう。すると、両者ともに対戦相手の裏をかくように自分の戦略を決めるでしょう。すなわち、思考は次のように進みます。
- あなたは「相手が戦略 $q_2^{(0)}$ を取るのだから、自分は最適応答 $q_1^{(1)}\in B_1(q_2^{(0)})$ をとろう」と考えます。
- 相手は「あなたが戦略 $q_1^{(0)}$ を取るのだから、自分は最適応答 $q_2^{(1)}\in B_2(q_1^{(0)})$ をとろう」と考えます。

両者が十分に賢ければ、読み合いはここで止まりません。以上の流れを両者とも予測できるので、もう一段裏をかくことができます。
- あなたは「相手が戦略 $q_2^{(1)}$ を取るのだから、自分は最適応答 $q_1^{(2)}\in B_1(q_2^{(1)})$ をとろう」と考えます。
- 相手は「あなたが戦略 $q_1^{(1)}$ を取るのだから、自分は最適応答 $q_2^{(2)}\in B_2(q_1^{(1)})$ をとろう」と考えます。

このような読み合いは無限に続けることができますが、もしこれがある $q_1^*,q_2^*$ で停止した (自分の戦略を変える必要がなくなった) としたら、それは一体どういう状況でしょうか。
このとき、
- あなたの戦略は相手の戦略に対する最適応答になっている：$q_1^*\in B_1(q_2^*)$
- 相手の戦略はあなたの戦略に対する最適応答になっている：$q_2^*\in B_2(q_1^*)$

となるはずです。すなわち、この戦略の組 $(q_1^*,q_2^*)$ は「両者とも、自分の戦略を変えるだけでは(期待値の意味で)より大きな利得を得ることができない」という状況にあります。この性質をもつ戦略の組 $(q_1^*,q_2^*)$ は**Nash均衡**と呼ばれます。

Nash均衡の性質をもう少し詳しく見てみましょう。
$B_1,B_2$ の定義を思い出すと、$(q_1^*,q_2^*)$ がNash均衡であることは次のように言い換えられます。
\begin{align*}
&q_1^*\in B_1(q_2^*),\ q_2^*\in B_2(q_1^*)\iff F(q_1^*,q_2^*)=\max_{q_1\in Q}F(q_1,q_2^*)=\min_{q_2\in Q}F(q_1^*,q_2)
\end{align*}したがって、特に次の不等式が成り立ちます。
\begin{align}
\min_{q_2\in Q}\max_{q_1\in Q}F(q_1,q_2)
\le\max_{q_1\in Q}F(q_1,q_2^*)
=\min_{q_2\in Q}F(q_1^*,q_2)
\le\max_{q_1\in Q}\min_{q_2\in Q}F(q_1,q_2)
\tag{1}
\end{align}一方、任意の$q_1,q_2\in Q$に対して
\begin{align*}
\min_{q_2'\in Q}F(q_1,q_2')\le\max_{q_1'\in Q}F(q_1',q_2)
\end{align*}となることから逆の不等式
\begin{align*}
\max_{q_1\in Q}\min_{q_2\in Q}F(q_1,q_2)
\le\min_{q_2\in Q}\max_{q_1\in Q}F(q_1,q_2)
\end{align*}の成立も分かるので、$\textrm{(1)}$ の二つの不等号は実は等号になることがいえます。

以上により、Nash均衡 $(q_1^*,q_2^*)$ は次の性質をもつことがわかりました[^2]。
- $\displaystyle\min_{q_2\in Q}F(q_1^*,q_2)
=\max_{q_1\in Q}\min_{q_2\in Q}F(q_1,q_2).$
すなわち、相手があなたにとって最も都合が悪い ($F$ を最小化する) 戦略をとる場合に、あなたの利得を最大化するような戦略が $q_1^*$ である。
- $\displaystyle\max_{q_1\in Q}F(q_1,q_2^*)
=\min_{q_2\in Q}\max_{q_1\in Q}F(q_1,q_2).$
すなわち、あなたが相手にとって最も都合が悪い ($F$ を最大化する) 戦略をとる場合に、相手の利得を最大化する (あなたの利得を最小化する) ような戦略が $q_2^*$ である。
[^2]: ここではじゃんけんに限定して話をしていますが、一般の二人零和ゲームに対して同じことがいえます。

この意味で、Nash均衡に沿った戦略をとることは最善の選択です。

ところで、じゃんけんにはただ一つのNash均衡
\begin{align*}
q_1^*=q_2^*=\Bigl(\frac{1}{3},\frac{1}{3},\frac{1}{3}\Bigr)
\end{align*}が存在することが知られています (証明してみてください)。結局、等確率でランダムに手を選ぶのが一番丸いんですね。

## 変則じゃんけん
じゃんけんのルールを少し変えてみましょう。
前節の利得関数 $f$ は「勝つと $1$ 点が得られ、負けると $1$ 点を失う」という状況に相当します。
これを「チョキで勝つと $2$ 点が得られ、チョキで負けると $2$ 点を失う (それ以外は前節と同じ)」と変更するとどうなるでしょうか。

| あなた \ 相手 | グー | チョキ | パー |
|:-:|:-:|:-:|:-:|
| グー | $0$ | $2$ | $-1$ |
| チョキ | $-2$ | $0$ | $2$ |
| パー | $1$ | $-2$ | $0$ |

結果だけ述べると、この変則じゃんけんにはただ一つのNash均衡
\begin{align*}
q_1^*=q_2^*=\Bigl(\frac{2}{5},\frac{1}{5},\frac{2}{5}\Bigr)
\end{align*}が存在します。すなわち、グーとパーを $40$ %の確率で、チョキを $20$ %の確率で出すのが最善ということになります。

この事実に直感的な説明を与えることはできるでしょうか？
私はこの問いの答えを持っていないので、何か思いついた方は是非教えてください。

## 参考文献
[1] 岡田, ゲーム理論 第3版, 有斐閣, 2021.

この記事全体にわたって参考にしました。

[2] N. Brown, Equilibrium Finding for Large Adversarial Imperfect-Information Games, 2020.

5.2.1 節から、変則じゃんけんの話題を引用しました。