基于加权VGC机制的最小连接问题研究

Study of minimum connection based on the weighted VGC mechanism

文章讨论了网络上的计算机不执行给定的算法,而是执行最利于其主人工作的这种情况。作为这样的参与者即操纵算法的代理,算法设计者应事先确保代理的利益通过真实报告是最大的。文章引用了机制设计的概念,提出了研究该算法的框架,并将机制设计的标准工具VGC机制应用于解决最小连接问题。

This paper deals with algorithmic problems in a setting where the participants are assumed to follow their own self-interest rather than the algorithm. 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. By following the notions from the field of mechanism design, a framework for studying such algorithms is suggested. The standard tools of mechanism design is applied to the minimum connection problem.