Distributed algorithmic mechanism design for scheduling on unrelated machines

In a classical mechanism design setting the outcome of the mechanism is computed by a trusted central party. In this paper we consider distributed implementations in which the outcome is computed by the agents themselves. We propose a distributed mechanism for solving the problem of scheduling on unrelated machines. This mechanism, called distributed MinWork (DMW) is a distributed implementation of the MinWork mechanism proposed by Nisan and Ronen. DMW is resilient to agents deviating from the protocol since the cheaters are detected and eliminated from further participation. We show that DMW is truthful, since it preserves the incentives and allocation policies from MinWork. Finally, we show that DMW has polynomial communication and computation costs.