|
Título:
|
The Complexity of pure Nash equilibria in weighted Max-Congestion Games
|
|
Autor/a:
|
Álvarez Faura, M. del Carme; Francès Medina, Guillem
|
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors; Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. CAP - Grup de Computació d'Altes Prestacions |
|
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. |
|
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
-Nash Equilibria
-PLS
-Complexity
-Maximum Congestion |
|
Derechos:
|
|
|
Tipo de documento:
|
Artículo - Versión publicada
Informe |
|
Editor:
|
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
|
|
Compartir:
|
|
