Selfish, Local and Online Scheduling via Vector Fitting

We provide a dual fitting technique on a semidefinite program yielding simple proofs of tight bounds for the robust price of anarchy of several congestion and scheduling games under the sum of weighted completion times objective. The same approach also allows to bound the approximation ratio of local search algorithms and the competitive ratio of online algorithms for the scheduling problem R|| w j C j . All of our results are obtained through a simple unified dual fitting argument on the same semidefinite programming relaxation, which can essentially be obtained through the first round of the Lasserre/Sum of Squares hierarchy.

As our main application, we show that the known coordination ratio bounds of respectively 4, (3 + √ 5)/2 ≈ 2.618, and 32/15 ≈ 2.133 for the scheduling game R|| w j C j under the coordination mechanisms Smith's Rule, Proportional Sharing and Rand (STOC 2011) can be extended to congestion games and obtained through this approach. For the natural restriction where the weight of each player is proportional to its processing time on every resource, we show that the last bound can be improved from 2.133 to 2. This improvement can also be made for general instances when considering the price of anarchy of the game, rather than the coordination ratio. As a further application of this technique in a game theoretic setting, we show that it recovers the tight bound of (3 + √ 5)/2 for the price of anarchy of weighted affine congestion games and the Kawaguchi-Kyan bound of (1 + √ 2)/2 for the pure price of anarchy of P || w j C j . Moreover, we show that this approach recovers the known tight approximation ratio of (3 + √ 5)/2 for a natural local search algorithm for R|| w j C j , as well as the best currently known combinatorial approximation algorithm for this problem achieving an approximation ratio of (5 + √ 5)/4 + ε ≈ 1.809 + ε, and provide an almost matching lower bound.

Finally, we show that this technique also extends to online algorithms by analyzing a randomized algorithm for R|| w j C j achieving a competitive ratio of 4 in an online setting where the arrival order of the jobs is adversarial and the ordering on each machine is optimal.