イプシロン平衡
プレイヤーが戦略を変える動機がほとんどない状況
イプシロン平衡
ゲーム理論における解決概念
関係
のスーパーセットナッシュ均衡
意義
用途確率ゲーム

ゲーム理論において、イプシロン均衡、あるいは近似ナッシュ均衡とは、ナッシュ均衡の条件を近似的に満たす戦略プロファイルである。ナッシュ均衡では、どのプレイヤーも行動を変えるインセンティブを持たない。近似ナッシュ均衡では、この要件が弱められ、プレイヤーが何か違うことをする小さなインセンティブを持つ可能性が許容される。これは、例えば現状維持バイアスを想定すれば、依然として適切な解決策の概念とみなされるかもしれない。この解決策の概念は、計算が容易なため、あるいは2人以上のプレイヤーによるゲームでは、正確なナッシュ均衡に含まれる確率が有理数である必要がない可能性があるため、ナッシュ均衡よりも好まれるかもしれない。[1]

意味

代替の定義は複数あります。

標準的な定義

ゲームと実数の非負パラメータ が与えられたとき、どのプレイヤーも自分の戦略から一方的に逸脱することで期待される利得よりも多くを得ることが不可能な場合、その戦略プロファイルは-均衡であると 言われる。[2] : 45  すべてのナッシュ均衡はである -均衡に等しい。 ε {\displaystyle \varepsilon } ε {\displaystyle \varepsilon } ε {\displaystyle \varepsilon } ε {\displaystyle \varepsilon } ε ＝ 0 {\displaystyle \varepsilon =0}

正式には、各プレイヤーの行動集合と効用関数を持つ -プレイヤーゲーム を とする。戦略プロファイルがプレイされた場合のプレイヤーの利得をとする。を 上の確率分布空間とする。戦略のベクトルは、の -ナッシュ均衡である。 G ＝ （ 北 、 あ ＝ あ 1 × ⋯ × あ 北 、 あなた : あ → R 北 ） {\displaystyle G=(N,A=A_{1}\times \dotsb \times A_{N},u\colon A\to R^{N})} 北 {\displaystyle N} あ 私 {\displaystyle A_{i}} 私 {\displaystyle i} あなた {\displaystyle u} あなた 私 （ s ） {\displaystyle u_{i}(s)} 私 {\displaystyle i} s {\displaystyle s} Δ 私 {\displaystyle \Delta _{i}} あ 私 {\displaystyle A_{i}} σ ∈ Δ ＝ Δ 1 × ⋯ × Δ 北 {\displaystyle \sigma \in \Delta =\Delta _{1}\times \dotsb \times \Delta _{N}} ε {\displaystyle \varepsilon } G {\displaystyle G}

