{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T00:03:02Z","timestamp":1787443382061,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>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\u2013based 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.<\/jats:p>","DOI":"10.1137\/090772988","type":"journal-article","created":{"date-parts":[[2011,12,13]],"date-time":"2011-12-13T18:27:16Z","timestamp":1323800836000},"page":"1587-1622","source":"Crossref","is-referenced-by-count":41,"title":["Approximation Techniques for Utilitarian Mechanism Design"],"prefix":"10.1137","volume":"40","author":[{"given":"Patrick","family":"Briest","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Krysta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,12,13]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Andelman, Y. Azar, and M. Sorani,\n                      Truthful approximation mechanisms for scheduling selfish related machines\n                      , in Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), 2005, pp. 69\u201382.","DOI":"10.1007\/978-3-540-31856-9_6"},{"key":"R2","unstructured":"A. Archer, C. Papadimitriou, K. Talwar, and \u00c9. Tardos,\n                      An approximate truthful mechanism for combinatorial auctions with single parameter agents\n                      , in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 205\u2013214."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"A. Archer and E. Tardos,\n                      Truthful mechanisms for one-parameter agents\n                      , in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2001, p. 482.","DOI":"10.1109\/SFCS.2001.959924"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, and A. Meyerson,\n                      Reducing truth-telling online mechanisms to online optimization\n                      , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), 2003, pp. 503\u2013510.","DOI":"10.1145\/780542.780616"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, and S. Plotkin,\n                      Throughput-competitive online routing\n                      , in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1993, pp. 32\u201340.","DOI":"10.1109\/SFCS.1993.366884"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Y. Azar, I. Gamzu, and S. Gutner,\n                      Truthful unsplittable flow for large capacity networks\n                      , in Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2007, pp. 320\u2013329.","DOI":"10.1145\/1248377.1248432"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Y. Azar and O. Regev,\n                      Strongly polynomial algorithms for the unsplittable flow problem\n                      , in Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2001, pp. 15\u201329.","DOI":"10.1007\/3-540-45535-3_2"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Y. Bartal, R. Gonen, and N. Nisan,\n                      Incentive compatible multi-unit combinatorial auctions\n                      , in Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 2003, pp. 72\u201387.","DOI":"10.1145\/846241.846250"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"P. Briest, P. Krysta, and B. V\u00f6cking,\n                      Approximation techniques for utilitarian mechanism design\n                      , in Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), 2005, pp. 39\u201348.","DOI":"10.1145\/1060590.1060597"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"D. Buchfuhrer, S. Dughmi, H. Fu, R. Kleinberg, E. Mossel, C. Papadimitriou, M. Schapira, Y. Singer, and C. Umans,\n                      Inapproximability for VCG-based combinatorial auctions\n                      , in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010, pp. 518\u2013536.","DOI":"10.1137\/1.9781611973075.45"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. Chakrabarti, C. Chekuri, A. Kumar, and A. Gupta,\n                      Approximation algorithms for the unsplittable flow problem\n                      , in Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002), 2002, pp. 51\u201366.","DOI":"10.1007\/3-540-45753-4_7"},{"key":"R12","unstructured":"C. Chekuri and S. Khanna,\n                      On multi-dimensional packing problems\n                      , in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999, pp. 185\u2013194."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"S. Dobzinski and S. Dughmi,\n                      On the power of randomization in algorithmic mechanism design\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2009, pp. 505\u2013514.","DOI":"10.1109\/FOCS.2009.42"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"S. Dobzinski and N. Nisan,\n                      Mechanisms for multi-unit auctions\n                      , in Proceedings of the 8th ACM Conference on Electronic Commerce (EC'07), 2007, pp. 346\u2013351.","DOI":"10.1145\/1250910.1250960"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"S. Dobzinski, N. Nisan, and M. Schapira,\n                      Truthful randomized mechanisms for combinatorial auctions\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), 2006, pp. 644\u2013652.","DOI":"10.1145\/1132516.1132607"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90053-5"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"N. Garg and J. K\u00f6nemann,\n                      Faster and simpler algorithms for multicommodity flow and other fractional packing problems\n                      , in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1998, pp. 630\u2013652.","DOI":"10.1137\/S0097539704446232"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"F. Grandoni, P. Krysta, S. Leonardi, and C. Ventre,\n                      Utilitarian mechanism design for multi-objective optimization\n                      , in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010, pp. 573\u2013584.","DOI":"10.1137\/1.9781611973075.48"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"M. Halld\u00f3rsson,\n                      A survey on independent set approximations\n                      , in Proceedings of the 1st International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 1998), 1998, pp. 1\u201314.","DOI":"10.1007\/BFb0053959"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1287\/moor.17.1.36"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"K. Jain and V. Vazirani,\n                      Applications of approximation algorithms to cooperative games\n                      , in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), 2001, pp. 364\u2013372.","DOI":"10.1145\/380752.380825"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"K. Jain and V. Vazirani,\n                      Equitable cost allocation via primal-dual-type algorithms\n                      , in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 313\u2013321.","DOI":"10.1145\/509907.509956"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.08.030"},{"key":"R25","unstructured":"J. Kleinberg,\n                      Approximation Algorithms for Disjoint Paths Problems\n                      , Ph.D. thesis, MIT, Cambridge, MA, 1996."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"S. Kolliopoulos and C. Stein,\n                      Approximating disjoint-path problems using greedy algorithms and packing integer programs\n                      , in Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization (IPCO), 1998, pp. 153\u2013168.","DOI":"10.1007\/3-540-69346-7_12"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.039"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"A. Kothari, D. Parkes, and S. Suri,\n                      Approximately-strategyproof and tractable multi-unit auctions\n                      , in Proceedings of the 4th ACM Conference on Electronic Commerce (EC'03), 2003, pp. 166\u2013175.","DOI":"10.1145\/779928.779948"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"R. Lavi, A. Mu'alem, and N. Nisan,\n                      Towards a characterization of truthful combinatorial auctions\n                      , in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2003, p. 574.","DOI":"10.1109\/SFCS.2003.1238230"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"R. Lavi and C. Swamy,\n                      Truthful and near-optimal mechanism design via linear programming\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2005, pp. 595\u2013604.","DOI":"10.1109\/SFCS.2005.76"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585266"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0930"},{"key":"R33","unstructured":"A. Mu'alem and N. Nisan,\n                      Truthful approximation mechanisms for restricted combinatorial auctions\n                      , in Proceedings of the 18th National Conference on Artificial Intelligence (AAAI-02), 2002, pp. 379\u2013384."},{"key":"R34","doi-asserted-by":"crossref","unstructured":"N. Nisan,\n                      Bidding and allocation in combinatorial auctions\n                      , in Proceedings of the 2nd ACM Conference on Electronic Commerce (EC'00), 2000, pp. 1\u201312.","DOI":"10.1145\/352871.352872"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ronen,\n                      Algorithmic mechanism design\n                      , in Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), 1999, pp. 129\u2013140.","DOI":"10.1145\/301250.301287"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"C. A. Phillips,\n                      The network inhibition problem\n                      , in Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), 1993, pp. 776\u2013785.","DOI":"10.1145\/167088.167286"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"R39","unstructured":"G. Robins and A. Zelikovsky,\n                      Improved Steiner tree approximation in graphs\n                      , in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, pp. 770\u2013779."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321934"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796314240"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090772988","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:00Z","timestamp":1787337180000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090772988"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/090772988"],"URL":"https:\/\/doi.org\/10.1137\/090772988","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}