Competitive generalized auctions

ABSTRACT

We describe mechanisms for auctions that are simultaneously truthful (alternately known as strategy-proof or incentive compatible) and guarantee high "net" profit. We make use of appropriate variants of competitive analysis of algorithms in designing and analyzing our mechanisms. Thus, we do not require any probabilistic assumptions on bids.We present two new concepts regarding auctions, that of a cancellable auction and that of a generalized auction. We use cancellable auctions in the design of generalized auctions, but they are of independent interest as well. Cancellable auctions have the property that if the revenue collected does not meet certain predetermined criteria, then the auction can be cancelled and the resulting auction is still truthful. The trivial approach (run a truthful auction and cancel if needed) yields an auction that is not necessarily truthfu.Generalized auctions can be used to model many problems previously considered in the literature, as well as numerous new problems. In particular, we give the first truthful profit-maximizing auctions for problems such as conditional financing and multicast.

REFERENCES

• 1: 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
• 2: Aaron Archer , Éva Tardos, Frugal path mechanisms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.991-999, January 06-08, 2002, San Francisco, California
• 3: Ziv Bar-Yossef , Kirsten Hildrum , Felix Wu, Incentive-compatible online auctions for digital goods, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.964-970, January 06-08, 2002, San Francisco, California
• 4: E. H. Clarke. Multipart Pricing of Public Goods. Public Choice, 11:17--33, 1971.
• 5: Joan Feigenbaum , Christos Papadimitriou , Scott Shenker, Sharing the cost of muliticast transmissions (preliminary version), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.218-227, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335332]
• 6: A. V. Goldberg, J. D. Hartline, A. R. Karlin, and A. Wright. Competitive Auctions. In submitted to Games and Economic Behavior., 2002.
• 7: Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
• 8: T. Groves. Incentives in Teams. Econometrica, 41:617--631, 1973.
• 9: J. Hershberger and S. Suri. Vickrey Pricing in network routing: Fast payment computation. In Proc. of the 42nd IEEE Symposium on Foundations of Computer Science, 2001.
• 10: 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]
• 11: P. Klemperer. Auction theory: A guide to the literature. In Journal of Economic Surveys, pages 227--286. 13(3), 1999.
• 12: A. Mas-Collel, M. Whinston, and J. Green. Microeconomic Theory. Oxford University Press, 1995.
• 13: H. Moulin and S. Shenker. Strategyproof Sharing of Submodular Costs. Economic Theory, to appear.
• 14: N. Nisan. Algorithms for Selfish Agents: Mechanism Design for Distributed Computation. In Proc. STACS 1999, pages 1--15. Springer LNCS 1563, 1999.
• 15: 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]
• 16: 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]
• 17: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 18: L. S. Shapley. Core of Convex Games. Int. J. of Game Theory, 1:11--26, 1971.
• 19: S. Shenker and V. Vazirani. Private Comm., 2001.
• 20: Combinatorial Auctions: A survey. S. DeVries and R. Vohra. In Unpublished manuscript, 2000.
• 21: W. Vickrey. Counterspeculation, Auctions, and Competitive Sealed Tenders. J. of Finance, 16:8--37, 1961.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Experimentation, Performance, Theory