Journal article
Resource-Aware Cost-Sharing Methods for Scheduling Games
OPERATIONS RESEARCH, v 72(1)
Jan 2024
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
We study the performance of cost-sharing methods in a selfish scheduling setting where a group of users schedule their jobs on machines with load-dependent cost functions, aiming to minimize their own cost. Anticipating this user behavior, the system designer chooses a decentralized protocol that defines how the cost generated on each machine is to be shared among its users, and the performance of the protocol is evaluated over the Nash equilibria of the induced game. Previous work on selfish scheduling has focused on two extreme models: omniscient 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. We focus on a well-motivated middle-ground model of resource-aware protocols, which are aware of the set of machines in the system, but unaware of what jobs are active at any given time. Furthermore, we study the extent to which appropriately overcharging the users can lead to improved performance. We provide protocols that achieve small constant price of anarchy bounds when the cost functions are convex or concave, and we complement our positive results with impossibility results for general cost functions.
Metrics
3 Record Views
Details
- Title
- Resource-Aware Cost-Sharing Methods for Scheduling Games
- Publication Details
- OPERATIONS RESEARCH, v 72(1)
- Publisher
- INFORMS; CATONSVILLE
- Grant note
- This work was supported by the Royal Society [Grant LT140046] , the Engineering and Physical Sciences Research Council [Grant EP/M008118/1] , the National Science Foundation [Grants CCF-1161813, CCF-1216073, and CCF-1408635; CAREER Award CCF-2047907] , and the Lise Meitner Award Fellowship.
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Drexel University
- Web of Science ID
- WOS:000971743500001
- Scopus ID
- 2-s2.0-85184852858
- Other Identifier
- 991021861201104721
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
- Management
- Operations Research & Management Science