Decentralized Utilitarian Mechanisms for Scheduling Games

R. Cole, J. Correa, V. Gkatzelis, V. Mirrokni, N.K. Olver

Research output: Contribution to JournalArticleAcademicpeer-review

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.
Original languageEnglish
Pages (from-to)306-326
JournalGames and Economic Behavior
Volume92
Issue numberJuly
Early online date3 May 2013
DOIs
Publication statusPublished - 2015

Fingerprint Dive into the research topics of 'Decentralized Utilitarian Mechanisms for Scheduling Games'. Together they form a unique fingerprint.

  • Cite this

    Cole, R., Correa, J., Gkatzelis, V., Mirrokni, V., & Olver, N. K. (2015). Decentralized Utilitarian Mechanisms for Scheduling Games. Games and Economic Behavior, 92(July), 306-326. https://doi.org/10.1016/j.geb.2013.03.011