イプシロン平衡

イプシロン平衡
イプシロン平衡
ゲーム理論における解の概念
関係
スーパーセット	ナッシュ均衡
意義
用途	確率ゲーム

ゲーム理論において、イプシロン均衡、または近似ナッシュ均衡とは、ナッシュ均衡の条件を近似的に満たす戦略プロファイルのことである。ナッシュ均衡では、どのプレイヤーも自分の行動を変えるインセンティブを持たない。近似ナッシュ均衡では、この要件が緩和され、プレイヤーが異なる行動をとるわずかなインセンティブを持つ可能性が許容される。例えば現状維持バイアスを仮定すれば、これは依然として適切な解概念とみなされる可能性がある。この解概念は、計算が容易であること、あるいは2人以上のプレイヤーがいるゲームでは、厳密なナッシュ均衡に関わる確率が有理数である必要がない可能性があることから、ナッシュ均衡よりも好ましい場合がある。^[¹^]

意味

複数の代替定義が存在する。

標準的な定義

ゲームと実数の非負のパラメータが与えられた場合 $\varepsilon$ 戦略プロファイルは、 $\varepsilon$ -均衡状態とは、どのプレイヤーもそれ以上の利益を得ることができない状態を指します。 $\varepsilon$ 戦略から一方的に逸脱することで期待収益が減少する。^[²^]^：⁴⁵ すべてのナッシュ均衡は、 $\varepsilon$ -平衡状態 $\varepsilon =0$ 。

正式には、 $G=(N,A=A_{1}\times \dotsb \times A_{N},u\colon A\to R^{N})$ になる $N$ アクションセットを備えたプレイヤーゲーム $A_{i}$ 各プレイヤーについて $i$ および効用関数 $u$ 。させて $u_i(s)$ プレイヤーへの報酬を表す $i$ 戦略プロファイルの場合 $s$ 再生されます。 $\displaystyle \Delta _{i}}$ 確率分布の空間を $A_{i}$ 戦略のベクトル $\sigma \in \Delta =\Delta _{1}\times \dotsb \times \Delta _{N}$ は $\varepsilon$ -ナッシュ均衡 $G$ もし

