research-article

Informational overhead of incentive compatibility

Authors:

Moshe Babaioff,

Liad Blumrosen,

Michael SchapiraAuthors Info & Claims

EC '08: Proceedings of the 9th ACM conference on Electronic commerce

Pages 88 - 97

https://doi.org/10.1145/1386790.1386807

Published: 08 July 2008 Publication History

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

[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 and Michal Feldman. Implementation with a bounded action space. In Proceedings of the 7th ACM conference on Electronic commerce, pages 62--71, 2006.

Digital Library

[5]

Liad Blumrosen and Noam Nisan. On the computational power of iterative auctions I: demand queries. Discussion paper no. 381, The Center for the Study of Rationality, The Hebrew University., 2005. An extended abstract in EC'05 contained preliminary results.

Digital Library

[6]

Liad Blumrosen and Noam Nisan. On the computational power of iterative auctions II: ascending auctions. Discussion paper no. 382, The Center for the Study of Rationality, The Hebrew University., 2005. An extended abstract in EC'05 contained preliminary results.

Digital Library

[7]

Yuval Emek, David Peleg, and Liam Roditty. A near-linear time algorithm for computing replacement paths in planar directed graph. In SODA'08, 2008.

Digital Library

[8]

J. Hershberger and S. Suri. Vickrey prices and shortest paths: What is an edge worth? In Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, page 252, 2001.

Digital Library

[9]

Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997.

Digital Library

[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. In ACM Symposium on Theory of Computing, pages 209--213, 1979.

Digital Library

Cited By

Dobzinski SRon SKhuller SVassilevska Williams V(2021)The communication complexity of payment computationProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451083(933-946)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451083
Dobzinski S(2016)Computational Efficiency Requires Simple Taxation2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2016.30(209-218)Online publication date: Oct-2016
https://doi.org/10.1109/FOCS.2016.30
Wilkens CSivan B(2015)Single-Call MechanismsACM Transactions on Economics and Computation10.1145/27410273:2(1-60)Online publication date: 20-Apr-2015
https://dl.acm.org/doi/10.1145/2741027
Show More Cited By

Index Terms

Informational overhead of incentive compatibility
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics

Recommendations

On the communication requirements of verifying the VCG outcome
EC '08: Proceedings of the 9th ACM conference on Electronic commerce

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 ...
Estimating Approximate Incentive Compatibility
EC '19: Proceedings of the 2019 ACM Conference on Economics and Computation

In practice, most mechanisms for selling, buying, matching, voting, and so on are not incentive compatible. We present techniques for estimating how far a mechanism is from incentive compatible. Given samples from the agents' type distribution, we show ...
Testing Incentive Compatibility in Display Ad Auctions
WWW '18: Proceedings of the 2018 World Wide Web Conference

Consider a buyer participating in a repeated auction, such as those prevalent in display advertising. How would she test whether the auction is incentive compatible? To bid effectively, she is interested in whether the auction is single-shot incentive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '08: Proceedings of the 9th ACM conference on Electronic commerce

July 2008

332 pages

ISBN:9781605581699

DOI:10.1145/1386790

General Chair:
Lance Fortnow
Northwestern University, USA
,
Program Chairs:
John Riedl
University of Minnesota, USA
,
Tuomas Sandholm
Carnegie-Mellon University, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '08

Sponsor:

EC '08: ACM Conference on Electronic Commerce

July 8 - 12, 2008

Il, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
207
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)2

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dobzinski SRon SKhuller SVassilevska Williams V(2021)The communication complexity of payment computationProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451083(933-946)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451083
Dobzinski S(2016)Computational Efficiency Requires Simple Taxation2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2016.30(209-218)Online publication date: Oct-2016
https://doi.org/10.1109/FOCS.2016.30
Wilkens CSivan B(2015)Single-Call MechanismsACM Transactions on Economics and Computation10.1145/27410273:2(1-60)Online publication date: 20-Apr-2015
https://dl.acm.org/doi/10.1145/2741027
Feigenbaum JJaggard ASchapira M(2014)Approximate PrivacyACM Transactions on Algorithms10.1145/260106710:3(1-38)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.1145/2601067
Babaioff MBlumrosen LSchapira M(2013)The communication burden of payment determinationGames and Economic Behavior10.1016/j.geb.2012.08.00777:1(153-167)Online publication date: Jan-2013
https://doi.org/10.1016/j.geb.2012.08.007
Wilkens CSivan BFaltings BLeyton-Brown KIpeirotis P(2012)Single-call mechanismsProceedings of the 13th ACM Conference on Electronic Commerce10.1145/2229012.2229084(946-963)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.1145/2229012.2229084
Feigenbaum JJaggard ASchapira MParkes DDellarocas CTennenholtz M(2010)Approximate privacyProceedings of the 11th ACM conference on Electronic commerce10.1145/1807342.1807369(167-178)Online publication date: 7-Jun-2010
https://dl.acm.org/doi/10.1145/1807342.1807369
Babaioff MKleinberg RSlivkins AParkes DDellarocas CTennenholtz M(2010)Truthful mechanisms with implicit payment computationProceedings of the 11th ACM conference on Electronic commerce10.1145/1807342.1807349(43-52)Online publication date: 7-Jun-2010
https://dl.acm.org/doi/10.1145/1807342.1807349

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents