Verifiably truthful mechanisms

DOI10.1145/2688073.2688098zbMATH Open1364.91063arXiv1412.0056OpenAlexW2153285919MaRDI QIDQ2989043FDOQ2989043

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)

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.

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

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

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)

Cited In (17)

• Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions
• Obvious strategyproofness, bounded rationality and approximation
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• SOFSEM 2004: Theory and Practice of Computer Science
• The power of verification for one-parameter agents
• 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)