The complexity of pure nash equilibria in max-congestion games (2008).

Content Provider	CiteSeerX
Author	Medina, Guillem Frances
Abstract	We study Network Max-Congestion Games (NMC games, for short), a class of network games where each player tries to minimize themost congested edge along the path he uses as strategy. We focus our study on the complexity of computing a pure Nash equilibria in this kind of games. We show that, for single-commodity games with non-decreasing delay functions, this problem is in P when either all the paths from the source to the target node are disjoint or all the delay functions are equal. For the general case, we prove that the computation of a PNE belongs to the complexity class PLS through a new technique based on generalized ordinal potential functions and a slightly modified definition of the usual local search neighborhood. We further apply this technique to a different class of games (which we call Pareto-efficient) with restricted cost functions. Finally, we also prove some PLS-hardness results, showing that computing a PNE for Pareto-efficient NMC games is
File Format	PDF
Publisher Date	2008-01-01
Access Restriction	Open
Content Type	Text