展開形ゲームとは?

Weblio 辞書 > 同じ種類の言葉 > 文化 > 娯楽 > ゲーム > 展開形ゲームの意味・解説 

展開形ゲーム

読み方てんかいけいげーむ
【英】:game in extensive form

概要

プレイヤーの手番の系列グラフ理論の有向木を用いて表現するゲームモデル. 木の分岐点プレイヤーの手番, プレイヤー選択肢または行動を表す. ゲームプレイは木の初期点から始まり木の1つ終点到達して終了する. プレイヤー同時的な意思決定定式化する戦略形ゲームに対して, 展開形ゲームはプレイヤー動学的な意思決定問題分析するために用いられる.代表的均衡概念部分ゲーム完全均衡, 完全均衡逐次均衡がある.

詳説

 展開形ゲーム (game in extensive form) はプレイヤーの手番の系列ゲームの木 (game tree) を用いて表現するモデルである. ゲームの木 K\, グラフ理論でいう有向木で, 木の分岐点プレイヤー選択肢を選ぶ手番, プレイヤー選択肢あるいは行動を表す. 木の始点から終点までの経路ゲーム1つプレイという.

 プレイヤー分割 P=[P_{0}, P_{1}. \cdots, P_{n}]\, は, ゲームの木 K\, 分岐点全体n+1\, 個の部分集合分割する. P_{i}\ (i=1, 2, \cdots, n)\, プレイヤー i\, の手番の集合を表す. P_{0}\, 含まれる手番は偶然手番とよばれ, プレイヤー意思とは無関係な偶然機構によって選択される. 天候トランプゲームランダムカードを配るなどは, 偶然手番典型的な例である. 偶然手番に対して選択行なう確率分布 p\, 付与される.

 ゲーム情報分割 U=[U_{0}, U_{1}, \cdots, U_{n}]\, は,プレイヤー分割P\, 細分割である.各 i=1, 2, \cdots, n\, に対して U_{i}=[u_{i1}, u_{i2}, \cdots, u_{im_{i}}]\, プレイヤー i\, の手番の集合 P_{i}\, m_{i}\, 個の非空な部分集合分割する. U_{i}\, 属す部分集合 u_{ij}\ (j=1, 2, \cdots, m_{i})\, プレイヤー i\, 情報集合 (information set) という.プレイヤー行動選択するとき,自分の手番がどの情報集合属するかは知っているが,情報集合の中のどの分岐点であるかは知らない.

 ゲーム利得関数 h\, は,ゲームの木 K\, の各終点 z\, に対してプレイヤー利得ベクトル h(z)=(h_{1}(z), h_{2}(z), \cdots, h_{n}(z))\, を対応させる.

 形式的には, 展開形ゲーム \Gamma\, は以上の5つの要素の組 (K, P, p, U, h)\, によって定義される. これらの5つの構成要素ゲームのルールという.


図1:展開形ゲーム
図1:展開形ゲーム


 展開形ゲームの例として図1を考える.プレイヤー1と2の情報分割それぞれ U_{1}=[u_{1}], U_{2}=[u_{21}, u_{22}]\, である.図1では最初にプレイヤー1がRとLの2つの行動のうち1つ選択する. 次に, プレイヤー2はプレイヤー1の選択を知った上で, RとLのうちから1つ行動選択する.ゲームは4つの終点をもち, 終点付与されている利得ベクトル上の数字プレイヤー1の利得, 下の数字プレイヤー2の利得を表す.

 図1のゲームのように, プレイヤーすべての情報集合がただ1つ分岐点から成るゲーム完全情報ゲーム (game with perfect information) といい, そうでないゲーム不完全情報ゲーム (game with imperfect information) という. 完全情報ゲームでは, すべての手番においてプレイヤーゲーム過去プレイ経過を完全に知った上で行動選択できる. チェス将棋完全情報ゲームである.

 展開形ゲームの部分木でそれ自身が展開形ゲームの構造をもつものを部分ゲームという. 図1のゲームは, 情報集合 u_{21}\, u_{22}\, から始まる2つの部分ゲームをもつ.

 プレイヤー i\, の各情報集合 u\in U_{1}\, に対して u\, における選択肢集合上の1つ確率分布 b_{i}(u)\, を対応させる関数 b_{i}\, プレイヤー i\, 行動戦略 (behavior strategy) という. 特に, すべての情報集合に対して1つ選択肢確定的に対応させる行動戦略純戦略という.

 例えば, 図1のゲームにおいて, プレイヤー1の純戦略 \pi_{1}\, はRとLの2通りであり, プレイヤー2の純戦略 \pi_{2}\, は, RR, RL, LR, LLの4通りである. ただし, 前の文字情報集合 u_{21}\, でとる行動, 後の文字情報集合 u_{22}\, でとる行動を表す. 図1の展開形ゲームから, プレイヤー純戦略利得の関係によって図2のような戦略形ゲーム作ることができる.



