ゲームとゲーム理論

相手を騙そうとして作戦を立てる場合、何がおきうるか？

ゲーム理論について（Wikipediaへのリンク）

対戦型のゲームで、交渉的な要素、先読み的要素がある場合に、どの様に行動したら得であるかを、理論的に分析する。　

例）
　ジャンケン
　オークション
　TicTacToe

上記の様なゲームで、対戦相手と自分がそれぞれ何らかの作戦を立てた場合、
　・その作戦が当たっているかどうかの　確認方法
　・相手の作戦がわかっている場合の　対処法
について考える。

以下のネタ元および参考文献：

　ゲームの理論入門　　　　　　　　　　　　モートン・D・デービス　　　　　　講談社
　ゲームと競技の数学　　　　　　　　　　　J・D・ビースリー　　　　　　　　　サイエンス社

絵札当て　ゲーム

例）

　・Ace〜Kingまでのカード１３枚を使用
　・親だけがカードを1枚めくり確認する。
　・親は、５点か、１点か　を賭ける。
　・子は、　
　　　　チャレンジするか、
　　　　降りて、親の賭けた点数を支払う。
　・チャレンジした場合、カードをオープンして確認する。
　　　　J,Q,Kの絵札　→　親の勝ち　→　子からかけた点の　２倍　を受け取る
　　　　A〜１０の絵札　→　子の勝ち　→　親からかけた点の　２倍　を受け取る

何回かゲームを続けてから、親と子を交代する。

上のゲームで、　親の作戦と、　子の作戦について考える。

（質問）
　このゲームで、得をしようと思ったら、　親と子　どちらでプレーすべきですか？

親の収支： 親の得点について、C言語風に表現すると、以下の様になる。

if(親が5点賭ける) {
    if(子がチャレンジする) {
         if(絵札){
                10点儲け;
         } else {
                10点支払い;
         }
     } else {
         5点儲け;
     }
} else {
    if(子がチャレンジする) {
         if(絵札){
                2点儲け;
         } else {
                2点支払い;
         }
     } else {
         1点儲け;
     }
}

親と子の行動（作戦）の結果をシミュレーションしてみる。

以下のシミュレータの動作：
●親の行動
　・ J Q K　は必ず　５点　賭ける
　・　絵札以外の、１-10の内、どこまでのカードを引いたときにも５点　賭けるかを選ぶ。
　　　　　１ → Aのとき、　2 → １〜2のとき、　　・・・・・10 → 全て、　0 → 絵札のみ5点賭ける

●子の行動
　・ 親が１点賭けたら　必ずチャレンジする
　・ 親が５点賭けたら　一定の確率で、チャレンジする。
　　　０　→　チャレンジしない
　　　１００　→　必ずチャレンジする
　　　５０　→　５０％の確率でチャレンジする。

シミュレーション

例1）　正直作戦

親：　絵札を引いたら　常に　５点　かける
子：　親が５点賭けたら　常に降りる、それ以外はチャレンジ

親は、平均幾ら儲かるか？

例２）　うそつき作戦

親：　絵札とAceを引いたら　常に　５点　かける
子：　親が５点賭けたら　常に降りる、それ以外はチャレンジ

親は、平均幾ら儲かるか？

例３）　欲張り作戦

親：　絵札とAceと２を引いたら　常に　５点　かける
子：　５点賭けられても　常に降りていたら　大損　→　作戦を修正　→　５点に対して、ある程度チャレンジ

作戦の均衡点について

親の作戦：　A（５点）とB（１点）　の割合を確率（数札を引いたとき、ウソをつく確率p）で表す
子の作戦：　C（チャレンジ）　・　D（降り）　の割合を確率（５点かけられたときチャレンジする確率q）で表す。

P（X,Y）：　親と子の作戦の組み合わせごとの利益
　　　　　　P（１０,−１０）　なら、親が１０点を得て、子が１０点を失うことを示す。

作戦ごとの親の利益：

親と子の利益配分：

※子は作戦Bに対して作戦Cを選択れば必ず利益を得る

親の平均利益：

10*3/13*q - 10*10/13*p*q + 5*3/13*(1-q) + 5*10/13*p*(1-q) - 2*10/13*(1-p)

qの影響が０になるのは、(q＊α＋βのかたちに変形して、α＝０とする)
10*3/13 - 10*10/13*p - 5*3/13 - 5*10/13*p = 0 を解いて、
　p = 1/10
同様にして、
　q = 7/15

それぞれの最善手：
　親：　絵札は常に５点。　字札は１/１０で、５点。　それ以外は１点。
　子：　親が５点賭けたら、　７/１５の確率でチャレンジ。　１点かけたときは必ずチャレンジ。

この作戦を、それぞれが実行する場合、どちらがどれだけ得するといえるか？
　（上記シミュレータ、または確率計算で確認）

・親と子の作戦の組み合わせによる利益をグラフ表示

ゲーム理論の教えるところによれば、　上記の様なゲーム的シチュエーション（例：　対立する２者がお互いに確率的に戦略を選択する）においては、

