  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.
