Decentralized utilitarian mechanisms for scheduling games

Richard Cole, Jose Correa, Vasillis Gkatzelis, Vahab Mirrokni and Neil Olver

LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library

Abstract: Game Theory and Mechanism Design are by now standard tools for studying and designing massive decentralized systems. Unfortunately, designing mechanisms that induce socially efficient outcomes often requires full information and prohibitively large computational resources. In this work we study simple mechanisms that require only local information. Specifically, in the setting of a classic scheduling problem, we demonstrate local mechanisms that induce outcomes with social cost close to that of the socially optimal solution. Somewhat counter-intuitively, we find that mechanisms yielding Pareto dominated outcomes may in fact enhance the overall performance of the system, and we provide a justification of these results by interpreting these inefficiencies as externalities being internalized. We also show how to employ randomization to obtain yet further improvements. Lastly, we use the game-theoretic insights gained to obtain a new combinatorial approximation algorithm for the underlying optimization problem.

Keywords: coordination mechanisms; scheduling; price of anarchy (search for similar items in EconPapers)
JEL-codes: C72 D71 D82 (search for similar items in EconPapers)
Pages: 21 pages
Date: 2015-07
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Published in Games and Economic Behavior, July, 2015, 92, pp. 306 - 326. ISSN: 0899-8256

Downloads: (external link)
http://eprints.lse.ac.uk/103081/ Open access version. (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ehl:lserod:103081

Access Statistics for this paper

More papers in LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library LSE Library Portugal Street London, WC2A 2HD, U.K.. Contact information at EDIRC.
Bibliographic data for series maintained by LSERO Manager ().