フィックスP

コンピュータサイエンスにおいて、FIXPは2010年にKousha EtessamiとMihalis Yannakakisによって導入された計算量クラスである。^[1]これは、Brouwerの不動点定理の条件を満たす関数の不動点を計算することで解ける問題を表す。より正式には、FIXPは、有理定数を持つ基底{+,*,-,/,max,min}上の代数回路で表される関数の不動点計算問題として表現できる探索問題を含む。

彼らは、経済学とゲーム理論におけるいくつかの基本的な問題が FIXP に対して完全であることを証明しています。特に次のことが証明されています。

ナッシュ均衡計算- 3 人以上のプレイヤーによるゲームで、正確な、または近似的な混合戦略ナッシュ均衡を計算します。
市場均衡計算- 代数的需要関数を持つ交換経済の競争均衡価格を計算します。

FIXPのメンバーシップの証明

Filos-Ratsikas、Hansen、Høgh、Hollender ^{[2]は、FIXP への帰属関係を証明するための一般的な手法を提示している。彼らの手法は、彼らが「OPT-gate」と呼ぶブラックボックスを構築し、ほとんどの}凸最適化問題を解くことができる。彼らはこの手法を用いて、以下の FIXP への帰属関係を証明している。

一般的な凹型効用を持つ Arrow-Debreu 市場における市場均衡の計算。
非常に一般的な評価を使用して羨望のないケーキカットを計算することは、FIXP 完全です。

彼らはまた、ナッシュ均衡計算と公平なランダム割り当てのためのHyllandとZeckhauser ^[3]のメカニズムのFIXPメンバーシップを証明しました。

他のクラスとの関係

PPADとの関係

エテッサミとヤナカキスは、「 FIXPの区分線形部分は PPADに等しい」と簡潔に説明しています。言い換えれば、^[4] PPADの問題は、入力関数が区分線形であるFIXPの問題です。

PPADの問題の解は有理数であるのに対し、FIXPの問題の解は代数数である。^[5]

PPADはNPとco-NPの交差にある関数クラスに含まれるが、FIXPははるかに困難であると推測され、PSPACEの「より困難な」端に位置する。^[5]

SRSとの関係

1/2 より小さい任意の因数に対する近似ナッシュ均衡を計算することは、少なくとも平方根和問題と同じくらい困難です。

参考文献

^ エテッサミ、コウシャ;ヤナカキス、ミハリス（2010 年 1 月）。「ナッシュ均衡とその他の不動点の複雑さについて」。SIAM ジャーナルオンコンピューティング。39 (6): 2531–2597。土井:10.1137/080720826。ISSN 0097-5397。
^ フィロス＝ラツィカス、アリス;ハンセン、クリストファーA.ホー、カスパー。ホレンダー、アレクサンドロス (2023-04-04)。「凸最適化による FIXP メンバーシップ: ゲーム、ケーキ、マーケット」。SIAM ジャーナルオンコンピューティング: FOCS21–30。arXiv : 2111.06878。土井：10.1137/22M1472656。ISSN 0097-5397。
^ Hylland, Aanund; Zeckhauser, Richard (1979). 「個人のポジションへの効率的な配分」. Journal of Political Economy . 87 (2): 293. doi :10.1086/260757. S2CID 154167284.
^ Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19). 「勾配降下法の計算量：CLS = PPAD ∩ PLS」. Journal of the ACM . 70 (1): 7:1–7:74. arXiv : 2011.01929 . doi :10.1145/3568163. ISSN 0004-5411. S2CID 263706261.
^ ab Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra (2017-06-19). 「レオンチェフ市場とPLC市場における複雑性の厳密な均衡と近似均衡における解決」.第49回ACM SIGACT計算理論シンポジウム議事録. STOC 2017. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp. 890– 901. doi :10.1145/3055399.3055474. ISBN 978-1-4503-4528-6。

このコンピュータサイエンスの記事はスタブです。記事を拡張することでWikipediaに貢献できます。

[1] エテッサミ、コウシャ;ヤナカキス、ミハリス（2010 年 1 月）。「ナッシュ均衡とその他の不動点の複雑さについて」。SIAM ジャーナルオンコンピューティング。39 (6): 2531–2597。土井:10.1137/080720826。ISSN 0097-5397。

[2] フィロス＝ラツィカス、アリス;ハンセン、クリストファーA.ホー、カスパー。ホレンダー、アレクサンドロス (2023-04-04)。「凸最適化による FIXP メンバーシップ: ゲーム、ケーキ、マーケット」。SIAM ジャーナルオンコンピューティング: FOCS21–30。arXiv : 2111.06878。土井：10.1137/22M1472656。ISSN 0097-5397。

[hz79-3] Hylland, Aanund; Zeckhauser, Richard (1979). 「個人のポジションへの効率的な配分」. Journal of Political Economy . 87 (2): 293. doi :10.1086/260757. S2CID 154167284.

[4] Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19). 「勾配降下法の計算量：CLS = PPAD ∩ PLS」. Journal of the ACM . 70 (1): 7:1–7:74. arXiv : 2011.01929 . doi :10.1145/3568163. ISSN 0004-5411. S2CID 263706261.

[:5-5] Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra (2017-06-19). 「レオンチェフ市場とPLC市場における複雑性の厳密な均衡と近似均衡における解決」.第49回ACM SIGACT計算理論シンポジウム議事録. STOC 2017. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp. 890– 901. doi :10.1145/3055399.3055474. ISBN 978-1-4503-4528-6。