Verifiably truthful mechanisms

<a class="pub-badge pub-badge--doi" href="https://doi.org/10.1145/2688073.2688098" rel="nofollow">DOI 10.1145/2688073.2688098</a><a class="pub-badge pub-badge--grey" href="https://zbmath.org/1364.91063" rel="nofollow">zbMATH</a><a class="pub-badge pub-badge--grey" href="https://openalex.org/works/W2153285919" rel="nofollow">OpenAlex</a><a class="pub-badge pub-badge--mardi" href="https://portal.mardi4nfdi.de/wiki/Item:Q2989043" rel="nofollow">MaRDI QID Q2989043</a><a class="pub-badge pub-badge--grey" href="https://fdo.portal.mardi4nfdi.de/fdo/Q2989043" rel="nofollow">FDO</a>

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)

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

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)