背景介绍
     随着互联网和移动网络上共享经济的发展，大规模网络资源共享问题越来越受到研究界的关注。P2P 网络中的共享带宽模型是一个很成功的案例，并且它经过了 BitTorrent 商业化后得到了广泛的应用。要设计这样成功的 P2P 网络，激励（incentives）被认为是最重要的因素之一。我们应该向用户提供一个公平的资源交换规则，来促进用户参与到网络中互相合作，达到充分利用社会资源的目的。大约10年前 STOC 的一篇论文中提出了一个公平的资源交换规则，它是一个成比例交换协议（proportional response protocol）。简单解释为，如果你给我的资源量占我所收到所有资源量的 t%，则我会把我手中 t% 的资源量送给你。

　　这样的一个协议做到了“成比例公平”（proportional fairness），是一个很成功的协议，但对于它鲁棒性的研究进展却十分缓慢。大约10年后第一篇关于这个协议鲁棒性的研究问世，随后出现了很多相关的研究[1][2]。

　　我们要设计成功的 P2P 网络协议，要使得这个协议在保持公平性的前提下，同时保持一定的健壮性。经济学假设人是理性并且策略性的，人们有动机采取一些策略（利用规则的漏洞）来获得更多的本不属于他的利益，并且这样的行为多数情况下会损害到他人的利益。我们应当研究设计的协议可以抵抗什么样的策略，如果不能抵抗，这样的策略会对协议造成多大的破坏。由此引出博弈论中一个非常重要的概念，Truthful。一个人诚实地参与系统合作会得到 w 的收益，如果他不能通过某一类策略来获得多于 w 的收益，我们就称这个机制对于这个策略是 Truthful 的。也就是告诉大家，不要费脑筋想策略了，诚实地参与合作获得的收益就是最多的。如果机制是 Truthful 的，那么大家都应该诚实的参与到合作当中，会使得整个系统处于稳定的合作状态，不会被策略攻击所破坏，并且参与者在参与合作的时候也很省心（不必浪费没有必要的资源来尝试获得更多的收益）。

　　过去的研究证明了这个协议：
      1. 对于谎报自己拥有的资源量是 Truthful 的，即没必要故意藏着自己的资源不给别人；
      2. 对于和邻居的连通性是 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。技术上主要的贡献是：
      1. 对于这个问题中最关键的瓶颈分解（bottleneck decomposition）如何变化做了更清晰的描述。
      2. 提出了一个新的技术 Adjusting technique，这是一个至关重要的技术，它不仅可以应用与环上情况的分析，同样适用于一般图，而这个技术也使我们可以从市场的角度重新理解这个问题，从而发现许多纯数学角度无法发现的性质。
      3. 最后一步分析时用了很强的数学技巧，最终把 3 这个宽松的界缩紧为 2 这个紧的界。

　　结论
      这篇论文的主要工作即证明环上 incentive ratio≤2 这个紧的界，做出了一些新的技术贡献，这些技术为我们彻底完成一般图 incentive ratio≤2 这个最终问题提供了一条更有可行性的道路。