展開形ゲーム
【英】:game in extensive form
概要
プレイヤーの手番の系列をグラフ理論の有向木を用いて表現するゲームのモデル. 木の分岐点はプレイヤーの手番, 枝はプレイヤーの選択肢または行動を表す. ゲームのプレイは木の初期点から始まり木の1つの終点に到達して終了する. プレイヤーの同時的な意思決定を定式化する戦略形ゲームに対して, 展開形ゲームはプレイヤーの動学的な意思決定問題を分析するために用いられる.代表的な均衡概念に部分ゲーム完全均衡, 完全均衡や逐次均衡がある.
詳説
展開形ゲーム (game in extensive form) はプレイヤーの手番の系列をゲームの木 (game tree) を用いて表現するモデルである. ゲームの木 はグラフ理論でいう有向木で, 木の分岐点はプレイヤーが選択肢を選ぶ手番, 枝はプレイヤーの選択肢あるいは行動を表す. 木の始点から終点までの経路をゲームの1つのプレイという.
プレイヤー分割 は, ゲームの木
の分岐点の全体を
個の部分集合に分割する.
はプレイヤー
の手番の集合を表す.
に含まれる手番は偶然手番とよばれ, プレイヤーの意思とは無関係な偶然機構によって枝が選択される. 天候やトランプゲームでランダムにカードを配るなどは, 偶然手番の典型的な例である. 偶然手番に対しては枝の選択を行なう確率分布
が付与される.
ゲームの情報分割 は,プレイヤー分割
の細分割である.各
に対して
はプレイヤー
の手番の集合
を
個の非空な部分集合に分割する.
に属する部分集合
をプレイヤー
の情報集合 (information set) という.プレイヤーは行動を選択するとき,自分の手番がどの情報集合に属するかは知っているが,情報集合の中のどの分岐点であるかは知らない.
ゲームの利得関数 は,ゲームの木
の各終点
に対してプレイヤーの利得ベクトル
を対応させる.
形式的には, 展開形ゲーム は以上の5つの要素の組
によって定義される. これらの5つの構成要素をゲームのルールという.
![]() |
図1:展開形ゲーム |
展開形ゲームの例として図1を考える.プレイヤー1と2の情報分割はそれぞれ である.図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のゲームは, 情報集合 と
から始まる2つの部分ゲームをもつ.
プレイヤー の各情報集合
に対して
における選択肢の集合上の1つの確率分布
を対応させる関数
をプレイヤー
の行動戦略 (behavior strategy) という. 特に, すべての情報集合に対して1つの選択肢を確定的に対応させる行動戦略を純戦略という.
例えば, 図1のゲームにおいて, プレイヤー1の純戦略 はRとLの2通りであり, プレイヤー2の純戦略
は, RR, RL, LR, LLの4通りである. ただし, 前の文字は情報集合
でとる行動, 後の文字は情報集合
でとる行動を表す. 図1の展開形ゲームから, プレイヤーの純戦略と利得の関係によって図2のような戦略形ゲームを作ることができる.
|
|||||
R |
|
||||
L |
|
図2:図1の展開形ゲームから作られた戦略形ゲーム
プレイヤーの行動分析のための最も基本的なゲームの解の概念は, ナッシュ (J. F. Nash) によって定義された非協力均衡点である. 一般にナッシュ均衡と呼ばれている. 展開形ゲームの行動戦略の組 がナッシュ均衡であるとは,すべてのプレイヤー
のすべての行動戦略
に対して,
が成り立つことである. ただし, は
からプレイヤー
だけが戦略を
から
に変更してできる行動戦略の組を表し,
はプレイヤー i の期待利得関数を表す.
完全情報ゲームのナッシュ均衡は, 最初に, 終点に一番近い分岐点で, その手番のプレイヤーの利得を最大にする最適戦略を求め, 以下順次, ゲームの木を後向きに解くことによって計算できる. 例えば, 図1のゲームで情報集合 と
におけるプレイヤー2の最適戦略はそれぞれLとRである. このとき, 情報集合
におけるプレイヤー1の最適戦略はRであり, 純戦略の組 (R, LR) はゲームのナッシュ均衡である. このようなナッシュ均衡の計算方法を, ゲームの後向き帰納法という. キューン (H. Kuhn) は,
人完全情報ゲーム は純戦略の範囲で少なくとも1つのナッシュ均衡をもつことを証明した [1].
図1のゲームは (R, LR) の他に図2の利得行列で*をつけたナッシュ均衡をもつ. しかし, これらのナッシュ均衡は均衡プレイ上にない分岐点ではプレイヤーの最適戦略を導かないという欠点をもつ. ゼルテン (R. Selten) はナッシュ均衡のこのような欠点を解消するために, より強い均衡概念として, すべての部分ゲーム上にナッシュ均衡を導く部分ゲーム完全均衡 (subgame perfect equilibrium) を定義した [3].
ゼルテンの研究以後, 展開形ゲームの理論は大きく進展し, 現在, ゲーム的状況におけるプレイヤーの戦略的行動を解明する基礎理論としてORや経済学を始め広範囲の分野に応用されている.
[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.
[3] R. Selten, "Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games," International Journal of Game Theory, 4 (1975), 25-55.
「game in extensive form」の例文・使い方・用例・文例
- 同植物に複数の形態のgametoeciaがあるさま
- 雌のgametoecium
- http://www.niehs.nih.gov/kids/lyrics/ballgame.htmでこの歌のメロディーを聴くことができます。
- 「アサガオ」に対する英語は「morning glory」です
- Holman Healthは栄養補助食品業界の巨大企業で、最高経営責任者であるBud Rollinsを交代させようとしているが、Bud Rollinsは機会があるたびに、彼と同社取締役会とがあらゆる点で合意できるようには思えないと公言していた。
- 私は6月後半に休暇を取るので、参加のご要望は必ずLyle GrodinをCCに入れてください。
- 工事が完了するまで、正面とVine通りの入口からしかセンターに入れない。
- 昨年までは、Train FirstとTop Shareと契約をしていました。
- 興味のある方は、12月5日までに、履歴書と少なくとも2通の職務に関する推薦状を添付したEメールを、Singh金融サービスのMisa Takahama、mtakahama@singhfs.comまで送ってください。
- 現在、香港のMing銀行で下級市場アナリストとして働いており、この職に就いて2 年半になります。
- 私はBellingham大学の数学の学位があり、どちらの推薦状にも書かれているように、高いコミュニケーションスキルを持ち合わせています。
- John AbrahamsとTina Linがアンケートデータの収集担当で、この作業は5 月5 日までに終わるでしょう。
- 配達はWestlake、Pinewood、Ramona限定
- Direct Marketingという会社が、私たちの卸売業者となることに同意してくれました。
- この地域では、Direct Marketingは比較的新しい企業ですが、すでに地元の小売店だけでなく、近隣の州の大小の小売店とも、しっかりとした関係を確立しています。
- Direct Marketingと、円滑で長く続く関係が築けることを期待しています。
- この家は北側がWinona川に接しており、美しく景観の整えられた半エーカーの土地に位置しています。
- 詳細は、Sophistication のウェブサイト、www.sophistication-magazine.comをご覧ください。
- Bryce Rollins の回顧展が、6 月17 日から9 月15 日までSchulz美術館にて、同美術館の35 周年を祝って行われる。
- 1970 年代初頭以来、独特の皮肉精神を持つRollinsは、近代化によってもたらされた複雑な社会を風刺した、印象的な作品を立て続けに発表している。
- game in extensive formのページへのリンク