進化的安定戦略

同義語:進化的に安定な戦略evolutionarily stable strategyevolutionary stable strategy

概要

進化的安定戦略(evolutionarily stable strategy)とは、利得行列 $A$ の対称な 2 人ゲームの混合戦略 $p$ で、$p$ と異なるどの戦略 $q$ についても $q^{\mathsf T}Ap\le p^{\mathsf T}Ap$ であり、等号なら $q^{\mathsf T}Aq< p^{\mathsf T}Aq$ となるもので、全員が $p$ をとる集団に少数の $q$ が入っても、入った側の利得が小さくなる。この条件は、$p$ が近くのどの集団 $x$ に対しても $x$ 自身より多く得をすることと同値で、侵入を退ける割合は侵入者によらずにとれる。判定は最適反応の集合の上の 2 次形式の符号で行い、2 つの戦略のゲームは利得の 2 つの差の符号で分類される。台が入れ子の 2 つの進化的安定戦略はない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Nash均衡, ゲーム理論, 標準単体

進化的安定戦略(evolutionarily stable strategy)は、同じ種の個体どうしが出会ってゲームをする集団で、全員がとっている戦略に、ごく少数の別の戦略(突然変異)が入り込んでも、入り込んだ側の利得が元の側より小さくなって消えていく、という性質をもつ戦略である。Maynard Smith と Price が動物の争いの模型として導入した(MSP73)。
たとえば、資源をめぐって争う個体が「闘う(タカ)」か「退く(ハト)」を選ぶとする。全員がハトなら、タカが少し入ると資源を独り占めして増える。全員がタカなら、闘いの損失が大きいときにはハトが入り込んで増える。損失が十分大きければ、タカの割合が $v/(2C)$($v$ は資源の価値、$C$ は闘いの損失)の混合戦略だけが、どちらの侵入も退ける(ex-ess-hawk-dove)。
この記事は、利得行列 $A$ から進化的安定戦略を 判定し、求める ことを中心に、次のことを扱う。

  • 定義の 2 つの条件は、近くのどの集団に対しても利得で勝つこと(局所的な優越)と同値で、侵入を退ける割合の上限は侵入者によらずにとれる(thm-ess-local)。
  • 判定は、最適反応の集合の上で利得行列の 2 次形式が負であるかを見ればよい(prop-ess-criterion)。
  • 一方の台がもう一方の台を含む 2 つの進化的安定戦略はない。とくに進化的安定戦略は有限個である(thm-ess-support)。
  • $2\times2$ のゲームは利得の 2 つの差の符号で完全に分類できる(prop-ess-two-by-two)。
    進化的安定戦略は対称な Nash均衡 を強めた概念である。存在するとは限らない(ex-ess-rps)。

定義と使える条件

対称な 2 人ゲーム

$n\ge1$ とし、$A=(a_{ij})$ を実の $n\times n$ 行列とする。純粋戦略 $1,\dots,n$ をもつ 2 人のゲームで、参加者 1 が $i$、参加者 2 が $j$ を選ぶと、参加者 1 の利得が $a_{ij}$、参加者 2 の利得が $a_{ji}$ であるものを、利得行列 $A$ の 対称な 2 人ゲーム という。混合戦略は単体 $\Delta_n:=\{x\in\mathbb R^n\mid x_i\ge0,\ \sum_ix_i=1\}$ の点で表し、純粋戦略 $j$ は第 $j$ 成分だけが $1$ の単位ベクトル $e_j$ と同一視する。$q$ をとる個体が $x$ をとる相手から得る期待利得を $q^{\mathsf T}Ax$ と書く。$\operatorname{supp}x:=\{i\mid x_i>0\}$ を $x$ の 台 という。

$(p,p)$ が Nash 均衡であることは、すべての $q\in\Delta_n$ で $q^{\mathsf T}Ap\le p^{\mathsf T}Ap$ であることと同値である(参加者 2 の利得行列は $A^{\mathsf T}$ なので、2 人の条件は同じ式になる)。このとき $p$ を 対称な Nash 均衡 という。Nash均衡 の定理「対称な均衡」により、対称な Nash 均衡は必ずある。

進化的安定戦略

$p\in\Delta_n$ が 進化的安定戦略 であるとは、$p$ と異なるすべての $q\in\Delta_n$ について、次の 2 つが成り立つことをいう。

  1. (均衡の条件)$q^{\mathsf T}Ap\le p^{\mathsf T}Ap$。
  2. (安定の条件)$q^{\mathsf T}Ap=p^{\mathsf T}Ap$ ならば $q^{\mathsf T}Aq< p^{\mathsf T}Aq$。

