Approximation Techniques for Utilitarian Mechanism Design

P. Briest, P. Krysta, B. Vöcking, SIAM Journal on Computing (2011) 1587–1622.

No fulltext has been uploaded.
Journal Article | Published | English
Briest, Patrick; Krysta, Piotr; Vöcking, Berthold
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.
Publishing Year
Journal Title
SIAM Journal on Computing

Cite this

Briest P, Krysta P, Vöcking B. Approximation Techniques for Utilitarian Mechanism Design. SIAM Journal on Computing. 2011:1587-1622. doi:10.1137/090772988
Briest, P., Krysta, P., & Vöcking, B. (2011). Approximation Techniques for Utilitarian Mechanism Design. SIAM Journal on Computing, 1587–1622.
@article{Briest_Krysta_Vöcking_2011, title={Approximation Techniques for Utilitarian Mechanism Design}, DOI={10.1137/090772988}, journal={SIAM Journal on Computing}, author={Briest, Patrick and Krysta, Piotr and Vöcking, Berthold}, year={2011}, pages={1587–1622} }
Briest, Patrick, Piotr Krysta, and Berthold Vöcking. “Approximation Techniques for Utilitarian Mechanism Design.” SIAM Journal on Computing, 2011, 1587–1622.
P. Briest, P. Krysta, and B. Vöcking, “Approximation Techniques for Utilitarian Mechanism Design,” SIAM Journal on Computing, pp. 1587–1622, 2011.
Briest, Patrick, et al. “Approximation Techniques for Utilitarian Mechanism Design.” SIAM Journal on Computing, 2011, pp. 1587–622, doi:10.1137/090772988.


Marked Publications

Open Data LibreCat

Search this title in

Google Scholar