ベイジアンゲーム

ゲーム理論において、ベイジアンゲームは、プレイヤーが不完全な情報を持っていると仮定する戦略的意思決定モデルです。プレイヤーはゲームに関連する個人情報を持っている可能性があり、その場合、報酬は共通の知識ではありません。^{[1]ベイジアンゲームは、}ベイジアン確率の側面を使用してプレイヤーの相互作用の結果をモデル化します。ゲーム理論で初めて、不完全な情報を持つゲームのソリューションの指定を可能にした点で注目に値します。

ハンガリーの経済学者ジョン・C・ハルサニは、1967年と1968年の3つの論文でベイジアンゲームの概念を導入しました。^{[2] [3] [4]}彼は、これらの論文とゲーム理論へのその他の貢献により、1994年にノーベル経済学賞を受賞しました。 大まかに言えば、ハルサニはベイジアンゲームを次のように定義しました。 プレイヤーには、ゲームの開始時に一連の特性が自然に割り当てられます。これらの特性に確率分布をマッピングし、ベイジアン確率を使用してゲームの結果を計算すると、技術的な理由により、非ベイジアンコンテキストでの同様のゲームよりもはるかに簡単に解を計算できるゲームが得られます。 技術的な理由については、この記事の「ゲームの仕様」セクションを参照してください。

ベイジアンゲームは(N,A,T,p,u)で定義され、以下の要素から構成される: ^[5]

1. プレイヤーの集合、N :ゲーム内のプレイヤーの集合
2. アクションセット、a _i :プレーヤーiが実行できるアクションのセット。アクションプロファイルa = (a ₁ , . . . , a _N )は、各プレーヤーに 1 つずつ割り当てられるアクションのリストです。
3. タイプセット、t _i :プレイヤーiのタイプの集合。「タイプ」はプレイヤーが持つことができる個人情報を捕捉します。タイププロファイルt = (t ₁ , . . . , t _N )は、各プレイヤーに 1 つずつ存在するタイプのリストです。
4. ペイオフ関数u :プレイヤーのタイプと行動プロファイルに基づいてプレイヤーにペイオフを割り当てる。ペイオフ関数u=(u ₁ , . . . , u _N )はプレイヤーiの効用を表す。
5. 事前、p :すべての可能なタイプ プロファイルの確率分布。ここで、p(t) = p(t ₁、...、t _N )は、プレーヤー 1 がタイプt ₁を持ち、プレーヤーNがタイプt _Nを持つ確率です。

戦略ゲームにおいて、純粋戦略とは、プレイヤーが決定を下さなければならない各ポイントにおけるプレイヤーの行動の選択である。^[6]

ベイジアン ゲームには 3 つの段階があり、それぞれがゲーム内の型に関するプレイヤーの知識を表します。

1. 事前段階のゲーム。プレイヤーは自分のタイプや他のプレイヤーのタイプを知りません。プレイヤーは、すべての可能なタイプの事前分布に基づいて、期待値としてペイオフを認識します。
2. 中間段階のゲーム。プレイヤーは自分のタイプを知っていますが、他のプレイヤーの確率分布しか知りません。プレイヤーは、報酬を検討するときに、他のプレイヤーのタイプの期待値を調べます。
3. 事後段階のゲーム。プレイヤーは自分のタイプと他のプレイヤーのタイプを知っている。報酬はプレイヤーに知られている。^[7]

ベイジアン ゲームには、ハーサニによって定義された 2 つの重要かつ斬新な側面があります。^[8] 1 つ目は、ベイジアン ゲームは完全情報ゲームと同じように考えられ、構造化される必要があるということです。ただし、確率をゲームに付加することで、最終的なゲームは不完全情報ゲームのように機能します。したがって、プレイヤーは本質的に不完全情報を持つものとしてモデル化でき、ゲームの確率空間は依然として全確率の法則に従います。ベイジアン ゲームは、無限の連続計算を必要としないという点でも便利です。無限の連続計算は、プレイヤーが (本質的に)「お互いの頭の中に入っていこう」とするときに発生します。たとえば、質問をして、「プレイヤー B の何らかの行動を期待する場合、プレイヤー B は私がその行動を期待することを予測するだろうから、私はその予測を予測するべきだ」と無限に決定することができます。ベイジアン ゲームでは、異なる結果に異なる確率の重みを同時に割り当てることで、1 回の手順でこれらの結果を計算できます。この効果により、ベイジアン ゲームでは、非ベイジアン設定では計算するのが不可能な多数のゲームをモデル化できるようになります。

