ゼロ行列式戦略(Zero-determinant strategies)のまとめ

一ノ瀬元喜,間宮安曇,宮川大樹,岩倉謙心

はじめに

ゼロ行列式戦略(Zero-determinant strategies)は,PressとDyson [1] によって2012年に発見されたゲーム理論の繰り返しゲームにおける新しいクラスの戦略です.文献 [1] が契機となって,海外ではその発展が意欲的に研究されていますが,日本での認知度はそれほどでもないように思います.その理由の1つに「ゼロ行列式戦略とは何か」というところを理解するまでのハードルが少々高いということがあるのではないかと思いました.我々はゼロ行列式戦略について,これまでにいくつかの研究 [2-4] を行ってきましたので,興味のある日本人研究者にこの分野に参入してきてもらいたい(あわよくば我々と共同研究をやってほしい)という願いを込めて,我々が現時点までに理解して持っている情報をここで整理してお伝えできればと思います.知っている情報を全てさらけ出して惜しげもなく紹介します!

 

ゼロ行列式戦略(Zero-determinant strategies)とは何か

ゼロ行列式戦略(ZD戦略)とは,繰り返しゲームにおいて,相手がどのような戦略をとったとしても,相手に線形の利得関係を強いることができる戦略です.

以下の図は,その一例を示しています.これは,プレイヤーXとプレイヤーYの2人のプレイヤーが囚人のジレンマゲームを無限回繰り返したときの1回のゲーム(ラウンド)あたりの各プレイヤーの期待利得を示しています.注:「無限回ゲームを繰り返したときの1回のゲーム(ラウンド)あたりの期待利得」というのもポイントです.ラウンドごとの利得はばらつきます.

どちらの図でもプレイヤーXがZD戦略をとっています.左の図では横軸がプレイヤーXの利得の期待値で,右の図では縦軸がプレイヤーXの利得の期待値です.左の図のZD戦略は,Equalizerと呼ばれているZDの特殊ケースの戦略であり,右の図のZD戦略はExtortionerと呼ばれている別のZDの特殊ケースの戦略です [1] .ZD戦略について,図では,それぞれ1つのEqualizer戦略と1つのExtortioner戦略に固定していますが,プレイヤーYについては,ランダムに1,000戦略生成しています.1本の線のように見えますが,実際にはこれは黒い点が1,000個打たれています.数値的にですが,ZD戦略は相手(プレイヤーY)がどんな戦略(ここではランダムに作った)をとっても相手に直線の利得関係を強いていることが分かります(解析的なZD戦略の導出方法は下のZD戦略の名前の由来に書いています).

 

ZD戦略ではないとどうなるか?

ZD戦略ではないとどうなるでしょうか? 下の図はよく知られたWin-Stay-Lose-Shift(WSLS)(Pavlov戦略とも呼ばれます)戦略です.この図では縦軸の方がWSLS戦略の期待値で横軸が相手の利得の期待値です.相手の戦略はここでも1,000戦略ランダムに生成していて,WSLS戦略と相手の1つの戦略の利得の期待値の組が1つの黒い点で表されています.図を見ればわかるように,一般的には,WSLS戦略はZD戦略ではないです(相手に直線の利得関係を強いていない).

 

EqualizerとExtortioner戦略

「ZD戦略が相手に直線の利得関係を強いるのは分かった,だから何だ」と思われる方もいるでしょう.ここで,その疑問にお答えします.上でZD戦略の特殊ケースとしてEqualizer戦略とExtortioner戦略というのが出てきました.図を見ると,これらは,直線関係に加えて,相手に特別な関係を強いていることが分かります.

まずEqualizerの方から見ていきましょう.下図に再掲しました.図を見ると水平線になっていることが分かります.これが意味することはEqualizerは相手がどんな戦略をとっても相手の得点をある固定した点数にさせることができるということです.正確に言うと,ここでは繰り返しゲームの利得ベクトルが(T, R, P, S)=(1.5, 1, 0, -0.5)となっているとき,記憶1戦略p=(2/3, 1/3, 2/3, 1/3)で表されるEqualizer戦略は相手がどんな戦略をとっても相手の利得の期待値s_Yを0.5に固定していることが分かります.Equalizer戦略は相手の期待利得をP以上R以下のどんな値にでも固定できることが知られています.その一方で,Equalizer戦略の方は,水平線が横に広がっていることからもわかるように,相手の戦略に依存して様々な利得の期待値になることが分かります.つまり,Equalizer戦略は相手の利得の期待値をコントロールできます.

 

