混雑ゲーム

混雑ゲーム(CG) は、ゲーム理論におけるゲームのクラスです。これらは、道路、通信ネットワーク、寡占市場、自然生息地で一般的に発生する状況を表します。リソースのセット (道路や通信リンクなど) があり、リソースを必要とするプレーヤーが複数存在します (ドライバーやネットワーク ユーザーなど)。各プレーヤーはこれらのリソースのサブセット (ネットワーク内のパスなど) を選択します。各リソースの遅延は、このリソースを含むサブセットを選択したプレーヤーの数によって決まります。各プレーヤーのコストは、選択したすべてのリソース間の遅延の合計です。当然、各プレーヤーは自分の遅延を最小限に抑えたいと考えますが、各プレーヤーの選択は他のプレーヤーに負の外部性を課し、非効率的な結果につながる可能性があります。

混雑ゲームの研究は、1973年にアメリカの経済学者ロバート・W・ローゼンタールによって開始されました。 ^{[1]彼は、すべての混雑ゲームが}純粋戦略におけるナッシュ均衡（純粋ナッシュ均衡、PNEとも呼ばれる）を持つことを証明しました。証明の過程で、彼は実際にすべての混雑ゲームが正確なポテンシャルゲームであることを証明しました。後に、モンデラーとシャプレー^[2]は逆の結果、つまり正確なポテンシャル関数を持つゲームは、何らかの混雑ゲームと同等であることを証明しました。その後の研究は、次のような質問に焦点が当てられました。

• 均衡の存在、およびポテンシャル関数の存在は、混雑ゲームのより一般的なモデルにまで拡張されるのでしょうか?
• 混雑ゲームの量的な非効率性とは何ですか?
• 平衡点を見つけるための計算の複雑さはどれくらいですか?

2 人のプレーヤーがポイント から出発し、ポイント に到達する必要がある交通ネットワークについて考えます。右の図に示すように、ノードがノード に- -と- -の 2 つのパスで接続されており、が よりも少し近い(つまり、各プレーヤーが を選択する可能性が高い) とします。 ${\displaystyle O}$${\displaystyle T}$${\displaystyle O}$${\displaystyle T}$${\displaystyle O}$${\displaystyle A}$${\displaystyle T}$${\displaystyle O}$${\displaystyle B}$${\displaystyle T}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$

両方の接続ポイントからの道路は混雑しやすいため、ポイントを通過するプレーヤーが増えるほど、各プレーヤーの遅延が大きくなり、両方のプレーヤーが同じ接続ポイントを通過すると余分な遅延が発生します。正式には、プレーヤーがそこに行くときのおよびのそれぞれの遅延は です。 ${\displaystyle T}$${\displaystyle A}$${\displaystyle T}$${\displaystyle B}$${\displaystyle T}$${\displaystyle x}$${\displaystyle x^{2}}$

このゲームで良い結果は、2 人のプレイヤーが「調整」して、異なる接続ポイントを通過することです。そのような結果は達成できるでしょうか?

次のマトリックスは、プレイヤーの選択に応じて遅延に関してプレイヤーのコストを表します。

このゲームにおける純粋なナッシュ均衡は(OAT,OBT) と (OBT,OAT) です。つまり、プレイヤーの 1 人による一方的な変更は、そのプレイヤーのコストを増加させます (表の値はコストであるため、プレイヤーは値が小さいことを好むことに注意してください)。この例では、ナッシュ均衡は効率的です。プレイヤーは異なるレーンを選択し、コストの合計は最小になります。

対照的に、プレイヤーがそこに行ったときのおよび のそれぞれの遅延が であると仮定します。この場合、コスト マトリックスは次のようになります。 ${\displaystyle A}$${\displaystyle T}$${\displaystyle B}$${\displaystyle T}$${\displaystyle x}$${\displaystyle 0.8x}$

現在、唯一の純粋なナッシュ均衡は (OAT,OAT) です。つまり、OBT に切り替えるプレーヤーは、コストが 2.6 から 2.8 に増加します。均衡はまだ存在しますが、効率的ではありません。コストの合計は 5.2 ですが、(OAT,OBT) と (OBT,OAT) のコスト合計は 4.6 です。

CG の基本的な定義には、次のコンポーネントが含まれます。

