Premium
The complexity of welfare maximization in congestion games
Author(s) -
Meyers Carol A.,
Schulz Andreas S.
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20439
Subject(s) - maximization , computer science , time complexity , mathematical optimization , game theory , mathematical economics , mathematics , algorithm
We investigate issues of complexity related to welfare maximization in congestion games. In particular, we provide a full classification of complexity results for the problem of finding a minimum cost solution to a congestion game, under the model of Rosenthal. We consider both network and general congestion games, and we examine several variants of the problem concerning the structure of the game and the properties of its associated cost functions. Many of these problem variants turn out to be NP‐hard, and some are hard to approximate to within any finite factor, unless P = NP . We also identify several versions of the problem that are solvable in polynomial time. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012