Mechanism design with incomplete languages

ABSTRACT

A major achievement of mechanism design theory is the family of truthful mechanisms often called VCG (named after Vickrey, Clarke and Groves). Although these mechanisms have many appealing properties, their essential intractability prevents them from being applied to complex problems like combinatorial auctions. In particular, VCG mechanisms require the agents to fully describe their valuation functions to the mechanism. Such a description may require exponential size and thus be infeasible for the agents.A natural approach for this problem is to introduce an intermediate language for the description of the valuations. Such a language must be succinct to both the agents and the mechanism. Unfortunately, the resulting mechanisms are neither truthful nor do they satisfy individual rationality.This paper suggests a general method for overcoming this difficulty. Given an intermediate language and an algorithm for computing the results, we propose three different mechanisms, each more powerful than its predecessor, but also more time consuming. Under reasonable assumptions, the results of our mechanisms are at least as good as the results of the algorithm on the actual valuations. All of our mechanisms have polynomial computational time and satisfy individual rationality.

REFERENCES

• 1: E.H.Clarke.Multipart pricing of public goods.Public Choice pages 17 -33,1971.
• 2: Sven de Vries and Vohra Rakesh.Combinatorial auctions:A survey.To appear.
• 3: Yuzo Fujishima , Kevin Leyton-Brown , Yoav Shoham, Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.548-553, July 31-August 06, 1999
• 4: J.Green and J.J.La .ont.Characterization of satisfactory mechanisms for the revelation of preferences for public goods.Econometrica pages 427 -438,1977.
• 5: T.Groves.Incen ives in teams.Econometrica pages 617 -631,1973.
• 6: M. H. Rothkopf , A. Pekec , R. M. Harstad, Computationally Manageable Combinatorial Auctions, Certer for Discrete Mathematics & Theoretical Computer Science, 1995
• 7: 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]
• 8: A.Mas-Collel,Whinston W.,and J.Green. Microeconomic Theory Oxford university press,1995.
• 9: J.McMillan.Selling spectrum righ s.Journal of Economic Perspectives pages 145 -162,1994.
• 10: Paul Milgrom.Putting auction heory o work:the simultaneous ascending auction.Technical Report 98-002,Dept.of Economics,Stanford University,1998.
• 11: 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]
• 12: Noam Nisan.Private communication,2000.
• 13: Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
• 14: 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]
• 15: M.J.Osborne and A.Rubinstein.A Course in Game Theory MIT press,1994.
• 16: David C. Parkes, iBundle: an efficient ascending price bundle auction, Proceedings of the 1st ACM conference on Electronic commerce, p.148-157, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337032]
• 17: Kevin Roberts.The characterization of implemen able choise rules.In Jean-Jacques La .ont,editor, Aggregation and Revelation of Preferences pages 321 -349.North-Holland,1979.Papers presen ed at the .rst European Summer Workshop of he Econometric Society.
• 18: Amir Ronen.Mechanism design with incomplete languages.http://task.stanford.edu/,2001.(full version).
• 19: Toumas Sandholm.Issues in computational vickrey auctions.International Journal of Electronic Commerce 4(3):107 -129,2000.
• 20: Tuomas Sandholm, Approaches to winner determination in combinatorial auctions, Decision Support Systems, v.28 n.1-2, p.165-176, March 2000 [doi>10.1016/S0167-9236(99)00066-4]
• 21: W.Vickrey.Counterspeculation,auctions and competitive sealed enders.Journal of Finance pages 8-37,1961.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Natural language interfaces

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Design, Languages, Performance