Approximate composable truthful mechanism design

作者：Ye, Deshi; Zhang, Guochuan^*

来源：Theoretical Computer Science, 2016, 654: 188-198.

DOI：10.1016/j.tcs.2016.02.025

• Mechanism design
• Knapsack auction
• Approximation algorithms

This paper aims to study techniques for designing truthful mechanisms for a combinatorial optimization problem that might require composition algorithms. We show that the composition algorithm A o B is monotone if the algorithm A and the algorithm B are both monotone. We apply this technique to the two-dimensional orthogonal knapsack problem with provable constant approximation bounds, improving the previous non constant results in [5]. Moreover, we show that the technique can also be applied to the heterogeneous multiple clusters scheduling problem, and, a truthful mechanism with provable approximation bounds was presented.

• 出版日期2016-11-22
• 单位浙江大学