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
Pages297-306
ISBN (print) 978-1-4503-3333-7
DOIs
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

Conference

ConferenceConference on Innovations in Theoretical Computer Science
Nummer6
LocationWeizmann Institute of Science
LandIsrael
Periode11/01/201513/01/2015

See relations at Aarhus University Citationformats

ID: 84608450