静5前沿讲座回顾 | 周俊杰教授谈多层网络上的协作博弈

关键词：静5前沿讲座

编者按

2023年11月15日，清华大学的周俊杰教授访问北京大学前沿计算研究中心，并在静园五院作了题为“Coordination on Multilayer Networks”的报告，介绍了多层网络模型上关于个体选择、社会协作的概念、算法和应用。此次报告由中心教授孔雨晴老师主持。

周俊杰教授报告现场

多层网络协作模型与实际生活关系密切，围绕不同动机，不同环境和不完全信息之下的二元互补博弈广泛存在。比如对立技术的采用，不同的生涯选择等。不同的选择具有不互相兼容和个人偏好异质性的特征。周老师此次报告围绕这个主题进行展开。基本模型构造如下：每个玩家只能在二元动作之间二选一，选择一个动作后则进入到对应的网络，只和同样选择了这个动作的相邻用户交互。进而收益由自身对动作的独立偏好加上与同样选择的其他玩家/邻居的额外交互收益构成。后者由无向图网络定义，选择相同动作的玩家构成对应的网络层。周老师基于定义给出了四个假设：网络是无向但可能有权的；两个选择是不兼容的；两个交互权重中至少一个非负；在大多数情境下不同选择的独立价值相同。

周老师首先回顾了从早期两个人的协作博弈，到在网络上的协作博弈，再到复合活动、多层网络的相关工作。在他们的工作之前，已经有过针对交互网络和参与者收益的广泛研究，但更多地局限在单个网络。而现实情景中很多实例是关于多个网络、多种活动的。比如针对买家卖家交易市场通过在两侧设置不同提成来达到最大化收益等。这里的网络主要是静态的数值计算，给出一个确定的结果，和智能角度动态分布/学习的网络概念有所区别。

在此次报告中，周老师基于上面的模型，介绍了他们在多层网络上建立的协作博弈模型的研究工作。第一部分，对特定的参与者定义不同选择的效益差。在给定自身独立价值的前提下，因为只能选择获得其中一层网络的相邻交互收益，所以它取决于相邻其他玩家选择的分布。考虑到网络的非负性，这是一个超模博弈，效益差关于选择一个选项的相邻玩家分布单调递增。参与者根据效益差正负选择自己的动作。效益差的表达并不能合并成一个综合网络，因为前面还包含单个网络的度的部分。

之后，周老师向大家阐述了如何实现对多层网络上协作博弈的全局博弈计算。首先定义针对不同动作权重参数的阈值：参与者在权重参数高于阈值时选择第一个动作，否则选择第二个。然后引入对信号的扰动分布，从而取得贝叶斯纳什均衡，当扰动趋于0时可以计算出对应的给定权重分布的阈值，回到用期望给出的纯贝叶斯纳什均衡。可以证明这个均衡就是所求的对应每个参与者的最大均衡。

最后周老师介绍了简化前后 SAND（序列平均网络密度）算法的实现。重点是围绕网络密度（interconnectedness）和从 S 到 T 的链接情况（embeddedness）的两个步骤。第一步用前面的密度和独立收益情况计算F函数，计算为达到最大的平均值应取子集，如果所得部分非全集则除去前一步得到的子顶点集后重新计算最大均值对应子集。对上面的步骤进行递推，直到最终得到一个递减的阈值序列和一个递增的顶点子集序列。对多层网络的情况来说，主要的区别在于F函数的重新设计，不同特点的网络具备不同的结果。

报告最后，周老师又给出了相关的开放性问题。汇报引起了在座老师同学们的积极提问，讨论了和工作匹配等问题的联系和计算复杂性方面的优化。此次报告在热烈的讨论氛围中结束。

合影留念

图文 | 吴宇森

往期讲座

• 静5前沿讲座回顾 | 区文浩教授谈密码学前沿进展及在区块链中的应用

• 静5前沿讲座回顾 | 黄志毅教授谈数据驱动的拍卖机制设计问题

• 静5青年讲座回顾 | 卢丽强博士谈量子计算软件优化方法

• 静5杰出讲座回顾｜叶荫宇教授谈随机Fisher市场中的在线均衡标价问题

—   版权声明  —

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