条件 1 は $p$ が対称な Nash 均衡であることにほかならない。条件 2 は、$p$ に対して $p$ と同じだけ得をする $q$($p$ への 別の最適反応)について、$q$ どうしで出会ったときの利得が、$p$ が $q$ と出会ったときの利得より小さいことを求める。
定義の背後にある模型と、この記事の結果が使える条件は次のとおりである。
(i) 無限の集団と無作為な出会い:集団は十分大きく、個体は無作為に 2 体ずつ出会う。割合 $\varepsilon$ の個体が $q$、残りが $p$ をとる集団は、混合戦略 $w=\varepsilon q+(1-\varepsilon)p$ をとる 1 人の相手と同じに扱える。
(ii) 対称性:2 体の役割に区別がなく、同じ利得行列 $A$ を使う。役割の区別のあるゲーム(2 つの利得行列が転置の関係にないゲーム)は、この記事では扱わない。
(iii) 突然変異は混合戦略:侵入者 $q$ には、純粋戦略だけでなく混合戦略も許す。
(iii) について、KP17 Definition 7.1.1(p. 139)は侵入者 $q$ を純粋戦略に限って定義している。$q$ を純粋戦略に限った条件は一般に弱く、混合戦略の侵入者を退けられない戦略を含んでしまう(ex-ess-pure-mutant)。

公式の表

問い答え条件根拠
定義の言い換え近くのどの $x\ne p$ にも $p^{\mathsf T}Ax>x^{\mathsf T}Ax$—thm-ess-local
侵入を退ける割合侵入者 $q$ によらない $\varepsilon_0>0$ がある—thm-ess-local
判定別の最適反応の集合 $J$ の上で $(q-p)^{\mathsf T}A(q-p)< 0$$p$ は対称な Nash 均衡prop-ess-criterion
内部の点 $p$$A$ が $\{v\mid\sum v_i=0\}$ の上で負定値$Ap$ の成分がすべて等しいprop-ess-criterion
狭義の Nash 均衡進化的安定戦略である—prop-ess-criterion
台の包含台が入れ子の進化的安定戦略の組はない—thm-ess-support
$2\times2$$\alpha:=a_{11}-a_{21}$、$\beta:=a_{22}-a_{12}$ の符号で決まる$\alpha\beta\ne0$prop-ess-two-by-two
列に定数を足す進化的安定戦略は変わらない—lem-ess-column

主定理と証明

侵入を退ける割合と局所的な優越

割合 $\varepsilon$ の $q$ が入った集団 $w=\varepsilon q+(1-\varepsilon)p$ の中で、$p$ の利得から $q$ の利得を引いた差を
$$ f(q,\varepsilon):=(p-q)^{\mathsf T}A\bigl(\varepsilon q+(1-\varepsilon)p\bigr)=(1-\varepsilon)\,a(q)+\varepsilon\,b(q) $$
とおく。ここで $a(q):=(p-q)^{\mathsf T}Ap$、$b(q):=(p-q)^{\mathsf T}Aq$ である。定義の条件 1 は $a(q)\ge0$、条件 2 は「$a(q)=0$ なら $b(q)>0$」である。よって $p$ が進化的安定戦略であることは、各 $q\ne p$ について、十分小さいすべての $\varepsilon>0$ で $f(q,\varepsilon)>0$ となることと同値である($\varepsilon\to0$ で $f\to a(q)$ で、$a(q)=0$ なら $f=\varepsilon b(q)$)。
次の定理は、この「十分小さい」の範囲が $q$ によらずにとれることを示す。

局所的な優越と一様な侵入障壁

$p\in\Delta_n$ について、次の 3 つは同値である。

  1. $p$ は進化的安定戦略である。
  2. $\varepsilon_0\in(0,1]$ があって、$p$ と異なるすべての $q\in\Delta_n$ とすべての $\varepsilon\in(0,\varepsilon_0)$ で $f(q,\varepsilon)>0$ である。
  3. $p$ の近傍 $U$ があって、$p$ と異なるすべての $x\in U\cap\Delta_n$ で $p^{\mathsf T}Ax>x^{\mathsf T}Ax$ である。
台の外れた面の上で一様にし、半直線で全体に広げる

