Social Welfare and Price of Anarchy in Preemptive Priority Queues

Jul 1, 2020·
Jonathan Chamberlain
David Starobinski
· 0 min read
Consider an unobservable M|G|1 queue with preemptive-resume scheduling and two priority classes. Customers are strategic and may join the premium class for a fee. We analyze the resulting equilibrium outcomes, equilibrium stability, and social welfare. We find that for service distributions with coefficient of variation greater than 1, there exists a unique and stable mixed equilibrium at low loads. We also establish a tight bound on the price of anarchy, which is 4/3.
Operations Research Letters