本文是 AAMAS 2023入选论文 Sybil-Proof Diffusion Auction in Social Networks 的解读。该工作由北京大学前沿计算研究中心邓小铁课题组和上海科技大学赵登吉课题组共同完成。文章聚焦于扩散拍卖中的女巫攻击行为，给出了两个抗女巫攻击的扩散拍卖机制并进行性能分析。

　　论文链接：https://arxiv.org/abs/2211.01984

01 引 言

　　在传统拍卖中，卖家只考虑将物品贩卖给一个确定的买家群体；当拍卖发生在社交网络上时，这个买家群体就是卖家在社交网络上的邻居集。为了提高拍卖的卖家收益和社会福利，扩散拍卖（diffusion auction）允许买家邀请邻居进入拍卖。通过赋予中间买家一定的邀请报酬，一些扩散拍卖机制（如，Information Diffusion Mechanism [1]）保证了诚实报价并邀请其所有邻居是所有买家的最优策略。然而，这种奖励买家邀请邻居的设计让攻击者可以通过社交网络上低成本的女巫攻击获取不正当收益——即攻击者可以通过创造并邀请若干个虚假身份骗取邀请报酬。现有的所有非平凡的扩散拍卖机制均无法解决这一问题。

　　本文对有向社交网络中无共谋的女巫攻击行为进行建模，并提出两个抗女巫攻击的扩散拍卖机制：STM（Sybil Tax Mechanis）和 SCM（Sybil Cluster Mechanism）。进一步地，本文比较了两个提出的机制与经典扩散拍卖机制、传统拍卖机制的性能，发现 STM 和 SCM 在防止女巫攻击的同时保持了较高的社会福利和卖家收益；此外，我们还分析了抗女巫攻击的扩散拍卖机制的效率比，发现所有抗女巫攻击的扩散拍卖机制在最坏情况下都有非常低的社会福利和卖家收益。

02 女巫攻击建模

　　在有向社交网络中，点 x 有邻居 y（点 x 有指向点 y 的有向边）表示 x 知道 y 的存在。扩散拍卖机制要求买家汇报它的报价（如图 (a) 中 x 报价8）和他的邻居集（图 (a) 中 x 的邻居集为 {y, z, w} ），买家不必要诚实汇报他对物品的私人价格，也可以选择瞒报他的邻居。在女巫攻击的情况下，一个买家 x 可以创造任意多个假身份 x_{1}, x_{2},... 。一个假身份 x_{i} 的邻居集可以包含 x 的邻居，x 本身以及 x 的其他假身份；在无共谋的情况下，x_{i} 不可以在除 x 和 x 的假身份外其他人的邻居集中。模型允许社交网络中的任何买家发起女巫攻击。

　　因为假身份只被他的创造者和这一创造者的其他假身份知道，所有从卖家出发的沿买家汇报的社交网络单向边的经过该假身份的路径都会经过该假身份的创造者。基于以上性质，扩散拍卖机制可以根据买家汇报的邻居关系从图论角度找出部分“一定不是假身份”的买家，文中称为图论非女巫节点（Graphical non-Sybil agents）。一个自然的想法是在由图论非女巫节点构成的社交网络中实行已有的扩散拍卖机制，但这个想法是不可行的：通过瞒报邻居集，买家可以改变图论非女巫节点的构成，诱导对自己更有利的社交网络结构（如下图，通过瞒报邻居 c，买家 a 可以将 c 排除在图论非女巫节点的社交网络结构之外，从而降低自己买入物品的费用）。

03 主要贡献1 抗女巫攻击机制

　　上一节说明简单使用图论方法来抵抗女巫攻击是不可行的。本节介绍本文的主要贡献：两个抗女巫攻击机制 STM 和 SCM。机制设计上借鉴了经典的扩散拍卖机制 IDM，综合利用图论信息和买家报价来排除恶意竞价的假身份。

　　类似 IDM，STM 首先找到汇报社交网络中报价最高的买家 x^{*}，再确认卖家到 x^{*} 扩散拍卖的必经节点；必经节点中任意一个瞒报邻居都可以导致 x^{*}改变，因此称这些必经节点构成的路径为“支配路径”。STM 可以看成一个多次转卖过程：物品将在支配路径上传递，直到下传物品不能给买家带来更高收益。支配路径上的买家收到物品时需要支付买入价格，这一价格由所有不被它支配的节点报价共同决定。下传物品时，买家会收入卖出价格，这一价格由买入价格和由它引入的“图论非女巫节点”及后继共同决定。这一过程中，上家的卖出价可能小于下家的买入价，差价可以看作转卖的税收成为卖家收入的一部分。（机制的严格定义请参考原文）

　　文章证明了 STM 满足独立理性（IR）、卖家收益非负（non-deficit）以及抗女巫攻击（Sybil-proof）。在没有其他“non-Sybil agents”确认途径的情况下，STM 的中间买家收益都是 0；虽然攻击行为不能为中间买家带来收益，但 STM 中的买家也没有足够的激励汇报自己的邻居。

　　为了进一步驱动买家诚实汇报邻居集，文章节提出了第二个抗女巫攻击的机制 ACM；SCM 通过随机删边将图论非女巫节点的出现归功于部分幸运的中间买家，从而提高买家诚实汇报邻居集的意愿（机制的具体描述请参考原文）。SCM 也满足独立理性、卖家收益非负以及抗女巫攻击，同时，它给中间买家更强激励来邀请邻居。

04 主要贡献2 性能分析

　　在提出两个抗女巫攻击的扩散拍卖机制后，文章讨论了以下三个问题：

　　（1）只在卖家邻居集中进行的传统拍卖机制天然是抗女巫攻击的，相比于传统拍卖机制，STM 和 SCM 在卖家收益和社会福利上是否有更好表现？

　　（2）在所有抗女巫攻击的扩散拍卖机制中，STM 或 SCM 是否能达到最优的社会福利或卖家收益？

　　（3）相比于已有的扩散拍卖机制，STM 和 SCM 为了达到抗女巫攻击，在社会福利和卖家收益上有多大牺牲？

　　针对问题（1）和问题（3），文章理论分析了 STM、SCM 和传统二价拍卖机制 NSP，和经典扩散拍卖机制 IDM、VCG 在社会福利与卖家收益方面的表现（详见原文 Theorem 6.1，6.2，6.3）同时采用模拟实验定量比较平均情况下，在不同密度的社交网络中，以上五个机制在社会福利和卖家收益上的表现。

　　针对问题（2），文章给出了负面结论：在最坏的情况下，任何保证卖家收益非负、抗女巫攻击、满足独立理性的扩散拍卖机制的社会福利相比于最优社会福利都无限趋近于零。在卖家收益上有类似结论。

参考文献

[1] Bin Li, Dong Hao, Dengji Zhao, and Tao Zhou. 2017. Mechanism Design in Social Networks. Proceedings of the AAAI Conference on Artificial Intelligence 31, 1 (Feb.
2017). https://ojs.aaai.org/index.php/AAAI/article/vie