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

本文主要是介绍人工智能笔记之专业选修课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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:https://blog.csdn.net/fsdaewrq/article/details/104969186
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/712986。如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！我们的邮箱：23002807@qq.com