TheWebConf 2025 Oral｜凸成本函数和异质性博弈主体下的网络公共品博弈

关键词：纳什均衡, 公共品博弈, 网络博弈

导读

本文是互联网领域国际重要会议 TheWebConf 2025 入选的口头报告论文 Networked Digital Public Goods Games with Heterogeneous Players and Convex Costs 的解读。该工作由北京大学邓小铁课题组主导完成。

文章针对具有凸成本函数的异质性博弈主体构成的网络公共品博弈问题，对纳什均衡的存在唯一性展开了研究。文献对网络公共品博弈问题的研究集中于博弈主体具有线性成本函数的模型上，该文章首次将问题扩展到博弈主体具有凸成本函数的一般情形。

论文作者按照姓氏首字母排序，为江南大学教授程郁琨、北京大学讲席教授邓小铁和北京大学博士生马允轩。

← 扫码跳转论文

论文地址：

https://arxiv.org/abs/2502.01001

背景

在数字时代，开源软件和公开数据库等资源构成了数字公共品的重要组成部分，为互联网提供了广泛的利益，公共品对互联网的重要性也日益显著。然而，这些公共品的非排他性和非竞争性常常导致供给不足，这一问题因个体的搭便车行为而进一步加剧。最近 Wikipedia（维基百科）向广大用户募集捐款就是一个典型的例子，尽管 Wikipedia 提供了难以用金钱衡量的知识价值，却鲜有用户为之捐款。而对于一般的公共品而言，不同用户之间可能产生各种各样的复杂互动，形成了具有网络结构的公共品博弈。

对网络公共品博弈的研究可以追溯到 21 世纪初。Bramoullé 和 Kranton 首次提出了网络公共品博弈模型，并对同质的、具有线性成本函数的博弈主体在无向、无权图上的纳什均衡展开了研究。之后，López-Pintado [2013] 和 Bramoullé 等人 [2014] 分别将模型延伸到了有向图和带权图上，Bayer 等人 [2023] 考虑了博弈主体的效用函数具有异质性的模型。前人的工作全部假设博弈主体具有线性的成本函数。这个假设尽管带来了数学上的便利，在很多场景下仍然不切实际。

模型与技术难点

我们假设这个博弈具有 $n$ 个博弈主体，网络结构可以表示为 $W \in \mathbb{R}^{n\times n}$ ，刻画了博弈主体之间的相互作用，其中 $w_{ij}$ 表示博弈主体 $j$ 的单位努力可以给博弈主体 $i$ 带来多少单位的回报，并做归一化 $w_{ii}=1$ 。令 $\boldsymbol{x}=\left(x_{1}, \ldots, x_{n}\right) \in \mathbb{R}^{n}$ 代表博弈主体的一个策略组合，其中 $x_i$ 是博弈主体 $i$ 的策略，也代表着博弈主体 $i$ 的努力程度，因此 $\boldsymbol{k}=W\boldsymbol{x}\in\mathbb{R}^n$ 代表博弈主体的回报向量，其中 $k_i$ 代表博弈主体 $i$ 的总回报。

每个人的效用函数可以被表示为 $u_i(\boldsymbol{x})=f_i (k_i )-c_i (x_i )$ ，其中 $k_i$ 由 $k=Wx$ 给出， $f_i(k_i)$ 表示博弈主体 $i$ 对回报 $k_i$ 享有的严格单增且凹的价值函数， $c_i(x_i)$ 表示博弈主体 $i$ 对自身努力 $x_i$ 承担的严格单增且凸的成本函数。纳什均衡的解概念由效用函数 $u_i(\boldsymbol{x})$ 自然定义。

上图描绘了一个网络公共品博弈的例子。这个例子共有 $n=4$ 个博弈主体，分别用节点表示，有向箭头上的值表示 $W$ 中对应元素的权重，未标记则视为0权重。节点上的 $x$ 表示努力值， $k$ 表示收获值。

