美國加州大學伯克利分校的克里斯托斯·帕帕迪米特里歐(Christos Papadimitriou) 教授定義了PPAD（polynomial parity arguments on directed graphs，有向圖的多項式校驗參數）計算複雜類來描述經濟學中的計算問題。並與其合作者一起證明了在4 人及以上的博弈中，納什均衡的計算是屬於PPAD-Complete 的。
基本介紹
- 中文名：有向圖的多項式校驗參數
- 外文名：polynomial parityarguments on directed graphs
- 提出者：Christos Papadimitriou
經濟學中的計算問題
計算無處不在，任何一門成熟的學科都涉及一些計算問題，在經濟學中，這樣的概念尤其多。以經
濟學中的最基本概念“納什均衡”以及“市場均衡”的計算為例，它們與傳統計算機科學中所研究的計算問題存在很大區別：它們不是判定問題，納什均衡點的存在性是有納什定理直接保證的；它們也不是最佳化問題，因為沒有一個最佳化的目標。從本質上講，它們是一類不動點的計算問題，所以從傳統的NP-Complete（non-deterministic polynomial，非確定多項式完全問題）角度來研究他們的計算複雜度並不合適。為此，美國加州大學伯克利分校的克里斯托斯·帕帕迪米特里歐(Christos Papadimitriou) 教授定義了PPAD（polynomial parityarguments on directed graphs，有向圖的多項式校驗參數）計算複雜類來描述這類問題，並與其合作者一起證明了在4 人及以上的博弈中，納什均衡的計算是屬於PPAD-Complete 的。哥倫比亞大學的陳汐教授和上海交通大學的鄧小鐵教授把結果加強到二人博弈的納什均衡的計算也是屬於PPAD-Complete 的。
