Distributed algorithmic mechanism design for scheduling on unrelated machines |
| |
Authors: | Thomas E. CarrollAuthor Vitae |
| |
Affiliation: | a Pacific Northwest National Lab, 902 Battelle Boulevard, Richland, WA 99352, USAb Department of Computer Science, Wayne State University, Detroit, MI 48202, USA |
| |
Abstract: | In classical mechanism design the outcome of the mechanism is computed by a trusted central party. In this paper, we consider the design of distributed mechanisms in which the outcome is computed by the agents themselves. We propose Distributed MinWork (DMW), a mechanism for solving the problem of scheduling on unrelated machines. We show that DMW is a faithful implementation of the MinWork mechanism, which was proposed by Nisan and Ronen in their seminal work (Nisan and Ronen (2001) [30]). We show that in addition to being faithful, DMW protects the anonymity of the losing agents and the privacy of their bids. Furthermore, we show that DMW is efficient as it has polynomial communication and computation costs. |
| |
Keywords: | Algorithmic mechanism design Scheduling on unrelated machines Truthful mechanism Distributed computation |
本文献已被 ScienceDirect 等数据库收录! |
|