loading...
Distributed Algorithmic Mechanism Design for Scheduling on Unrelated Machines
Las Vegas, Nevada, USA December 07-December 09
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.378th International Symposium on Parall ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Thomas E. Carroll, Daniel Grosu, "Distributed Algorithmic Mechanism Design for Scheduling on Unrelated Machines," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 194-201, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005.
 
 
BibTex
x
 
@article{ 10.1109/ISPAN.2005.37,
author = {Thomas E. Carroll and Daniel Grosu},
title = {Distributed Algorithmic Mechanism Design for Scheduling on Unrelated Machines},
journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on},
volume = {0},
year = {2005},
issn = {1087-4089},
pages = {194-201},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.37},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel Architectures, Algorithms, and Networks, International Symposium on
TI - Distributed Algorithmic Mechanism Design for Scheduling on Unrelated Machines
SN - 1087-4089
SP194
EP201
A1 - Thomas E. Carroll,
A1 - Daniel Grosu,
PY - 2005
KW - null
VL - 0
JA - Parallel Architectures, Algorithms, and Networks, International Symposium on
ER -
 
Thomas E. Carroll, Wayne State University
Daniel Grosu, Wayne State University
In 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 theMinWork mechanism proposed by Nisan and Ronen [12]. 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.
Citation:
Thomas E. Carroll, Daniel Grosu, "Distributed Algorithmic Mechanism Design for Scheduling on Unrelated Machines," ispan, pp.194-201, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.