如果成本函数是线性的， $u_i(\boldsymbol{x})=f_i(k_i)-c_i\cdot x_i$ ，由纳什均衡的概念可知，若 $x^*$ 是纳什均衡应有 $\frac{\partial u_{i}}{\partial x_{i}}\left(x^{*}\right)=f_{i}^{\prime}\left(k_{i}^{*}\right) w_{i i}-c_{i}=0$ ，即每个人的最优努力程度 $x^*_i$ 应该使得对应的 $k^*_i$ 满足 $f_{i}^{\prime}\left(k_{i}^{*}\right) =c_i$ 。通过这种分析， $f_i$ 的函数形式也无关紧要，真正发挥作用的是每个博弈主体满足前式的唯一 $k^*_i$ 。前人的研究皆通过这种方式对问题进行了简化，但如果成本函数并非线性，这种推导则难以适用。然而，如果 $c_i(x_i)$ 为线性函数施加很小扰动所得，可想而知均衡的性质在一般情况下不会发生太大改变。对于这种情况，应该用什么数学手段对均衡的性质加以分析呢？

近似势能博弈

为了分析成本函数非凸的情况，我们需要一个中间产物——近似势能博弈（near-potential game）。这个概念是借助势能博弈（potential game）的概念提出的。直观而言，如果每个博弈主体的效用函数和某个势能函数都足够接近，那么这个博弈可以称之为近似势能博弈。下图是一个对近似势能博弈的直观理解。

对于势能博弈，一个为人所熟知的结论是如果势能对任意博弈主体的策略是凹函数，那么势能的局部极小值对应于纳什均衡；如果势能对全体博弈主体的策略是（强）凹函数，那么势能具有唯一的局部极小值，因此也具备唯一的纳什均衡。我们将上述结论推广到近似势能博弈，并且刻画了上述结论成立的条件（见下图引理3.2）。

将网络公共品博弈视作近似势能博弈

我们下一步要消除网络公共品博弈和近似势能博弈的隔阂。我们发现，存在三种网络公共品博弈类型，这些类型可以构造势能函数使得博弈成为（严格）势能博弈。分别是：独立利益博弈（individual-interest game），公共利益博弈（common-interest game）和对称博弈（symmetric game）。下面三张图直观展示了这三种博弈结构。每张图都是在本文开始的图通过修改得到。

1. 独立利益博弈

2. 公共利益博弈

3. 对称博弈

对于网络公共品博弈的分析则通过以下步骤完成: 首先，将一个一般化的网络公共品博弈看作如上三种博弈之一的近似，构造对应的近似势能博弈，并保证纳什均衡在这个变换下保持不变；其次，利用引理 3.2 对近似势能博弈中均衡的刻画，从而得到原博弈问题均衡的刻画。注意到尽管对称博弈要求了线性成本函数，但通过近似势能函数的方式，这并不妨碍本研究的结果依然适用于非线性成本函数的模型中。

总结

本研究提出了一种新颖的视角来分析异质性博弈主体和凸成本函数下的网络公共品博弈，并拓展了对网络公共品中策略性互动的传统理解。通过了解纳什均衡得以实现和维持的条件，本研究有助于政策制定者更好地设计对互联网经济和社交网络的干预和激励措施，从而鼓励公共品维持在最佳贡献水平。

图文 | 马允轩

PKU daGAME Lab

算法博弈论实验室

Distributed and Automated Games and Managerial Economics Lab

算法博弈论实验室由邓小铁教授于2019年创立，研究方向为算法博弈论、互联网和区块链经济学、多智能体及强化深度学习理论。科研兴趣聚焦在人和智能体在互联网、物联网和区块链交互环境下多方博弈的理论与方法论建立，包括数据信息的认识论刻画、均衡和动力学分析、计算复杂性和算法设计。关注计算与通讯技术兴起中应用领域的问题，特别关注互联网广告机制设计、共享经济中的激励分析和合作竞争，以及区块链的高效共识、声誉机制和跨链机制设计。

↑↑扫码转实验室主页↑↑

实验室 PI 简介：邓小铁讲席教授

实验室相关新闻：#PKU daGAME

daGAME近期动态

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

点“阅读原文”转论文链接

内容中包含的图片若涉及版权问题，请及时与我们联系删除

TheWebConf 2025 Oral｜凸成本函数和异质性博弈主体下的网络公共品博弈

评论