Resource-Aware Cost-Sharing Methods for Scheduling Games

George Christodoulou (), Vasilis Gkatzelis () and Alkmini Sgouritsa ()
Additional contact information
George Christodoulou: School of Informatics, Aristotle University of Thessaloniki, 541 24 Thessaloniki, Greece
Vasilis Gkatzelis: Department of Computer Science, Drexel University, Philadelphia, Pennsylvania 19104
Alkmini Sgouritsa: Athens University of Economics and Business, Athina 104 34, Greece

Operations Research, 2024, vol. 72, issue 1, 167-184

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.

Keywords: Market Analytics and Revenue Management; cost-sharing; price of anarchy; resource-aware protocols (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.2434 (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:inm:oropre:v:72:y:2024:i:1:p:167-184

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().