ゲーム 理 論 第 一 部 知 的 都 市 基 盤 工 学 5 月 3 日 ( 水 )5 限 (6:30~8:0)
ゲーム 理 論 とは マルチエージェントシステム あるエージェントの 意 思 決 定 他 のエージェントの 意 思 決 定 ゲーム 的 状 況 : エージェント 間 の 相 互 依 存 関 係 対 立 と 協 力 合 理 的 意 思 決 定 を 解 析 する 理 論 の 必 要 性 ゲーム 理 論 [944 フォン ノイマンオスカー モルゲンシュテルン] 利 害 が 対 立 するプレイヤーの 合 理 的 行 動 を 表 現 する 数 理 モ デルを 構 築 し 数 理 的 に 合 理 的 行 動 の 一 般 的 特 性 を 導 出
ゲーム 理 論 の 歴 史 944 年 990 年 990 年 完 全 合 理 性 アプローチ フォン ノイマンとオスカー モルゲンシュテルン ゲームの 理 論 と 経 済 行 動 の 出 版 950 年 ジョン ナッシュによるナッシュ 均 衡 解 の 提 唱 980~ 限 定 合 理 性 アプローチ 合 理 性 アプローチに 対 する 再 検 討 情 報 処 理 や 計 算 能 力 に 関 する 限 定 進 化 ゲーム 理 論 合 理 的 推 論 結 果 に 対 する 限 定 主 体 は 利 益 の 最 大 化 を 目 指 し 相 手 の 行 動 を 可 能 な 限 り 推 論 [Mynrd:Evolution nd the theory of gme 98] [Axelrod:The evolution of coopertion 984] 例 )チェーンストア パラドックス [Selten: 990] 994 年 ナッシュ ゼルテン ハルサニがノーベル 経 済 学 賞 受 賞 ナッシュ 均 衡 解 の 提 唱 均 衡 解 の 選 択 理 論
ゲームの 分 類 分 類 非 協 力 ゲーム 拘 束 力 のある 合 意 なし 協 力 ゲーム 拘 束 力 のある 合 意 あり 分 類 戦 略 形 ゲーム 一 度 きりの 行 動 決 定 を 同 時 におこなう ゼロ 和 ゲーム 全 員 の 利 得 の 総 和 がゼロ ex.) ジャンケン 非 ゼロ 和 ゲーム 全 員 の 利 得 の 総 和 が 非 ゼロ 繰 り 返 しゲーム 同 じゲームを 繰 り 返 しおこなう 無 限 繰 り 返 しゲーム 戦 略 形 ゲームを 無 限 回 繰 り 返 す 有 限 繰 り 返 しゲーム 戦 略 形 ゲームを 有 限 回 繰 り 返 す 展 開 形 ゲーム 行 動 決 定 を 時 間 の 経 過 とともにおこなう ex.) 将 棋 チェス
戦 略 形 ゲームの 表 現 戦 略 形 ゲームの 構 成 要 素 プレイヤー 決 定 主 体 は 誰 か? 戦 略 プレイヤーはどのような 行 動 計 画 を 持 つか? 利 得 戦 略 の 選 択 の 結 果 に 対 してどのような 評 価 を 持 つか? 例 ) 人 でジャンケン プレイヤー 集 合 戦 略 集 合 A 利 得 関 数 ( 利 得 行 列 ) N {} {グー チョキ パー} A グー チョキ パー グー チョキ パー 0 0 0 勝 : 負 :- 引 き 分 け:0
人 ゼロ 和 ゲームの 一 般 型 人 ゼロ 和 ゲーム.プレイヤーの 数 は 人. 利 得 の 和 はゼロ 3. 各 プレイヤーのとりうる 戦 略 の 数 は 有 限 4.ゲームは 一 回 限 り 5. 各 プレイヤーは 相 手 の 戦 略 に 関 して 情 報 を 持 たない ゲームの 前 提 条 件 合 理 的 なプレイヤー ) 利 得 の 最 大 化 を 目 指 す ) 相 手 の 行 動 を 可 能 な 限 り 推 論 する 共 有 知 識 ゲームに 参 加 する 全 てのプレイヤーはゲームに 関 する 全 ての ルールを 完 全 に 知 っていて 全 てのプレイヤーが 他 のプレイヤーも ゲームのルールを 完 全 に 知 っていることを 相 互 に 認 識 し 合 っている ゲームのルール プレイヤーの 集 合 プレイヤーの 目 的 選 択 可 能 な 行 動 の 集 合 等 のゲームの 進 行 を 定 めるさまざまな 規 定
人 ゼロ 和 ゲーム 例 ) あるゲーム プレイヤー 集 合 戦 略 集 合 利 得 関 数 プレイヤー N {} S {3} S {3 } 3 プレイヤー 3 4 4 33 00 3 3 3 3 プレイヤーの 利 得 3 プレイヤーの 利 得 -3 この 双 行 列 では 左 側 の 要 素 がプレイヤーの 利 得 右 側 の 要 素 がプレイヤーの 利 得 を 表 わしている 同 一 の 行 列 に 対 して お 互 いに 最 大 を 求 めて 行 動 利 害 の 対 立 する 状 況 単 純 な 最 大 化 原 理 によって プレイヤーの 行 動 を 考 えることはできない どのような 行 動 原 理 を 用 いるべきだろうか?
ミニマックス 原 理 プレイヤー のミニマックス 行 動 プレイヤー 保 障 水 準 プレイヤーがどの 戦 略 を 選 択 しても 最 プレイヤー 低 限 獲 得 できるプレイヤーの 利 得 3 3 4 4 33 3 3 プレイヤーの 戦 略 ~3に 対 しての 保 障 水 準 を 求 める 00 3 3 最 低 限 得 られる 利 得 の 中 から 最 大 の 利 得 を 選 択 する mx(min( 4 )min( 303)min(3 )) min( 4 ) min( 303) min( 3) mx( 3) 3 プレイヤーは 戦 略 3を 選 択 すれば 最 低 でも 利 得 は 獲 得 できる
ミニマックス 原 理 プレイヤー のミニマックス 行 動 プレイヤー プレイヤーの 戦 略 ~3に 対 しての 保 障 水 準 を 求 める c 3 3 4 4 33 3 3 プレイヤー 00 min( 43 3) min( 0 ) min( 3 ) 3 3 3 4 c 最 低 限 得 られる 利 得 の 中 から 最 大 の 利 得 を 選 択 する mx( 4 3) プレイヤーは 戦 略 選 択 すれば 最 低 でも 利 得 - は 獲 得 できる
ミニマックス 原 理 プレイヤーとプレイヤー のミニマックス 行 動 をまとめると プレイヤー 3 プレイヤー 4 4 33 00 3 3 3 3 3 min( 43 3) 4 min( 0 ) min( 3 ) mx( 4 ) プレイヤーは 戦 略 を 選 択 min( 4 ) min( 303) min( 3) 3 mx( 3) プレイヤーは 戦 略 3を 選 択 プレイヤーは 戦 略 3を 選 択 し プレイヤーは 戦 略 を 選 択 する それ 以 外 の 戦 略 を 選 択 すると 獲 得 できる 利 得 が 減 ってしまう 戦 略 の 組 (3)を 均 衡 点 プレイヤーの 戦 略 3と プレイヤーの 戦 略 を 最 適 戦 略 という
非 ゼロ 和 ゲーム ゼロ 和 ゲームから 非 ゼロ 和 ゲームへ ゼロ 和 ゲーム 自 分 の 利 益 相 手 の 損 失 自 分 の 損 失 相 手 の 利 益 非 ゼロ 和 ゲーム 自 分 の 利 益 相 手 の 損 失? 自 分 の 損 失 相 手 の 利 益? 協 力 の 可 能 性 なし 協 力 の 可 能 性 が 生 まれるか?
人 非 ゼロ 和 ゲームの 一 般 型 ゼロ 和 ゲーム.プレイヤーの 数 は 人. 利 得 の 和 はゼロ 3. 各 プレイヤーのとりうる 戦 略 の 数 は 有 限 4.ゲームは 一 回 限 り 5. 各 プレイヤーは 相 手 の 戦 略 に 関 して 情 報 を 持 たない. 利 得 の 和 はゼロ を 変 更 する 非 ゼロ 和 ゲーム. 利 得 の 和 はゼロとは 限 らない
人 非 ゼロ 和 ゲームの 一 般 型 プレイヤーとプレイヤーの 戦 略 集 合 } {... m S } {... S n S S プレイヤーの 利 得 行 列 A(ij) とプレイヤーの 利 得 行 列 B(ij) mn n n m ij B M L L L L M ) ( mn n n m ij A M L L L L M ) ( ABをまとめて 双 行 列 G で 表 す mn mn n n n n m m ij ij G ) ( M L L L L M 0 + ij ij が 常 に 成 り 立 っている 場 合 ゼロ 和 ゲームは 双 行 列 G において
囚 人 のジレンマ 人 の 容 疑 者 は 隔 離 相 談 は 不 可 能 容 疑 者 黙 秘 自 白 容 疑 者 黙 秘 自 白 年 年 0 年 3ヶ 月 右 が 容 疑 者 の 刑 期 3ヶ 月 0 年 8 年 8 年 左 が 容 疑 者 の 刑 期 二 人 とも 黙 秘 二 人 とも 懲 役 年 二 人 とも 自 白 二 人 とも 懲 役 8 年 一 方 が 黙 秘 一 方 が 自 白 黙 秘 懲 役 0 年 自 白 懲 役 3ヶ 月 ( ij ij ) 33 4 双 行 列 表 現 4 右 がプレイヤーの 利 得 G 左 がプレイヤーの 利 得
囚 人 のジレンマ 容 疑 者 の 合 理 的 な 思 考 もし 相 手 が 黙 秘 するならば 自 分 は 自 白 をするのが 適 当 である. 容 疑 者 の 合 理 的 な 思 考 もし 相 手 が 黙 秘 するならば 自 分 は 自 白 をするのが 適 当 である. もしそうすると 相 手 は 黙 秘 から 自 白 に 変 えるであろう. もしそうすると 相 手 は 黙 秘 から 自 白 に 変 えるであろう. そのとき 自 分 は 黙 秘 に 変 えると 刑 期 が 延 びてしまうから 自 白 に 留 まる. そのとき 自 分 は 黙 秘 に 変 えると 刑 期 が 延 びてしまうから 自 白 に 留 まる. 人 とも 自 白 を 選 択 二 人 とも 懲 役 8 年
ナッシュ 均 衡 とは 非 ゼロ 和 ゲームの 均 衡 解 自 己 拘 束 性 の 必 要 性 均 衡 解 に 自 己 拘 束 性 がなければ 必 ず 少 なくとも 一 人 のプレイヤーはその 均 衡 から 離 脱 する 動 機 を 持 つ.このときゲームの 解 自 体 は 拘 束 力 のある 合 意 に 基 づくものではないから 実 際 のプレイがゲームの 解 と 一 致 する 保 証 はない ナッシュ 均 衡 解 定 義 相 手 のナッシュ 均 衡 戦 略 に 対 して 自 分 の 利 得 を 最 大 にする 戦 略 はナッシュ 均 衡 戦 略 である 他 のすべてのプレイヤーがナッシュ 均 衡 点 に 従 うと 予 想 するときどのプレイヤーも 自 らそのナッシュ 均 衡 点 から 離 脱 する 動 機 を 持 たない 自 己 拘 束 性 を 持 つため 非 ゼロ 和 ゲームに おける 合 理 的 行 動 の 解 となり 得 る
ナッシュ 均 衡 の 定 義 定 義 5 [Nh 950] ナッシュ 均 衡 戦 略 の 組 ) ( ) ( mx ) ( f f S が ) ( mx ) ( f f S をナッシュ 均 衡 点 という を 満 たすとき 相 手 のナッシュ 均 衡 戦 略 に 対 して 自 分 の 利 得 を 最 大 にする 戦 略 はナッシュ 均 衡 戦 略 である
最 適 反 応 戦 略 の 定 義 定 義 最 適 反 応 相 手 がある 戦 略 を 取 ったときにその 戦 略 のもとで 自 分 の 利 益 を 最 大 にするように 行 動 するという 行 動 原 理 を 最 適 反 応 原 理 という 定 義 最 適 反 応 戦 略 最 適 反 応 原 理 により 選 択 された 戦 略 を 最 適 反 応 戦 略 という プレイヤーの 戦 略 がプレイヤーの 戦 略 に 対 する 最 適 反 応 戦 略 であるとは f であるときをいう このとき f ( ) mx f( ( ) S はプレイヤーの 利 得 関 数 である )
最 適 反 応 戦 略 囚 人 のジレンマでの 最 適 反 応 戦 略 黙 秘 プレイヤー 自 白 プレイヤー 黙 秘 33 4 自 白 4 右 がプレイヤーの 利 得 左 がプレイヤーの 利 得 プレイヤー プレイヤーのそれぞれ 戦 略 に 対 する 最 適 反 応 戦 略 相 手 が 黙 秘 自 分 の 利 得 を 最 大 にする 戦 略 は 自 白 相 手 が 自 白 自 分 の 利 得 を 最 大 にする 戦 略 は 自 白
最 適 反 応 戦 略 集 合 の 定 義 定 義 3 最 適 反 応 戦 略 集 合 プレイヤーの 任 意 の 戦 略 に 対 するプレイヤーの 最 適 反 応 戦 略 は 存 在 するとしてもただ 一 つであるとは 限 らない. その 集 合 を 最 適 反 応 戦 略 集 合 R ) とすると ( R ( ) { S f ( ) mx f S ( )}
最 適 反 応 戦 略 集 合 囚 人 のジレンマでの 最 適 反 応 戦 略 集 合 プレイヤー プレイヤー 黙 秘 自 白 黙 秘 33 4 自 白 4 右 がプレイヤーの 利 得 左 がプレイヤーの 利 得 プレイヤーの 各 戦 略 に 対 するプレイヤーの 最 適 反 応 戦 略 集 合 R ( プレイヤーが 黙 秘 ) { 自 白 } R ( プレイヤーが 自 白 ) { 自 白 } プレイヤーの 各 戦 略 に 対 するプレイヤーの 最 適 反 応 戦 略 集 合 R ( プレイヤーが 黙 秘 ){ 自 白 } R ( プレイヤーが 自 白 ){ 自 白 }
最 適 反 応 集 合 の 定 義 定 義 4 最 適 反 応 集 合 プレイヤー の 戦 略 とそれに 対 するプレイヤー の 最 適 反 応 戦 略 の 組 の 集 合 をプレイヤーの 最 適 反 応 集 合 プレイヤーの 戦 略 とそれに 対 するプレイヤーの 最 適 反 応 戦 略 の 組 の 集 合 をプレイヤーの 最 適 反 応 集 合 とよぶ. プレイヤーの 最 適 反 応 集 合 を D D プレイヤーの 最 適 反 応 集 合 を D D { ( ) : R ( ) } S { ( ) : S R ( )} とすると 次 のように 表 される.
最 適 反 応 集 合 囚 人 のジレンマでの 最 適 反 応 集 合 プレイヤーに 対 するプレイヤーの 最 適 反 応 集 合 R ( プレイヤーが 黙 秘 ) { 自 白 } R ( プレイヤーが 自 白 ) { 自 白 } D {( 自 白 黙 秘 )( 自 白 自 白 )} (プレイヤーの 戦 略 プレイヤーの 戦 略 ) プレイヤーに 対 するプレイヤーの 最 適 反 応 集 合 R ( プレイヤーが 黙 秘 ) { 自 白 } R ( プレイヤーが 自 白 ) { 自 白 } D {( 黙 秘 自 白 )( 自 白 自 白 )}
ナッシュ 均 衡 定 理 ナッシュ 均 衡 の 集 合 をD とすると 次 のことが 成 り 立 つ D D D 囚 人 のジレンマでのナッシュ 均 衡 D {( 自 白 黙 秘 )( 自 白 自 白 )} {( 黙 秘 自 白 )( 自 白 自 白 )} D (プレイヤーの 戦 略 プレイヤーの 戦 略 ) 定 理 より D {( 自 白 自 白 )} D D ゲーム 理 論 的 な 合 理 的 行 動 は 自 白 を 選 択