如何理解分布式系统中的机制与策略

Question

如题所述

Answer 1

近年来由于计算机网络的快速成长,策略性分布式系统变得越来越重要。在传统基于分布式系统研究中,代理都被假设为服从性的。这种假设忽略了不同代理之间的利益关系,也即当从属于不同组织的代理的行为遵循个体利益最大化的策略而非全局算法时,系统的动因(Incentive)就成为了一个急待解决的重要问题。机制设计(Mechanism Design)从经济学和博弈论中得到的概念能够描述策略性的代理,提供代理的动因,能解决这样的问题,从而达到个体自私的代理的利润最大化的同时,全局系统的最优化。 然而,在传统的机制设计问题定义中,人们考虑的通常只有用户愿意支付的价格或者服务商的成本,而不同用户,不同服务商之间的差异性被忽视了。在实际情况中,不同用户视同一服务商,基于不同用户考量的标准和参数不同,对该服务的估值是不一样的。相应的,不同服务商根据具体的情况,服务同一用户的服务成本很有可能也是不同的。在这样的前提下,基于传统的VCG的机制将不能保证strategyproof的特性,我们将提出Value-based解决方案来替代。 同时,在理性前提假设下,不同场景中的机制是不一样的。在本文中,我们讲分别讨论相应场景下的strategyproof机制。我们还将结合实际的分布式策略系统的说明机制的适用性,其中包括了从最早web cache,分布式存储,计算,到p2p文件共享,adhoc网络以及最近很热门的认知无线电网络,证明了我们的机制可以很好的解决系统中存在的动因问题,让博弈方说出真实的类型值,做出理性的判断。 另外,我们也将引入双向拍卖的概念来讨论最复杂的多服务对多用户的场景。我们从双向拍卖的背景开始,逐一介绍双向拍卖的运行环境和相应的买家卖家报价策略,并在McAfee的机制基础上提出我们的双向VCG机制,并证明了在一定条件下的strategyproof特性。最后,我们也以实际的外汇交易系统中的定价策略为例,讨论了双向拍卖中第三方撮合交易的方法以及原理。