| |
| Algorithmic mechanism design, as an important research area in the theoretical computer science in recent years, is not only to give an efficient algorithm for the given problem, but also to prevent the rational agents from manipulating the input date for the
problem. For many NP-hard problems, there have been a lot of good approximation algorithms. So, it’s a new task for us to design truthful mechanisms with the same
approximation ratios for these NP-hard problems. This paper focuses on a large family of approximation algorithms based on the technique of randomized rounding which combines the techniques of randomized algorithms and linear/semi-definite programming. By giving an exact characterization of the randomized truthful mechanisms, the paper presents a general
framework to efficiently transfer the family of approximation algorithms to the truthful
mechanisms without a loss of approximation ratio. |
|
| Keywords:Mechanism design, approximation algorithms, randomized rounding, linear programming, semi-definite programming |
|
