潜在的なゲーム

ゲーム理論では、すべてのプレイヤーが戦略を変更するインセンティブが、ポテンシャル関数と呼ばれる単一のグローバル関数を使用して表現できる場合、そのゲームはポテンシャルゲームであると言われます。この概念は、1996年にDov MondererとLloyd Shapleyによる論文で生まれました。^[1]

それ以来、いくつかの種類のポテンシャル ゲームの特性が研究されてきました。ゲームは、順序ポテンシャル ゲームまたは基数ポテンシャル ゲームのいずれかになります。基数ゲームでは、他の条件が同じであれば、各プレイヤーが個別に戦略を変更することで得られる個々の報酬の差は、ポテンシャル関数の値の差と同じ値でなければなりません。順序ゲームでは、差の符号のみが同じでなければなりません。

ポテンシャル関数は、すべてのプレイヤーのインセンティブが 1 つの関数にマッピングされ、ポテンシャル関数の局所最適値を見つけることで純粋なナッシュ均衡のセットを見つけることができるため、ゲームの均衡特性を分析するのに役立つツールです。反復ゲームのナッシュ均衡への収束と有限時間収束も、ポテンシャル関数を研究することで理解できます。

ポテンシャルゲームは、プレイされる各ラウンドが次のラウンドのゲームの状態に直接影響を与えるような状態を持つ繰り返しゲームとして研究することができます。 ^[2]このアプローチは、分散リソース割り当てなどの分散制御に応用されており、中央相関メカニズムを持たないプレイヤーが協力して、全体的に最適なリソース配分を実現できます。

プレイヤーの数を 、各プレイヤーのアクション セット上のアクション プロファイルの集合を、プレイヤーのペイオフ関数を とします。 ${\displaystyle N}$${\displaystyle A}$${\displaystyle A_{i}}$${\displaystyle u_{i}:A\to \mathbb {R} }$${\displaystyle 1\leq i\leq N}$

ゲーム が与えられたとき、 がに対する正確な（それぞれ重み付き、順序付き、一般化順序付き、最良応答）ポテンシャル関数である場合、 は正確な（重み付き、順序付き、一般化順序付き、最良応答）ポテンシャル関数を持つポテンシャルゲームであると言う。ここで、はと呼ばれる 。${\displaystyle G=(N,A=A_{1}\times \ldots \times A_{N},u:A\rightarrow \mathbb {R} ^{N})}$${\displaystyle G}$${\displaystyle \Phi :A\rightarrow \mathbb {R} }$${\displaystyle G}$${\displaystyle \Phi}$

• 正確なポテンシャル関数の場合 、${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})=u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})}$

つまり、プレイヤーがアクションを切り替えると、ポテンシャルの変化はそのプレイヤーの効用の変化に等しくなります。${\displaystyle i}$${\displaystyle a'}$${\displaystyle a''}$${\displaystyle \Phi}$

• 重み付きポテンシャル関数は、ベクトルが存在する場合に、${\displaystyle w\in \mathbb {R} _{++}^{N}}$${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})=w_{i}(u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i}))}$つまり、プレイヤーがアクションを切り替えると、 の変化は、プレイヤーの効用における変化に、プレイヤー固有の正の重みを掛けたものに等しくなります。すべての正確な PF は、すべてのiに対してw _i =1となる重み付き PF です。${\displaystyle \Phi}$

• 順序ポテンシャル関数の場合 、${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})>0\Leftrightarrow \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})>0}$つまり、プレイヤーがアクションを切り替えると、変化の符号はプレイヤーの効用の変化の符号と等しくなりますが、変化の大きさは異なる場合があります。すべての加重 PF は順序 PF です。${\displaystyle \Phi}$

• 一般化された順序ポテンシャル関数の場合、${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})>0\Rightarrow \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})>0}$つまり、プレイヤーがアクションを切り替えると、プレイヤーの効用が増加する場合、潜在的可能性も増加します (ただし、その逆は必ずしも真ではありません)。すべての順序 PF は、一般化順序 PF です。

• 最良応答ポテンシャル関数の場合 、${\displaystyle \forall i\in N,\ \forall {a_{-i}\in A_{-i}}}$

${\displaystyle b_{i}(a_{-i})=\arg \max _{a_{i}\in A_{i}}\Phi (a_{i},a_{-i})}$プレイヤーにとって最善のアクションはどこにあるでしょうか。${\displaystyle b_{i}(a_{-i})}$${\displaystyle i}$${\displaystyle a_{-i}}$

プレイヤーごとに 1 つずつ効用関数があるのに対し、潜在的関数は 1 つしかないことに注意してください。したがって、潜在的関数のレンズを通して見ると、プレイヤーは交換可能になります (上記の定義の 1 つの意味で)。ゲームのこの対称性により、共有潜在的関数に基づく分散アルゴリズムは、多くの場合、ナッシュ均衡に収束します (ある意味で)。 ${\displaystyle N}$

