Conference proceeding
Cost-Sharing Methods for Scheduling Games under Uncertainty
EC'17: PROCEEDINGS OF THE 2017 ACM CONFERENCE ON ECONOMICS AND COMPUTATION, pp 441-458
01 Jan 2017
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
We study the performance of cost-sharing protocols in a selfish scheduling setting with load-dependent cost functions. Previous work on selfish scheduling protocols has focused on two extreme models: omnipotent protocols that are aware of every machine and every job that is active at any given time, and oblivious protocols that are aware of nothing beyond the machine they control. The main focus of this paper is on a well-motivated middle-ground model of resource-aware protocols, which are aware of the set of machines that the system comprises, but unaware of what jobs are active at any given time. Apart from considering budget-balanced protocols, to which previous work was restricted, we augment the design space by also studying the extent to which overcharging can lead to improved performance.
We first show that, in the omnipotent model, overcharging enables us to enforce the optimal outcome as the unique equilibrium, which largely improves over the Theta(log n)-approximation of social welfare that can be obtained by budget-balanced protocols, even in their best equilibrium [32]. We then transition to the resource-aware model and provide price of anarchy (PoA) upper and lower bounds for different classes of cost functions. For concave cost functions, we provide a protocol with PoA of 1 + epsilon for arbitrarily small epsilon > 0. When the cost functions can be both convex and concave we construct an overcharging protocol that yields PoA <= 2; a spectacular improvement over the bounds obtained for budget-balanced protocols, even in the omnipotent model. We complement our positive results with impossibility results for general increasing cost functions. We show that any resource-aware budget-balanced cost-sharing protocol has PoA of Theta(n) in this setting and, even if we use overcharging, no resource-aware protocol can achieve a PoA of o(root n).
Metrics
Details
- Title
- Cost-Sharing Methods for Scheduling Games under Uncertainty
- Creators
- Giorgos Christodoulou - University of LiverpoolVasilis Gkatzelis - Drexel UniversityAlkmini Sgouritsa - University of LiverpoolAssoc Comp Machinery
- Publication Details
- EC'17: PROCEEDINGS OF THE 2017 ACM CONFERENCE ON ECONOMICS AND COMPUTATION, pp 441-458
- Publisher
- Assoc Computing Machinery
- Number of pages
- 18
- Grant note
- CCF-1216073; CCF-1161813; CCF-1408635 / National Science Foundation; National Science Foundation (NSF) EP/M008118/1 / EPSRC; UK Research & Innovation (UKRI); Engineering & Physical Sciences Research Council (EPSRC) LT140046 / Royal Society; Royal Society of London
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000628648900045
- Scopus ID
- 2-s2.0-85025813278
- Other Identifier
- 991019302020804721
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
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Artificial Intelligence
- Computer Science, Theory & Methods
- Economics
- Mathematics, Applied
- Operations Research & Management Science