Algorithms for Game Theory

HW1

纯策略的纳什均衡（NE），混合策略的NE的计算方法、复杂度分析

考虑一般情况：n players，每个player有$m$个策略，$i=1,2,\dots,n$。收益矩阵（payoff matrix）为$P=(p_{ij})$，$i=1,2,\dots,n$，$j=1,2,\dots,m$，这个矩阵有$m^n$个元素。

暴力枚举（Brute Force）：

纯策略（Pure Strategy）

固定某个 cell 后，要判断它是不是纯策略 NE。

对每个玩家 $i$：

• 目前他选了一个策略
• 还要检查他改成其他 $m-1$ 个策略时，收益会不会更高

所以一个玩家要检查 $m-1$ 次，$n$ 个玩家总共要检查$n(m-1)$次。

因此，检查一个 cell 的时间是$O(nm)$

一共有 $m^n$ 个 cell，每个 cell 检查成本是$O(nm)$，所以总复杂度是$O(m^n \cdot nm)$

要注意：是相对于 payoff table 的输入大小而言是 polynomial。因为一个 (n)-player normal-form game 的 payoff table 本身就要写出所有 (m^n) 个策略组合的收益；每个 cell 里有 (n) 个玩家的 payoff，所以输入规模大约是$O(m \cdot \text{input size})$

所以它是对输入长度的多项式时间算法。

所以更准确地说：

• 相对于显式给出的 normal-form payoff matrix 的大小，找纯策略 NE 是 polynomial

混合策略（Mixed Strategy）

在混合策略里，每个玩家不是只选一个动作，而是给每个动作一个概率。但通常 只有一部分动作概率 > 0。这部分动作集合叫：support。

枚举所有可能的 support 组合，对每个 support 组合求一组方程：

• support 里的动作收益必须 相等
• 非 support 动作收益 ≤ support 收益

假设每个玩家有 $m$ 个动作。support所有非空子集的数量为$2^m-1$。对于 $n$ 个玩家，总共有$(2^m-1)^n$个 support 组合。所以遍历所有 support 组合的时间是$O((2^m-1)^n)$，即指数时间。