D3.2 Strongly Truthful and Composable Mechanism Design

We are presenting a new, extended utilities model for mechanism design settings which can incorporate externalities, such as malicious and spiteful behavior of the participating agents. Based on this, a new notion of strong truthfulness is presented and analyzed, which is based on the principle of "punishing" players that lie. Due to this, strongly truthful mechanisms can serve as subcomponents in bigger mechanism protocols in order to "boost truthfulness" in settings with externalities and achieve a kind of externalities-resistant performance. The related solution concept equilibria are discussed. This decomposability scheme is rather general and powerful, and we show how it can be also adapted to the case of the well known mechanism design problem of scheduling
tasks to machines for minimizing the makespan.

D3.2 Strongly Truthful and Composable Mechanism Design