基于VGC机制的最小支撑树问题研究

Research on Minimum Spanning Tree Solved by VGC Mechanism

讨论了网络上的计算机不执行给定的算法,而是执行最利于其主人工作的这种情况。作为这样的参与者即操纵算法的代理,算法设计者应事先确保代理的利益通过真实报告是最大的。文中引用了机制设计的概念,提出了研究这样算法的框架。在这个模型中,算法解与参与者的支付有关。支付应选择那些激励所有参与者真实报告的支付。文中将机制设计的标准工具VGC机制应用到解决最小支撑树问题。

Consider algorithmic problems in a setting where the participants cannot be assumed to follow the algorithm but rather their own self- interest. As such participants, agents are capable of manipulating the algorithm; the algorithm designer should ensure in advance that the agents＇ interests are best served by telling truthfully. Following notions from the field of mechanism design,suggest a framework for studying such algorithms. In this model the algorithmic solution is adorned with payments to the participants. The payments should be carefully chosen as to motivate all participants to act as the algorithm designer wishes. Apply the standard tools of VGC mechanism design to solve the minimum spanning tree problem.