Journal article
Decentralized utilitarian mechanisms for scheduling games
Games and economic behavior, v 92, pp 306-326
01 Jul 2015
Featured in Collection : UN Sustainable Development Goals @ Drexel
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. (C) 2013 Elsevier Inc. All rights reserved.
Metrics
Details
- Title
- Decentralized utilitarian mechanisms for scheduling games
- Creators
- Richard Cole - New York UniversityJose R. Correa - University of ChileVasilis Gkatzelis - Courant Institute of Mathematical SciencesVahab Mirrokni - Google (United States)Neil Olver - IIT@MIT
- Publication Details
- Games and economic behavior, v 92, pp 306-326
- Publisher
- Elsevier
- Number of pages
- 21
- Grant note
- 1115849 / Direct For Computer & Info Scie & Enginr; Division of Computing and Communication Foundations; National Science Foundation (NSF); NSF - Directorate for Computer & Information Science & Engineering (CISE) CCF0830516; CCF1217989; CCF1115849 / NSF; National Science Foundation (NSF) ICM/FIC P10-024F / "Millennium Nucleus Information and Coordination in Networks" 1217989 / Division of Computing and Communication Foundations; Direct For Computer & Info Scie & Enginr; National Science Foundation (NSF); NSF - Directorate for Computer & Information Science & Engineering (CISE) 1090050 / FONDECYT; Comision Nacional de Investigacion Cientifica y Tecnologica (CONICYT); CONICYT FONDECYT Andreas Mentzelopoulos Scholarships for University of Patras
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000360251100018
- Scopus ID
- 2-s2.0-84938976297
- Other Identifier
- 991021868728904721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Industry collaboration
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Economics