Informational overhead of incentive compatibility

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Informational overhead of incentive compatibility

Full text

Pdf (533 KB)

Source

Electronic Commerce archive
Proceedings of the 9th ACM conference on Electronic commerce table of contents

Chicago, Il, USA

SESSION: Communication complexity in mechanisms table of contents

Pages 88-97

Year of Publication: 2008

ISBN:978-1-60558-169-9

Authors

Moshe Babaioff	Microsoft, Mountain View, CA, USA
Liad Blumrosen	Microsoft, Mountain View, CA, USA
Moni Naor	Weizmann Institute, Rehovot, Israel
Michael Schapira	Hebrew University, Jerusalem, Israel

Sponsors

ACM: Association for Computing Machinery
SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 54, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1386790.1386807 What is a DOI?

ABSTRACT

In the presence of self-interested parties, mechanism designers typically aim to achieve their goals (or social-choice functions) in an equilibrium. In this paper, we study the cost of such equilibrium requirements in terms of communication, a problem that was recently raised by Fadel and Segal. While a certain amount of information x needs to be communicated just for computing the outcome of a certain social-choice function, an additional amount of communication may be required for computing the equilibrium-supporting prices (even if such prices are known to exist).

Our main result shows that the total communication needed for this task can be greater than x by a factor linear in the number of players n, i.e., nx. This is the first known lower bound for this problem. In fact, we show that this result holds even in single-parameter domains (under the common assumption that losing players pay zero). On the positive side, we show that certain classic economic objectives, namely, single-item auctions and public-good mechanisms, only entail a small overhead. Finally, we explore the communication overhead in welfare-maximization domains, and initiate the study of the overhead of computing payments that lie in the core of coalitional games.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L. M. Ausubel and P. R. Milgrom. Ascending auctions with package bidding. Frontiers of Theoretical Economics, 1:1--42, 2002.
	2	Lawrence M. Ausubel and Paul Milgrom. In P. Cramton and Y. Shoham and R. Steinberg (Editors), Combinatorial Auctions. Chapter 1. The Lovely but Lonely Vickrey Auction. MIT Press., 2006.
	3	Sushil Bikhchandani, Rakesh Vohra, Sven de Vries, and JamesSchummer. Linear programming and Vickrey auctions. Mathematics of the Internet: E-Auction and Markets, pages 75--115, 2002.
	4	Liad Blumrosen , Michal Feldman, Implementation with a bounded action space, Proceedings of the 7th ACM conference on Electronic commerce, p.62-71, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134715]
	5	Liad Blumrosen , Noam Nisan, On the computational power of iterative auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.29-43, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064013]
	6	Liad Blumrosen , Noam Nisan, On the computational power of iterative auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.29-43, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064013]
	7	Yuval Emek , David Peleg , Liam Roditty, A near-linear time algorithm for computing replacement paths in planar directed graphs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.428-435, January 20-22, 2008, San Francisco, California
	8	J. Hershberger , S. Suri, Vickrey Prices and Shortest Paths: What is an Edge Worth?, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.252, October 14-17, 2001
	9	Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
	10	Noam Nisan. Introduction to Mechanism Design (for Computer Scientists) In Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay Vazirani (Editors), Algorithmic Game Theory. Chapter 9.
	11	Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behaviour, 35:166--196, 2001. A preliminary version appeared in STOC 1999.
	12	Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. Journal of Economic Theory, 129(1):192--224, 2006.
	13	Ilya Segal. In P. Cramton and Y. Shoham and R. Steinberg (Editors), Combinatorial Auctions. Chapter 11. The Communication Requirements of Combinatorial Allocation Problems. MIT Press., 2006.
	14	Ilya Segal. The communication requirements of social choice rules and supporting budget sets. Journal of Economic Theory, 136:341--378, 2007.
	15	Ilya Segal and Ronald Fadel. The communication cost of selfishness, 2006. Journal of Ecnomic Theory, to appear.
	16	Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]