Designing Local Distributed Mechanisms
Designing Local Distributed Mechanisms
In this work we introduce a new notion: local mechanisms. These are truthful mechanisms that have an implementation as fast distributed algorithms and non-trivial approximation guarantees. We show how monotone distributed optimisation algorithms can be turned into truthful mechanisms using Myerson's Lemma. We demonstrate mechanisms for four fundamental graph problems: …