次にExtortioner戦略について見ていきます.下に図を再掲します.Extortionerの定義は,「(P, P)を始点として傾きが1より大きいZD戦略」です.(P, P)が始点で傾きが1より大きいが意味することは? これが意味するのは,相手がどんな戦略をとっても相手より必ず得点が高いということです.ALLDなどが相手の場合,(P, P)で引き分けになるので,Extortionerはどんな相手にも負けないがより正確ですが.でもその引き分けになる以外の相手には,どんな相手にでも勝ちます(Extortioner vs. Extortionerでは引き分けです).つまり,Extortionerは繰り返しゲームにおいて負けない戦略です.下の図では,ゲームの利得ベクトルが(T, R, P, S)=(1.5, 1, 0, -0.5)において,p=(0.9, 0.65, 0.25, 0)というExtortioner戦略の一例を示しています.この時,直線の傾きは2になります.ちなみに,直線の傾きが2より小さいものや2よりも大きいものも作れ,無限のExtortioner戦略が考えられます.

Extortionerにはもう1つ,重要な性質があります.図をもう一度よく見てください.青点と赤点があります.青点は相手がALLCの時の場合,赤点は相手がALLDの場合です.赤から青になるにしたがって,相手は得点が上がるように見えます.相手が常に自分の利得の期待値を大きくしたい,と考えることができる賢いプレイヤーだとしましょう.すると,Extortionerに相対している相手は,自分の戦略を協力的な方向,そしてやがてはALLCにもっていかないとだめなのです.なぜなら,それが相手にとって,自分の利得の期待値を上げる唯一の手段だから.というわけで,Extortionerは相手を協力に向かわせることができる,という別の強力な性質を持っています.

 

ZD戦略の名前の由来

ZD戦略とは何かが少しは伝わったでしょうか.ところで,ゼロ行列式戦略の「ゼロ行列式」ってなんだろうか? と思われた方もいるでしょう.これは,正確には,「行列式を0にする」という意味です.そう,大学の数学で習うあの線形代数と大きな関連があります.数学的な詳細は以下の添付(ZDの導出)に書いてありますが,ここでは大筋をつかんでもらいたいと思います.まずPressとDysonが発見した最初に重要なことは,プレイヤーXとプレイヤーYの2人がゲームを無限回繰り返したときの1回のゲーム(ラウンド)あたりの利得の期待値が行列式の形で計算できる,ということです.以下の「ZDの導出」リンクの式9がプレイヤーXの利得の期待値(s_X),式10がプレイヤーYの利得の期待値(s_Y)になり,Dで表されているのが行列式です.Dの具体的な形は式7です.式7までたどり着くのは,少し線形代数の知識がいりますが,それはさておき,最初の大事なポイントは利得の期待値が行列式で表せるということです.

次に大事な部分を説明します.2人のプレイヤーの利得の期待値(s_Xとs_Y)が行列式で表せたので,それを線形結合したもの(式11の左辺)も行列式の形で表せます(式11の右辺).とすると,式11の右辺の行列式が0となれば,左辺=0となり,2人のプレイヤーの利得の期待値が線形になります.この時,右辺を0にするにあたって,プレイヤーXは相手の戦略qに依存しない形で自分の戦略pを決められます(行列式の2列目と4列目を使えばそうできます).これが,名前の由来です.ゼロ行列式戦略は,式11の右辺の行列式を0にする(そしてそれが相手と線形の利得関係となる)ので,ゼロ行列式戦略と呼ばれているわけです.上のEqualizerやExtortionerの具体的な数値例は,TRPSの値と戦略pの一部の値が与えられれば,決まります.

 

我々の研究成果

我々のグループの研究成果について少し紹介したいと思います.まず,文献 [2] のIchinoseとMasudaでは,割引因子がある場合にZD戦略があるかについて調査しました.割引因子δ(0<δ<1)とは繰り返しゲームでよく取り入れられる仮定で将来の利得を割り引いて考えるために導入されるものです.文献 [2] で示した最初に重要なことは,この割引因子がある場合でもZD戦略が存在することです.計算は,間宮がまとめた割引因子ありのモデルで確認できます.この文章の式18が割引因子ありでのZD戦略です.文献 [2] では,さらにZD戦略の特殊ケースのEqualizer,Extortioner,Generous戦略(はじめて出てきましたが,これも重要な戦略です)が存在しうるδの条件や,線形の利得関係を強いることができるのはZD戦略と無条件戦略(ALLCやALLDもこれに含まれます)のみであることも解析的に示しました.この研究については,国際会議ALife 2018ゲーム理論ワークショップ2018で発表しました.その時の発表資料を以下に付けましたので,興味のある方はご覧ください.

  • 一ノ瀬元喜, 増田直紀, Zero-determinant strategies in finitely repeated games, ゲーム理論ワークショップ2018, 2018. 発表資料
  • G. Ichinose, N. Masuda, Zero-determinant strategies in repeated prisoner’s dilemma games, Proceedings of the 2018 Conference on Artificial Life (ALIFE 2018), 284-285, 2018. 発表資料

