  To what extent does the structure of the players' strategy space influence
the efficiency of decentralized solutions in congestion games? In this work, we
investigate whether better performance are possible when restricting to load
balancing games in which players can only choose among single resources. We
consider three different solutions concepts, namely, approximate pure Nash
equilibria, approximate one-round walks generated by selfish players aiming at
minimizing their personal cost and approximate one-round walks generated by
cooperative players aiming at minimizing the marginal increase in the sum of
the players' personal costs. The last two concepts can be interpreted as
solutions of greedy online algorithms for the related resource selection
problem. We show that, under fairly general latency functions on the resources,
better bounds cannot be achieved if players are either weighted or asymmetric.
On the positive side, we prove that, under mild assumptions on the latency
functions, improvements on the performance of approximate pure Nash equilibria
are possible for load balancing games with weighted and symmetric players in
the case of identical resources. We also design lower bounds on the performance
of one-round walks in load balancing games with unweighted players and
identical resources.
