非原子ゲーム

ゲーム理論において、非原子ゲーム（NAG）は、プレイヤーが連続体とみなせるほど多数存在する状況への標準形ゲームの一般化である。NAGはデイビッド・シュマイドラーによって導入された。^{[ 1 ]}彼は、ジョン・ナッシュが有限ゲームに対して最初に証明したナッシュ均衡の存在定理をNAGに拡張した。

シュマイドラーはNAGの研究を次のように動機づけている。^{[ 1 ]}

「非原子ゲームを用いることで、個々のプレイヤーは状況に影響を与えないものの、多数のプレイヤーの集合的な行動によって利得が変化するような紛争状況を分析することが可能になる。その例は数多く存在する。選挙、少数の競合企業から多数の小口購入者が購入する場合、複数の道路から選択できるドライバーなどだ。」

標準的な（「アトミック」な）ゲームでは、プレイヤーの集合は有限集合である。NAGでは、プレイヤーの集合は無限かつ連続的な集合である。${\displaystyle P}$例えば単位間隔でモデル化できる${\displaystyle [0,1]}$プレイヤーの集合上にはルベーグ測度が定義されており、これは各「タイプ」のプレイヤーが何人いるかを表します。

各プレイヤーは以下のいずれかを選択できます。${\displaystyle m}$行動（「純粋戦略」）。プレイヤーの集合とは対照的に、行動の集合は標準的なゲームと同様に有限であることに注意してください。プレイヤーは混合戦略、つまり行動の確率分布を選択することもできます。戦略プロファイルは、プレイヤーの集合から得られる測定可能な関数です。${\displaystyle P}$アクションに関する確率分布の集合に対して、関数は各点に割り当てます。${\displaystyle p}$で${\displaystyle P}$確率分布${\displaystyle x(p)}$;それは、微小なプレーヤーが${\displaystyle p}$混合戦略を選択した${\displaystyle x(p)}$。

させて${\displaystyle x}$戦略プロファイルである。微小なプレイヤーの選択${\displaystyle p}$全体的な結果には影響しないが、彼自身の利益には影響する。具体的には、各純粋行動について${\displaystyle j}$で${\displaystyle \{1,\dots ,m\}}$関数があります${\displaystyle u_{j}}$各プレイヤーをマッピングする${\displaystyle p}$で${\displaystyle P}$そして各戦略プロファイル${\displaystyle x}$そのプレイヤーの有用性${\displaystyle p}$彼がプレイするときに受け取る${\displaystyle j}$そして他のすべてのプレイヤーは次のようにプレイします${\displaystyle x}$プレイヤーとして${\displaystyle p}$混合戦略を採用する${\displaystyle x(p)}$彼の報酬は内積である${\displaystyle x(p)\cdot u(p,x)}$。

戦略概要${\displaystyle x}$純粋と呼ばれるのは${\displaystyle x(p)}$ほぼすべての​${\displaystyle p}$で${\displaystyle P}$。

戦略概要${\displaystyle x}$ほぼすべてのプレイヤーにとって${\displaystyle p}$そしてあらゆる混合戦略${\displaystyle y}$次のように主張する$${\displaystyle x(p)\cdot u(p,x)\geq y\cdot u(p,x).}$$

デイビッド・シュマイドラーは、次のケースについて以下の定理を証明した。${\displaystyle P=[0,1]}$: ^{[ 1 ]}

定理１．すべての${\displaystyle p}$機能${\displaystyle u(p,\cdot )}$弱連続​${\displaystyle L^{1}([0,1])}$に${\displaystyle \mathbb {R} }$、そしてすべての${\displaystyle x}$そして${\displaystyle i}$、${\displaystyle j}$セット${\displaystyle \{p\mid u_{i}(p,x)>u_{j}(p,x)\}}$測定可能であれば、均衡状態が存在する。

この証明では、グリックスバーグの不動点定理を使用します。

定理2.上記の条件に加えて、${\displaystyle u(p,x)}$戦略プロファイルのアクション積分のみに依存する、つまり、$${\displaystyle \left(\int _{P}x_{j}(t)\,\mathrm {d} t\right)_{j\in \{1,\dots ,m\}},}$$すると、純粋戦略均衡が存在する。

この証明はロバート・オーマンの定理を用いている。定理2の追加条件は不可欠である。すなわち、純粋戦略均衡が存在しないにもかかわらず、定理1の条件を満たすゲームの例が存在する。デイビッド・シュマイドラーもまた、ナッシュ均衡定理が定理2の系として導かれることを示した。具体的には、有限正規形ゲームが与えられた場合、${\displaystyle G}$と${\displaystyle n}$プレイヤーは非原子ゲームを構築することができる${\displaystyle H}$各プレイヤーが${\displaystyle G}$のサブ区間に対応する${\displaystyle P}$長さ${\displaystyle 1/n}$効用関数は定理2の条件を満たすように定義される。${\displaystyle H}$これは、ナッシュ均衡（混合戦略を含む可能性あり）に対応します。${\displaystyle G}$。

