The Complexity of Welfare Maximization in Congestion Games
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 c...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
John Wiley & Sons, Inc.
2013
|
| Online Access: | http://hdl.handle.net/1721.1/77914 https://orcid.org/0000-0002-9595-459X |
| _version_ | 1826193871850176512 |
|---|---|
| author | Meyers, Carol A. Schulz, Andreas S |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Meyers, Carol A. Schulz, Andreas S |
| author_sort | Meyers, Carol A. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T09:46:38Z |
| format | Article |
| id | mit-1721.1/77914 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:46:38Z |
| publishDate | 2013 |
| publisher | John Wiley & Sons, Inc. |
| record_format | dspace |
| spelling | mit-1721.1/779142023-03-01T02:14:38Z The Complexity of Welfare Maximization in Congestion Games Meyers, Carol A. Schulz, Andreas S Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Schulz, Andreas S. Schulz, Andreas S. 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. United States. Dept. of Energy (Grant Number: DE-AC52-07NA27344) Lawrence Livermore National Laboratory (Grant Number: LLNL-JRNL-410585) United States. Office of Naval Research (Grant Number: N000141110056) 2013-03-15T18:03:35Z 2013-03-15T18:03:35Z 2012-03 2010-02 Article http://purl.org/eprint/type/JournalArticle 1097-0037 0028-3045 http://hdl.handle.net/1721.1/77914 Meyers, Carol A., and Andreas S. Schulz. “The Complexity of Welfare Maximization in Congestion Games.” Networks 59.2 (2012): 252–260. CrossRef. Web. https://orcid.org/0000-0002-9595-459X en_US http://dx.doi.org/10.1002/net.20439 Networks Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf John Wiley & Sons, Inc. Prof. Schulz via Alex Caracuzzo |
| spellingShingle | Meyers, Carol A. Schulz, Andreas S The Complexity of Welfare Maximization in Congestion Games |
| title | The Complexity of Welfare Maximization in Congestion Games |
| title_full | The Complexity of Welfare Maximization in Congestion Games |
| title_fullStr | The Complexity of Welfare Maximization in Congestion Games |
| title_full_unstemmed | The Complexity of Welfare Maximization in Congestion Games |
| title_short | The Complexity of Welfare Maximization in Congestion Games |
| title_sort | complexity of welfare maximization in congestion games |
| url | http://hdl.handle.net/1721.1/77914 https://orcid.org/0000-0002-9595-459X |
| work_keys_str_mv | AT meyerscarola thecomplexityofwelfaremaximizationincongestiongames AT schulzandreass thecomplexityofwelfaremaximizationincongestiongames AT meyerscarola complexityofwelfaremaximizationincongestiongames AT schulzandreass complexityofwelfaremaximizationincongestiongames |