skip to main content
10.1145/1151454.1151473acmotherconferencesArticle/Chapter ViewAbstractPublication PagesicecConference Proceedingsconference-collections
Article

Passive verification of the strategyproofness of mechanisms in open environments

Published: 13 August 2006 Publication History

Abstract

Consider an open infrastructure in which anyone can deploy mechanisms to support automated decision making and coordination amongst self-interested computational agents. Strategyproofness is a central property in the design of such mechanisms, allowing participants to maximize their individual benefit by reporting truthful private information about preferences and capabilities and without modeling or reasoning about the behavior of other agents. But, why should participants trust that a mechanism is strategyproof? We address this problem, proposing and describing a passive verifier, able to monitor the inputs and outputs of mechanisms and verify the strategyproofness, or not, of a mechanism. Useful guarantees are available to participants before the behavior of the mechanism is completely known, and metrics are introduced to provide a measure of partial verification. Experimental results demonstrate the effectiveness of our method.

References

[1]
A Archer and E Tardos. Truthful mechanisms for one-parameter agents. In Proc. 42nd IEEE Symp. on Foundations of Computer Science, 2001.
[2]
Moshe Babaioff, Noam Nisan, and Elan Pavlov. Mechanisms for a spatially distributed market. In Proc. 5th ACM Conf. on Electronic Commerce, pages 9--20. ACM Press, 2004.
[3]
Y. Bartal, R. Gonen, and N. Nisan. Incentive compatible multi unit combinatorial auctions. In In Proc. Theoretical Aspect of Rationality and Knowledge, 2003.
[4]
A. Broder and M. Mitzenmacher. Network applications of bloom filters: A survey. Internet Math, 1, no. 4, 2003.
[5]
D. C. Parkes, M. O. Rabin, S. M. Shieber, and C. A. Thorpe. Practical secrecy-preserving, verifiably correct and trustworthy auctions. In Proc. 8th Int. Conf. on Electronic Commerce (ICEC'06), 2006.
[6]
Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial Intelligence Journal, 49:61--95, 1991.
[7]
Amos Fiat, Andrew Goldberg, Jason Hartline, and Anna Karlin. Competitive generalized auctions. In Proc. 34th ACM Symposium on Theory of Computing (STOC'02), 2002.
[8]
A. Garcia-Camino, P. Noriega, and J. A. Rodriguez-Aguilar. Implementing norms in electronic institutions. In Proceedings of the 4th Int. Joint Conf. on Autonomous Agents and Multiagent Systems (AAMAS-05), 2005.
[9]
Andrew Goldberg and Jason Hartline. Envy-free auctions for digital goods. In Proc. ACM E'Commerce, 2003.
[10]
F. Guerin and J. V. Pitt. Guaranteeing properties for e-commerce systems. In O. Shehory and N. Sadeh J. Padget, D. Parkes, editor, LNAI 2531: Agent-Mediated Electronic Commerce IV, pages 253--272. Springer-Verlag, 2002.
[11]
Honwei Gui, Rudolf Muller, and Rakesh V Vohra. Dominant strategy mechanisms with multidimensional types. Technical report, Northwestern Univ., 2004.
[12]
Holger H. Hoos and Craig Boutilier. Solving combinatorial auctions with stochastic local search. In Proc. 17th National Conference on Artificial Intelligence (AAAI-00), July 2000.
[13]
Matthew O. Jackson. Mechanism theory. In The Encyclopedia of Life Support Systems. EOLSS Publishers, 2000.
[14]
R. Lavi, A. Mu'alem, and N. Nisan. Towards a characterization of truthful combinatorial auctions. In Proc. 44th Annual Symposium on Foundations of Computer Science, 2003.
[15]
Daniel Lehmann, Liadan Ita O'Callaghan, and Yoav Shoham. Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM, 49(5):577--602, September 2002.
[16]
Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham. Towards a universal test suite for combinatorial auctions. In Proc. 2nd ACM Conf. on Electronic Commerce (EC-00), 2000.
[17]
Robert B. Myerson. Optimal auction design. Mathematics of Operation Research, 6:58--73, 1981.
[18]
M Naor, B Pinkas, and O Reingold. Privacy preserving auctions and mechanism design. In Proc. 1st ACM Conf. on Electronic Commerce (EC-99), pages 129--139, 1999.
[19]
S. Papai. Groves sealed bid auctions of heterogeneous objects with fair prices. Social Choice and Welfare, 20:371--385, March 2003.
[20]
M. Pauly. Programming and verifying subgame perfect mechanisms. Journal of Logic and Computation, 15(3):295--316, 2005.
[21]
M. Pauly and M. Wooldridge. Logic for mechanism design - a manifesto. Proceedings of the Game Theoretic and Decision Theoretic Agents Workshop, 2003.
[22]
W. van der Hoek, A. Lomuscio, and M. Wooldridge. On the complexity of practical atl model checking. In Proceedings of the 5th Int. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS-06), 2006.
[23]
Makoto Yokoo. The characterization of strategy/false-name proof combinatorial auction protocols: Price-oriented, rationing-free protocol. In Proc. 18th Int. Joint Conf. on Art. Intell., 2003.

Cited By

View all
  • (2023)Differentially Private Resource AllocationAnnual Computer Security Applications Conference10.1145/3627106.3627181(772-786)Online publication date: 4-Dec-2023
  • (2015)Verifiably Truthful MechanismsProceedings of the 2015 Conference on Innovations in Theoretical Computer Science10.1145/2688073.2688098(297-306)Online publication date: 11-Jan-2015
  • (2011)Distributed algorithmic mechanism design for scheduling on unrelated machinesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.11.00471:3(397-406)Online publication date: 1-Mar-2011

Index Terms

  1. Passive verification of the strategyproofness of mechanisms in open environments

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    ICEC '06: Proceedings of the 8th international conference on Electronic commerce: The new e-commerce: innovations for conquering current barriers, obstacles and limitations to conducting successful business on the internet
    August 2006
    624 pages
    ISBN:1595933921
    DOI:10.1145/1151454
    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: 13 August 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. constraint networks
    2. game theory
    3. mechanism design
    4. strategyproofness
    5. verification

    Qualifiers

    • Article

    Acceptance Rates

    ICEC '06 Paper Acceptance Rate 53 of 112 submissions, 47%;
    Overall Acceptance Rate 150 of 244 submissions, 61%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 17 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Differentially Private Resource AllocationAnnual Computer Security Applications Conference10.1145/3627106.3627181(772-786)Online publication date: 4-Dec-2023
    • (2015)Verifiably Truthful MechanismsProceedings of the 2015 Conference on Innovations in Theoretical Computer Science10.1145/2688073.2688098(297-306)Online publication date: 11-Jan-2015
    • (2011)Distributed algorithmic mechanism design for scheduling on unrelated machinesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.11.00471:3(397-406)Online publication date: 1-Mar-2011

    View Options

    Login options

    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