本文是 Mathematics of Operations Research (MOR) 期刊入选论文 Truthfulness of a Network Resource-Sharing Protocol 的解读。该论文是由苏州科技大学程郁琨教授、北京大学邓小铁教授、中国人民大学祁琦教授以及华为理论计算机实验室阎翔研究员合作完成。

　　文章分析了互联网中网络数字资源共享的比例反应动态协议 Proportional Response Dynamics 的优良性质，运用本领域用户对该类资源有着相同偏好的特性，证明了在网络中的任意节点都无法通过谎报其私有信息而获取额外收益，即该协议针对网络节点的策略行为满足诚实性。在理论上为互联网资源共享系统的机制设计长处给出了一个技术证据。

01 概 述

　　用户通过点对点网络（P2P 网络）分享资源，如网络带宽、计算算力等，的思想已经成为许多商业成功案例的基石，而这些成功背后的根源在于选择恰当的资源共享协议，例如 Wu 和 Zhang[1]证明了通过采取比例反应协议（Proportional Response Dynamics），节点之间的资源分配结果将会收敛到市场均衡状态下的资源分配结果。

　　尽管在经济学研究当中，市场均衡状态是资源分配、定价等场景中最理想的状态，但从机制设计的角度，由于资源共享协议是通过分布式部署的方式指导网络中节点参与资源共享，那么能否避免网络中节点出于自私目的采取某种策略行为仍然至关重要。

　　本篇论文将参与资源共享的网络建模为一个无向图 G=(V, E; w)，其中节点 v∈V 的权重 w_{v}表示其用于与其他节点共享的资源总量。我们令 a_{vu} 表示节点 v 分配给其邻点 u 的资源量，则节点 v 的收益便定义为它自身资源与从其邻点收到资源的总和，即 U_{v}=w_{v}+\sum_{u \in \Gamma(v)} a_{u v}。该收益函数的定义表明，节点不仅可以从自身资源中获得效用，同时也可从与他人共享的资源中获得效用。在此网络中，比例反应协议要求 t 时刻节点 v 向节点 u 分配资源的比例 a_{v u}(t) 满足：a_{v u}(0)=1 / d_{v} （d_{v} 为 v 邻点的个数），并且 \forall t \geq 0，有 a_{v u}(t)=\frac{a_{u v}(t+1) w_{u}}{\sum_{k \in \Gamma(v)} a_{k v}(t) w_{k}}

　　当节点遵循此分布式机制时，分配结果不仅会收敛至市场均衡状态，同时我们也证明了该分配结果也在核（core）当中。

　　本篇论文重点关注收敛到市场均衡的资源分配机制，称为比例反应机制，分析了网络中的节点能否通过策略行为操纵该机制。具体来说，论文考虑了节点能够采用的两种谎报策略，隐瞒自己的部分资源（weight-misreporting）和屏蔽自己的部分邻点（edge-deleting），以及节点采用这两种策略的组合策略。论文证明了任何节点都无法通过采取其中任何一种策略提升其收益。

02 背景知识

　　比例反应机制下的资源分配，可以通过一项名为“瓶颈分解”的技术进行刻画。具体来说，在图 G=(V, E; w) 中，对于任何一个节点集合 S \subseteq V，定义 Γ(S) 为集合 S 的邻集；w(S) 为集合 S 的权重，即 w(S)=\sum_{v \in S} w_{v}；α(S)=\frac{w(\Gamma(S))}{w(S)}为集合 S 的 α-ratio。一个节点集合 B \subseteq V 满足当 α(B)=\min _{S \subset V} \alpha(S)，则称 B 为 G 的“瓶颈”。图 G 的“瓶颈”可能有多个，其中包含节点最多的瓶颈被称为“最大瓶颈”。可以证明，图 G 的“最大瓶颈”是唯一确定的。图 G 的“瓶颈分解”可以表示为 \mathcal{B}(G)=\left\{\left(B_{1}, C_{1}=\Gamma\left(B_{1}\right)\right), \ldots,\left(B_{k}, C_{k}\right)\right\}，其中 B_{1} 为 G 的“最大瓶颈”， B_{2} 为从 G 中删去 \left(B_{1}, \Gamma\left(B_{1}\right)\right) 后剩余子图中的 “最大瓶颈”，以此类推，可得图 G 的“瓶颈分解”。每个 \left(B_{i}, C_{i}\right) 被称为“瓶颈”时，其 α-ratio 为 \alpha_{i}=w\left(C_{i}\right) / w\left(B_{i}\right)。

　　在比例反应机制 (1) 下的资源分配中，所有的资源仅在 \left(B_{I}, C_{i}\right) 之间交换，即 B_{i} 中节点的资源分配给 C_{i} 中的节点，反之亦然。可以证明，在比例反应协议的最终收敛状态中，B_{i} 中节点 v∈B_{i} 的收益为 U_{v}=w_{v} \cdot \alpha_{i}，C_{i} 中节点 v∈C_{i} 的收益为 U_{v}=w_{v} / \alpha_{i}。

