Approximation techniques for utilitarian mechanism design

ABSTRACT

This paper deals with the design of efficiently computable incentive compatible, or truthful, mechanisms for combinatorial optimization problems with multi-parameter agents. 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 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 multi-unit auctions. The best previous result for such auctions was a 2-approximation. In addition, we present a monotone PTAS for the generalized assignment problem with any bounded number of parameters per agent.The most efficient way to solve packing integer programs (PIPs) is LP-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 approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle.

REFERENCES

• 1: Aaron Archer , Christos Papadimitriou , Kunal Talwar , Éva Tardos, An approximate truthful mechanism for combinatorial auctions with single parameter agents, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 2: A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
• 3: Baruch Awerbuch , Yossi Azar , Adam Meyerson, Reducing truth-telling online mechanisms to online optimization, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780616]
• 4: B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive online routing. In Proc. 34th IEEE FOCS, pages 32--40, 1993.
• 5: Yossi Azar , Oded Regev, Strongly Polynomial Algorithms for the Unsplittable Flow Problem, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.15-29, June 13-15, 2001
• 6: Yair Bartal , Rica Gonen , Noam Nisan, Incentive compatible multi unit combinatorial auctions, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846250]
• 7: G. Calinescu. Bounding the payment of approximate truthful mechanisms. In ISAAC, 2004.
• 8: Amit Chakrabarti , Chandra Chekuri , Anuptam Gupta , Amit Kumar, Approximation Algorithms for the Unsplittable Flow Problem, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.51-66, September 17-21, 2002
• 9: Chandra Chekuri , Sanjeev Khanna, A PTAS for the multiple knapsack problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 09-11, 2000, San Francisco, California, United States
• 10: Chandra Chekuri , Sanjeev Khanna, On multi-dimensional packing problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.185-194, January 17-19, 1999, Baltimore, Maryland, United States
• 11: E. Clarke. Multipart pricing of public goods. Public Choice, 8, pp. 17--33, 1971.
• 12: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 13: T. Groves. Incentives in teams. Econometrica, 41(4), 617--631, 1973.
• 14: M.M. Halldórsson. A survey on independent set approximations. In Proc. APPROX '98, Springer LNCS 1444, pp. 1--14, 1998.
• 15: Refael Hassin, Approximation schemes for the restricted shortest path problem, Mathematics of Operations Research, v.17 n.1, p.36-42, Feb. 1992
• 16: Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece [doi>10.1145/380752.380825]
• 17: Kamal Jain , Vijay V. Vazirani, Equitable cost allocations via primal-dual-type algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509956]
• 18: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, 1996
• 19: Stavros G. Kolliopoulos , Clifford Stein, Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.153-168, June 22-24, 1998
• 20: Anshul Kothar , David C. Parke , Subhash Sur, Approximately-strategyproof and tractable multi-unit auctions, Proceedings of the 4th ACM conference on Electronic commerce, p.166-175, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779948]
• 21: Daniel Lehmann , Liaden Ita O'Callaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Proceedings of the 1st ACM conference on Electronic commerce, p.96-102, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337016]
• 22: Madhav V. Marathe , R. Ravi , Ravi Sundaram , S. S. Ravi , Daniel J. Rosenkrantz , Harry B. Hunt, III, Bicriteria network design problems, Journal of Algorithms, v.28 n.1, p.142-171, July 1, 1998 [doi>10.1006/jagm.1998.0930 ]
• 23: Ahuva Mu'alem , Noam Nisan, Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract, Eighteenth national conference on Artificial intelligence, p.379-384, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 24: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 25: Noam Nisan, Bidding and allocation in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.1-12, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352872]
• 26: Cynthia A. Phillips, The network inhibition problem, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.776-785, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167286]
• 27: Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
• 28: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 29: Gabriel Robins , Alexander Zelikovsky, Improved Steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.770-779, January 09-11, 2000, San Francisco, California, United States
• 30: Sartaj K. Sahni, Algorithms for Scheduling Independent Tasks, Journal of the ACM (JACM), v.23 n.1, p.116-127, Jan. 1976 [doi>10.1145/321921.321934]
• 31: Aravind Srinivasan, Improved Approximation Guarantees for Packing and Covering Integer Programs, SIAM Journal on Computing, v.29 n.2, p.648-670, Oct. 1999 [doi>10.1137/S0097539796314240]
• 32: Kunal Talwar, The Price of Truth: Frugality in Truthful Mechanisms, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.608-619, February 27-March 01, 2003
• 33: W. Vickrey. Counterspeculation, auctions and competitive sealed tenders. J. Finance, 16, pp. 8--37, 1961.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Economics, Theory

Keywords:
approximation algorithms, combinatorial and multi-unit auctions, enumeration techniques, mechanism design, primal-dual method