Bi-Weekly Talk: Vipin Vijayalakshmi: Scheduling Games with Machine-Dependent Priority Lists
Wednesday, June 03, 2020, 10:30am
Location: Zoom meeting
Speaker: Vipin Vijayalakshmi
We consider a scheduling game in which jobs try to minimize their completion time by choosing a machine to be processed on. Each machine uses an individual priority list to decide on the order according to which the jobs on the machine are processed. We prove that it is NP-hard to decide if a pure Nash equilibrium exists and characterize four classes of instances in which a pure Nash equilibrium is guaranteed to exist. For each of these classes, we give an algorithm that computes a Nash equilibrium and we bound the inefficiency of Nash equilibria for each of these classes with respect to the makespan of the schedule. In particular, we show that for instances with machines with identical speeds, for which an NE is guaranteed to exist, it is NP-hard to approximate the best Nash equilibrium within a factor of 2- 1/m - c for all c>0. We finally extend our results to a more general model in which jobs pick subsets of machines.