Utilitarian Link Assignment
  Petra Berenbrink, Leslie Ann Goldberg,
  Paul Goldberg, and Russell Martin

Abstract:

We study a resource allocation problem introduced
by Koutsoupias and Papadimitriou. The scenario is modelled
as a multiple-player game in which each player selects one
of a finite number of known resources. The cost to the player
is the total weight of all players who choose that resource,
multiplied by the ``delay'' of that resource. Recent papers
have studied the Nash equilibria and social optima of this
game in terms of the $L_\infty$ cost metric, in which the
social cost is taken to be the maximum cost to any player.
We study the $L_1$ variant of this game, in which the
social cost is taken to be the sum of the costs to the
individual players, rather than the maximum of these costs.
We bound the ratio between the social optimum and the cost
of Nash equilibria in special cases where the resource delays
are identical, or when each player's weight contribution is
the same.  We also study the variation in cost between
different Nash equilibria in these cases.