一般モデルの特殊なケースとして、有限集合が存在する場合がある。${\displaystyle T}$プレイヤータイプの各種類。${\displaystyle t}$は、${\displaystyle P_{t}}$プレイヤーの集合${\displaystyle P}$サブインターバルの長さは、そのタイプのプレイヤーの数を表します。たとえば、${\displaystyle 1/2}$選手は${\displaystyle 1}$、${\displaystyle 1/3}$の型${\displaystyle 2}$、 そして${\displaystyle 1/6}$の型${\displaystyle 3}$同じタイプのプレイヤーは同じ効用関数を持つが、異なる戦略を選択する可能性がある。

非原子ゲームの特殊なサブクラスとして、混雑ゲームの非原子版（NCG）が挙げられる。この特殊なケースは以下のように説明できる。

• 有限集合が存在する${\displaystyle E}$混雑しやすい要素（例えば、道路や資源など）について。
• がある${\displaystyle n}$プレイヤーの種類。各種類について。${\displaystyle i}$数があります${\displaystyle r_{i}}$これは、そのタイプのプレイヤーの数（そのタイプのトラフィック率）を表します。
• 各タイプについて${\displaystyle i}$セットがあります${\displaystyle S_{i}}$可能な戦略（可能なサブセット）${\displaystyle E}$)
• 同じタイプのプレイヤーでも、異なる戦略を選択する場合があります。${\displaystyle s}$で${\displaystyle S_{i}}$、 させて${\displaystyle x_{i,s}}$タイプのプレイヤーの割合を表す${\displaystyle i}$戦略を用いる${\displaystyle s}$定義上、${\displaystyle \sum _{s\in S_{i}}x_{i,s}=r_{i}}$我々は、${\displaystyle x_{s}:=\sum _{i:s\in S_{i}}f_{s,i}}$
• 各要素について${\displaystyle e}$で${\displaystyle E}$負荷​​${\displaystyle e}$は、使用するプレーヤーの分数の合計として定義されます。${\displaystyle e}$つまり、${\displaystyle x_{e}=\sum _{s\ni e}x_{s}}$.プレイヤーが経験する遅延${\displaystyle e}$遅延関数によって定義される${\displaystyle d_{e}}$この関数は単調で、正の値を取り、連続でなければなりません。
• 各プレイヤーが戦略を選択する際の総不効用${\displaystyle s}$は、サブセット内のすべてのエッジにおける遅延の合計です。${\displaystyle s}$:${\displaystyle d_{s}(x)=\sum _{e\in s}d_{e}(x_{e})}$。
• 戦略プロファイルは、すべてのプレイヤータイプに対して均衡である。${\displaystyle i}$2 つの戦略ごとに${\displaystyle s_{1},s_{2}}$で${\displaystyle S_{i}}$、 もし${\displaystyle x_{i,s_{1}}>0}$、 それから${\displaystyle d_{s_{1}}(x)\leq d_{s_{2}}(x)}$つまり、タイプのプレーヤーの肯定的な尺度が${\displaystyle i}$選ぶ${\displaystyle s_{1}}$そうなると、他に考えられる戦略では、これより厳密に遅延時間を短縮することはできない。

NCGは、ミルヒタイヒ^{[ 2 ]} 、フリードマン^{[ 3 ] 、ブロンスキー[ 4 ]}によって最初に研究されました。ラフガーデンとタルドス^{[ 5 ]}は、NCGにおける無政府主義の代償を研究しました。

NCGにおける均衡の計算は凸最適化問題として再定式化でき、したがって弱多項式時間で解くことができる（例えば楕円体法による）。Fabrikant、Papadimitriou、Talwar ^{[ 6 ]}は、ネットワークNCGの特殊なケースにおけるPNEを見つけるための強多項式時間アルゴリズムを提示した。この特殊なケースでは、グラフが存在する。${\displaystyle G}$;各タイプについて${\displaystyle i}$ノードが2つあります${\displaystyle s_{i}}$そして${\displaystyle t_{i}}$から${\displaystyle G}$;そしてタイプに利用可能な戦略のセット${\displaystyle i}$は、からのすべてのパスの集合です。${\displaystyle s_{i}}$に${\displaystyle t_{i}}$すべてのプレイヤーの効用関数が定数でリプシッツ連続である場合${\displaystyle L}$すると、彼らのアルゴリズムは${\displaystyle e}$- 強多項式時間で PNE を近似- 多項式時間${\displaystyle n}$、${\displaystyle L}$そして${\displaystyle 1/e}$。

シュマイドラーの2つの定理は、いくつかの方法で一般化できる。^{[ 1 ]：最終的な考察}

• 定理2では、${\displaystyle u(p,x)}$のみに依存する${\displaystyle \int _{P}x}$要求できるのは${\displaystyle u(p,x)}$のみに依存する${\displaystyle \int _{P_{1}}x,\ldots ,\int _{P_{k}}x}$、 どこ${\displaystyle P_{1},\dots ,P_{k}}$は、${\displaystyle P}$。
• 定理 1 では、各プレイヤーの戦略空間が単体であることを要求するのではなく、各プレイヤーの戦略空間がコンパクト凸部分集合であることを要求すれば十分である。${\displaystyle \mathbb {R} ^{m}}$定理2の追加仮定が成り立つ場合、ほぼすべてのプレイヤーの戦略が均衡する均衡が存在する。${\displaystyle p}$は戦略空間の極点である${\displaystyle p}$。

• 連続ゲーム― プレイヤーの数は有限だが、戦略の集合は連続的に大きくなるゲーム。
• 混雑ゲーム#非原子。