　　必ず均衡点が存在する（ナッシュ均衡）

ことが知られている。

どちらかの参加者が均衡点でゲームを進めた場合、

　　対戦相手がどのように”戦略を変化”させても、
　　戦略を変えた側の得られる利益は増えないか変化しない（減るか変化しない）

状況となる。

例えば、もし均衡状態で、（上記の絵札当てゲームのように）親の側に利益が出ることが分かっていれば、子がどのような作戦をとっても、何度もゲームを繰り返すことで親は利益を増やし続けることができる。

（質問）：
　　つまり、上記のカードゲームは、　どちらの側でプレーしたら得をするでしょうか？

混合戦略：

ゲームの参加者が、お互いにそれぞれ幾つかのゲーム上の行動（選択肢）を選び、　その行動の組み合わせに応じて、ゲームの結果（勝ち負け・損得）が決るという状況で、各自が行動を確率的に選択する作戦のこと。

上記のカードゲームでは、混合戦略をとることで、均衡状態にすることができる。

ゲーム理論の応用例

以下の幾つかのゲーム的な状況について、ゲーム理論的に合理的な戦略の選択について考える。

道の選択：

途中ですれ違うことのできない狭いトンネルが２本ある。
互いに反対方向から向こう側へ行こうとしている者がいた場合について考える。

両者が同じ道を選んだ場合、ジャンケンで負けたほうが道を譲るとする。（確率上、５０％でどちらかが勝つとする）

トンネルAを通れば、時間・燃料代が節約でき、利益＋１を得る。
トンネルBを通れば、時間・燃料代が浪費され、利益−１となる。

・トンネルを通る前に、予めジャンケンする場合、互いにとるべき戦略は？

（左の利益　，　右の利益）

・トンネルの中で鉢合わせしてから、ジャンケンするとする。
　ジャンケンで負けたほうは、後戻りにより、利益がトータルで−２になる（どちらのトンネルを選んでも）。
　互いにとるべき戦略は？

・トンネルの中で鉢合わせしてから、ジャンケンするとする。
　ジャンケンで負けたほうは、後戻りにより、利益がトータルで−４になる（どちらのトンネルを選んでも）。
　互いにとるべき戦略は？

お互いの得られる平均的な利益を元に、どうするべきか考えてみること。

ピッチャー対バッター：
　カウント２−３、　最後の一球。　
　ピッチャーは　”バッターの”不得意なコースに投げるべきか投げないべきか？
　バッターは　自分の得意コースで待つべきか待たないべきか？

例）

ヒットの確率：　0.6*p*q + 0.3*(1-p)*q + 0.2*p*(1-q) + 0.4*(1-p)*(1-q)

確率表示

ジャンケン：

ある人のジャンケンの癖

グー　の確率　：　G
チョキ　の確率：　C
それ以外（パー）の確率：　１　−　G　−　C

が分かっているとき、相手はどの様に対応するべきか？

応用：

　グーで勝つと　１点
　チョキで勝つと　２点
　パーで勝つと　３点

　　ゲームの例）

勝った手に応じて得点するじゃんけんの場合、　どの手をどのくらいの確率で出すべきか？

例えば、この点数付きジャンケンで、次のような場合について自分の得点を計算する

　・どの手も均等に1/3で相手が出す
　　　自分がパー100%
　　　　　1/3*3 - 1/3*2 + 1/3*0 = 1/3
　　　自分がチョキ100%
　　　　　-1/3*1 + 1/3*0 + 1/3*2 = 1/3

　・パーを1/2で、その他は1/4で相手が出す
　　　自分がパー100%
　　　　　1/2*0 - 1/4*2 + 1/4*3 = 1/4
　　　自分がチョキ100%
　　　　　1/2*2 + 1/4*0 - 1/4*1 = 3/4

均衡点：

戦略マトリックス（組み合わせ表）

自分：　mG, mC はグーを出す確率とチョキを出す確率、1 - mG - mCはパーを出す確率
相手：　eG, eC はグーを出す確率とチョキを出す確率、1 - eG - eCはパーを出す確率

平均得点
　eG*(-mC +3*(1 - mG - mC)) + eC*(mG -2*(1 - mG - mC)) + (1 - eG -eC)*(-3*mG +2*mC)

eGとeCで整理して、
　eG*(-mC +3*(1 - mG - mC) -(-3*mG +2*mC)) + eC*(mG -2*(1 - mG - mC) - (-3*mG +2*mC)) + (-3*mG +2*mC)

eG と eCの影響を受けない、mG と mC は、

-mC +3*(1 - mG - mC) -(-3*mG +2*mC) = 0
mG -2*(1 - mG - mC) - (-3*mG +2*mC) = 0

の連立方程式の解。　解くと、
mC = 1/2
mG = 1/3

つまり、チョキを50%、グーを３３%、パーを17%　出せば、相手がどのような割合で手を選んでも、平均点は0になり、引き分ける。
この割合以外の手を選んだ場合、　相手はその戦略の裏をかいて、より利益を得ることが可能になる。
つまり、この割合は、勝つこともないが、負けることもない戦略ということになる。