• 混雑要素の基本セット（リソースまたは要因とも呼ばれます）。上記の例では、は道路のセット（、、および）です。${\displaystyle E}$${\displaystyle E}$${\displaystyle O}$${\displaystyle A}$${\displaystyle A}$${\displaystyle T}$${\displaystyle O}$${\displaystyle B}$${\displaystyle B}$${\displaystyle T}$
• プレイヤーのセット。上記の例では。${\displaystyle n}$${\displaystyle n=2}$
• 各プレイヤーの戦略の有限集合。各戦略はのサブセットです。 ${\displaystyle S_{i}}$${\displaystyle P\in S_{i}}$${\displaystyle E}$
  • 上記の例では、両方のプレイヤーが同じ戦略セットを持っています。すべてのプレイヤーが同じ戦略セットを持っている CG は、対称 CGと呼ばれます。一般に、各プレイヤーが異なるソースや異なるターゲットを持っている場合など、異なるプレイヤーが異なるセットを持つことがあります。このような CG は非対称CGと呼ばれます。${\displaystyle S_{1}=S_{2}=\{\{OA,AT\},\{OB,BT\}\}}$
  • 一般に、戦略は の任意のサブセットになります。戦略が特定のグラフ内のパスのみになる CG (上記の例のように) は、ネットワーク CGと呼ばれます。戦略が単一のリソースのみになる CG は、シングルトン CGと呼ばれます。${\displaystyle E}$