03 主要贡献1

关于隐瞒部分资源策略的诚实性

　　在讨论比例反应机制关于隐瞒部分资源策略的诚实性之前，需求强调的是，节点只能隐瞒其用于分享的资源，而无法谎报其资源量的增加。这是因为对于网络中的节点来说，它可以通过限制自身向外传输资源的规模等方式实现资源分享量的减少；但节点若要撒谎提高其资源量，则它在最终收敛分配中必须付出这一额外的资源量，这显然是无法做到的，因此我们也就不再考虑这一欺骗策略。

　　为了证明节点无法通过隐瞒部分资源来提高其收益的结论，我们将其等价于证明一个节点的收益关于它提供的资源量是单调不减的，从而可以知道节点 v 只有真实汇报其资源量才可获得最大收益。令节点 v 谎报的资源量为 x_{v}\left(\leq w_{v}\right)，则图 G 的瓶颈分解依赖于 x_{v}，我们记为 \mathcal{B}\left(x_{v}\right)=\left\{\left(B_{1}\left(x_{v}\right), C_{1}\left(x_{v}\right)\right), \cdots,\left(B_{k\left(x_{v}\right)}\left(x_{v}\right), C_{k\left(x_{v}\right)}\left(x_{v}\right)\right)\right\}。借助“瓶颈分解”技术，节点 v 的在提供资源量为 x_{v} 时的收益为 x_{v} \alpha_{i}\left(x_{v}\right) （若 v \in B_{i}\left(x_{v}\right)）或 x_{v} / \alpha_{i}\left(x_{v}\right)（若 x \in C_{i}\left(x_{v}\right)）。我们通过分析图的“瓶颈分解”，不难发现，节点 v 的权重 x_{v} 从0增加至 w_{v} 的过程，可以被分为若干阶段，即 [0, w_{v}]可被分为若干不相交的区间，使得当权重 x_{v} 在一个区间内变化时，图 G 的“瓶颈分解”保持不变。因此，我们通过证明收益函数在每个区间内单调不降，并在相邻两个区间的间断点处保持连续，得出节点收益函数的单调性。

04 主要贡献2

关于屏蔽部分邻点策略的诚实性

　　直观上，参与资源共享的节点，可能有意屏蔽那些提供资源较少的邻点，即所谓的“穷邻居”，从而将自己的资源更多地分享给所谓的“富邻居”，用来从“富邻居”那换取更多资源。这一策略行为可以通过节点在图中删去若干邻边实现。

　　关于此种策略诚实性的证明较为复杂，我们这里不再详述相应的证明过程，仅介绍其中两个较为重要的中间结果。一是，当一个节点屏蔽某个在均衡状态下互不交换资源的邻点时，整个图的“瓶颈分解”保持不变，因此相应的分配结果也保持不变；二是，对于原图中的“B 类点”来说，屏蔽其邻点中的“C 类点”，并不会使得其变为“C 类点”；类似地，对于原图中的“C 类点”来说，屏蔽其邻点中的“B 类点”，也不会使得其变为“B 类点”。基于上述结果以及关于相应情况下 α-ratio 函数值的变化分析，即可完成诚实性的证明。

　　特别地，隐瞒部分资源策略和屏蔽部分邻点策略是两种无法互相替代的策略，这一结论可以通过下图中的例子看出。节点 v_{1} 屏蔽邻边 (v_{1}, v_{2}) 后，v_{1} 不再与 v_{2} 进行资源交换，收益为 U_{v_{1}}=5/2；而当 v_{1} 谎报其资源量，v_{1} 与 v_{2} 之间始终有资源交换，并且当权重从5降低至2时，v_{1} 的收益为 U_{v_{1}}=2。

　　而当节点采用两种策略的组合策略时，如下图所示，可以被视为节点先采用一种策略，再采用另一种策略。根据已得的关于两种策略行为的诚实性结论，可以知道当节点采取两阶段策略行为过程中，节点的收益始终无法得到提升，从而说明只有诚实行为，才能获得最高收益。

05 结 论

　　尽管共享经济取得了巨大的成功，但其面临的一个主要挑战就是能否防止参与者偏离预期设计的规则。本篇论文表明，市场均衡机制作为资源共享网络中比例反应协议的极限，对于任何个体参与者的欺骗行为都是鲁棒的。比例反应协议源于提供 P2P 文件共享的 BT 协议，可以说是互联网上第一个实际成功的网络资源共享协议。本文关于市场均衡机制诚实性的研究得益于各类经济学概念，论文的研究结果“市场均衡机制具有诚实性”不仅具有非常重要的理论意义，而对于算法机制的实际运用以及其优越性的体现有积极的现实意义。未来研究它与其他由独立的理性个体组成的网路系统相关的问题将是特别有趣的。

参考文献

[1] Wu F, Zhang L (2007) Proportional response dynamics leads to market equilibrium. Johnson DS, Feige U, eds. Proc. 39th Annual ACM Sympos. Theoretical Comput. (ACM), 354–363.