本文主要是介绍人工智能笔记之专业选修课4.1.5 - 博弈论 5.计算纳什均衡难点,复杂度层级,Lemke-Howson算法,PPAD,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧! 计算纳什均衡难点 compute a Nash equilibrium 纳什均衡早期历史: 1928年约翰·冯·诺依曼 (John von Neumann),现代博弈论的奠基人之一:研究证明了零和博弈 (zero sum game) 中存在纳什均衡。 在证明过程中 他使用了布劳威尔不动点定理 需要用到在线性规划中计算不动点的算法 一个是但泽 (Danzig) 的算法,相当于我们现在说的线性规划对偶理论 (LP duality) ,在实践中被广泛应用的,这是指数复杂度的一个算法。 卡哈基扬 (Khachiyan) 的多项式级线性规划算法,实际上在实践中并不常用 1950年约翰·纳什证明了任意博弈中纳什均衡的存在性 催生了一系列的算法 这篇关于人工智能笔记之专业选修课4.1.5 - 博弈论 5.计算纳什均衡难点,复杂度层级,Lemke-Howson算法,PPAD的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!