Price of Anarchy for Congestion and Scheduling Games 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 for the scheduling problem R || ∑ wⱼ Cⱼ. 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ⱼ Cⱼ 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 the technique, 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ⱼ Cⱼ. In addition, this approach recovers the known tight approximation ratio of (3 + √5)/2 ≈ 2.618 for a natural local search algorithm for R || ∑ wⱼ Cⱼ, as well as the best currently known combinatorial approximation algorithm for this problem achieving an approximation ratio of (5 + √5)/4 + ε ≈ 1.809 + ε.