静5青年讲座回顾 | Argyrios Deligkas博士介绍求解近似纳什均衡的最新算法

关键词：静5青年讲座

编者按

2022年7月21日，伦敦大学皇家哈洛威学院（Royal Hollway, University of London）的 Argyrios Deligkas 博士受邀于北京大学前沿计算研究中心做题为“A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games”的线上报告。报告由中心邓小铁教授主持，相关内容通过蔻享学术、Bilibili 同步直播，线上数百人观看。

Argyrios Deligkas博士做在线报告

报告开始，Deligkas 博士首先讲解了  纳什均衡的历史发展。  近似纳什均衡是对纳什均衡进行松弛后定义的近似问题。近似参数  度量了结果对纳什均衡的近似程度。  越接近0，结果就越接近纳什均衡。因此，寻找一个计算迅速且计算结果保证  尽可能小的算法一直是近似纳什均衡研究的重心。

Deligkas 博士讲解 ε-纳什均衡的历史发展

Deligkas 博士先介绍了历史上人们寻找这样的算法的努力。一方面，从难解的层面上，陈汐、邓小铁、滕尚华以及 Daskalakis, PW Goldberg, CH Papadimitriou 在2009年的工作证明了在  时  近似纳什均衡是 PPAD 完全的，奠定了纳什均衡难解性的基础。A Rubinstein 在2016年证明了，如果假设 PPAD 具有指数时间复杂度，则存在某个  ，使得求解  近似纳什均衡是拟多项式复杂的，提示了多项式时间求解近似纳什均衡的可能下界。另一方面，人们也在寻找更好的求解近似纳什均衡的多项式算法。大量的工作将多项式算法的输出结果的近似参数保证从3/4、1/2逐渐下降，最终2007年 H Tsaknakis and PG Spirakis 提出的 TS 算法保证了算法的结果一定有0.3393的近似度。最后，Deligkas 博士引出了自己最近与 M Fasoulakis、E Markakis 合作的工作。他们对 TS 算法进行了改进，将算法的近似度改进到了1/3。

随后，Deligkas 博士讲述了自己工作的细节：将TS算法的结果分为五种情况讨论，并且针对不满足1/3近似度的最后两个情况进行特殊的改进。具体而言，TS 算法的基础是使用两名玩家的最大 regret 作为优化方法的损失函数，求解出一个具有较好性质的稳定点，并同时使用对偶方法求出稳定点的对偶解，以其线性组合为基础即可构建出近似度保证很低为0.3393的算法；而他们的工作则是在 TS 算法不能达到1/3的近似度时进一步求解各策略的线性组合的 best response 来提升该情况下算法的保证。

报告的最后，Deligkas 博士简单介绍了自己最近的另一篇合作工作，在近似 well-supported 纳什均衡的背景下将算法的界限提升到了1/2，同时展望了纳什均衡近似算法方面的未来。他指出，在非多项式算法和多项式算法之间还有巨大的鸿沟，等待着未来更多新的算法和理论去填补。

在讲座的最后，Deligkas 博士和参会的老师、同学们交流了论文中的一些细节以及未来的可能方向。值得一提的是，TS 算法的提出者之一 Paul Spirakis 也参加了会议。会后，他告知参会者，他的重要合作者、算法的另一位提出者 Haralampos Tsaknakis 在两年前因为感染新冠肺炎去世。在这里笔者也对 Tsaknakis 博士的逝世表示缅怀，并衷心希望我们能够赓续他们的使命，继续推进纳什均衡近似算法的理论研究。

报告回放：

图文 | 李东晨

PKU daGAME Lab

往期讲座

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。