LL LR RL RR
R
1, 1* 1, 1* -2, 0 -2, 0
L
-1, 0 0, 1 -1, 0 0, 1*

図2:図1の展開形ゲームから作られた戦略形ゲーム


 プレイヤー行動分析のための最も基本的ゲームの解の概念は, ナッシュ (J. F. Nash) によって定義された非協力均衡点である. 一般にナッシュ均衡呼ばれている. 展開形ゲームの行動戦略の組 b^{*}=(b_{1}^{*}, b_{2}^{*}, \cdots, b_{n}^{*})\, ナッシュ均衡であるとは,すべてのプレイヤー i=1, 2, \cdots, n\, すべての行動戦略 b_{i}\, に対して,


H_{i}(b^{*}) \ge H_{i}(b^{*}/b_{i})\,

 

成り立つことである. ただし, b^{*}/b_{i}\, b^{*}\, からプレイヤー i\, だけが戦略b_{i}^{*}\, から b_{i}\, 変更してできる行動戦略の組を表し, H_{i}\, プレイヤー i の期待利得関数を表す.

 完全情報ゲームナッシュ均衡は, 最初に, 終点に一番近い分岐点で, その手番のプレイヤー利得最大にする最適戦略求め, 以下順次, ゲームの木を後向きに解くことによって計算できる. 例えば, 図1のゲーム情報集合 u_{21}\, u_{22}\, におけるプレイヤー2の最適戦略それぞれLとRである. このとき, 情報集合 u_{1}\, におけるプレイヤー1の最適戦略はRであり, 純戦略の組 (R, LR) はゲームナッシュ均衡である. このようなナッシュ均衡計算方法を, ゲームの後向き帰納法という. キューン (H. Kuhn) は, n\, 完全情報ゲーム純戦略範囲少なくとも1つナッシュ均衡をもつことを証明した [1].

 図1のゲームは (R, LR) の他に図2の利得行列で*をつけたナッシュ均衡をもつ. しかし, これらのナッシュ均衡均衡プレイ上にない分岐点ではプレイヤー最適戦略を導かないという欠点をもつ. ゼルテン (R. Selten) はナッシュ均衡このような欠点解消するために, より強い均衡概念として, すべての部分ゲーム上にナッシュ均衡を導く部分ゲーム完全均衡 (subgame perfect equilibrium) を定義した [3].

 ゼルテン研究以後, 展開形ゲームの理論大きく進展し, 現在, ゲーム状況におけるプレイヤー戦略的行動解明する基礎理論としてORや経済学始め広範囲分野応用されている.

 展開形ゲームについて詳しくは, [2] を参照されたい.



参考文献

[1] H. W. Kuhn, "Extensive Games and the Problem of Information," in H. W. Kuhn and A. Tucker(eds.), Contributions to the Theory of Games, Vol. II, Annals of Mathematics Studies 28, Princeton University Press, 1953, 193-216.

[2] 岡田 章, 『ゲーム理論』, 有斐閣, 1996.

[3] R. Selten, "Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games," International Journal of Game Theory, 4 (1975), 25-55.

「OR事典」の他の用語
ゲーム理論:  完全均衡  完全情報ゲーム  実験  展開形ゲーム  市場ゲーム  微分ゲーム  情報集合

展開型ゲーム

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2017/01/24 14:51 UTC 版)

(展開形ゲーム から転送)

展開型ゲーム(てんかいがたげーむ、: game for extensive form)とは、ゲームの表現形式のひとつであり、ゲームの木と呼ばれるグラフの形式で表現されたものである。ゲームの表現形式には展開型と標準型(または戦略型)特性関数型(または提携型)の3種がある。ある非協力ゲームは展開型でも標準型でも表現できるが、展開型の方が情報量が多い。特性関数型は特に協力ゲームの表現に使われる[1][2][3][4]




  1. ^ 日本数学会「岩波数学辞典-第3版」岩波書店(1985/12)
  2. ^ 岡田章「ゲーム理論」有斐閣(1997/01)[要ページ番号]
  3. ^ 佐々木宏夫「入門ゲーム理論―戦略的思考の科学」日本評論社(2003/03)[要ページ番号]
  4. ^ 武藤滋夫「ゲーム理論入門」日本経済新聞社(2001/01)[要ページ番号]


「展開型ゲーム」の続きの解説一覧





展開形ゲームと同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

展開形ゲームに関連した本

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「展開形ゲーム」の関連用語

展開形ゲームのお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング

画像から探す

肝属川

ウミウチワ

カワラナデシコ

小川原湖畔の野鳥

栃倉

猩々

ランサーエボリューションX

蓬莱竹





展開形ゲームのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2017 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの展開型ゲーム (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2017 Weblio RSS