کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431588 688591 2011 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Distributed algorithmic mechanism design for scheduling on unrelated machines
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Distributed algorithmic mechanism design for scheduling on unrelated machines
چکیده انگلیسی

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.

Research highlights
► Proposed DMW, a distributed mechanism for scheduling on unrelated machines.
► DMW is a faithful implementation of the MinWork mechanism.
► DMW protects the anonymity of the losing agents and the privacy of their bids.
► DMW is efficient as it has polynomial communication and computation costs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 71, Issue 3, March 2011, Pages 397–406
نویسندگان
, ,