Polynomial Time Equilibria in Bottleneck Congestion Games

We consider bottleneck congestion games in an arbitrary graph G where player strategies are flows in G . The player's objective is to select a flow that minimizes the maximum load on any edge, that is, minimize the bottleneck congestion. We consider splittable and unsplittable games with pure strategies. It has been an open problem for many years to determine whether it is possible to compute in polynomial time Nash equilibriums for bottleneck congestion games in arbitrary graphs. For splittable games we provide a polynomial time algorithm to compute a Nash equilibrium which is also a global optimum. The unsplittable game problem is known to be PLS-complete, and so we focus on approximate Nash equilibria where players are approximately stable. For uniform player demands we give an algorithm to compute a O(łog m)-approximate unsplittable equilibrium in polynomial time, where m is the number of edges. For non-uniform player demands we give an algorithm to compute a O(ζ łog(ζ m))-approximate unsplittable equilibrium in polynomial time, where ζ = O(1 + łog (d_max /d_min)) and d_max, d_min are the respective maximum and minimum player demands. To our knowledge, these are the first general results for efficiently computing equilibria of pure bottleneck congestion games in arbitrary graphs, both for the splittable and unsplittable cases.