あなた 私 （ σ ） ≥ あなた 私 （ σ 私 ′ 、 σ − 私 ） − ε {\displaystyle u_{i}(\sigma )\geq u_{i}(\sigma _{i}^{'},\sigma _{-i})-\varepsilon } すべての人のために σ 私 ′ ∈ Δ 私 、 私 ∈ 北 。 {\displaystyle \sigma _{i}^{'}\in \Delta _{i},i\in N.}

すべてのプレイヤーの効用は[0,1]、[3]に正規化されているので、これは実際には乗法近似であり、利得は最高の効用の倍数を超えることはできません。 ε {\displaystyle \varepsilon }

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

次の定義[4] は、プレイヤーが純粋戦略に正の確率を割り当てることができるのは、 の利得が最良応答利得よりも期待利得が最大でも低い場合のみであるという、より強い要件を課している。 を戦略プロファイルがプレイされる確率とする。プレイヤー に対して以外のプレイヤーの戦略プロファイルとする。に対しての純粋戦略 をがプレイし、他のプレイヤーが をプレイする戦略プロファイルとする。を戦略プロファイル使用時のへの利得とする。この要件は、次式で表される。 1つの {\displaystyle a} 1つの {\displaystyle a} ε {\displaystyle \varepsilon } × s {\displaystyle x_{s}} s {\displaystyle s} p {\displaystyle p} S − p {\displaystyle S_{-p}} p {\displaystyle p} s ∈ S − p {\displaystyle s\in S_{-p}} j {\displaystyle j} p {\displaystyle p} j s {\displaystyle js} p {\displaystyle p} j {\displaystyle j} s {\displaystyle s} あなた p （ s ） {\displaystyle u_{p}(s)} p {\displaystyle p} s {\displaystyle s}

∑ s ∈ S − p あなた p （ j s ） × s > ε + ∑ s ∈ S − p あなた p （ j ′ s ） × s ⟹ × j ′ p ＝ 0。 {\displaystyle \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）の存在は、ε-well-supported近似ナッシュ均衡に対するPTASが存在するかどうかという問題と同義である[5]。しかし、PTASの存在は未解決の問題である。εの値が一定である場合、近似均衡に対する多項式時間アルゴリズムは、well-supported近似均衡に対して知られているものよりも低いεの値に対して知られている。ペイオフが[0,1]の範囲でε=0.3393のゲームでは、ε-ナッシュ均衡は多項式時間で計算できる[6] 。 ペイオフが[0,1]の範囲でε=2/3のゲームでは、ε-well-supported均衡は多項式時間で計算できる[7] 。

例

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

おそらく最も単純な例は、エヴェレットが提案した次のMatching Penniesのバリエーションです。プレイヤー 1 は 1 セント硬貨を隠し、プレイヤー 2 はそれが表か裏かを推測します。プレイヤー 2 が正しく推測した場合、プレイヤー 1 から 1 セント硬貨を獲得し、ゲームは終了します。プレイヤー 2 が 1 セント硬貨が表を向いていると誤って推測した場合、両方のプレイヤーの支払いがゼロでゲームは終了します。裏を向いていると誤って推測した場合、ゲームは繰り返されます。ゲームが永遠に続く場合、両方のプレイヤーの支払いはゼロになります。

パラメータε > 0 が与えられた場合、プレイヤー2が確率 ε で表を予想し、確率 1 −  εで裏を予想する戦略プロファイル（ゲームの全ステージにおいて、かつそれ以前のステージとは独立して）は、ゲームの ε均衡となる。このような戦略プロファイルにおけるプレイヤー2の期待利得は、少なくとも 1 − εである。しかし、プレイヤー2にとって期待利得が正確に 1 になることを保証できる戦略は存在しないことは容易に理解できる。したがって、このゲームにはナッシュ均衡は存在しない。

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

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

参照

  • ナッシュ均衡の計算- 正確なナッシュ均衡または近似ナッシュ均衡を計算する一般的な問題について説明します。

参考文献

インライン引用
  1. ^ V. Bubelis (1979). 「有限ゲームにおける均衡について」.国際ゲーム理論ジャーナル. 8 (2): 65– 79. doi :10.1007/bf01768703. S2CID  122843303.
  2. ^ ヴァジラニ、ヴィジェイ V. ;ニサン, ノーム;ティム・ラフガーデン;タルドス、エヴァ(2007)。アルゴリズムゲーム理論(PDF)。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-87282-0。
  3. ^ Tsaknakis, Haralampos; Spirakis, Paul G. (2007). 「近似ナッシュ均衡のための最適化アプローチ」 . Deng, Xiaotie; Graham, Fan Chung (編).インターネットとネットワーク経済学. コンピュータサイエンス講義ノート. 第4858巻. ベルリン、ハイデルベルク: 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). 「近似ナッシュ均衡のための最適化アプローチ」.インターネット数学. 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.
出典
  • H Dixon「複製産業における近似ベルトラン均衡」Review of Economic Studies、54 (1987)、47-62ページ。
  • H. エヴェレット「再帰ゲーム」HW クーンとAW タッカー編『 ゲーム理論への貢献』第3巻、数学研究年報第39巻、プリンストン大学出版局、1957年。
  • レイトン・ブラウン、ケビン、ショーハム、ヨアブ（2008年）、ゲーム理論のエッセンシャルズ：簡潔で学際的な入門、サンラファエル、カリフォルニア州：モーガン＆クレイプール出版社、ISBN 978-1-59829-593-188ページの数学入門書。3.7節を参照。多くの大学でWayback Machineから2000年8月15日にアーカイブされた無料オンライン版。
  • R. ラドナー「長期的だが有限な寿命を持つ寡占の非協力的イプシロン均衡における共謀行動」『経済理論ジャーナル』22、121-157、1980年。
  • ショーハム、ヨアブ、レイトンブラウン、ケビン（2009）、マルチエージェントシステム：アルゴリズム、ゲーム理論的、論理的基礎、ニューヨーク：ケンブリッジ大学出版局、ISBN 978-0-521-89943-7計算論的観点からの包括的な参考資料。セクション3.4.7を参照。オンラインで無料でダウンロードできます。
  • SH Tijs.非協力n人ゲームの正規形におけるナッシュ均衡、SIAM Review、23、225-237、1981年。
「https://en.wikipedia.org/w/index.php?title=Epsilon-equilibrium&oldid=1324070236」より取得