基于任意人数任意策略的防共谋均衡判断算法分析

· · 个人记录

已知防共谋均衡的定义如下：

如果一个博弈的某个策略组合满足下列要求:(1)没有任何单个博弈方的“串通”会改变博弈的结果,即单独改变策略无利可图;(2)给定选择偏离的博弈方有再次偏离的自由时,没有任何两个博弈方的串通会改变博弈的结果;(3)依此类推,直到所有博弈方都参加的串通也不会改变博弈的结果。满足这些要求时,可称为“防共谋均衡”。

防共谋均衡是多人博弈的重要内容，常被用于分析纳什均衡是否稳健的一个重要标准。当博弈方只有少数几个人时，判断是否存在稳定的纳什均衡、防共谋均衡是否存在可能需要花上一番工夫，但人力范畴之中尚可以完成。但当人数达到100、1000乃至十万几百万后，其分析难度便会呈指数级增长。本文试图在现有博弈论与计算机算法理论的框架之下，构建出n人博弈矩阵中防共谋均衡的算法判断，及其是否属于NP-hard与NPC问题的证明，以及在此基础上对于其问题求解的优化算法实现分析。

一、对于使用遍历算法的复杂度分析

假设给定了有n个参与人的策略组合S=(S_1,S_2,S_3,…,S_n)，每个人都有m个策略，要求判断是否具有纳什均衡，以及是否存在其他参与人共谋的可能性。首先应得出是否存在纳什均衡。

在不考虑复杂度的情况下，我们不妨采用遍历算法得出该策略空间的纳什均衡，基于划线法的一般原理，即固定第i名参与者的选择，在其余n-1名参与者的选择的结果中求得最大值result_{max}或者最小值result_{min}，并另外定义一个变量check记录该选择，遍历完该参与者所有的选择后，选择第i+1名参与者，按照最初的流程再次进行遍历，以此类推，直到走完所有的参与者的选择。此时再对判断变量check进行一遍判断，得出check共同存在的交点后将其记录，并进行输出。

可利用深度优先搜索或广度优先搜索进行解决，伪代码如下：

1.1

int dfs(int k, int m)
{
    if (k == n)
        break;
    if (k == m)
        dfs(k + 1, m);
    for (int i = 1; i <= m; ++i)
        maxn = max(maxn, s[k][i]);
    dfs(k + 1, m);
    return maxn;
}
for (int i = 1; i <= n; ++i)
    a[k++] = dfs(1, i);

其中check可在代码第8行中插入，只需令check等于取得最大值时的i即可。 对于复杂度的分析，易知在代码中，先对n个人进行遍历，又对剩下n-1个人的m个策略进行最大最小值的求解（上述代码假定为最大值），因而复杂度为O(mn^2 ).

此时我们只是找到了纳什均衡的存在，我们还需要在此基础上判断是否存有共谋的可能性。由防共谋均衡的定义可知，若均衡A为防共谋均衡，当且仅当在该选择的空间之下，任意t(t≤n-1)个人串通的结果都不会使得其所有参与串通人员的收益大于未串通之前的收益。因而对于每一位n-1个人的串通组合进行遍历，不难列出如下式子：

C_{n-1}^1+C_{n-1}^2+C_{n-1}^3+⋯+C_{n-1}^{n-1}=2^{n-1}-1

此时我们发现，在检查是否存在防共谋均衡的时候，我们需要在得出的纳什均衡相对确定的选择之中再度以未被共谋的人的策略组合之中进行遍历，依次比较有无改良其收益的其他选择存在。在最坏的情况下，便是i从1遍历到n-1时，才发现有串通的可能性存在，而刚好k遍历到了最后一个决策组合时才发现，此时遍历的最坏情况次数为：

m×\sum_{k=1}^{n-1}(n-k-1) C_{n-1}^k=m(2^{n-2}-1)(n-1)

最后得出防共谋均衡遍历算法的最坏情况复杂度为O(m[n^2+(n-1)(2^{n-2}-1)]).

但是仔细思考，我们是否忽略了什么因素？

倘若我们不止得出一个纳什均衡，而是s个纳什均衡呢？

此时复杂度自然而然的就变为O(sm[n^2+(n-1)(2^{n-2}-1)])了，而此时最坏程度，便是存在n个纳什均衡，则时间复杂度则变为O(m[n^3+n(n-1)(2^{n-2}-1)]).这样的复杂度，显然对于任何一种计算机来说，只要数据稍微复杂一些，其运算的负荷和时间便会呈指数级增长了。

二、对于NP、NP-hard以及NPC性质的证明

