On the communication requirements of verifying the VCG outcome

ABSTRACT

We consider the amount of communication required to verify the outcome of the Vickrey-Clarke-Groves (VCG) mechanism: an efficient allocation together with incentivizing VCG payments. We compare this to the communication required to verify the efficient decision rule alone, to assess the overhead imposed by VCG payments. Our characterizations are obtained by leveraging a connection between the VCG outcome and a price equilibrium concept known as universal competitive equilibrium. We consider four related environments within a common framework: the classic single-item setting, the multi-unit setting with decreasing marginal values, the classic assignment problem with unit-demand valuations, and the multi-unit assignment problem with substitutes valuations. We find that the single-unit settings have zero overhead, whereas the multi-unit settings can have significant positive overhead. With multiple units, the naïve VCG protocol that runs several efficient protocols in sequence (one with all agents, and ones with an agent removed, for each agent) is asymptotically optimal for several parameter settings of the number of agents, commodities, and units.

References

1. Lawrence M. Ausubel. An efficient ascending-bid auction for multiple objects. American Economic Review, 94(5):1452--1475, 2004.
2. Lawrence M. Ausubel. An efficient dynamic auction for heterogeneous commodities. American Economic Review, 96(3):602--629, 2006.
3. Lawrence M Ausubel and Paul R Milgrom. Ascending auctions with package bidding. Frontiers of Theoretical Economics, 1:1--42, 2002.
4. Sushil Bikhchandani and Joseph M. Ostroy. The package assignment model. Journal of Economic Theory, 107:377--406, 2002.
5. E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
6. Sven de Vries, James Schummer, and Rakesh V. Vohra. On ascending Vickrey auctions for heterogeneous objects. Journal of Economic Theory, 132(1):95--118, 2007.
7. Gabrielle Demange, David Gale, and Marilda Sotomayor. Multi-item auctions. Journal of Political Economy, 94(4):863--872, 1986.
8. Ronald Fadel and Ilya Segal. The communication cost of selfishness. Journal of Economic Theory, 2008. Forthcoming.
9. Satoru Fujishige and Zaifu Yang. A note on Kelso and Crawford's gross substitutes condition. Mathematics of Operations Research, 28(3):463--469, 2003.
10. Jerry Green and Jean-Jacques Laffont. Characterization of satisfactory mechansims for the revelation of preferences for public goods. Econometrica, 45:427--438, 1977.
11. Theodore Groves. Efficient collective choice when compensation is possible. Review of Economic Studies, 46:227--241, 1979.
12. Faruk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic Theory, 87:95--124, 1999.
13. Bengt Holmstrom. Groves schemes on restricted domains. Econometrica, 47(5):1137--1144, 1979.
14. Leonid Hurwicz. On the dimensional requirements of informationally decentralized Pareto-satisfatory processes. In K. J. Arrow and L. Hurwicz, editors, Studies in Resource Allocation Processes, pages 413--424. Cambridge University Press, 1977.
15. Alexander S. Kelso and Vincent P. Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50:1483--1504, 1982.
16. Vijay Krishna and Motty Perry. Efficient mechanism design. Technical report, Pennsylvania State University, 2000.
17. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997.
18. Sébastien Lahaie, Florin Constantin, and David C. Parkes. More on the power of demand queries in combinatorial auctions: Learning atomic languages and handling incentives. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, 2005.
19. Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270--296, May 2006.
20. Herman B. Leonard. Elicitation of honest preferences for the assignment of individuals to positions. The Journal of Political Economy, 91(3):461--479, 1983.
21. Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. Microecononmic Theory. Oxford University Press, 1995.
22. Debasis Mishra and David C. Parkes. Ascending price Vickrey auctions for general valuations. Journal of Economic Theory, 132(1):335--366, 2007.
23. Kenneth R. Mount and Stanley Reiter. The information size of message spaces. Journal of Economic Theory, 28:1--18, 1974.
24. Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. Journal of Economic Theory, 129(1):192--224, 2006.
25. David C. Parkes. Price-based information certificates for minimal-revelation combinatorial auctions. In J. Padget, D. Parkes, N. Sadeh, O. Shehory, and W. Walsh, editors, Agent-Mediated Electronic Commerce IV: Designing Mechanisms and Systems (LNAI 2531), pages 103--122. Springer-Verlag, 2002.
26. David C. Parkes and Lyle H. Ungar. An ascending-price generalized Vickrey auction. Technical report, Harvard University, 2002.
27. Stefan Reichelstein. Incentive compatibility and informational requirements. Journal of Economic Theory, 34:32--51, 1984.
28. Michael H. Rothkopf, Thomas J. Teisberg, and Edward P. Kahn. Why are Vickrey auctions rare? Journal of Political Economy, 98:94--109, 1990.
29. Lloyd S. Shapley and Martin Shubik. The assignment game I: The core. International Journal of Game Theory, 1:111--130, 1972.
30. William Vickrey. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Economics

• Theory of computation

  • Design and analysis of algorithms