在政府组织的无线电频谱拍卖中，多家电信公司需同时对多个频段提交竞价组合。由于每个公司可选择的出价策略涉及不同频段的组合定价，其策略空间呈现高维特征。在此博弈中，当所有可能的策略组合及其对应收益均为共同知识时，每家公司都希望确保，即便竞争对手的出价策略存在细微偏差（例如因市场价值误判导致的非最优出价），且此类偏差的发生概率与其引发的收益损失呈负相关，自身策略仍能维持最优性。此时，如何确定各公司的最优响应策略成为关键问题。

这种互动关系可建模为正则式博弈：每个参与者都有一系列可选策略，所有参与者同时选择策略后，会根据策略组合获得相应收益。均衡是一种稳定的策略选择状态，在此状态下，任何参与者都没有动力单方面改变自己的策略。Myerson于1978年提出的“适当均衡”概念对均衡理论做出了重要拓展：它假设参与者会以极小的概率选择到非最优策略，且要求选择到某个非最优策略的概率要和这个策略带来的损失大小成反比。这一特性恰好刻画了频谱拍卖中公司面对对手策略扰动时的稳健决策需求。然而，在参与者数量众多且策略空间维度较高的复杂博弈中，适当均衡的计算面临显著障碍，传统计算方法往往因计算复杂度高而难以实施。

针对这一难题，西安交通大学管理学院曹译尹助理教授联合深圳技术大学陈寅副教授、香港城市大学党创寅教授开展研究提出了一套系统性的解决方案，并以“A Differentiable Path-Following Method with a Compact Formulation to Compute Proper Equilibria”为题发表将研究成果发表在国际期刊《INFORMS JOURNAL ON COMPUTING》 （UTD 24 期刊）上 。该研究提出了一种可微路径跟随方法，结合紧凑公式化表达，来高效计算正则式博弈中的适当均衡。

首先，文章创新性地设计了一种可微路径跟踪方法：通过在原始博弈中引入扰动参数和障碍函数，构建一个参数化的新博弈。随着参数变化，新博弈的均衡会从简单初始点连续过渡到目标均衡。这种方法就像是为均衡计算铺设了一条“导航路线”，通过连续调整参数逐步逼近目标，有效避免了传统方法常见的局部收敛问题。采用该方法对左图所示的正则式博弈进行求解，得到右图中的光滑路径。当参数t趋近于0时，该路径收敛所得的解集构成一个适当均衡。

然而，由于适当均衡的严格定义导致约束条件呈指数级增长，文章进一步提出了紧凑公式化技术。借助排序网络，将变量和方程数量从指数级降至多项式级。通过严格的数学证明这种简化后的约束系统与原系统等价。这意味着在保证计算结果准确性的同时，计算复杂度得到了显著降低。这一进展使得算法能够有效处理高维博弈场景。

该研究更进一步的突破来自概念层面的创新。文章提出了“完美d-适当均衡”这一新概念，通过引入调节参数d，在保持均衡适当性的同时，显著降低了计算精度的要求。理论证明，当d趋近于零时，新概念会收敛到传统适当均衡；而实际计算表明，即使d取值较大（如1/5），仍能得到令人满意的结果。文章进一步提出了一种计算完美d-适当均衡的可微同伦方法。令d=1/5，应用该方法求解前述左图中的正则式博弈，得到下图所示的光滑路径。当参数t趋近于0时，该路径收敛所得到的解集不仅构成一个完美d-适当均衡，而且与上文求得的适当均衡完全一致。

在算法实验部分，本文在随机生成的大规模博弈中对这些方法进行了测试。结果显示：初始的可微路径跟踪方法在计算完美d-适当均衡时比计算适当均衡时展现出更高的效率；当结合紧凑公式化技术后，计算完美d-适当均衡的速度得到进一步提升。

整套方案就像是为适当均衡计算打造了一个“导航系统”，不仅修了一条高速公路（可微路径），还设置了简化路标（紧凑公式化），甚至允许司机灵活绕行（完美d-适当均衡）。实验数据证实，这一系统不仅能够快速精准地抵达目的地（适当均衡），更能应对复杂路况（大规模博弈场景），为实际决策应用提供了强有力的计算工具。

作者信息：

曹译尹，西安交通大学管理学院助理教授，主要研究方向：博弈论，计算经济学，供应链管理

陈寅，深圳技术大学副教授；党创寅，香港城市大学教授。

原文链接：https://pubsonline.informs.org/doi/10.1287/ijoc.2022.0148