PPAD（複雑さ）

コンピュータサイエンスにおいて、PPAD（「有向グラフ上の多項式パリティ引数」）は、1994年にクリストス・パパディミトリウによって導入された複雑性クラスです。PPADは、パリティ引数によって完全であることが示される関数に基づくTFNPのサブクラスです。 ^{[1] [2]} このクラスは、ナッシュ均衡を計算する問題を含んでいるため、アルゴリズムゲーム理論の分野で大きな注目を集めました。この問題は、少なくとも3人のプレーヤーがいるPPADではDaskalakis、Goldberg、Papadimitriouによって完全であることが示され、後にChenとDengによって2人のプレーヤーに拡張されました。^{[3] [4]}

PPAD は、完全であることが保証されているFNPの関数問題のクラスであるTFNPクラスのサブセットです。TFNPの正式な定義は次のとおりです。

二項関係 P( x , y ) が TFNP に属するのは、xとy の両方が与えられた場合にP( x , y ) が成り立つかどうかを決定できる決定論的多項式時間アルゴリズムが存在し、すべてのxに対して、 P( x , y ) が成り立つようなyが存在する場合のみです。

TFNP のサブクラスは、解が常に存在することを証明するために使用される数学的証明の種類に基づいて定義されます。非公式には、PPAD は、有向グラフのパリティ引数に基づいてP( x、y ) が成り立つyが存在するという保証がある TFNP のサブクラスです。クラスは、 End-Of-The-Lineと呼ばれる完全な問題の 1 つを指定することによって正式に定義されます。

G は、各頂点が最大 1 つの先行頂点と最大 1 つの後続頂点を持つ有向グラフ (場合によっては指数関数的に大きい) です。 G は、頂点vの先行頂点と後続頂点 (存在する場合) を返す多項式時間で計算可能な関数 f( v ) ( vのサイズの多項式) を与えることで指定されます。 G に先行頂点のない頂点sが与えられた場合、先行頂点も後続頂点もない頂点t≠ sを見つけます(問題への入力は、ソース頂点sと関数 f( v ) です)。言い換えると、s以外の有向グラフのソースまたはシンクが必要です。

G の構造により、隣接する頂点が 1 つだけの頂点はペアで出現するため、s が存在する場合、そのようなt も必ず存在します。特に、 sが与えられている場合、 sから始まる文字列のもう一方の端にそのようなt を見つけることができます。( f を繰り返し評価するだけでは、指数関数的に時間がかかる可能性があることに注意してください。)

PPADは、 TFNPに含まれるPPA （無向グラフのパリティ引数の対応するクラス）に含まれています（ただし、等しいかどうかはわかりません）。PPADは、TFNPの別のサブクラスであるPPPにも含まれています（ただし、等しいかどうかはわかりません）。PPPにはCLSが含まれています。^[5]

PPAD は困難であると考えられている問題の一種ですが、PPAD 完全性を得ることはNP 完全性を得ることよりも扱いにくさの証拠としては弱いものです。 NP は意思決定問題の一種であるという技術的な理由から、PPAD 問題は NP 完全ではあり得ませんが、PPAD 問題の答えは常に「はい」です。なぜなら、その解決策を見つけるのは難しいかもしれませんが、解決策が存在することがわかっているからです。^[6]しかし、PPAD と NP は密接に関連しています。 特定のゲームにナッシュ均衡が存在するかどうかという質問は、答えが常に「はい」であるため NP 困難ではあり得ませんが、2 番目の均衡が存在するかどうかという質問は NP 完全です。^[7] PPAD 完全問題の例としては、ナッシュ均衡を見つけること、ブラウワー関数の不動点を計算すること、市場におけるアロー・ドブリュー均衡を見つけることなどが挙げられます。^[8]

Fearnley、Goldberg、Hollender、Savani ^[9]は、CLSと呼ばれる複雑性クラスがPPADとPLSの共通部分に等しいことを証明した。

• 均衡、固定点、複雑性クラス：概観^[10]

• 2人プレイのゲームにおけるナッシュ均衡^[3]または、任意の人数のプレイヤがいるゲームにおけるイプシロン均衡^[8]を見つける。

• スペルナーの補題における3色点の探索。^[11]
• 効用関数が多項式時間アルゴリズムによって与えられた場合に、嫉妬のないケーキカットを見つける。 ^[12]