ppad专题

人工智能笔记之专业选修课4.1.5 - 博弈论 5.计算纳什均衡难点,复杂度层级,Lemke-Howson算法,PPAD

计算纳什均衡难点 compute a Nash equilibrium 纳什均衡早期历史: 1928年约翰·冯·诺依曼 (John von Neumann),现代博弈论的奠基人之一:研究证明了零和博弈 (zero sum game) 中存在纳什均衡。 在证明过程中 他使用了布劳威尔不动点定理 需要用到在线性规划中计算不动点的算法 一个是但泽 (Danzig) 的算法,相当于我们现