ベイジアン ゲームのベイジアン ナッシュ均衡は、関連する事前正規形ゲームのナッシュ均衡です。

非ベイジアン ゲームでは、戦略プロファイル内のすべての戦略がプロファイル内の他のすべての戦略に対する最適な応答である場合、その戦略プロファイルはナッシュ均衡です。つまり、他のプレイヤーがプレイするすべての戦略を考慮すると、より高い報酬を得られる戦略はプレイヤーがプレイできません。

類似の概念はベイジアン ゲームにも定義できますが、違いは、各プレイヤーの戦略が自然状態に関する信念に基づいて期待される利益を最大化するという点です。自然状態に関するプレイヤーの信念は、ベイズの法則に従って、プレイヤー自身のタイプに基づいて事前確率を条件付けすることによって形成されます。 ${\displaystyle p}$

ベイジアン・ナッシュ均衡（BNE）は、各プレイヤーの信念と他のプレイヤーが採用した戦略を前提として、各プレイヤーの期待利益を最大化する戦略プロファイルとして定義されます。つまり、戦略プロファイルがベイジアン・ナッシュ均衡となるのは、各プレイヤーが他のすべてのプレイヤーの戦略を固定したまま、戦略がそのプレイヤーの信念に従ってプレイヤーの期待利益を最大化する場合に限ります。 ^[5]${\displaystyle \sigma }$${\displaystyle i,}$${\displaystyle \sigma _{i}}$${\displaystyle i}$

有限ベイジアンゲーム、すなわちアクションとタイプ空間の両方が有限である場合、2 つの同等の表現が存在します。1 つ目はエージェント形式ゲームと呼ばれ (ゲーム理論の本^[9]の定理 9.51 を参照)、プレーヤーの数を から に拡張します。つまり、各プレーヤーのすべてのタイプがプレーヤーになります。2 つ目は誘導正規形と呼ばれ (マルチエージェントシステム^[10]のセクション 6.3.3 を参照)、プレーヤーはまだ存在しますが、各プレーヤー i のアクションの数を から に拡張します。つまり、純粋なポリシーは、プレーヤーが異なるタイプに対して実行する必要があるアクションの組み合わせです。ナッシュ均衡 (NE) は、これら 2 つの同等の表現で計算でき、BNE は NE から復元できます。 ${\displaystyle |N|}$${\textstyle \sum _{i=1}^{|N|}|\Theta _{i}|}$${\displaystyle |N|}$${\displaystyle |A_{i}|}$${\textstyle |A_{i}|^{|\Theta _{i}|}}$

• ゼロサム目的関数を持つ2人のプレイヤーを考えてみましょう。BNEを計算するために線形計画法を形成できます。^[11]

完全情報または不完全情報を用いた拡張形式ゲームには、以下の要素があります。^[12]

1. プレイヤーのセット
2. 決定ノードのセット
3. 各決定ノードにプレイヤーを割り当てるプレイヤー関数
4. 各プレイヤーのそれぞれの決定ノードにおける一連のアクション
5. ターミナルノードのセット
6. 各プレイヤーの報酬関数

自然のノードは通常、塗りつぶされていない円で示されます。その戦略は常に指定されており、常に完全に混合されています。通常、自然はツリーのルートにありますが、自然は他のポイントにも移動できます。

プレイヤーiの情報セットは、プレイヤーi が区別できない決定ノードのサブセットです。つまり、プレイヤーi が情報セット内の決定ノードの 1 つにいる場合、情報セット内のどのノードにいるのかはわかりません。

2つの決定ノードが同じ情報セットに存在するためには、^[13]

1. 同じプレイヤーに属していること。
2. 同じ一連のアクションを実行する

情報セットは点線で示されます。これは現在最も一般的な表記法です。

ベイジアンゲームでは、ゲームに関するプレイヤーの信念は、さまざまな種類の確率分布によって表されます。

