Aarhus University Seal

Verifiably Truthful Mechanisms

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Simina Branzei
  • Ariel D. Procaccia, Carnegie Mellon University, United States
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.
Original languageEnglish
Title of host publicationProceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS '15
EditorsTim Roughgarden
Number of pages10
PublisherAssociation for Computing Machinery
Publication yearJan 2015
ISBN (print) 978-1-4503-3333-7
Publication statusPublished - Jan 2015
EventConference on Innovations in Theoretical Computer Science - Weizmann Institute of Science, Israel
Duration: 11 Jan 201513 Jan 2015
Conference number: 6


ConferenceConference on Innovations in Theoretical Computer Science
LocationWeizmann Institute of Science

See relations at Aarhus University Citationformats

ID: 84608450