它有什么作用?
纳什均衡是博弈论中的一个解概念,指在其中任何一个参与者都无法通过单方面改变策略来获得更好收益的状态。该概念由约翰·纳什(John Nash)于1950年正式提出。Lemke-Howson算法通过识别策略多面体(strategy polytopes)中完全标记的顶点对来计算双矩阵博弈(bimatrix games)的均衡点。
方法背后的直觉
在纳什均衡中,每个参与者的策略都是对其他所有参与者策略的最佳响应。设想这样一种情境:双方都知道对方的策略,但都不愿改变,因为这样做只会损害自身利益。Lemke-Howson算法利用博弈多面体的几何特性,跟踪标记(未满足的约束条件),并通过顶点进行迭代(pivoting),直至找到一个完全标记的顶点对——即一种双方均无有利可图的偏离的配置。
历史学
约翰·纳什(John Nash)在其1950年的博士论文中证明,每个有限博弈至少存在一个混合策略纳什均衡。1964年,Lemke和Howson发表了第一个寻找这些均衡的构造性算法,将纳什的存在性证明转化为实用的计算方法。他们的工作成为计算博弈论和算法经济学的基础。
何时使用
在研究参与者为两人、策略空间离散的博弈,或寻求完全混合策略均衡(fully mixed equilibria)时,可使用纳什均衡分析。适用于模拟竞争、谈判和协调问题,其中策略互动至关重要。Lemke-Howson方法最适用于非退化(non-degenerate)的双矩阵博弈;退化情况可能需要符号计算或扰动。
局限与注意事项
- 仅限于双矩阵(两人)博弈;扩展到n人博弈是NP难问题
- 在退化博弈中会失效或效率低下,因为在退化博弈中可能存在多个进入迭代的可能
- 可能只找到一个均衡;非零和博弈通常存在多个均衡
- 不能直接处理动态博弈或扩展型博弈(extensive-form games),除非进行重构
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 在计算上,对于有限双矩阵博弈,寻找纳什均衡的效率很高
- 对于非退化博弈,保证收敛到一个完全标记的顶点对
- 提供了连接组合几何与博弈论的理论基础
- 可应用于混合策略均衡,这通常比纯策略结果更符合实际
应用
- 经济学:模拟寡头垄断竞争和市场中的定价行为
- 拍卖与机制设计:分析第一价格密封投标拍卖中的竞标策略
- 网络安全:预测网络安全博弈中的攻击者-防御者均衡
- 野生动物生物学:分析捕食者-猎物相互作用中的进化稳定策略
使用方式
使用方式
将双矩阵博弈转化为两个线性互补问题(LCP),每个问题对应一个参与者,代表其最佳响应条件。
根据哪些参与者的激励约束被违反,为策略多面体的边和顶点分配标记。
从全1顶点(完全标记)开始,执行类似单纯形法的迭代操作,在多面体中导航,移除和添加标记,直到发现一个完全标记的顶点对。
通过检查在对方策略不变的情况下,任何一方都无法获得更高收益,来确认双方策略构成相互的最佳响应。
常见陷阱
- 假设存在唯一均衡;许多博弈存在多个具有不同收益影响的纳什均衡
- 将混合策略均衡(概率性博弈)与纯策略均衡混淆,导致对参与者行为的误解
- 忽略了均衡的必要条件和充分条件之间的区别;完全标记的顶点对满足最优性,但如果参与者无法协调,则可能无法实现
常见问题
一个博弈可以没有纳什均衡吗?
纯策略纳什均衡可能不存在(例如,石头-剪刀-布),但每个有限博弈至少存在一个混合策略均衡,其中参与者以特定概率在行动上进行随机化。
混合策略均衡与纯策略均衡有何不同?
在纯策略均衡中,每个参与者确定性地选择一个特定行动。在混合策略均衡中,每个参与者对行动使用一个概率分布。混合均衡通常更具普遍性,并且在纯策略均衡不存在时存在。
为什么Lemke-Howson算法比暴力搜索更受青睐?
该算法利用策略空间的凸多面体结构,将搜索空间呈指数级缩小,并在非退化博弈中以多项式时间收敛,而暴力枚举随着策略空间的增长而变得不可行。
相关方法
参考文献
Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.
打开 DOI 文献已复制。Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.
打开 DOI 文献已复制。