由上文（一）可知，防共谋均衡的求解问题（为了方便讨论，我们不妨设该问题为Y）是在多项式时间内可验证的问题，因而，我们可在此基础之上初步探讨该问题是否符合本标题所列举的那些性质。

首先是否属于NP的问题，由上文论述可知，对于一组给定的数据，纳什均衡是否存在、即使存在有多少，是无法加以确定的，而最坏情况则是O(m[n^3+n(n-1)(2^{n-2}-1)])，数据规模和运算空间是确定的，因而，Y∈NP.

欲判断某问题是否属于NPC问题，我们应当首先判断该问题是否同时满足NP和NP-hard，而欲判断NP-hard，我们需要证明对于所有的NP问题，都可以约化到本问题之上。换句话说，欲证明该问题不是一个NP-hard的问题，只需证明该问题可以继续约化到下一个NP问题之上即可；反之，则需要证明存在一个NPC问题X，使得X≤Y_{NP}，且X有解当且仅当Y有解。基于此，我们对防共谋均衡的NP-hard问题进行分析：

首先，我们应当考虑Y是否可以化为其他的子问题。由上文的分析易知，在防共谋均衡的计算过程中，我们将算法分为了两个阶段：寻找纳什均衡、在纳什均衡中寻找串通可能。因而，我们剩下的工作，只需证明此二者中有一个是NPC问题，或者都不是NPC问题即可。

纳什均衡的NP问题，Constantinos Daskalakis与 UC伯克利的Christos Papadimitriou、英国利物浦大学的Paul Goldberg早在2008年便证明出纳什均衡属于NP问题的一个子集，而且是属于PPAD-完全问题^{[1]}。因而，对于防共谋均衡，则自然而然地得出结论，其属于NP-hard问题。

综上所述的一切讨论结果，便可得出，防共谋均衡是NPC问题，无法通过穷举以外的手段将其进行计算。

三、对于遍历算法的优化计算

我们不妨在判断纳什均衡的同时，对于某些结果，其大小是小于任何一种其他得益，以至于即使将其考虑，也不会有任何的理性人会选择将其作为一种可能性进行选择。因而，对于有n个参与者的选项，则出现了n个最劣势的情形可以不将其考虑。然而此类剪枝依旧有劣势存在：加入此最劣势的情形本身便是纳什均衡的一种，依旧不能避免继续遍历n-1种选择的最坏情况存在。其次，可以优化check变量的逻辑，伪代码如下：

dfs()
{
    ...;
    for (…)
    {
        …;
        if (max = another value)
            check = false;
    }
    …;
}
for (…)
{
    dfs(…);
    if (check)
        anti_collusion_find();
    if (anti - collusion is true)
        break;
}

其中，省略号的内容与1.1内容相同，故省略。

如此便可在找到第一个防共谋均衡时及时跳出循环，避免无意义的重复寻找。然而此种方法不仅亦存在剪枝共有的弊病，适用范围也十分局限——若问题从判断有无变为计算防共谋均衡的数量，则该方法失效，需要考虑其他的剪枝方法。 最后一种剪枝方法，是对于几乎所有防共谋均衡类问题都适用的方法：额外定义一个数组K，或者利用结构体和类继承的形式定义一个空间，内部存储的变量如下：

1）参与者的编号i;

2）参与者的策略空间数组a_m;

3）参与者的决策对应编号num;

4）跳出循环判断用bool变量check（默认为false）。

此时，在录入数据结束后，在寻找纳什均衡之前，我们需要预先进行如下的预处理：

1）通过排序算法，将策略收益按照升序或降序进行排列；

2）利用编号记录原本策略收益应处的位置。

最后，纳什均衡的寻找需假如判断该均衡对应的对策是否属于最大值，如果有，则将check标记为true，防共谋均衡的判断中加入如下判断逻辑：

1）判断被选中串通的t个人的check是否皆为true，如果有，则立即跳出循环，不再遍历；

2）选择num编号最小的对象进行遍历，若发现t个参与者对应的收益皆大于等于原收益，则立即跳出循环，不再遍历。

此时复杂度的计算如下：

排序算法复杂度为O(m×logm)，纳什均衡复杂度不变，而防共谋均衡的判断公式在最坏情况下依旧不变。虽然在客观上复杂度相较于前者提高了，但是随之换得的是高概率的及时退出循环的可能性，如果运气不是太过糟糕，此类优化甚至会比没有优化之前快上许多。

[1]Daskalakis C. The Complexity of Nash Equilibria[D]. the University of California, Berkeley, 2008.