Cost-Sharing Methods for Scheduling Games under Uncertainty

8^th November 2017, 13:00
Paul Spirakis
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. We will discuss a 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.

Joint work with Alkmini Sgouritsa and Vasilis Gkatzelis (Drexel University).

Appeared in EC 2017.