Abstract:
|
We study Network Max-Congestion Games (NMC games,
for short), a class of network games where each player tries to minimize
the most congested edge along the path he uses as strategy. We focus
our study on the complexity of computing a pure Nash equilibria in
weighted NMC 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 semi-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 indeed a PLS-
complete problem. |