计算纳什均衡的复杂性

经济主体收敛到均衡需要多久？通过研究在博弈中计算混合纳什均衡的问题复杂性，我们提供了证据，表明存在一些博弈，收敛到这样的均衡所需的时间极其漫长。传统上，计算问题分为两类：一类是具有多项式时间算法的问题，另一类是NP-hard问题。然而，NP-hard性的概念无法应用于“每个实例都有解”的稀有问题——例如，在博弈中，纳什定理断言每个博弈都有一个混合均衡（现称为纳什均衡，以纪念该结果）。我们展示找到纳什均衡在一类称为PPAD的问题中是完全的，这类问题包含几个其他已知的难题；PPAD中的所有问题共享每个实例都有解的相同证明风格。