文献 [3] のMamiyaとIchinoseでは,観測エラーを考えた時にZD戦略があるかについて調査しました.観測エラーも繰り返しゲームでよく用いられる仮定で,相手が行った行動と逆の信号(例:相手が協力していたら普通はgoodの信号を観測するが,エラーによってbadの信号を観測する)を観測してしまうことです.文献 [3] では,この観測エラーありの場合でもやはりZD戦略が存在することを示しました.計算の詳細は,間宮がまとめた文章をご覧ください.この文章の式33が観測エラーありでのZD戦略です.この研究については,国際会議ALife 2019国際会議CCS 2019ゲーム理論ワークショップ20192019年度日本数理生物学会年会等で発表しました.いくつかの発表資料をつけておきます.

  • 日本語発表資料
  • A. Mamiya, G. Ichinose, Only two types of strategies enforce linear payoff relationships under observation errors in repeated Prisoner’s dilemma games, Conference on Complex Systems 2019 (CCS 2019), 2019. 発表資料
  • 間宮安曇, 一ノ瀬元喜, 観測エラー付き繰り返し囚人のジレンマゲームにおけるゼロ行列式戦略, 2019年度日本数理生物学会年会, 2019.
  • A. Mamiya and G. Ichinose, Only two types of strategies enforce linear payoff relationships under observation errors in Repeated Prisoner’s Dilemma Games, Proceedings of the 2019 Conference on Artificial Life (ALIFE 2019), 161-162, 2019.
  • 間宮安曇, 一ノ瀬元喜, 観測エラー付き繰り返し囚人のジレンマゲームにおける利得の線形関係を強いる戦略, ゲーム理論ワークショップ2019, 2019.

文献 [4] のMamiyaとIchinoseは,割引因子と観測エラーを2つとも同時にモデルに入れました.この場合にもやはりZD戦略が存在することを発見しました.この時のZD戦略は文献 [4] の式26で表されます.

 

我々が開発したアプリ

間宮・宮川が開発している繰り返しゲームの1回あたりの利得の期待値を可視化するPythonアプリが以下のGitHubにおいてあります.

ここからGUI_PDgame.pyをダウンロードして,実行すると(いくつか外部ライブラリが必要ですが,Anaconda経由でPythonを入れているなら最初から入っていると思います),下図のようなプレイヤーXYの利得が可視化されます.スライダーを動かすとプレイヤーXの戦略を変えることができます.Xの戦略をZD戦略に設定すれば,緑の点が直線上に並ぶのが観察できるでしょう.

 

おわりに

ゼロ行列式戦略(ZD戦略)について我々が知っている情報を整理してまとめてみました.日本語でまとまっているサイトは今のところ他にはないと思うので,このページが今後繰り返しゲームの研究者の何か役に立てば幸いです.特に,繰り返しゲームは経済学のゲーム理論でとてもよく研究されていて,日本人のゲーム理論の方々の華々しい活躍は分野が違う私(一ノ瀬)でも認識しています.しかし,経済学のゲーム理論の人で「ゼロ行列式戦略」について何かやられている方はあまり知りません.これまでのところ,ゼロ行列式戦略については,主に数理生物系か情報系のゲーム理論の興味のある研究者が何かいろいろやっている,という印象です.経済学のゲーム理論の方々は,「均衡」という視点から分析を進められると私は理解しているのですが,その視点からすると「ゼロ行列式戦略」はあまりピンとこないということでしょうか.このまとめが経済学のゲーム理論の研究者の方々の目にも留まれば幸いです.

ここで書いた記事が,どなたかの興味関心を引いて,我々との共同研究にまでつながれば一番嬉しいですが,ただ興味を持ってもらうだけで我々としては嬉しい限りです.ただゼロ行列式戦略がどんなものかが伝わってほしいという思いが強くて書いただけですので.もしこの記事があなたの研究の進展に役立ったとしたら,それで十分です.

何か質問等あれば,お気軽にichinose.genki@shizuoka.ac.jp(@は半角に変更)までご連絡ください.

参考文献

  1. W. H. Press, F. J. Dyson, Iterated Prisoner’s Dilemma contains strategies that dominate any evolutionary opponent, Proc. Natl. Acad. Sci. USA 109, 10409–10413, 2012.
  2. G. Ichinose, N. Masuda, Zero-determinant strategies in finitely repeated games, J. Theor. Biol. 438, 61-77, 2018.
  3. A. Mamiya and G. Ichinose, Strategies that enforce linear payoff relationships under observation errors in Repeated Prisoner’s Dilemma game, J. Theor. Biol. 477, 63-76, 2019.
  4. A. Mamiya and G. Ichinose, Zero-determinant strategies under observation errors in repeated games, bioRxiv, 2020 (under review).