9.1 算法与复杂度

文档摘要

9.1 算法与复杂度第九章：计算博弈论与求解工具 9.1 算法与复杂度：当理性遭遇可计算性边界我们常把博弈论想象成一出精密的智力戏剧——参与者各怀策略、彼此揣度、在信息与激励的张力中寻找最优落点。纳什在1950年那篇仅一页纸的论文，用不动点定理轻轻一推，便为这场戏剧奠定了存在性基石：只要策略集是紧凸集、支付函数连续，均衡就必然存在。可存在，不等于可抵达；存在，更不意味着可被人类或机器在有限时间内识别、验证、复现。这恰是计算博弈论（Computational Game Theory）诞生的原点：它不再满足于“是否存在”，而执着追问——“能否算出？多快能算出？算不准时，又能逼近到何种程度？