$C:=\{q\in\Delta_n\mid\text{ある }i\in\operatorname{supp}p\text{ で }q_i=0\}$ とおく。$C$ はコンパクトで、$p\notin C$ である。
半直線の補題:$x\in\Delta_n$、$x\ne p$ とする。$\sum_i(x_i-p_i)=0$ なので $x_i< p_i$ となる $i$ があり、そのような $i$ は $\operatorname{supp}p$ に入る。$t^\ast:=\min\{p_i/(p_i-x_i)\mid x_i< p_i\}\ge1$ とおき、$x':=p+t^\ast(x-p)$ とすると、$x'\in\Delta_n$ で、最小を与える $i$ で $x'_i=0$ なので $x'\in C$ である。$s:=1/t^\ast\in(0,1]$ について $x=sx'+(1-s)p$ であり、$s=\lvert x-p\rvert/\lvert x'-p\rvert\le\lvert x-p\rvert/d$($d:=\min_{q\in C}\lvert q-p\rvert>0$)である。
1 ⇒ $C$ の上での一様性:$\varepsilon_1>0$ があって、すべての $q\in C$、$\varepsilon\in(0,\varepsilon_1)$ で $f(q,\varepsilon)>0$ となることを示す。そうでないとすると、$q_k\in C$ と $\varepsilon_k\to0$($0< \varepsilon_k< 1$)で $f(q_k,\varepsilon_k)\le0$ となるものがある。部分列をとって $q_k\to q\in C$ としてよい。条件 1 から $a(q_k)\ge0$ なので
$$ 0\le(1-\varepsilon_k)\,a(q_k)\le-\varepsilon_k\,b(q_k) $$
である。$k\to\infty$ とすると左の不等式と右辺から $a(q)=0$ を得る。また $b(q_k)\le0$ なので $b(q)\le0$ である。$q\in C$ なので $q\ne p$ で、条件 2 に反する。
$C$ の上での一様性 ⇒ 2:$q\ne p$ に半直線の補題を使い、$q=sq'+(1-s)p$($q'\in C$、$0< s\le1$)と書く。$w=\varepsilon q+(1-\varepsilon)p=\varepsilon sq'+(1-\varepsilon s)p$ で、$p-q=s(p-q')$ なので
$$ f(q,\varepsilon)=s\,(p-q')^{\mathsf T}Aw=s\,f(q',\varepsilon s) $$
である。$\varepsilon< \varepsilon_1$ なら $\varepsilon s< \varepsilon_1$ なので $f(q,\varepsilon)>0$ である。$\varepsilon_0:=\min(\varepsilon_1,1)$ とすればよい。
$C$ の上での一様性 ⇒ 3:$U:=\{x\mid\lvert x-p\rvert< \varepsilon_1d\}$ とする。$x\in U\cap\Delta_n$、$x\ne p$ を $x=sx'+(1-s)p$ と書くと $s\le\lvert x-p\rvert/d< \varepsilon_1$ で、$p-x=s(p-x')$ から
$$ p^{\mathsf T}Ax-x^{\mathsf T}Ax=(p-x)^{\mathsf T}Ax=s\,f(x',s)>0 $$
である。
2 ⇒ 1、3 ⇒ 1:$q\ne p$ をとる。2 なら小さい $\varepsilon>0$ で $f(q,\varepsilon)>0$ である。3 なら、小さい $\varepsilon>0$ で $x=\varepsilon q+(1-\varepsilon)p\in U$ で、上と同じ計算で $p^{\mathsf T}Ax-x^{\mathsf T}Ax=\varepsilon f(q,\varepsilon)>0$ である。どちらでも、十分小さいすべての $\varepsilon$ で $f(q,\varepsilon)>0$ となり、冒頭の言い換えにより $p$ は進化的安定戦略である。$\square$

2 の $\varepsilon_0$ を 一様な侵入障壁 という。3 は、$p$ が近くのどの集団 $x$ と出会っても、$x$ 自身より多く得をすることを述べている。3 は、集団の割合の時間変化を表す方程式(レプリケーター方程式)で $p$ が漸近安定になることの鍵になる。

判定法

列に定数を足す

$c\in\mathbb R^n$ とし、$A$ の第 $j$ 列に $c_j$ を足した行列を $A'$ とする。また $\lambda>0$ とする。$A$、$A'$、$\lambda A$ の対称な 2 人ゲームの進化的安定戦略は同じで、対称な Nash 均衡も同じである。

要点:同じ相手に対する 2 つの戦略の利得の差は変わらない。

詳しい証明を開く

$\mathbf 1$ を成分がすべて $1$ のベクトルとすると $A'=A+\mathbf 1c^{\mathsf T}$ で、$q\in\Delta_n$ なら $q^{\mathsf T}\mathbf 1=1$ なので $q^{\mathsf T}A'x=q^{\mathsf T}Ax+c^{\mathsf T}x$ である。定義の 2 つの条件は、どちらも同じ相手 $x$(条件 1 では $p$、条件 2 では $q$)に対する 2 つの戦略の利得の比較なので、$c^{\mathsf T}x$ が両辺に加わっても、正の数 $\lambda$ を掛けても変わらない。$\square$

2 次形式による判定

$p$ を対称な Nash 均衡とし、$J:=\{j\mid(Ap)_j=p^{\mathsf T}Ap\}$(純粋戦略の最適反応の集合)とおく。$J\supseteq\operatorname{supp}p$ である。

  1. $p$ が進化的安定戦略であることは、$\operatorname{supp}q\subseteq J$ を満たす $p$ と異なるすべての $q\in\Delta_n$ で $(q-p)^{\mathsf T}A(q-p)< 0$ となることと同値である。
  2. $J=\operatorname{supp}p$ なら、1 の条件は、$\operatorname{supp}v\subseteq J$、$\sum_iv_i=0$ を満たす $0$ でないすべての $v\in\mathbb R^n$ で $v^{\mathsf T}Av< 0$ となることと同値である。
  3. とくに、狭義の Nash 均衡($J$ が 1 点)は進化的安定戦略であり、内部の点 $p$($\operatorname{supp}p=\{1,\dots,n\}$)が進化的安定戦略であることは、$A$ が部分空間 $T:=\{v\mid\sum_iv_i=0\}$ の上で負定値であることと同値である。
別の最適反応だけを調べればよい

$J\supseteq\operatorname{supp}p$ は Nash均衡 の命題「台による判定」による。$c:=p^{\mathsf T}Ap$ とおく。
1:$a(q)=c-q^{\mathsf T}Ap=\sum_jq_j\bigl(c-(Ap)_j\bigr)$ で、各項は $0$ 以上である。$\operatorname{supp}q\not\subseteq J$ なら $a(q)>0$ で、$q$ について定義の条件は成り立つ。$\operatorname{supp}q\subseteq J$ なら $a(q)=0$ で
$$ b(q)=(p-q)^{\mathsf T}A(q-p)+(p-q)^{\mathsf T}Ap=-(q-p)^{\mathsf T}A(q-p)+a(q)=-(q-p)^{\mathsf T}A(q-p) $$
なので、条件 2 は $(q-p)^{\mathsf T}A(q-p)< 0$ と同じである。
2:$\operatorname{supp}q\subseteq J$ なら $v:=q-p$ は 2 の形である。逆に 2 の形の $v\ne0$ について、$J$ の上で $p_i>0$ なので、小さい $t>0$ で $q:=p+tv\in\Delta_n$、$\operatorname{supp}q\subseteq J$ となり、$(q-p)^{\mathsf T}A(q-p)=t^2v^{\mathsf T}Av$ である。
3:$J=\{k\}$ なら $\operatorname{supp}p=\{k\}$ で、2 の $v$ は $0$ しかないので条件は空である。内部の点では $J=\operatorname{supp}p$ が全体で、2 の部分空間は $T$ である。$\square$

$J\ne\operatorname{supp}p$ のとき(台の外にも最適反応があるとき)は、1 の条件は部分空間ではなく錐 $\{t(q-p)\mid t>0,\ \operatorname{supp}q\subseteq J\}$ の上で 2 次形式が負であるという条件になり、2 の形には直せない(ex-ess-boundary)。

台と個数

台の包含

$p$ を進化的安定戦略、$q$ を対称な Nash 均衡とし、$\operatorname{supp}q\subseteq\operatorname{supp}p$ とする。このとき $q=p$ である。

2 つの均衡の条件をぶつける

$q\ne p$ とする。Nash均衡 の命題「台による判定」により、$i\in\operatorname{supp}p$ なら $(Ap)_i=p^{\mathsf T}Ap$ なので、$q^{\mathsf T}Ap=\sum_{i\in\operatorname{supp}q}q_i(Ap)_i=p^{\mathsf T}Ap$ である。$p$ の条件 2 から $q^{\mathsf T}Aq< p^{\mathsf T}Aq$ である。一方、$q$ は対称な Nash 均衡なので $p^{\mathsf T}Aq\le q^{\mathsf T}Aq$ であり、矛盾する。$\square$

進化的安定戦略の個数
  1. 異なる 2 つの進化的安定戦略 $p,p'$ について、一方の台が他方の台を含むことはない。とくに、同じ台をもつ進化的安定戦略は高々 1 つで、進化的安定戦略は高々 $2^n-1$ 個である。
  2. 内部の進化的安定戦略 $p$ があれば、$p$ は唯一の対称な Nash 均衡で、唯一の進化的安定戦略である。

進化的安定戦略は対称な Nash 均衡なので、1 は thm-ess-support を $p,p'$ に両方向から使えばよい。2 は、どの対称な Nash 均衡 $q$ も $\operatorname{supp}q\subseteq\{1,\dots,n\}=\operatorname{supp}p$ を満たすことから従う。$\square$

2 つの戦略の場合

$2\times2$ のゲームの分類

$n=2$ とし、$\alpha:=a_{11}-a_{21}$、$\beta:=a_{22}-a_{12}$、$\alpha\beta\ne0$ とする。$p^\ast:=\bigl(\frac\beta{\alpha+\beta},\frac\alpha{\alpha+\beta}\bigr)$ とおく。

符号対称な Nash 均衡進化的安定戦略
$\alpha>0$、$\beta< 0$$e_1$$e_1$
$\alpha< 0$、$\beta>0$$e_2$$e_2$
$\alpha>0$、$\beta>0$(調整ゲーム)$e_1$、$e_2$、$p^\ast$$e_1$、$e_2$
$\alpha< 0$、$\beta< 0$(反調整ゲーム)$p^\ast$$p^\ast$
対角行列に直す

要点:列に定数を足して $A'=\operatorname{diag}(\alpha,\beta)$ にすると、純粋戦略は $\alpha$ や $\beta$ の符号で狭義の均衡かどうかが決まり、内部の均衡は $T$ の上の 2 次形式 $\alpha+\beta$ で決まる。

詳しい証明を開く

第 1 列から $a_{21}$、第 2 列から $a_{12}$ を引くと $A'=\operatorname{diag}(\alpha,\beta)$ になり、lem-ess-column により $A'$ で調べてよい。$q^{\mathsf T}A'x=\alpha q_1x_1+\beta q_2x_2$ である。

$e_1$ について、$(A'e_1)_1=\alpha$、$(A'e_1)_2=0$ なので、$\alpha>0$ なら $e_1$ は狭義の Nash 均衡で、prop-ess-criterion の 3 により進化的安定戦略である。$\alpha< 0$ なら $e_2$ のほうが $e_1$ に対して得をするので、$e_1$ は Nash 均衡でない。$e_2$ も $\beta$ について同じである。

内部の点 $p$ が対称な Nash 均衡であることは、Nash均衡 の命題「台による判定」により $(A'p)_1=(A'p)_2$、すなわち $\alpha p_1=\beta p_2$ と同値で、$p_1+p_2=1$ と合わせて $p=p^\ast$ である。$p^\ast$ が内部にあることは $\alpha\beta>0$ と同値である。$T$ は $v=(1,-1)$ で張られ、$v^{\mathsf T}A'v=\alpha+\beta$ なので、prop-ess-criterion の 3 により、$p^\ast$ が進化的安定戦略であることは $\alpha+\beta< 0$、すなわち($\alpha\beta>0$ のもとで)$\alpha< 0$ かつ $\beta< 0$ と同値である。表の 4 行はこれらをまとめたものである。$\square$

計算の手順

利得行列 $A$ の進化的安定戦略をすべて求める手順は次のとおりである。

  1. 列をそろえる(任意):lem-ess-column により、各列から定数を引いて対角成分を $0$ にするなど、計算しやすい形にしてよい。
  2. 対称な Nash 均衡をすべて求める:空でない $I\subseteq\{1,\dots,n\}$ ごとに、$i\in I$ で $(Ap)_i=c$、$\sum_{i\in I}p_i=1$、$I$ の外で $p_i=0$ を解く。$I$ の上で $p_i>0$ で、$I$ の外の $j$ で $(Ap)_j\le c$ となる解だけを残す(Nash均衡 の節「計算の手順」の対称な場合)。
  3. 最適反応の集合 $J$ を求める:残った各 $p$ について $J=\{j\mid(Ap)_j=p^{\mathsf T}Ap\}$ を計算する。
  4. 2 次形式を調べる:次の表で判定する(prop-ess-criterion)。
  5. 台で絞る:進化的安定戦略 $p$ が 1 つ見つかったら、台が $\operatorname{supp}p$ に含まれるほかの均衡と、台が $\operatorname{supp}p$ を含むほかの均衡は、進化的安定戦略でない(thm-ess-support)。
    場合やること結果
    $J$ が 1 点なし進化的安定戦略(狭義の Nash 均衡)
    $J=\operatorname{supp}p$$j_0\in J$ を 1 つ選び、$v_j:=e_j-e_{j_0}$($j\in J\setminus\{j_0\}$)について行列 $M:=\bigl(v_j^{\mathsf T}\tfrac{A+A^{\mathsf T}}2v_k\bigr)$ を作る$M$ が負定値なら進化的安定戦略、そうでなければ違う
    $J\supsetneq\operatorname{supp}p$錐 $\{q-p\mid\operatorname{supp}q\subseteq J\}$ の上で $(q-p)^{\mathsf T}A(q-p)$ の符号を調べるすべて負なら進化的安定戦略
    $M$ の負定値性は、固有値がすべて負であることか、首座小行列式の符号が交互に負・正であること(正定値行列)で確かめる。$v^{\mathsf T}Av$ は $A$ の対称部分 $\frac12(A+A^{\mathsf T})$ だけで決まるので、$M$ は対称部分から作る。

例題

タカ–ハトゲーム

価値 $v>0$ の資源を 2 体が争う。2 体ともタカなら等しい確率で一方が資源を得て、どちらも損失 $C>0$ を負う。タカとハトなら、タカが資源を得る。2 体ともハトなら資源を分ける。戦略の順をタカ・ハトとすると
$$ A=\begin{pmatrix}\frac v2-C&v\\0&\frac v2\end{pmatrix} $$
である(KP17 §7.1.1、p. 137)。
使う公式:prop-ess-two-by-two。
答え:$\alpha=\frac v2-C$、$\beta=-\frac v2< 0$ である。$C>\frac v2$ なら、タカの割合 $\frac v{2C}$ の混合戦略だけが進化的安定戦略である。$C< \frac v2$ なら、全員がタカの $e_1$ だけが進化的安定戦略である。$v=2$、$C=2$ では $p^\ast=(\frac12,\frac12)$ で、$x=(0.6,0.4)$ について $p^{\ast\mathsf T}Ax-x^{\mathsf T}Ax=0.02$ である。

途中の計算を開く

$C>\frac v2$ なら $\alpha,\beta< 0$ で、$p^\ast_1=\frac\beta{\alpha+\beta}=\frac{-v/2}{-C}=\frac v{2C}$ である。$C< \frac v2$ なら $\alpha>0>\beta$ である。$v=C=2$ では $A=\begin{pmatrix}-1&2\\0&1\end{pmatrix}$ で、$p^\ast$ は内部の Nash 均衡なので $(p^\ast-x)^{\mathsf T}Ap^\ast=0$ であり、$p^{\ast\mathsf T}Ax-x^{\mathsf T}Ax=-(x-p^\ast)^{\mathsf T}A(x-p^\ast)$ となる。$x-p^\ast=(0.1,-0.1)$ について $(x-p^\ast)^{\mathsf T}A(x-p^\ast)=0.01\cdot(-1)-0.01\cdot(2+0)+0.01\cdot1=-0.02$ である。

KP17 Example 7.1.2(p. 139)は、$C>\frac v2$ のときの混合戦略を純粋戦略の侵入者について確かめている。

じゃんけん

勝てば $a>0$、負ければ $-b$($b>0$)、あいこは $0$ のじゃんけんの利得行列は、グー・パー・チョキの順で
$$ A=\begin{pmatrix}0&-b&a\\a&0&-b\\-b&a&0\end{pmatrix} $$
である。
使う公式:prop-ess-criterion の 3。
答え:対称な Nash 均衡は $u:=(\frac13,\frac13,\frac13)$ だけである。$u$ が進化的安定戦略であることは $a>b$ と同値である。とくに通常のじゃんけん($a=b=1$)には進化的安定戦略がない。$a=2$、$b=1$ では、$q=e_1$ について $(q-u)^{\mathsf T}A(q-u)=-\frac13$ である。

途中の計算を開く

$\sigma(v):=v_1v_2+v_2v_3+v_3v_1$ とおくと $v^{\mathsf T}Av=(a-b)\sigma(v)$ で、$v\in T$ では $\sigma(v)=\frac12\bigl((v_1+v_2+v_3)^2-\lvert v\rvert^2\bigr)=-\frac12\lvert v\rvert^2$ なので $v^{\mathsf T}Av=-\frac{a-b}2\lvert v\rvert^2$ である。$Au=\frac{a-b}3\mathbf 1$ なので $u$ は内部の Nash 均衡で、prop-ess-criterion の 3 から $u$ が進化的安定戦略であることは $a>b$ と同値である。

ほかに対称な Nash 均衡がないこと:純粋戦略 $e_i$ には、それに勝つ戦略が利得 $a>0$ を得るので Nash 均衡でない。台が 2 点、たとえば $p=(s,1-s,0)$($0< s< 1$)なら $(Ap)_1=-b(1-s)< 0< as=(Ap)_2$ で、台の上の利得が等しくない。ほかの 2 点の台も巡回の対称性で同じである。内部の均衡は $Ap=c\mathbf 1$ を満たす。$A$ は巡回行列で、固有値は $\lambda_k=-b\omega^k+a\omega^{2k}$($\omega=e^{2\pi i/3}$、$k=0,1,2$)、$\lambda_0=a-b$ の固有ベクトルは $\mathbf 1$ である。$k=1,2$ では $\lvert\lambda_k\rvert=\lvert a\omega^k-b\rvert>0$($a\omega^k$ は実数でない)なので、$A$ の核は $\mathbf 1$ の張る空間に含まれる。$a\ne b$ なら $A$ は正則で、$A\mathbf 1=(a-b)\mathbf 1$ から $p=\frac c{a-b}\mathbf 1$、すなわち $p=u$ である。$a=b$ なら $A$ は交代行列で $3c=\mathbf 1^{\mathsf T}Ap=-p^{\mathsf T}A\mathbf 1=0$ となり、$Ap=0$ から $p$ は $\mathbf 1$ の定数倍で $p=u$ である。$a=2$、$b=1$、$q=e_1$ では $\lvert e_1-u\rvert^2=\frac23$ なので $(q-u)^{\mathsf T}A(q-u)=-\frac12\cdot\frac23=-\frac13$ である。

$a=b=1$ の場合は KP17 Example 7.1.3(p. 139)にある。$u$ は Nash 均衡だが、どの $q$ も $u$ に対して $u$ と同じだけ得をし、$q$ どうしでも $u$ と同じだけ得をする($q^{\mathsf T}Aq=0=u^{\mathsf T}Aq$)ので、条件 2 を満たさない。

調整ゲーム

$A=\begin{pmatrix}10&0\\0&5\end{pmatrix}$ とする(KP17 Example 7.1.4、p. 141)。
使う公式:prop-ess-two-by-two、thm-ess-local。
答え:$\alpha=10$、$\beta=5$ なので、進化的安定戦略は $e_1$ と $e_2$ で、混合の均衡 $p^\ast=(\frac13,\frac23)$ は進化的安定戦略でない。$e_2$ に $e_1$ が割合 $\varepsilon$ で入るとき $f(e_1,\varepsilon)=5-15\varepsilon$ で、$e_2$ が侵入を退けるのは $\varepsilon< \frac13$ のときである。

途中の計算を開く

$p=e_2$、$q=e_1$ について $a(q)=(e_2-e_1)^{\mathsf T}Ae_2=5-0=5$、$b(q)=(e_2-e_1)^{\mathsf T}Ae_1=0-10=-10$ なので $f=5(1-\varepsilon)-10\varepsilon=5-15\varepsilon$ である。

純粋戦略の侵入者だけでは足りない例

$$ A=\begin{pmatrix}-8&4&4\\4&-1&-3\\4&-3&-1\end{pmatrix} $$
とし、$u=(\frac13,\frac13,\frac13)$ とする。
使う公式:prop-ess-criterion の 3。
答え:$u$ は対称な Nash 均衡で、どの純粋戦略 $e_i$ も定義の条件 2 を満たす。しかし $q=(\frac13,\frac23,0)$ について $q^{\mathsf T}Aq=\frac49>0=u^{\mathsf T}Aq$ で、$u$ は進化的安定戦略でない。

途中の計算を開く

$A$ の各行の和は $0$ なので $Au=0$ で、$u$ は内部の Nash 均衡、$A$ は対称なので $u^{\mathsf T}Ax=0$ である。$e_i^{\mathsf T}Ae_i=a_{ii}< 0=u^{\mathsf T}Ae_i$ なので、純粋戦略は条件 2 を満たす。$q^{\mathsf T}Aq=\frac19(-8-4+2\cdot4\cdot2)=\frac49$ である。$T$ の向き $v=(0,1,-1)$ で $v^{\mathsf T}Av=-1-1+6=4>0$ なので、$A$ は $T$ の上で負定値でない。

$T$ の 2 次形式は、3 つの向き $e_i-u$ では負でも、その間の向きで正になりうる。純粋戦略の侵入者を調べるだけでは、thm-ess-local の 3 の局所的な優越は保証されない。

台の外に最適反応がある例

$$ A=\begin{pmatrix}0&0&0\\0&-2&-3\\0&-3&-2\end{pmatrix},\qquad p=e_1 $$
とする。
使う公式:prop-ess-criterion の 1。
答え:$Ae_1=0$ なので $J=\{1,2,3\}\ne\operatorname{supp}p$ である。$p$ は狭義の Nash 均衡ではないが進化的安定戦略である。一方、$A$ は $\{v\mid\sum_iv_i=0\}$ の上で負定値でない。

途中の計算を開く

$q\in\Delta_3$ について $q-e_1=(-(s+t),s,t)$($s=q_2\ge0$、$t=q_3\ge0$)で、$A$ の第 1 行と第 1 列は $0$ なので $(q-e_1)^{\mathsf T}A(q-e_1)=-2s^2-6st-2t^2$ である。$q\ne e_1$ なら $s+t>0$ で、これは負である。一方 $v=(0,1,-1)$ では $v^{\mathsf T}Av=-2-2+6=2>0$ である。

使える条件と反例

外す条件反例成り立たなくなること
定義の条件 2ex-ess-rps($a=b$)局所的な優越(thm-ess-local の 3):すべての $x$ で $u^{\mathsf T}Ax=x^{\mathsf T}Ax=0$
侵入者に混合戦略を許すことex-ess-pure-mutant局所的な優越:$x=(1-\varepsilon)u+\varepsilon q$ で $u^{\mathsf T}Ax< x^{\mathsf T}Ax$
prop-ess-criterion の 2 の $J=\operatorname{supp}p$ex-ess-boundary進化的安定戦略なら部分空間の上で負定値であること
prop-ess-two-by-two の $\alpha\beta\ne0$$A=0$($\alpha=\beta=0$)2 つの戦略のゲームに進化的安定戦略があること
戦略が 2 つであることex-ess-rps($a\le b$)進化的安定戦略が存在すること

$A=0$ では、どの $p,q$ についても $q^{\mathsf T}Ap=p^{\mathsf T}Ap=0$、$q^{\mathsf T}Aq=p^{\mathsf T}Aq=0$ なので、すべての $p$ が対称な Nash 均衡で、条件 2 はどの $p$ でも成り立たない。$\alpha\beta\ne0$ の 4 つの場合には、prop-ess-two-by-two の表のどの行にも進化的安定戦略がある。

よくある誤り

誤り正しくはなぜ
対称な Nash 均衡は進化的安定戦略である条件 2 を別に確かめるex-ess-rps、ex-ess-coordination の $p^\ast$
純粋戦略の侵入者だけを調べればよい混合戦略の侵入者も調べるex-ess-pure-mutant
進化的安定戦略は必ずある2 つの戦略で $\alpha\beta\ne0$ ならあるが、一般にはないex-ess-rps
境界の点でも部分空間 $T$ の上の負定値性で判定する$J$ の上の錐で調べるex-ess-boundary
侵入を退ける割合は侵入者しだいでいくらでも小さくなる侵入者によらない下限 $\varepsilon_0>0$ があるthm-ess-local の 2

補足

集団の時間変化との関係

戦略 $i$ の割合 $x_i$ が、平均の利得 $x^{\mathsf T}Ax$ との差 $(Ax)_i-x^{\mathsf T}Ax$ に比例して増える、という方程式(レプリケーター方程式、複製子方程式ともいう)では、進化的安定戦略は漸近安定な平衡点である。証明は、$\sum_{i\in\operatorname{supp}p}p_i\log(p_i/x_i)$ が解に沿って減ることを thm-ess-local の 3 から導くものである。進化的安定戦略とこの方程式の関係は Taylor と Jonker(TJ78)、Hofbauer・Schuster・Sigmund(HSS79)が論じた。2 つの理論を並べて扱う教科書に HS98 がある。

定義の流儀

この記事の定義は、侵入者 $q$ を混合戦略全体にとる。KP17 Definition 7.1.1(p. 139)は侵入者を純粋戦略に限っている。両者は狭義の Nash 均衡では一致するが、一般には異なる(ex-ess-pure-mutant)。thm-ess-local と thm-ess-support は、この記事の定義について成り立つ。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する