Approximation Techniques for Utilitarian Mechanism Design
Authors:
- Patrick BriestPBPatrick Briest
- Piotr KrystaPKPiotr Krysta
- Berthold VöckingBVBerthold Vöcking
- 1 January 2011
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 40 (6) , 1587-1622
Abstract
This paper deals with the design of efficiently computable incentive-compatible mechanisms for combinatorial optimization problems with single-minded agents each possibly having multiple private parameters. We focus on approximation algorithms for NP-hard mechanism design problems. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques do not fulfill these properties, we study alternative techniques. Our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone fully polynomial time approximation scheme (FPTAS). This can be applied to various problems like, e.g., knapsack, constrained shortest path, or job scheduling with deadlines. For example, the monotone FPTAS for the knapsack problem gives a very efficient, truthful mechanism for single-minded multiunit auctions. The best previous result for such auctions was a 2-appro-xi-ma-tion. In addition, we present a monotone PTAS for the generalized assignment problem with any constant number of private parameters per agent. The most efficient way to solve packing integer programs (PIPs) is linear programming–based randomized rounding, which also is in general not monotone. We show that primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. The advantage is that these algorithms are inherently monotone. This way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions (CAs), unsplittable flow routing, and multicast routing. Our primal-dual approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle.Keywords
This publication has 36 references indexed in Scilit:
- A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due dateTheoretical Computer Science, 2006
- Approximation algorithms for minimizing the total weighted tardiness on a single machineTheoretical Computer Science, 2006
- A Polynomial Time Approximation Scheme for the Multiple Knapsack ProblemSIAM Journal on Computing, 2005
- Truth revelation in approximately efficient combinatorial auctionsJournal of the ACM, 2002
- Bicriteria Network Design ProblemsJournal of Algorithms, 1998
- Approximation Schemes for the Restricted Shortest Path ProblemMathematics of Operations Research, 1992
- Probabilistic construction of deterministic algorithms: Approximating packing integer programsJournal of Computer and System Sciences, 1988
- Randomized rounding: A technique for provably good algorithms and algorithmic proofsCombinatorica, 1987
- Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-case and probabilistic analysesEuropean Journal of Operational Research, 1984
- Algorithms for Scheduling Independent TasksJournal of the ACM, 1976