导 读
本文是计算经济学领域顶级会议 ACM EC 2022入选论文 Tight Incentive Analysis on Sybil Attacks to Market Equilibrium of Resource Exchange over General Networks 的解读。该论文为北京大学前沿计算研究中心邓小铁教授和苏州科技大学程郁琨教授、北京大学毕业生李毓浩和上海交通大学毕业生阎翔共同合作完成。
文章分析和证明了一类资源共享机制在面对女巫攻击时激励比的紧质界
。论文链接：
https://dl.acm.org/doi/10.1145/3490486.3538378
01
研究背景
资源共享在过去的十多年中借助互联网技术的蓬勃发展，其中的用户同时拥有“资源提供者”和“资源需求者”的双重身份；他们将各自闲置资源贡献给他人，并从他人贡献出的资源中获得收益，创造更多社会价值，实现基于互联网的共享经济模式。目前，资源共享在现实中已得到广泛应用，并获得巨大商业价值。众多应用软件、在线平台在此背景下应运而生，涉及住宿、交通、教育及生活服务等领域。资源共享的理念已经深入人心，共享经济的模式也已成为人们新的生活和工作方式，影响着我们的观念与生活。如何使资源在网络上得到高效、公平分配，参与其中“人”的因素起到重要作用。本文在此背景下，同时受到 BitTorrent 分配机制的启发，运用算法博弈论框架下最新成果，结合计算经济学理论，以互联网市场中资源共享博弈问题为研究对象，开展资源分配的激励分析与研究。更数学化地，网络上资源共享问题可以被模型化为一个赋权无向图，其中每个节点代表一个参与者，每条无向边代表和两个参与者之间的链接，可以进行资源交换，每个点的权重 代表该参与者拥有的资源量。我们用 代表整个网络的资源分配方案。2007年，Wu 和 Zhang [1] 证明了在上述的资源共享模型中，“比例反应动态”（Proportional Response Dynamics）可以收敛至市场均衡（Market Equilibrium），证明了此类“成比例公平”（Proportional Fairness）的资源分配方法是有效的（efficient）。图1. 比例反应动态所收敛的市场均衡分配此后，一系列工作以“比例反应动态”最终收敛的市场均衡作为资源分配机制，基于经济学中的“理性人”假设，从机制设计的角度出发，研究这一公平、高效分配机制的鲁棒性（Robustness）。更具体的，[2] 和 [3] 分别证明了，某一个策略玩家（strategic agent）通过切断与邻点的链接（edge deleting）或者谎报自己拥有的资源量（resource misreporting）两种策略行为，是无法使其获得更高收益，从而证明了市场均衡机制在面对这两类策略的激励相容性（incentive compatibility）。02
女巫攻击
本文聚焦于网络中一类更强的攻击行为——女巫攻击的激励分析
。其中女巫攻击是指，一个策略玩家可以伪造多个虚拟节点（没有数量限制），策略玩家可以控制这些虚拟节点，与原有邻点建立链接，参与网络上的资源交换，通过虚拟节点获得收益。可以想象，在女巫攻击后，整个网络结构发生了变化，因此资源分配也发生了改变，策略玩家的收益，即所有虚拟节点收益之和，也有相应的变化。经过分析可以发现，在大部分情况下，策略玩家确实可以通过女巫攻击获得更高收益，如下图所示，策略玩家在原图中的收益为1；当 发动女巫攻击，伪造虚拟节点 和 ，两个虚拟节点分别与的邻点关联，在市场均衡机制的运作下，获得收益 ，收益增加。图2. 女巫攻击行为03
主要贡献
由上述介绍，可知市场均衡机制关于“女巫攻击”行为不具备激励相容性。为此，我们进一步借助激励比（incentive ratio）[4] 的解概念来刻画一个策略玩家可以通过策略行为（strategic behavior）获得最大可能的效益增加。激励比的数学定义为，策略玩家使用策略所能获得的最大收益除以其诚实行为时获得的收益。我们的结果证明，在一般网络中，任意一位策略玩家单独进行女巫攻击，只能获得相比于诚实行为时两倍的收益，即，激励比的上界为2；同时，我们也给出例子（见图2）说明激励比的下界为2。由此可以推断，激励比的上界和下界一致，严格等于2，完全解决了市场均衡机制关于“女巫攻击”的激励分析研究。04
未来工作展望
我们将继续聚焦于不同场景下参与者的策略分析，并将其对应的均衡问题作为未来工作最重要的目标。策略分析在近年来已经成为算法博弈论领域的蓬勃发展的方向。在绝大多数场景下，机制面对复杂的攻击时很难是激励相容的。所以理性人们有动机采取策略行为。而在所有参与者都有可能采取策略行为时，整个系统将到达何种均衡可能会是这个方向最重要的问题。参考文献
[1] Fang Wu and Li Zhang. 2007. Proportional response dynamics leads to market equilibrium. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. ACM, 354-363.
[2] Yukun Cheng, Xiaotie Deng, Yifan Pi, and Xiang Yan. 2015. Can Bandwidth Sharing Be Truthful . In International Symposium on Algorithmic Game Theory. Springer, 190-202.
[3] Yukun Cheng, Xiaotie Deng, Qi Qi, and Xiang Yan. 2016. Truthfulness of a Proportional Sharing Mechanism in Resource Exchange. In IJCAI. 187-193.
[4] Ning Chen, Xiaotie Deng, and Jie Zhang. 2011. How profitable are strategic behaviors in a market . In European Symposium on Algorithms. Springer, 106-118.图文 | PKU daGAME Lab