• 各要素と戦略のベクトルに対して、負荷はと定義されます。${\displaystyle e\in E}$${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$${\displaystyle x_{e}=\#\{i:e\in P_{i}\}}$
• 各要素には遅延関数（レイテンシ関数またはコスト関数とも呼ばれる）があります。戦略のベクトルが与えられた場合、遅延はです。それぞれは正で単調に増加すると想定されます。${\displaystyle e\in E}$ ${\displaystyle d_{e}:\mathbb {N} \longrightarrow \mathbb {R} }$${\displaystyle e}$${\displaystyle d_{e}(x_{e})}$${\displaystyle d_{e}}$
• 戦略が与えられると、プレイヤーは遅延を経験します。各プレイヤーは遅延を最小限に抑えたいと考えます。${\displaystyle P_{i}}$${\displaystyle i}$${\displaystyle \textstyle \sum _{e\in P_{i}}d_{e}(x_{e})}$
• ナッシュ均衡とは、各プレイヤーについて、を別の戦略に置き換えても、 が経験する遅延が減少しないような戦略のベクトルです。${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$${\displaystyle i}$${\displaystyle P_{i}}$${\displaystyle Q_{i}}$${\displaystyle i}$

すべてのCGは、純粋戦略においてナッシュ均衡を持ちます。これは、各結果に値を割り当てるポテンシャル関数を構築することで示されます。 ^{[1]さらに、この構築により、反復}最善の応答がナッシュ均衡を見つけることも示されます。 を定義します。この関数は社会福祉ではなく、一種の離散積分であることに注意してください。混雑ゲームのポテンシャル関数の重要な特性は、1人のプレーヤーが戦略を切り替えると、遅延の変化がポテンシャル関数の変化に等しいことです。 ${\displaystyle \textstyle \Phi =\sum _{e\in E}\sum _{k=1}^{x_{e}}d_{e}(k)}$${\displaystyle \textstyle \sum _{e\in E}x_{e}d_{e}(x_{e})}$

プレーヤーがからに切り替える場合を考えてみましょう。両方の戦略にある要素は影響を受けず、プレーヤーが離れる要素 (つまり) はポテンシャルを だけ減少させ、プレーヤーが参加する要素 (つまり) はポテンシャルを だけ増加させます。このポテンシャルの変化は、プレーヤー の遅延の変化とまったく同じであるため、実際には はポテンシャル関数です。 ${\displaystyle i}$${\displaystyle P_{i}}$${\displaystyle Q_{i}}$${\displaystyle e\in P_{i}-Q_{i}}$${\displaystyle d_{e}(x_{e})}$${\displaystyle e\in Q_{i}-P_{i}}$${\displaystyle d_{e}(x_{e}+1)}$${\displaystyle i}$${\displaystyle \Phi}$

ここで、 の最小値は純粋なナッシュ均衡であることに注意してください。 1 人のプレーヤーを除くすべてのプレーヤーを固定すると、そのプレーヤーの戦略の改善は の減少に対応しますが、これは最小値では発生しません。 ここで、構成の数は有限であり、それぞれが単調であるため、均衡が存在します。 ${\displaystyle \Phi}$${\displaystyle \Phi}$${\displaystyle d_{e}}$

潜在的関数の存在には、有限改善特性 (FIP)と呼ばれる追加の意味があります。任意の戦略ベクトルから始めて、プレーヤーを任意に選択し、そのプレーヤーが戦略を自分にとってより良い戦略に変更できるようにし、これを繰り返すと、改善のシーケンスは有限である必要があります (つまり、シーケンスは循環しません)。これは、このような改善のそれぞれが潜在的可能性を厳密に増加させるためです。

以下では、基本的な CG モデルのさまざまな拡張とバリエーションを紹介します。

非原子的（連続的とも呼ばれる）CGは、 n人のプレイヤーがいる標準的なCGの極限であり、 である。プレイヤーの連続体があり、プレイヤーは「無限に小さい」と考えられ、各プレイヤーは混雑にほとんど影響を与えない。非原子的CGは、Milchtaich、^[3]、 Friedman ^{[4] 、Blonsky [ 5]}によって研究された。 [6]${\displaystyle n\rightarrow \infty}$

• 輻輳可能な要素の有限セットを保持します。${\displaystyle E}$
• 離散的な場合のようにプレーヤーを認識する代わりに、プレーヤーのタイプがあり、各タイプにはそのタイプのトラフィックのレートを表す数値が関連付けられています。${\displaystyle n}$${\displaystyle n}$ ${\displaystyle i}$${\displaystyle r_{i}}$
• タイプiの各エージェントは戦略セットから戦略を選択します。${\displaystyle S_{i}}$
• 以前と同様に、遅延関数は単調かつ正ですが、ここでは遅延関数が連続的であるという仮定も追加します。${\displaystyle d_{e}}$
• タイプのプレイヤーが戦略セットに部分的に配分することを許可します。つまり、すべての戦略 に対して、が戦略 を使用するタイプのプレイヤーの割合を表すものとします。定義により、 となります。${\displaystyle P\in S_{i}}$${\displaystyle f_{P}}$${\displaystyle i}$${\displaystyle P}$${\displaystyle \textstyle \sum _{P\in S_{i}}f_{P}=r_{i}}$
• 各要素について、負荷はe を使用するプレーヤーの割合の合計、つまりとして定義されます。${\displaystyle e\in E}$${\displaystyle x_{e}=\sum _{P\ni e}f_{P}}$

戦略は戦略プロファイルの集合になりました。サイズ の戦略セットの場合、すべての有効なプロファイルの集合はのコンパクトなサブセットです。ここで、離散積分を標準積分に置き換えて、ポテンシャル関数を と定義します。 ${\displaystyle f_{P}}$${\displaystyle S_{i}}$${\displaystyle n}$${\displaystyle [0,r_{i}]^{n}}$${\displaystyle \textstyle \Phi =\sum _{e\in E}\int _{0}^{x_{e}}d_{e}(z)\,dz}$

戦略の関数として、は連続しています。仮定により、は連続しており、戦略の連続関数です。次に、極値定理により、は大域的最小値を達成します。 ${\displaystyle \Phi}$${\displaystyle d_{e}}$${\displaystyle x_{e}}$${\displaystyle \Phi}$

最後のステップは、 の最小値が確かにナッシュ均衡であることを示すことです。矛盾のため、 を最小化するがナッシュ均衡ではないの集合が存在すると仮定します。すると、何らかのタイプの に対して、現在の選択よりも改善された が存在します。つまり、 です。ここでのアイデアは、戦略 を使用している少数のプレイヤーを戦略 に移動させることです。これで、任意の に対して、その負荷を だけ増加させたので、 における の項はになりました。積分を微分すると、この変化はおよそ で、誤差 です。 のエッジを見ると、変化の同等の分析が成り立ちます。 ${\displaystyle \Phi}$${\displaystyle f_{P}}$${\displaystyle \Phi}$${\displaystyle i}$${\displaystyle Q\in S_{i}}$${\displaystyle P}$${\displaystyle \textstyle \sum _{e\in Q}d_{e}(x_{e})<\sum _{e\in P}d_{e}(x_{e})}$${\displaystyle \delta <f_{P}}$${\displaystyle P}$${\displaystyle Q}$${\displaystyle x_{e}\in Q}$${\displaystyle \delta}$${\displaystyle \Phi}$${\displaystyle \textstyle \int _{0}^{x_{e}+\delta }d_{e}(z)dz}$${\displaystyle \delta \cdot d_{e}(x_{e})}$${\displaystyle \delta^{2}}$${\displaystyle P}$

したがって、ポテンシャルの変化はおよそ で、これはゼロより小さい。これは、 が最小化されていないため矛盾している。したがって、 の最小値はナッシュ均衡でなければならない。 ${\displaystyle \textstyle \delta (\sum _{e\in Q}d_{e}(x_{e})-\sum _{e\in P}d_{e}(x_{e}))}$${\displaystyle \Phi}$${\displaystyle \Phi}$

分割可能な CGでは、原子 CG と同様に、有限数のプレーヤーが存在し、各プレーヤーには転送する特定の負荷があります。非原子 CG と同様に、各プレーヤーは、輸送会社が大量輸送のために一連の経路を選択するのと同じように、負荷を異なる経路を通る部分的な負荷に分割できます。非原子 CG とは対照的に、各プレーヤーは混雑に無視できない影響を及ぼします。

分割可能なCGは、1993年に通信ネットワークの文脈で、アリエル・オルダ、ラファエル・ロム、ナフム・シムキンによって初めて分析されました。 ^{[7] [8]}彼らは、2つのノードと複数の並列リンクを持つ単純なネットワークの場合、ナッシュ均衡は合理的な凸性条件下で一意であり、いくつかの興味深い単調性特性を持つことを示しています。一般的なネットワークトポロジーの場合、ナッシュ均衡の一意性を保証するには、より複雑な条件が必要です。

重み付き CGでは、異なるプレイヤーが渋滞に異なる影響を及ぼす可能性があります。たとえば、道路網では、トラックはオートバイよりもはるかに大きな渋滞を引き起こします。一般に、プレイヤーの重みはリソース (リソース固有の重み) に依存する場合があります。つまり、すべてのプレイヤーiとリソースeに対して重み があり、リソースeの負荷があります。重要な特殊なケースは、重みがプレイヤーのみに依存する場合 (リソースに依存しない重み) です。つまり、各プレイヤー i には重み があり、 です。 ${\displaystyle w_{i,e}}$${\displaystyle x_{e}=\sum _{i:e\in P_{i}}w_{i,e}}$${\displaystyle w_{i}}$${\displaystyle x_{e}=\sum _{i:e\in P_{i}}w_{i}}$

ミルヒタイヒ^{[9]は、各戦略が単一のリソース（「シングルトンCG」）であり、重みが}リソースに依存せず、すべてのプレイヤーが同じ戦略セットを持つ重み付きCGの特殊なケースを検討した。次のことが証明されている。

• すべてのプレイヤーが同じ遅延関数を持つ場合、ゲームは有限改善特性を持ちます (したがって PNE を持ちます)。
• 戦略が 2 つだけの場合 (および遅延関数が異なる可能性のある任意の数のプレイヤーがいる場合)、ゲームは有限改善特性を持ちます (したがって PNE を持ちます)。
• プレイヤーが 2 人だけの場合 (遅延関数が異なる可能性あり)、ゲームは有限最良応答特性を持ちます (したがって PNE を持ちます)。
• 3 つ以上の戦略と、異なる遅延関数を持つ 3 人以上のプレーヤーが存在する場合、PNE は存在しない可能性があります。

ミルヒタイヒは、各戦略が与えられた無向グラフ（「ネットワーク CG」）内のパスである重み付き CG の特殊なケースを検討しました。彼は、すべての有限ゲームが、非減少（ただし必ずしも負ではない）コスト関数を持つ重み付きネットワーク輻輳ゲームとして表現できることを証明しました。^[10]これは、そのようなゲームのすべてが PNE を持つわけではないことを意味します。PNE のない重み付き CG の具体的な例は、Libman と Orda、^[11]および Goemans Mirrokni と Vetta によって示されています。^[12]これにより、どのような条件が PNE の存在を保証するのかという疑問が生じます。^[13]

特に、あるグラフG が特定の特性を持つとは、その基礎となるネットワークがGである重み付きネットワーク CG のすべてがその特性を持つ場合を言う。Milchtaich ^[14]は、PNE の存在と有限改善特性を保証するネットワークを、より重みの低いプレイヤーが弱くより多くの許容戦略を持つ (正式にはを意味する)という追加条件で特徴付けた。彼は次のことを証明した。 ${\displaystyle w_{i}<w_{j}}$${\displaystyle |S_{i}|\geq |S_{j}|}$

• グラフG が有限改善特性を保証するのは、Gが並列ネットワーク(1 つ以上の単一エッジ ネットワークが並列に接続されたグラフ) か、 1 つまたは 2 つの単一エッジ ネットワークが直列に接続された並列ネットワークに同相である場合に限ります。^{: Thm.2}
• グラフGは、 Gが 6 つの「許可されたネットワーク」のセットからの 1 つ以上のネットワークの直列の接続に同相である場合に限り、PNE の存在を保証します。同等の条件は、 6 つの「禁止されたネットワーク」のセットからのネットワークがGに埋め込まれていないことです。^{: Thm.3}

すべてのプレイヤーが任意の戦略（「パブリックエッジ」）を使用できる特別なケースでは、PNEの存在を保証するネットワークがさらに存在します。そのようなネットワークの完全な特徴付けは未解決の問題として提起されています。^[14]

Mlichtaich ^[15]は、ネットワークトポロジがPNEの 効率に与える影響を分析している。

• グラフG は、 3 つの単純な「禁止ネットワーク」がGに埋め込まれていない場合に限り、すべての PNE がパレート効率的であることを保証します。
• グラフG は、それが直列並列グラフである場合に限り、 Braess のパラドックスが発生しないことを保証します。

ミルヒタイヒ^[16]は、ネットワークトポロジがPNEコストの 一意性に与える影響を分析している。

• グラフGは、 G がいくつかの単純な種類の 1 つ以上のネットワークの直列接続である場合に限り、PNE コストが一意であることを保証します。
• グラフG は、 G に特定の単純なタイプの埋め込みネットワークが含まれている場合にのみ、PNE コストが一意であることを保証しません。

ホルツマンとロー・ヨネ^{[17]は、すべての原子CGが}強いPNE、一意のPNE、またはパレート効率的なPNEを持つことを保証するネットワークも特徴付けている。

リッチマンとシムキン^[18]は、分割可能なCGごとに固有のPNEを持つ ことを保証するネットワークを特徴付けている。

すべての遅延関数がCの要素である重み付き CG がすべて特定のプロパティを持つ場合、関数のクラスC は特定のプロパティを保証すると言います。

• フォタキス、コントギアニス、スピラキス^[19]は、線形関数のクラスが正確なポテンシャルの存在を保証し、したがってPNEの存在を保証することを証明した。
• パナゴポウロウとスピラキス^[20]は、指数関数のクラスが重み付きポテンシャルの存在を保証し、したがってPNEの存在を保証することを証明した。
• Harks、Klimm、Mohring ^[21]は、関数のクラスが正確なポテンシャルの存在を保証するのは、それがアフィン関数のみを含む場合のみであることを証明しています。この特徴付けは、2人用ゲーム、3リソースゲーム、シングルトンゲーム、対称戦略のゲーム、または整数重みのゲームに制限された場合でも有効です。さらに、関数のクラスが重み付きポテンシャルの存在を保証するのは、(1)アフィン関数のみを含むか、(2)形式 の指数関数のみを含む場合で、 はすべてのリソースで同じである場合のみです。この特徴付けは、4人用ゲーム、4リソースゲーム、シングルトンゲーム、対称戦略のゲーム、または整数重みのゲームに制限された場合でも有効です。2人用ゲームでは、関数のクラスが重み付きポテンシャルの存在を保証するのは、その中のすべての関数が 形式 である場合で、 は単調関数（すべてのリソースで同じ）である場合のみです。${\displaystyle a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}}$${\displaystyle \phi }$${\displaystyle a_{e}\cdot f(x_{e})+b_{e}}$${\displaystyle f}$
• HarksとKlimm ^[22]は、PNEの存在について同様の結果を証明している。彼らは、関数のクラスがPNEの存在を保証するのは、(1)それがアフィン関数のみを含むか、(2)それが の形式 の指数関数のみを含む場合のみであり、ここで はすべてのリソースに対して同じであることを証明している。この特徴付けは、3人プレイのゲームに限定しても有効である。2人プレイのゲームでは、関数のクラスがPNEの存在を保証するのは、その中のすべての関数が の形式 であり、ここで は単調関数（すべてのリソースに対して同じ）である場合のみである。${\displaystyle a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}}$${\displaystyle \phi }$${\displaystyle a_{e}\cdot f(x_{e})+b_{e}}$${\displaystyle f}$

重み付き混雑ゲームに関する論文は他にも多数ある。^{[23] [24] [25]}

基本的な CG モデルは、各リソースの遅延関数をプレイヤーに依存させることで拡張できます。つまり、各リソースeとプレイヤーiには遅延関数が存在します。戦略が与えられれば、プレイヤーは遅延を経験します。 ${\displaystyle d_{i,e}}$${\displaystyle P_{i}}$${\displaystyle i}$${\displaystyle \textstyle \sum _{e\in P_{i}}d_{i,e}(x_{e})}$

ミルヒタイヒ^[9]は、次のような特殊なケースにおいて、 プレイヤー固有のコストを持つCGを導入し研究した。

• 各プレイヤーは単一のリソースを選択します（このようなゲームはシングルトン CGと呼ばれます）。
• すべてのプレイヤーは同じ戦略セットを持っています。

このCGの特殊なケースは、混雑ゲームとも呼ばれます。^{[26] [27]}これは、複数の人が同時に行く場所（部屋、集落、レストランなど）を選択し、その場所と同じ場所を選んだ他のプレイヤーの数によって報酬が決まる設定を表しています。

混雑ゲームでは、戦略 が与えられた場合、プレイヤーは遅延 を経験します。プレイヤーが別の戦略 に切り替えると、遅延 になります。したがって、戦略ベクトルは、すべてのプレイヤー i、すべてのe、fについて、その場合のみ PNE です。 ${\displaystyle P_{i}=\{e\}}$${\displaystyle i}$${\displaystyle d_{i,e}(x_{e})}$${\displaystyle f}$${\displaystyle d_{i,f}(x_{f}+1)}$${\displaystyle d_{i,e}(x_{e})\leq d_{i,f}(x_{f}+1)}$

一般に、プレイヤー固有の遅延を持つ CG は、潜在的な関数を受け入れない可能性があります。たとえば、3 つのリソース x、y、z と、次の遅延関数を持つ 2 人のプレイヤー A と B があるとします。

• ${\displaystyle d_{A,x}(1)<d_{A,y}(0)<d_{A,y}(2)<d_{A,z}(0)<d_{A,z}(2)<d_{A,x}(2)}$
• ${\displaystyle d_{B,y}(1)<d_{B,x}(0)<d_{B,x}(2)<d_{B,z}(0)<d_{B,z}(2)<d_{B,y}(2)}$

以下は循環改善パスです: 。これは有限改善プロパティが成立しないことを示しています。したがって、ゲームはポテンシャル関数 (一般化順序ポテンシャル関数でさえも) を持つことはできません。ただし、 ${\displaystyle (z,y)\to (y,y)\to (y,z)\to (x,z)\to (x,x)\to (z,x)\to (z,y)}$

• 2つのリソースのみの場合、有限改善特性が成立する。^{[9] : Thm.1}したがって、PNEが存在する。
• プレイヤーが 2 人だけの場合、すべての有限最善応答特性が保持されます。したがって、PNE が存在します。

プレイヤーが3人以上いる場合、最善の応答パスでさえ巡回的になる可能性がある。しかし、すべてのCGには依然としてPNEがある。^{[9] : Thm.2}証明は構成的であり、最大ステップでナッシュ均衡を見つけるアルゴリズムを示している。さらに、すべてのCGは弱非巡回的である。つまり、任意の初期戦略ベクトルに対して、このベクトルから始まる少なくとも1つの最善の応答パスの長さは最大で、均衡で終了する。^{[9] : Thm.3}${\displaystyle {n+1 \choose 2}}$${\displaystyle r{n+1 \choose 2}}$

あらゆる混雑ゲームは順次解ける。^[26]これは、プレイヤーの順序に関係なく、各プレイヤーが順番に戦略を選択する順次ゲームには、プレイヤーの行動が元の同時ゲームにおけるPNEである部分ゲーム完全均衡が存在することを意味する。あらゆる混雑ゲームには少なくとも1つの強いPNEが存在する。^[28]混雑ゲームの強いPNEはすべて、ゲームの順次バージョンの部分ゲーム完全均衡として達成できる。^[26]

一般的に、混雑ゲームにはさまざまな PNE が存在する可能性があります。たとえば、n人のプレイヤーとn 個のリソースがあり、混雑がペイオフに与えるマイナスの影響がリソースのプラスの価値よりもはるかに大きいとします。その場合、n! の異なる PNE が存在します。プレイヤーとリソースの 1 対 1 のマッチングはすべて PNE です。他のプレイヤーが占有しているリソースに移動するプレイヤーはいないからです。ただし、混雑ゲームをm回複製すると、 m が無限大に近づくにつれて PNE の集合は 1 つの点に収束します。さらに、「大規模な」(非原子的な) 混雑ゲームでは、一般的に一意の PNE が存在します。この PNE には興味深いグラフ理論的特性があります。G を、片側にプレイヤー、もう片側にリソースがある 2 部グラフとします。各プレイヤーは、一意の PNE で自分のコピーが選択するすべてのリソースに隣接しています。この場合、G にはサイクルは含まれません。^[27]

プレーヤー固有の遅延関数の特殊なケースとして、遅延関数をプレーヤー固有の要因と一般的な要因に分けることができます。次の 2 つのサブケースがあります。

• 乗法的に分離可能な コスト関数: 、ここで はプレイヤーiに対するリソースeの基本コストを表す定数、d は一般的な遅延関数 (すべてのリソースに対して同じ) です。${\displaystyle d_{i,e}(x_{e})=a_{i,e}\cdot d(x_{e})}$${\displaystyle a_{i,e}}$
• 加法分離可能な コスト関数: ^[29] 、ここで、はプレイヤーiに対するリソースeの固定コストを表す定数であり、dは一般的な遅延関数（すべてのリソースに対して同じ）である。${\displaystyle d_{i,e}(x_{e})=a_{i,e}+d(x_{e})}$${\displaystyle a_{i,e}}$

純粋戦略のみを考慮すると、積の対数は合計であるため、これら2つの概念は同等である。さらに、プレイヤーがリソース固有の重みを持つ場合、リソース固有の遅延関数を持つ設定は、普遍的な遅延関数を持つ設定に縮小できます。分離可能なコスト関数を持つゲームは、負荷分散、^[30] M/M/1キューイング、^[31]および生息地選択で発生します。^[32]分離可能なコストを持つ重み付きシングルトンCGについては、次のことがわかっています。^[33]

• 基本コストがプレイヤー独立（各プレイヤーiに対して）であれば、CG は FIP を持ち、したがって PNE を持つ。基本コストがリソース独立（各リソースeに対して）であっても同じことが言える。^{[30] [34]}証明はベクトル値のポテンシャル関数に基づいている。ゲームの各状態について、ポテンシャルはサイズnのベクトルであり、これにはすべてのプレイヤーのコストが大きなものから小さなものの順に並べられている。プレイヤーが自分にとってコストの小さいリソースに逸脱するたびに、コストのベクトルはレキシミン順序で小さくなる。${\displaystyle a_{i,e}}$${\displaystyle a_{i,e}=a_{e}}$${\displaystyle a_{i,e}=a_{i}}$
• 重みがプレイヤー独立であれば（つまり、CGは重み付けされておらず、遅延関数はリソース固有であれば）、FIPが存在し、したがってPNEが存在する。^{[35] [29]}コスト関数が加法的に分離可能であれば、ゲームは正確なポテンシャル関数さえ持つ。コスト関数が負荷に対して単調増加していなくても、結果は成り立つ。コスト関数が加法的に分離可能でない場合、FIPは成立せず、ポテンシャル関数は存在しないが、それでもPNEは存在する。^{[9] : Thm.2}
• 重みがリソースに依存しない場合、次の場合に PNE が存在します。
  • プレイヤーが最大3人の場合、PNEが存在するが^{[36] : Cor.3 、}最良応答改善特性は成立しない可能性がある。対照的に、分離可能なコストとリソースに依存しない重みを持つCGがあり、プレイヤーが8人の場合、PNEは存在しない。^{[33] : Thm.3}
  • コスト関数が線形可変コスト関数と加法的に分離可能な場合、CGは重み付きポテンシャルを持ち、したがってFIPを持ち、したがってPNEを持つ。^{[36] : Thm.6}
  • コスト関数が対数可変コスト関数と加法的に分離可能であり、プレイヤーが最大3人の場合、CGは最良応答改善特性を持ち、したがってPNEを持つ。しかし、有限改善特性を持たない可能性がある。^[37]プレイヤーが3人以上の場合、PNEの存在は未知数である。

分離可能なプレイヤー固有の好みを持つ重み付きシングルトンCGはすべて、プレイヤーに依存しない好みを持つ重み付きネットワークCGと同型である。 ^{[33] [2]}

ミルヒタイヒは、各戦略が特定のグラフ内のパスである、プレイヤー固有のコストを持つ CG の特殊なケース (「ネットワーク CG」) を検討しました。彼は、すべての有限ゲームが、プレイヤー固有のコストと非減少 (必ずしも負ではない) コスト関数を持つ (重み付けされていない) ネットワーク輻輳ゲームとして表すことができることを証明しました。^[10]このような CG で PNE が存在することを保証するネットワークの完全な特性評価は、未解決の問題として提起されています。^[14]

PNEの存在証明は構成的である。つまり、常にPNEを見つける有限アルゴリズム（改善パス）を示している。このことから、このPNEを見つけるには何ステップ必要かという疑問が生じる。Fabrikant、Papadimitriou、Talwar ^[38]は以下を証明した。

• すべての戦略がネットワーク内のパス（「ネットワーク CG」）であり、すべてのプレーヤーが同じ戦略セット（「対称 CG」）を持っている場合、最小コストフローへの削減を通じてポテンシャルを最大化することで、PNE を多項式時間で計算できます。アルゴリズムは非原子 CG に適応できます。特定の滑らかさの仮定の下では、そのようなゲームのナッシュ均衡は、強多項式時間で近似できます。
• 戦略が一般的なサブセットである場合、またはプレーヤーが異なる戦略セットを持つ場合 (「非対称 CG」)、PNE の計算はPLS 完全です。これは、指数関数的に長い改善パスを持つ例があることを意味します。また、指定された状態から到達可能なナッシュ均衡を見つけることはPSPACE 完全であることを意味します。
• PLSクラスのすべての問題は、ポテンシャル関数の議論によって純粋均衡が存在することが保証されるゲームとして表現できます。

Even-Dar、Kesselman、Mansour ^[30]は、負荷分散設定において平衡への収束に必要なステップ数を分析している。

Caragiannis、Fanelli、Gravin、Skopalik ^[39]は、定数係数近似PNEを計算するアルゴリズムを提示している。具体的には、

• 線形遅延関数では、近似比は 2+ε であり、実行時間はプレーヤー数、リソース数、および 1/ε の多項式です。
• 遅延関数がd次の多項式の場合、近似比はd ^{O( d )です}。

彼らのアルゴリズムは、近似均衡につながる、最適な応答動作の短いシーケンスを識別します。また、より一般的な CG の場合、PNE の任意の多項式近似を達成することは PLS 完全であることを示しています。

Fotakis、Kontogiannis、Spirakis ^[19]は、線形遅延関数を持つ任意の重み付きネットワークCGで、擬似多項式時間（プレイヤー数nとプレイヤーの重みの合計Wの多項式）でPNEを見つけるアルゴリズムを提示している。彼らのアルゴリズムは貪欲な 最良応答アルゴリズムである。プレイヤーは重みの降順でゲームに参加し、既存のプレイヤーの戦略に対する最善の応答を選択する。

PanagopoulouとSpirakis ^[20]は、Fotakis、Kontogiannis、Spirakisのアルゴリズムが実際にnとlog Wの多項式時間で実行されるという経験的証拠を示しています。彼らはまた、このアルゴリズムを劇的に高速化する初期戦略ベクトルを提案しています。

一般に、重み付きネットワークCGはPNEを持たない可能性がある。Milchtaich ^[14]は、与えられた重み付きネットワークCGがPNEを持つかどうかを判断することは、以下の場合でもNP困難であることを証明している。

• プレイヤーは 2 人います。すべてのプレイヤーはすべてのパスを使用できます。すべてのコスト関数は非負です。
• プレイヤーは 2 人います。CG は重み付けされておらず、コストはプレイヤー固有で非負です。

証明は有向辺分離パス問題からの還元によって行われる。^[40]

Caragiannis、Fanelli、Gravin、Skopalik ^[41]は、重み付きCGにおける定数係数近似PNEを計算するアルゴリズムを提示している。具体的には、

• 線形遅延関数の場合、近似比は であり、実行時間はプレイヤー数、リソース数、および 1/ε の多項式です。${\displaystyle {\frac {3+{\sqrt {5}}}{2}}+O(\epsilon )}$
• 遅延関数がd次多項式の場合、近似比は です。${\displaystyle d^{2d+o(d)}}$

結果を証明するため、重み付き CG には潜在的な関数がないかもしれないが、重み付き CG はすべて、特定の潜在的なゲームで近似できることを示しています。これにより、重み付き CG はすべて ( d !) 近似 PNE を持つことがわかります。アルゴリズムは、このような近似 PNE につながる、最適な応答移動の短いシーケンスを識別します。

要約すると、CG はさまざまなパラメータに従って分類できます。

• プレーヤーの数と分割可能性:アトミック CG、分割可能な CG、または非アトミック CG。
• プレイヤーの重み:重み付けされていない CGまたは重み付けされた CG (リソースに依存しない重みまたはリソース固有の重み付き)。
• 同じリソースを使用する異なるプレーヤーのコスト関数:同一またはプレーヤー固有(分離可能または分離不可能なコスト関数を使用)。
• 可能な戦略: 1 つのリソース (シングルトン CG )、ネットワーク内のパス (ネットワーク CG )、または任意のサブセット (一般 CG)。
• 異なるプレイヤーの戦略セット: 異なる (非対称 CG ) または同一 (対称 CG )。

• すべての CG にはナッシュ均衡があるため、次の自然なトピックはその品質を分析することです。これは、混雑ゲームにおける無政府状態の価格の概念を使用して行われます。
• ּ資源配分ゲーム^{[42] [31]}は混雑ゲームと多少関連がある。
• 不完全情報：ファッキーニ、ファン・メーゲン、ボルム、ティイス^{[35]は、ローゼンタールのモデルを}不完全情報の設定に拡張した。彼らは、関連するベイズゲームが潜在的なゲームであり、したがって純粋なベイズ・ナッシュ均衡を持つことを証明した。
• 連合：Fotakis、Kontogiannis、Spirakis ^[43]は、プレイヤーが連合に参加するCGを研究した。
• 自然界における混雑ゲーム：ミリンスキー^[44]は、自然のCGがナッシュ均衡に収束する実験について説明しています。彼の実験では、水槽の両端から6匹のトゲウオに餌を与えました。両端間の魚の分布は、平均して、餌の供給率の比率に似ていたため、どの魚も反対側に移動して餌の供給率を上げることはできませんでした。ムリヒタイヒ^[3]は、種間競争におけるCGのより一般的な扱い方を提示しています。