基于机制设计理论的一些最优化问题的研究

摘要

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

目录

文摘

英文文摘

论文说明：符号约定

独创性声明和学位论文版权使用授权书

第一章绪论

1.1引言

1.2机制设计理论简介

1.3机制设计理论的发展

1.4机制设计的研究现状

1.5机制设计的一些应用

1.6选题背景

1.7论文的研究内容及安排

第二章机制设计理论

2.1社会选择函数的性质

2.2机制的性质

2.3显示原理，激励相容和直接揭示

2.3.1激励相容和防策略操纵

2.3.2显示原理

2.4 Vickrey-Clarke-Groves机制

2.4.1功利主义函数

2.4.2 VGC机制

2.4.3分析

第三章VGC机制研究两个基本最优化问题

3.1最短路问题

3.1.1简介

3.1.2定义和名词解释

3.1.3传统算法

3.1.4基于VGC机制的算法

3.2最小支撑树问题

3.2.1简介

3.2.2定义和名词解释

3.2.3传统算法

3.2.4基于加权VGC机制的算法

第四章机制设计任务分配问题

4.1问题

4.2上界

4.3下界

4.3.1真实执行的基本性质

4.3.2基本下界

4.3.3特殊情况的紧界

4.4随机机制

第五章结论和展望

参考文献

攻读学位期间发表的学术论文目录

致谢