Verifiably truthful mechanisms

DOI10.1145/2688073.2688098MaRDI QIDQ2989043zbMATH OpenOpenAlexFDO

Authors Simina Brânzei, Ariel D. Procaccia

Publication date 19 May 2017

Published in Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.0056

zbMATH Keywords

verificationdecision treesapproximationfacility locationmechanism design

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Specification and verification (program logics, model checking, etc.) (68Q60) Discrete location and assignment (90B80)

Abstract: It is typically expected that if a mechanism is truthful, then the agents would, indeed, truthfully report their private information. But why would an agent believe that the mechanism is truthful? We wish to design truthful mechanisms, whose truthfulness can be verified efficiently (in the computational sense). Our approach involves three steps: (i) specifying the structure of mechanisms, (ii) constructing a verification algorithm, and (iii) measuring the quality of verifiably truthful mechanisms. We demonstrate this approach using a case study: approximate mechanism design without money for facility location.

Recommendations

• The power of verification for one-parameter agents
• Truthful optimization using mechanisms with verification
• Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions
• Automata, Languages and Programming
• Collusion-resistant mechanisms with verification yielding optimal solutions

Cited in

(17)

• Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions
• Obvious strategyproofness, bounded rationality and approximation
• scientific article; zbMATH DE number 7204414 (Why is no real title available?)
• Truthfulness flooded domains and the power of verification for mechanism design
• Collusion-resistant mechanisms with verification yielding optimal solutions
• Computer-aided verification for mechanism design
• Verifiable disclosure
• Algorithms for strategyproof classification
• Approaching utopia, strong truthfulness and externality-resistant mechanisms
• scientific article; zbMATH DE number 5547975 (Why is no real title available?)
• The power of verification for one-parameter agents
• SOFSEM 2004: Theory and Practice of Computer Science
• Approximation guarantee of OSP mechanisms: the case of machine scheduling and facility location
• New Constructions of Mechanisms with Verification
• Rationality authority for provable rational behavior
• From monetary to nonmonetary mechanism design via artificial currencies
• Facility location games with optional preference

This page was built for publication: Verifiably truthful mechanisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989043)