Authors: Richard Cole, Vasilis Gkatzelis, and Vahab Mirrokni


Title: Coordination Mechanisms for Weighted Sum of Completion Times

 Abstract: 
We study policies aiming to minimize the weighted sum of completion
times of jobs in the context of coordination mechanisms for selfish scheduling
problems. Our goal is to design local policies that achieve a good price
of anarchy in the resulting equilibria for unrelated machine scheduling. In
short, we present the first constant-factor-approximate coordination mechanisms
for this model.
First, we present a generalization of the ShortestFirst policy for weighted
jobs, called SmithRule; we prove that it achieves an approximation ratio
of 4 and we show that any set of non-preemptive ordering policies can result
in equilibria with approximation ratio at least 3 even for unweighted
jobs. Then, we present ProportionalSharing, a preemptive strongly local
policy that beats this lower bound of 3; we show that this policy achieves
an approximation ratio of 2.61 for the weighted sum of completion times
and that the EqualSharing policy achieves an approximation ratio of 2.5
for the (unweighted) sum of completion times. Furthermore, we show that
ProportionalSharing induces potential games (in which best-response dynamics
converge to pure Nash equilibria).
All of our upper bounds are for the robust price of anarchy, defined by
Roughgarden [36], so they naturally extend to mixed Nash equilibria, correlated
equilibria, and regret minimization dynamics. Finally, we prove that our
price of anarchy bound for ProportionalSharing can be used to design a new
combinatorial constant-factor approximation algorithm minimizing weighted
completion time for unrelated machine scheduling.