Inner Product Spaces for MinSum Coordination Mechanisms.

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. To obtain the approximation bounds, we introduce a new technique that while conceptually simple, seems to be quite powerful.
The method entails mapping strategy vectors into a carefully chosen inner product space; costs are shown to correspond to the norm in this space, and the Nash condition also has a simple description.

We also extract from our approach a factor 2+epsilon approximation algorithm for minimizing the weighted completion time.
While this doesn't match the current best 3/2 factor, unlike other constant factor algorithms it is combinatorial (via best-response dynamics).

(Joint work with Richard Cole, Jose Correa, Vasilis Gkatzelis and Vahab Morrokni).