（余談）

ケーキの分け方：

ケーキを半分に分けることにした。　出来るだけ公平に分けるにはどうしたらよいか？

戦力の投入：

A国とB国　が戦争をしていて、国境にある　X平原　と　Y高地　で戦闘中。

どちらの戦場でも、戦況は互角。
そこで、戦況を有利にするため、追加の戦力を互いに送ることになった。

　A国の追加戦力　５
　B国の追加戦力　３

それぞれの国の将軍は、　追加戦力を１単位ごとに分けて、XかYの戦場に送ることにする。
各戦場での勝敗は、　追加戦力の多い方が勝ち。　同じ戦力なら引き分け　とする。

お互いに、同時に戦力を戦場に送らなければならない場合（相手がどこにどれだけ送るか知ることが出来ない場合、　どのような作戦が考えられ、ベストの戦略は何か？

戦略マトリクス：

戦場に送る戦力(X-Y)とB国の勝ち数(引き分けは、0.5勝とする)

均衡戦略：　B国がXに送り込む戦力は、
　　1/3の確率で　3、　1/3で　0、　1/6で　2、　1/6で　1
とした場合、平均の勝利数は、A国がどのような戦略をとっても、　7/12勝となる。

西部劇：

　決闘、弾は互いに１発。　相手が外したら、　自分はどれだけ接近して撃っても良し（その場合100%命中させることができるとする）。
　どの距離で打つべきか？　デモンストレーション

　相手までの距離：　ｘ
　Aの命中率：　　A（ｘ）
　Bの命中率：　　B（ｘ）

自分が勝つケースについて考える。
　１・自分が先に命中させる
　２・相手が先に外す
このどちらかで、自分の勝ちとなる。つまり、１と２の確率をくらべて２が大きな間は、自分が撃つよりも相手が外すことを期待したほうがよい。
逆に、相手も、こちらと同様に考えるとすると、１が２よりも大きくなるまで待っていては、相手が不利になるので、１と２の値が同じになる距離で、相手も撃つ。
つまり、自分も相手も、この同じタイミングと距離で撃ち合う事になる。

背の高いボスの問題：

　5人のギャング達がホテルの1室で会議中。　ボスは5名のメンバー中１番背が高いとの情報あり。
　会議が終ると、時間を置いて１人ずつホテルから出てくるらしい。
　ホテルの近くには捜査官は１人しかおらず、応援も呼べない状況。
　出来れば、後をつけてボスのアジトをつき止めたい。
　さて、何番目に出てきた人のあとを付ければよいだろうか？

・問題をいいかえると、
　「最初の何人を見逃せば、ボスを捕まえられる確率が最も高いか？」
　最初のN人を見逃すとする。
　１〜５の順列について、最初のN個の中の最大値をPとする。
　このとき、N+1個以降の値でPより小さいものは無視して、最初にPよりも
　大き数字になった時、その値が5である確率を求める。
　確率を一番大きくするNはなにか？

（答え）　最初の2名を見逃した場合、　捕まえられる確率は40%となる。

・応用
　見張っていること、最初のN人を見逃す作戦であることがばれた場合、ボスと捜査官はそれぞれどういう作戦を取るべきか？

MAD戦略

MAD　相互確証破壊（mutually assured destruction）：

核戦略において、互いに等々の技術を保有する２国間でのシチュエーション
　先制攻撃による、相手の反撃用核戦力を完全に破壊することが出来ない状況

（A国の利益、B国の利益）

囚人のジレンマ

警察と囚人の取り引き：

　協調と裏切りについて

　警察が、２人の囚人AとBに、収監期間の取り引きを持ちかけた。
　AとBは別々の部屋に捉えられ、お互いに相談は出来ない状態で、決断しなければならない。
　取り引き内容は、
　「自白した場合、罪を軽くする。
　　特に、相手が黙っていて自分だけが罪を認めて事実が明らかとなった場合は直ちに釈放する。
　　その時、黙っていた方は５年の刑期。お互いに自白すれば両者とも３年の刑期。
　　お互いが黙っていた場合は、余罪で１年の刑期となる。」

取り引きの内容を整理すると、AとBの作戦、「黙秘・自白」の組み合わせについて以下の様になる。

囚人はどうすべきか？

上記の囚人のジレンマのシチュエーションにおいて、AやBが再犯を繰り返す場合、どのようなことが考えられるか？

しっぺ返し戦略について：

ミシガン大学で開かれた「コンピュータ囚人のジレンマ」トーナメント
　・参加するは、”プログラム”された囚人
　・総当りで繰返し囚人のジレンマを行う。
　・最も累計の刑期の少なかった囚人の勝ち

関連記事

レポート課題：（その２）

今回の講義テーマ　ゲーム理論　に関して、　日常生活における似たような状況を見つけてください。

または、ゲーム理論的な状況を想定し（架空のものでもOK）、何を選ぶのが合理的といえるか説明してください。

応用例の実用性は問わない。

いつもどおりメールで回答願います。