u_{i}(\sigma )\geq u_{i}(\sigma _{i}^{'},\sigma _{-i})-\varepsilon

すべての人々のために

\displaystyle \sigma _{i}^{'}\in \Delta _{i},i\in N.}

すべてのプレイヤーの効用は [0,1], ^{[ 3 ]}に正規化されていることに注意してください。これは実際には乗法近似です。利得は以下を超えることはありません。 $\varepsilon$ 最高の効用を倍増させる。

十分に裏付けられた近似均衡

以下の定義^{[ 4 ]} は、プレイヤーが純粋戦略にのみ正の確率を割り当てることができるという、より強い要件を課している。 $a$ 報酬が $a$ 期待される収益は最大で $\varepsilon$ 最良の反応報酬よりも少ない。 $x_{s}$ 戦略プロファイルの確率 $s$ プレイされます。プレイヤーの場合 $p$ させて $S_{-p}$ プレイヤー以外の戦略プロファイル $p$ ; のために $s ∈ S-p$ そして純粋な戦略 $j$ の $p$ させて $js$ 戦略プロファイルは $p$ プレイ $j$ そして他のプレイヤーがプレイする $s$ 。させて $u_{p}(s)$ 報酬となる $p$ 戦略プロファイルの場合 $s$ が使用される。要件は次の式で表すことができる。

\sum _{s\in S_{-p}}u_{p}(js)x_{s}>\varepsilon +\sum _{s\in S_{-p}}u_{p}(j's)x_{s}\Longrightarrow x_{j'}^{p}=0.

結果

ε-ナッシュ均衡に対する多項式時間近似スキーム（PTAS）の存在は、 ε-十分にサポートされた近似ナッシュ均衡に対するPTASが存在するかどうかという問題と同等であるが、^[⁵^] PTASの存在は未解決問題のままである。εの値が一定の場合、近似均衡に対する多項式時間アルゴリズムは、十分にサポートされた近似均衡に対して知られているよりも低いεの値に対して知られている。利得が[0,1]の範囲でε =0.3393のゲームの場合、ε-ナッシュ均衡は多項式時間で計算できる。^[⁶^] 利得が[0,1]の範囲でε =2/3のゲームの場合、ε-十分にサポートされた均衡は多項式時間で計算できる。^[⁷^]

例

ε均衡の概念は、潜在的に無限期間にわたる確率ゲームの理論において重要である。ナッシュ均衡は存在しないが、0より厳密に大きい任意のεに対してε均衡が存在する確率ゲームの単純な例が存在する。

おそらく最も単純な例は、エベレットが提案した「マッチング・ペニーズ」の次のバリエーションでしょう。プレイヤー1がペニーを隠し、プレイヤー2はそれが表か裏かを推測しなければなりません。プレイヤー2が正解すれば、プレイヤー1からペニーを獲得し、ゲームは終了します。プレイヤー2がペニーが表だと誤って推測した場合、両プレイヤーの報酬はゼロでゲームは終了します。裏だと誤って推測した場合、ゲームは繰り返されます。ゲームが永遠に続く場合、両プレイヤーの報酬はゼロになります。

パラメータε > 0 が与えられた場合、プレイヤー 2 がゲームのどの段階でも確率 ε で表を出し、確率 1 − εで裏を出す戦略プロファイル(前の段階とは独立に) は、ゲームのε均衡です。このような戦略プロファイルにおけるプレイヤー 2 の期待利得は少なくとも 1 − εです。しかし、プレイヤー 2 の戦略で期待利得がちょうど 1 になることを保証するものはないことは容易にわかります。したがって、このゲームにはナッシュ均衡は存在しません。

もう1つの簡単な例は、T期間にわたって利得が平均化される有限回繰り返し囚人のジレンマです。このゲームの唯一のナッシュ均衡は、各期間で裏切りを選択することです。次に、しっぺ返し戦略とグリムトリガー戦略の2つの戦略を考えてみましょう。しっぺ返し戦略もグリムトリガー戦略もこのゲームのナッシュ均衡ではありませんが、どちらも $\epsilon$ -いくつかの正の平衡 $\epsilon$ 許容値 $\epsilon$ 構成ゲームの利得と期間数Tに依存する。

経済学において、混合戦略アプローチが非現実的とみなされる場合、純粋戦略イプシロン均衡の概念が用いられる。純粋戦略イプシロン均衡では、各プレイヤーは自身の最良純粋戦略からイプシロン以内の純粋戦略を選択する。例えば、純粋戦略均衡が存在しないベルトラン＝エッジワース・モデルでは、純粋戦略イプシロン均衡が存在する可能性がある。

参考文献

インライン引用

↑ V. Bubelis (1979). "有限ゲームにおける均衡について". International Journal of Game Theory . 8 (2): 65–79 . doi : 10.1007/bf01768703 . S2CID 122843303 .
↑ヴァジラニ、ヴィジェイ V. ;ニサン, ノーム;ティム・ラフガーデン;タルドス、エヴァ(2007)。アルゴリズムゲーム理論(PDF)。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-87282-0。
↑ Tsaknakis, Haralampos; Spirakis, Paul G. (2007). "近似ナッシュ均衡のための最適化アプローチ" . Deng, Xiaotie ; Graham, Fan Chung (編).インターネットとネットワーク経済学. Lecture Notes in Computer Science. Vol. 4858. Berlin, Heidelberg: Springer. pp. 42–56 . doi : 10.1007/978-3-540-77105-0_8 . ISBN 978-3-540-77105-0。
↑ PW Goldberg およびCH Papadimitriou (2006). "平衡問題間の還元可能性".第 38 回理論計算機科学シンポジウム. pp. 61–70 . doi : 10.1145/1132516.1132526 .
↑ C. ダスカラキス、PW ゴールドバーグ、CH パパディミトリウ(2009)。「ナッシュ均衡の計算の複雑さ」。SIAM ジャーナルオンコンピューティング。39 (3): 195–259。CiteSeerX 10.1.1.68.6111。土井：10.1137/070699652。
↑ H. Tsaknakis および Paul G. Spirakis (2008). "近似ナッシュ均衡の最適化アプローチ" . Internet Mathematics . 5 (4): 365–382 . doi : 10.1080/15427951.2008.10129172 .
↑ Spyros C. Kontogiannis および Paul G. Spirakis (2010). "二行列ゲームにおける十分に支持された近似均衡". Algorithmica . 57 (4): 653– 667. doi : 10.1007/s00453-008-9227-6 . S2CID 15968419 .

情報源

H Dixon「複製産業における近似ベルトラン均衡」、Review of Economic Studies、54（1987）、47-62ページ。
H. エヴェレット「再帰的ゲーム」。H.W. クーンおよびA.W. タッカー編『 ゲーム理論への貢献』第3巻、数学研究年報第39巻、プリンストン大学出版局、1957年。
レイトン＝ブラウン、ケビン；ショハム、ヨアブ（2008）『ゲーム理論の基礎：簡潔で学際的な入門』サンラファエル、カリフォルニア州：モーガン＆クレイプール出版社、ISBN 978-1-59829-593-188ページにわたる数学入門書。セクション3.7を参照。多くの大学のWayback Machineに2000年8月15日にアーカイブされた無料オンライン版。
R. Radner「長期だが有限な寿命を持つ寡占企業の非協力イプシロン均衡における共謀行動」『経済理論ジャーナル』22巻、121-157ページ、1980年。
ショハム、ヨアブ、レイトン＝ブラウン、ケビン（2009）『マルチエージェントシステム：アルゴリズム的、ゲーム理論的、論理的基礎』ニューヨーク：ケンブリッジ大学出版局、ISBN 978-0-521-89943-7計算論的観点からの包括的なリファレンス。セクション 3.4.7 を参照。オンラインで無料でダウンロード可能。
SH Tijs.非協力的なn人ゲームの標準形におけるナッシュ均衡、SIAM Review、23、225–237、1981年。

[1] V. Bubelis (1979). "有限ゲームにおける均衡について". International Journal of Game Theory . 8 (2): 65–79 . doi : 10.1007/bf01768703 . S2CID 122843303 .

[AGT-2] ヴァジラニ、ヴィジェイ V. ;ニサン, ノーム;ティム・ラフガーデン;タルドス、エヴァ(2007)。アルゴリズムゲーム理論(PDF)。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-87282-0。

[3] Tsaknakis, Haralampos; Spirakis, Paul G. (2007). "近似ナッシュ均衡のための最適化アプローチ" . Deng, Xiaotie ; Graham, Fan Chung (編).インターネットとネットワーク経済学. Lecture Notes in Computer Science. Vol. 4858. Berlin, Heidelberg: Springer. pp. 42–56 . doi : 10.1007/978-3-540-77105-0_8 . ISBN 978-3-540-77105-0。

[4] PW Goldberg およびCH Papadimitriou (2006). "平衡問題間の還元可能性".第 38 回理論計算機科学シンポジウム. pp. 61–70 . doi : 10.1145/1132516.1132526 .

[5] C. ダスカラキス、PW ゴールドバーグ、CH パパディミトリウ(2009)。「ナッシュ均衡の計算の複雑さ」。SIAM ジャーナルオンコンピューティング。39 (3): 195–259。CiteSeerX 10.1.1.68.6111。土井：10.1137/070699652。

[6] H. Tsaknakis および Paul G. Spirakis (2008). "近似ナッシュ均衡の最適化アプローチ" . Internet Mathematics . 5 (4): 365–382 . doi : 10.1080/15427951.2008.10129172 .

[7] Spyros C. Kontogiannis および Paul G. Spirakis (2010). "二行列ゲームにおける十分に支持された近似均衡". Algorithmica . 57 (4): 653– 667. doi : 10.1007/s00453-008-9227-6 . S2CID 15968419 .

[

[

[ 3 ]

[ 4 ]

[

[

[

意味

標準的な定義

十分に裏付けられた近似均衡

結果

例

関連項目

参考文献