外部性を持つ 2 人のプレイヤー、2 つのアクションのゲームでは、個々のプレイヤーの利得は関数u _i ( a _i、a _j ) = b _i a _i + w a _i a _jで与えられます。ここで、a _iはプレイヤー i のアクション、a _jは対戦相手のアクション、w は同じアクションを選択することで得られる正の外部性です。アクションの選択肢は、図 1 の利得マトリックスに示されているように、+1 と -1 です。

このゲームには、潜在的な関数P ( a ₁ , a ₂ ) = b ₁ a ₁ + b ₂ a ₂ + w a ₁ a ₂があります。

プレイヤー1が-1から+1に移動する場合、支払いの差はΔ u ₁ = u ₁ (+1, a ₂ ) – u ₁ (–1, a ₂ ) = 2 b ₁ + 2 w a ₂となります。

電位の変化はΔP = P(+1, a ₂ ) – P(–1, a ₂ ) = ( b ₁ + b ₂ a ₂ + w a ₂ ) – (– b ₁ + b ₂ a ₂ – w a ₂ ) = 2 b ₁ + 2 w a ₂ = Δ u _{1 です}。

プレイヤー2の解は同等です。数値b ₁  = 2、b ₂  = −1、w  = 3を使用すると、この例は図2に示すように単純な男女の戦いに変換されます。ゲームには、(+1, +1)と(−1, −1)という2つの純粋なナッシュ均衡があります。これらは、ポテンシャル関数の局所的最大値でもあります (図3)。確率的に安定した均衡は、ポテンシャル関数のグローバル最大値 である(+1, +1)のみです。

2人プレイ、2アクションのゲームは、以下の条件を満たさない限り、潜在的なゲーム にはなり得ない。

${\displaystyle [u_{1}(+1,-1)+u_{1}(-1,+1)]-[u_{1}(+1,+1)+u_{1}(-1, -1)]=[u_{2}(+1,-1)+u_{2}(-1,+1)]-[u_{2}(+1,+1)+u_{2}(- 1,-1)]}$

正確なポテンシャルゲームは混雑ゲームと同等である。Rosenthal ^{[3]は、すべての}混雑ゲームが正確なポテンシャルを持つことを証明した。MondererとShapley ^[1]は、その逆を証明した。正確なポテンシャル関数を持つすべてのゲームは混雑ゲームである。

改善パス（ナッシュダイナミクスとも呼ばれる）は、戦略ベクトルのシーケンスであり、各ベクトルは、1人のプレーヤーが戦略を、効用を厳密に増加させる戦略に切り替えることによって、前のベクトルから達成されます。ゲームに一般化順序ポテンシャル関数がある場合、すべての改善パスで が厳密に増加するため、すべての改善パスは非巡回です。さらに、ゲームに有限個の戦略がある場合、すべての改善パスは有限でなければなりません。この特性は有限改善特性（FIP）と呼ばれます。すべての有限の一般化順序ポテンシャルゲームにFIPがあることを証明しました。逆もまた真です。つまり、すべての有限ゲームにFIPがあり、一般化順序ポテンシャル関数があります。^{[4] [説明が必要]}すべての有限改善パスの終端状態はナッシュ均衡であるため、FIPは純粋戦略ナッシュ均衡の存在を意味します。さらに、これは、各エージェントが自分の戦略を改善するだけでよい分散プロセスによってナッシュ均衡を計算できることを意味します。 ${\displaystyle \Phi}$${\displaystyle \Phi}$

最善応答パスは改善パスの特殊なケースであり、各ベクトルは、1 人のプレーヤーが戦略を最善応答戦略に切り替えることによって前のベクトルから達成されます。すべての最善応答パスが有限であるという特性は、有限最善応答特性 (FBRP)と呼ばれます。FBRP は FIP よりも弱いですが、それでも純粋戦略ナッシュ均衡の存在を意味します。また、ナッシュ均衡は分散プロセスによって計算できることも意味しますが、エージェントは最善応答を計算する必要があるため、FIP よりも計算負荷が高くなります。

さらに弱い性質は、弱い非循環性（WA）である。^[5]これは、任意の初期戦略ベクトルに対して、そのベクトルから始まる有限の最善の応答パスが存在することを意味する。弱い非循環性は、潜在的関数の存在には十分ではない（一部の改善パスは循環的であるため）が、純粋戦略ナッシュ均衡の存在には十分である。これは、各時点でプレーヤーがランダムに選択され、このプレーヤーが最善の戦略をランダムに選択する確率的分散プロセスによって、ナッシュ均衡がほぼ確実に計算できることを意味する。^[4]

• 混雑ゲーム
• 経済物理学
• 順序ポテンシャルゲームの特徴づけ。^[6]

• ポテンシャルと混雑ゲームに関する Yishay Mansour の講義ノート
• セクション 19: Vazirani、Vijay V.ニサン, ノーム;ティム・ラフガーデン;タルドス、エヴァ(2007)。アルゴリズムゲーム理論(PDF)。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-87282-0。
• ヒュー・ディクソンによる共謀の必然性についての非技術的な解説、第 8 章「ドーナツの世界と複占群島」、サーフィン経済学。