展開形ゲームとは:ゲーム理論の基礎知識5

ゲーム理論の基礎知識

更新日:2021年8月24日(初回投稿)
著者:東京都立大学 経済経営学部 教授 渡辺 隆裕

第2回から第4回までは、じゃんけんのようにプレイヤーが同時に行動する戦略形ゲームを解説しました。今回は、将棋や囲碁のようにプレイヤーが順番に行動する展開形ゲームについて説明します。まず、展開形ゲームがゲームの木で表されること、そして、最も簡単な完全情報の展開形ゲームと、その解き方であるバックワードインダクションについて解説します。さらに、一般的な展開形ゲームの解である部分ゲーム完全均衡という考え方についても紹介します。

1. 展開形ゲームとゲームの木

戦略形ゲームとは、じゃんけんのようにプレイヤーが同時に行動するゲームでした。
一方、展開形ゲームは、以下の2つの特徴を持ちます。

  • プレイヤーが行動するタイミングが異なってもよい
  • プレイヤーが他のプレイヤーの行動を知っているかどうかの情報構造も扱える

最も簡単な展開形ゲームは、完全情報ゲームと呼ばれています。将棋や囲碁のようにプレイヤーが順番に行動し、自分より前に行動したプレイヤーが何を選んだかが全て分かるゲームです。ここでは、以下の例を考えてみましょう。これは、第3回の戦略形ゲームで用いた例について、プレイヤーが同時ではなく先手・後手という順番で行動するとして、設定を変えたものです。

・完全情報ゲームの例(一ノ瀬と二子山の出店戦略)

和菓子店一ノ瀬と二子山は、A地区かB地区のどちらかに支店を出そうと考えています。A地区とB地区に別々に出店すれば各地区の客を独占でき、1日の売上はそれぞれ12万円と8万円になります。しかし、同じ地区に出店すると、各地区の客を奪い合い、売上はその半分になってしまいます。ここで、まず一ノ瀬がどちらに出店するかを決め、二子山はそれを知ってから出店することを決めるとすると、一ノ瀬と二子山はどちらに出店するでしょうか?

戦略形ゲームが利得行列と呼ばれる表で表されるのに対し、展開形ゲームはゲームの木と呼ばれる図で表します。図1にゲームの木を示します。ゲームの木は、点と枝からできています。点は、各プレイヤーが行動するタイミングを表す「意思決定点」と、ゲームの終わりに対応する「終点」の2種類があります。枝は、意思決定点で各プレイヤーが選ぶ行動に対応し、そこで選んだ点とその次の点を結ぶ線です。1番最初に行動するプレイヤーの意思決定点は、「初期点」と呼ばれます(図1では1番左の点x1)。終点には、全プレイヤーの利得が書かれています。

図1:ゲームの木

図1:ゲームの木

2. バックワードインダクション

バックワードインダクションとは、時間的に後から行動するプレイヤーの行動からさかのぼって完全情報ゲームの解を導く方法です(図2、図3)。ゲームの木において、各プレイヤーは何を選び、どのような結果になると考えられるでしょうか? ゲーム理論では、展開形ゲームにおいても戦略形ゲームと同様に、各プレイヤーは相手の行動を推測した上で、自分の利得が最も高くなる行動を選ぶと考えます。

例えば、先手の一ノ瀬は、自分の選択に対してその後の二子山がどのように行動するかを予測し、行動を選ぶと考えます。そこで、まず後手の二子山の行動を考えてみましょう。二子山は、点x2(一ノ瀬がA地区に立地した場合)においては、B地区を選択する(利得8)方が、A地区を選択する(利得6)より利得が高いためB地区を選びます。一方、点x3(一ノ瀬がB地区に立地した場合)においては、A地区を選択する(利得12)方が、B地区を選択する(利得4)よりも利得が高いためA地区を選びます(図2)。

図2:バックワードインダクション1

図2:バックワードインダクション1

これをもとにして、先手の点x1での一ノ瀬の選択を考えます。一ノ瀬は、A地区を選択したときに、後手の二子山が点x2でB地区を選択するので、結果として利得が12となることが推測できます。また、一ノ瀬は、B地区を選択したときに、後手の二子山が点x3でA地区を選択するので、結果として利得が8となることが推測できます。従って、一ノ瀬はA地区に立地することが最適な選択となります。このとき、二子山はB地区を選択するので、これがゲームの結果となります。(図3

図3:バックワードインダクション2

図3:バックワードインダクション2

このように、プレイヤーは自分の後から行動するプレイヤーの行動を先読みして、自分の行動を決めます。将棋や囲碁で、プレイヤーが自分の指した手に対して、相手がどう行動するか、そして、さらに自分がどう行動するかを推測することと同じです。一般的に、ゲームを解くためには、まず最後に行動するプレイヤーの最適な行動を決定します。次に、その前に行動するプレイヤーは、その後に行動するプレイヤーの行動が決まっているため、それをもとにして、最適な行動を決定します。次に、さらにその前のプレイヤーは…と続きます。このように、時間的に後手のプレイヤーの行動から、前にさかのぼってプレイヤーの行動を決定していき、最後に初期点のプレイヤーの行動を決定します。この解き方をバックワードインダクションと呼びます。

3. 不完全情報ゲームと部分ゲーム完全均衡

続きは、保管用PDFに掲載中。ぜひ、下記よりダウンロードして、ご覧ください。