论文部分内容阅读
本文引用了机制设计的概念，提出了研究这样算法的框架。在这个模型中，算法解与参与者的支付有关。支付应选择那些激励所有参与者真实报告的支付。首先，本文介绍了机制设计基本的概念和基本性质；然后，本文又将机制设计的标准工具VGC机制应用到解决最短路问题和最小支撑树问题。最后，本文讨论了任务分配问题。我们提出几个定理，包括近似机制，下界和随机机制。