Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Single-Call Mechanisms

Published: 20 April 2015 Publication History

Abstract

Truthfulness is fragile and demanding. It is oftentimes harder to guarantee truthfulness when solving a problem than it is to solve the problem itself. Even worse, truthfulness can be utterly destroyed by small uncertainties in a mechanism’s outcome. One obstacle is that truthful payments depend on outcomes other than the one realized, such as the lengths of non-shortest-paths in a shortest-path auction. Single-call mechanisms are a powerful tool that circumvents this obstacle: they implicitly charge truthful payments, guaranteeing truthfulness in expectation using only the outcome realized by the mechanism. The cost of such truthfulness is a trade-off between the expected quality of the outcome and the risk of large payments.
We study two of the most general domains for truthful mechanisms and largely settle when and to what extent single-call mechanisms are possible. The first single-call construction was discovered by Babaioff et al. [2010] in single-parameter domains. They give a transformation that turns any monotone, single-parameter allocation rule into a truthful-in-expectation single-call mechanism. Our first result is a natural complement to Babaioff et al. [2010]: we give a new transformation that produces a single-call VCG mechanism from any allocation rule for which VCG payments are truthful. Second, in both the single-parameter and VCG settings, we precisely characterize the possible transformations, showing that a wide variety of transformations are possible but that all take a very simple form. Finally, we study the inherent trade-off between the expected quality of the outcome and the risk of large payments. We show that our construction and that of Babaioff et al. [2010] simultaneously optimize a variety of metrics in their respective domains.
Our study is motivated by settings where uncertainty in a mechanism renders other known techniques untruthful, and we offer a variety of examples where such uncertainty can arise. In particular, we analyze pay-per-click advertising auctions, where the truthfulness of the standard VCG-based auction is easily broken when the auctioneer’s estimated click-through-rates are imprecise.

References

[1]
A. Archer and É. Tardos. 2001. Truthful mechanisms for one-parameter agents. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS’01). IEEE, 482.
[2]
Susan Athey and Jonathan Levin. 2001. Information and competition in U.S. Forest Service timber auctions. J. Political Econ. 109, 2, 375--417. http://ideas.repec.org/a/ucp/jpolec/v109y2001i2p375-417.html
[3]
Moshe Babaioff, Liad Blumrosen, Moni Naor, and Michael Schapira. 2008. Informational overhead of incentive compatibility. In Proceedings of the 9th ACM Conference on Electronic Commerce (EC’08). ACM, New York, 88--97.
[4]
Moshe Babaioff, Robert Kleinberg, and Aleksandrs Slivkins. 2013. Multi-parameter mechanisms with implicit payment computation. CoRR abs/1302.4138 (2013).
[5]
Moshe Babaioff, Robert D. Kleinberg, and Aleksandrs Slivkins. 2010. Truthful mechanisms with implicit payment computation. In Proceedings of the 11th ACM Conference on Electronic Commerce (EC’10). ACM, New York, 43--52.
[6]
Moshe Babaioff, Yogeshwer Sharma, and Aleksandrs Slivkins. 2009. Characterizing truthful multiarmed bandit mechanisms: extended abstract. In Proceedings of the 10th ACM Conference on Electronic Commerce (EC’09). ACM, New York, 79--88.
[7]
Alessandro Chiesa, Silvio Micali, and Zeyuan Allen Zhu. 2012. Mechanism design with approximat evaluations. In Proceedings of the 3rd Conference on Innovations in Theoretical Computer Science (ITCS’12). ACM, New York, 34--38.
[8]
Nikhil R. Devanur and Sham M. Kakade. 2009. The price of truthfulness for pay-per-click auctions. In Proceedings of the 10th ACM Conference on Electronic Commerce (EC’09). ACM, New York, 99--106.
[9]
Shahar Dobzinski and Shaddin Dughmi. 2009. On the power of randomization in algorithmic mechanism design. In Proceedings of the IEEE Symposium on Foundations of Computer Science. 505--514.
[10]
Shaddin Dughmi and Tim Roughgarden. 2010. Black-box randomized reductions in algorithmic mechanism design. In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science.775--784.
[11]
J. Hershberger and S. Suri. 2001. Vickrey prices and shortest paths: What is an edge worth? InProceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS’01). IEEE.
[12]
John Hershberger and Subhash Suri. 2002. Erratum to ’’Vickrey pricing and shortest paths: What is anedge worth?” In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS’02). IEEE.
[13]
John Hershberger, Subhash Suri, and Amit Bhosle. 2007. On the difficulty of some shortest pathproblems. ACM Trans. Algorithms 3, 1, Article 5.
[14]
David Jabas. 2010. Private communication.
[15]
Sébastien Lahaie. 2010. Stability and incentive compatibility in a kernel-based combinatorialauction. In Proceedings of the National Conference on Artificial Intelligence.
[16]
Roger B. Myerson. 1981. Optimal auction design. Math. Operations Research 6, 1,58--73.
[17]
Noam Nisan and Amir Ronen. 2001. Algorithmic mechanism design. Games Econ. Behavior 35,1--2, 166--196.
[18]
Noam Nisan and Amir Ronen. 2007. Computationally feasible VCG mechanisms. J. Artif.Intell. Res. 29, 19--47.
[19]
Kevin Roberts. 1979. The characterization of implementable social choice rules. In Aggretaionand Revelation of Preferences, J.-J. Laffont, Ed., North Holland Publishing Company.
[20]
Robert M. Stark. 1974. Unbalanced highway contract tendering. Oper. Res. Quart.25, 3, 373--388. http://www.jstor.org/stable/3007925
[21]
Hal R. Varian. 2009. Online Ad Auctions. American Econ. Rev. 99, 2, 430--34.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation
ACM Transactions on Economics and Computation  Volume 3, Issue 2
Special Issue on EC'12, Part 2
April 2015
171 pages
ISSN:2167-8375
EISSN:2167-8383
DOI:10.1145/2764902
Issue’s Table of Contents
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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 April 2015
Accepted: 01 May 2014
Revised: 01 April 2014
Received: 01 March 2013
Published in TEAC Volume 3, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. black-box reductions
  2. efficiency
  3. incentive compatibility
  4. single-call

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 100
    Total Downloads
  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media