Resource-Aware Cost-Sharing Methods for Scheduling Games

9^th October 2019, 13:00
Alkmini Sgouritsa
University of Liverpool

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. We provide protocols with dramatically improved price of anarchy compared to the oblivious ones. Apart from considering budget-balanced protocols, to which most of previous work was restricted, we augment the design space by also studying the extent to which overcharging can lead to improved performance.

Joint work with Giorgos Christodoulou and Vasilis Gkatzelis.
Appeared at EC '17.