IPDPS 2020 | 缩紧圈上资源共享的激励率
关键词：资源共享 激励率
导读
第34届并行分布式处理国际研讨会（IEEE International and Distributed Processing Symposium, IPDPS 2020）将于2020年5月18-22日在美国新奥尔良召开，中心邓小铁课题组共有2篇论文被接收。本文为其中一篇《缩紧环上资源共享的激励率（Tightening Up the Incentive Ratio for Resource Sharing Over the Rings）》的解读。
背景介绍
随着互联网和移动网络上共享经济的发展，大规模网络资源共享问题越来越受到研究界的关注。P2P 网络中的共享带宽模型是一个很成功的案例，并且它经过了 BitTorrent 商业化后得到了广泛的应用。要设计这样成功的 P2P 网络，激励（incentives）被认为是最重要的因素之一。我们应该向用户提供一个公平的资源交换规则，来促进用户参与到网络中互相合作，达到充分利用社会资源的目的。大约10年前 STOC 的一篇论文中提出了一个公平的资源交换规则，它是一个成比例交换协议（proportional response protocol）。简单解释为，如果你给我的资源量占我所收到所有资源量的 t%，则我会把我手中 t% 的资源量送给你。
这样的一个协议做到了“成比例公平”（proportional fairness），是一个很成功的协议，但对于它鲁棒性的研究进展却十分缓慢。大约10年后第一篇关于这个协议鲁棒性的研究问世，随后出现了很多相关的研究[1][2]。
我们要设计成功的 P2P 网络协议，要使得这个协议在保持公平性的前提下，同时保持一定的健壮性。经济学假设人是理性并且策略性的，人们有动机采取一些策略（利用规则的漏洞）来获得更多的本不属于他的利益，并且这样的行为多数情况下会损害到他人的利益。我们应当研究设计的协议可以抵抗什么样的策略，如果不能抵抗，这样的策略会对协议造成多大的破坏。由此引出博弈论中一个非常重要的概念，Truthful。一个人诚实地参与系统合作会得到 w 的收益，如果他不能通过某一类策略来获得多于 w 的收益，我们就称这个机制对于这个策略是 Truthful 的。也就是告诉大家，不要费脑筋想策略了，诚实地参与合作获得的收益就是最多的。如果机制是 Truthful 的，那么大家都应该诚实的参与到合作当中，会使得整个系统处于稳定的合作状态，不会被策略攻击所破坏，并且参与者在参与合作的时候也很省心（不必浪费没有必要的资源来尝试获得更多的收益）。
过去的研究证明了这个协议：
对于谎报自己拥有的资源量是 Truthful 的，即没必要故意藏着自己的资源不给别人；
对于和邻居的连通性是 Truthful的，即没必要故意不和自己的邻居交换资源。
这两个 Truthful 说明了这个协议的鲁棒性，第一条保证了系统拥有的资源不会被浪费，第二条保证了大家会更积极的参与合作。
本文关注并解决的问题
可惜的是，对于分布式系统有一个非常强力的攻击叫做 Sybil attack，即一个人伪造多个身份加入系统，最终的获利是每个身份获利的总和。很多工作都说明了这个协议在 Sybil attack 这样强力的攻击下不是 Truthful 的，但这时候会出现相对于 Truthful 的一个概念，incentive ratio，即一个人通过策略最多获得相较于诚实时几倍的收益。我们猜测在这个问题中 incentive ratio≤2，即最多获得两倍的收益。对于这个问题的研究持续了很长时间，对很多拥有特殊性质的图进行了详尽的分析，最新的进度是分析圈上的 incentive ratio。
过去的论文首先证明了环上 2≤incentive ratio≤4，随后被改进到 2≤incentive ratio≤3，如何缩紧环上的 incentive ratio 列在了这两篇论文中作为 open problem，而证明环上 incentive ratio≤2 是证明一般图上 incentive ratio≤2 不可或缺的一步。
这篇工作彻底解决了这个 open problem，即证明了环上 incentive ratio≤2。技术上主要的贡献是：
对于这个问题中最关键的瓶颈分解（bottleneck decomposition）如何变化做了更清晰的描述。
提出了一个新的技术 Adjusting technique，这是一个至关重要的技术，它不仅可以应用与环上情况的分析，同样适用于一般图，而这个技术也使我们可以从市场的角度重新理解这个问题，从而发现许多纯数学角度无法发现的性质。
最后一步分析时用了很强的数学技巧，最终把 3 这个宽松的界缩紧为 2 这个紧的界。
结论
这篇论文的主要工作即证明环上 incentive ratio≤2 这个紧的界，做出了一些新的技术贡献，这些技术为我们彻底完成一般图 incentive ratio≤2 这个最终问题提供了一条更有可行性的道路。
Reference
[1] Cheng, Y., Deng, X., Pi, Y., and Yan, X. (2015). Can bandwidth sharing be truthful? SAGT, pages 190-202.
[2] Cheng, Y., Deng, X., Qi, Q., and Yan, X. (2016). Truth- fulness of a proportional sharing mechanism in resource exchange. IJCAI, pages 187-193.
IPDPS
并行分布式处理国际研讨会（IEEE International and Distributed Processing Symposium, IPDPS）是并行与分布式计算领域的著名会议。该会议是一个面向世界各地工程师和科学家的国际论坛，旨在展示他们在并行计算各个方面的最新研究成果。IPDPS 2020 将于2020年5月18-22日在美国新奥尔良召开。
李毓浩
EconCS@PKU
近 期 科 研 进 展
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。