基于机制诚实性的显示原理算法比较

Computational Comparison of Revelation Principle Based on Mechanism Truth

机制设计是博弈规则设计的主要的方法。即使假设在博弈中的代理都是自利的,也可以通过机制设计获得一个最佳结果。显示原理是机制设计中一个基本原理。文中论证了在对计算和通信给出一定的合理约束条件下,显示原理就可能无效。研究了最优诚实机制的情况,说明中心处理这个机制的算法是NPC的。当情况变为非诚实机制时,算法也就从中心转移到了一个代理的计算上,从而解决算法的NPC问题的困难。

Mechanism design is the art of designing the rules of the game, so that a desirable outcome is reached even though the agents in the game behave selfishly. The revelation principle is a basic tool in mechanism design. Show that reasonable constraints on computation can invalidate the revelation principle. Study settings where the optimal truthful mechaniam is NP-complete to execute for the center. In that setting show that by moving to insincere mechanisms, one can shift the burden of having to solve the NP-complete problem from the center to one of the agents.