プレイヤーが個人情報を持っていない場合、タイプ間の確率分布は共通事前分布と呼ばれます。^[1]

拡張形式ゲームの評価はペア<b, μ>である。

1. 行動戦略プロファイル
2. 信念体系

評価<b, μ>がベイズの定理を満たすのは、^[14] μ(x|h _{i ) = Pr[b−i が与えられたらxに到達する] / Σ Pr[b −i}が与えられたらx'に到達する]であり、 b _−iに従ってh _iが厳密に正の確率で到達するときはいつでもそうである。

拡張形式ゲームにおける完全なベイズ均衡とは、以下の2つの条件が満たされるような戦略と信念の組み合わせである。^[15]

1. ベイズの一貫性: 信念は検討中の戦略と一致している。
2. 順次合理性: プレイヤーは自分の信念に基づいて最適な選択を行います。

ベイジアン ナッシュ均衡は、プレイヤーが同時ではなく順番に動くダイナミック ゲームでは、あり得ない均衡をもたらす可能性があります。完全情報ゲームと同様に、均衡経路から外れた信頼できない戦略によって、このような均衡が生じる可能性があります。不完全情報ゲームでは、信頼できない信念が生じる可能性もあります。

これらの問題に対処するために、サブゲーム完全均衡によれば、完全ベイズ均衡では、任意の情報セットから始めて、その後のプレイが最適になることが求められます。また、正の確率で発生するすべてのプレイ パスで、ベイズのルールに従って信念が一貫して更新されることが求められます。

確率的ベイジアンゲーム^[16]は、ベイジアンゲームの定義と確率的ゲームの定義を組み合わせて、状態間の確率的遷移と各状態のさまざまなプレーヤーのタイプに関する不確実性を伴う環境状態（物理世界の状態など）を表します。結果として得られるモデルは、ベイジアンナッシュ均衡とベルマン最適性方程式の再帰的組み合わせによって解決されます。確率的ベイジアンゲームは、防衛およびセキュリティ計画、^[17]、発電所のサイバーセキュリティ、^[18]、自動運転、^[19]、モバイルエッジコンピューティング、^[20]、動的システムの自己安定化、^[21]、クラウドソーシングIoTにおける不正行為の処理など、さまざまな問題の解決に使用されています。^[22]

ベイジアンゲームとベイジアン均衡の定義は、集団的エージェンシーを扱うために拡張されてきた。一つのアプローチは、個々のプレイヤーを孤立した推論者として扱い続けるが、ある程度の確率で集団の観点から推論できるようにすることである。^[23]もう1つのアプローチは、集団的エージェント内のプレイヤーはエージェントの存在を知っているが、他のプレイヤーはそれを知らないが、ある程度の確率でそれを疑っていると仮定するものである。^[24]たとえば、アリスとボブは、自然の状態に応じて、時には個人として最適化し、時にはチームとして共謀するかもしれないが、他のプレイヤーはどちらが当てはまるかわからないかもしれない。

保安官が武装した容疑者と対峙する。両者は同時に相手を撃つかどうかを決めなければならない。

容疑者は「犯罪者」または「民間人」のいずれかのタイプになります。保安官のタイプは 1 つだけです。容疑者は自分のタイプと保安官のタイプを知っていますが、保安官は容疑者のタイプを知りません。したがって、不完全な情報があり(容疑者は個人情報を持っているため)、ベイジアン ゲームになります。容疑者が犯罪者である確率はp で、容疑者が民間人である確率は1-pです。両方のプレイヤーはこの確率を認識しています (共通の事前仮定。これは不完全な情報を持つ完全情報ゲームに変換できます)。

保安官は、容疑者が発砲した場合は身を守るために発砲し、容疑者が発砲しない場合は（容疑者が犯罪者であっても）発砲しないでしょう。容疑者は、たとえ保安官が発砲しなくても自分が犯罪者であれば発砲するでしょうが、たとえ保安官が発砲しても自分が民間人であれば発砲しないでしょう。したがって、この正規形ゲームの両プレイヤーの利得行列は、容疑者のタイプによって異なります。このゲームは、 （N、A、T、p、u）で定義されます。ここで、

• N = {容疑者、保安官}
• _容疑者= {撃つ、撃たない}、_保安官= {撃つ、撃たない}
• T_容疑者= {犯罪者、民間人} 、 T_保安官= {*}
• p_犯罪者= p、p_民間人= (1 - p)
• ペイオフu は次のように与えられると仮定します。

両プレイヤーが合理的であり、両プレイヤーが合理的であることを知っており、どのプレイヤーが知っていることはすべてどのプレイヤーも知っているとわかっている場合（つまり、プレイヤー1はプレイヤー2がプレイヤー1が合理的であることを知っていることを知っており、プレイヤー2もこれを知っているなど、無限に続く共通知識）、ゲームにおけるプレイは完全なベイズ均衡に従って次のようになる：^{[25] [26]}

タイプが「犯罪者」の場合、容疑者にとっての優位戦略は発砲することであり、タイプが「民間人」の場合、容疑者にとっての優位戦略は発砲しないことです。したがって、代替の厳密に優位な戦略は削除できます。これを考慮すると、保安官が発砲した場合、確率pでペイオフ 0 、確率1-pでペイオフ -1 、つまり期待ペイオフはp-1になります。保安官が発砲しない場合、確率pでペイオフ -2 、確率1-pでペイオフ 0 、つまり期待ペイオフは-2pになります。したがって、 p-1 > -2pの場合、つまりp > 1/3の場合、保安官は常に発砲します。

「レモン市場」は、逆選択として知られる概念に関連しています。

設定

中古車があります。プレイヤー 1 は、その車に興味を持っている潜在的な購入者です。プレイヤー 2 は車の所有者であり、車の価値 v (車がどのくらい優れているかなど) を知っています。プレイヤー 1 はそれを知らず、所有者 (プレイヤー 2) にとっての車の価値 v は 0 から 100 の間で均一に分布していると考えています (つまり、長さが等しい 2 つの値サブ区間 [0, 100] のそれぞれが同等の確率で存在する)。

プレイヤー 1 は 0 から 100 (両端を含む) の間で入札 p を行うことができます。その後、プレイヤー 2 はオファーを受け入れるか拒否することができます。支払いは次のようになります。

• プレイヤー1の報酬: 入札受諾は3/2v-p、入札拒否は0
• プレイヤー2の利益: 入札が受け入れられた場合はp、入札が拒否された場合はv

サイドポイント：カットオフ戦略

プレイヤー 2 の戦略: 特定のカットオフP* を超える入札はすべて受け入れ、P* を下回る入札は拒否して入札する。これはカットオフ戦略と呼ばれ、P*はカットオフと呼ばれます。

• 取引されるのは「レモン」（状態の悪い中古車、具体的には価値が最大でpに等しいもの）のみである。
• プレイヤー1は0を入札することで報酬0を保証できるため、均衡状態ではp = 0となる。
• 状態の悪い中古車だけが取引されるため、市場は崩壊する
• 貿易が経済的に効率的である場合でも、貿易は不可能である^[27]

大企業が独占している市場に参入したい新規企業 (プレイヤー 1) は、2 種類の独占企業 (プレイヤー 2) に遭遇します。タイプ 1 は阻止され、タイプ 2 は許可されます。プレイヤー 1 はプレイヤー 2 に関する完全な情報を得ることはできませんが、以前の企業が市場に参入した際に阻止されたかどうかから、タイプ 1 とタイプ 2 が出現する確率を推測することはできます。これはベイジアン ゲームです。これらの判断を行う理由は、プレイヤー 2 には阻止コストがあり、プレイヤー 1 の市場参入を阻止するために大幅な値下げが必要になる可能性があるため、市場参入によって奪う利益が阻止コストよりも大きい場合にプレイヤー 1 を阻止するからです。

• ベイズ最適メカニズム
• ベイズ最適価格設定
• ベイジアンプログラミング
• ベイズ推論

• ギボンズ、ロバート（1992）。応用経済学者のためのゲーム理論。プリンストン大学出版局。pp. 144–52。ISBN 1400835887。
• レビン、ジョナサン (2002) 「不完全な情報を伴うゲーム」(PDF) 。2016 年8 月 25 日閲覧。