9.1.2 纳什均衡计算：Lemke-Howson算法

文档摘要

9.1.2 纳什均衡计算：Lemke-Howson算法在博弈论的广袤星图中，纳什均衡是那颗最耀眼、也最难以触及的北极星——它不承诺唯一性，不保证可构造性，更不向计算屈服于多项式时间。当两个理性玩家在零和之外的非合作博弈中角力，当收益矩阵不再对称、策略空间不再凸、最优反应映射不再连续，我们便踏入一片没有梯度、没有导数、甚至没有全局目标函数的荒原。而Lemke-Howson算法，正是人类在20世纪60年代锻造出的第一把真正意义上能在这片荒原上开凿出均衡解的镐头：它不依赖迭代收敛，不诉诸随机采样，不预设光滑性；