The complexity of pure equilibria in mix-weighted congestion games on parallel links

B. Monien, M. Mavronicolas, Information Processing Letters 115 (2015) 927–931.

Download
Restricted 244-Mavronic_Monien2015_01.pdf 239.98 KB
Journal Article | English
Author
Monien, Burkhard; Mavronicolas, Marios
Abstract
We revisit the simple class of weighted congestion games on parallel links [10], where each player has a non-negative weight and her cost on the link she chooses is the sum of the weights of all players choosing the link. We extend this class to mix-weighted congestion games on parallel links, where weights may as well be negative. For the resulting simple class, we study the complexity of deciding the existence of a pure equilibrium, where no player could unilaterally improve her cost by switching to another link.We show that even for a singlenegative weight, this decision problem is strongly NP-complete when the number of links is part of the input; the problem is NP-complete already for two links. When the number of links is a fixed constant, we show, through a pseudopolynomial, dynamic programming algorithm, that the problem is not strongly NP-complete unless P = NP; the algorithm works for any number of negative weights.
Publishing Year
Journal Title
Information Processing Letters
Volume
115
Issue
12
Page
927-931
LibreCat-ID
244

Cite this

Monien B, Mavronicolas M. The complexity of pure equilibria in mix-weighted congestion games on parallel links. Information Processing Letters. 2015;115(12):927-931. doi:10.1016/j.ipl.2015.07.012
Monien, B., & Mavronicolas, M. (2015). The complexity of pure equilibria in mix-weighted congestion games on parallel links. Information Processing Letters, 115(12), 927–931. https://doi.org/10.1016/j.ipl.2015.07.012
@article{Monien_Mavronicolas_2015, title={The complexity of pure equilibria in mix-weighted congestion games on parallel links}, volume={115}, DOI={10.1016/j.ipl.2015.07.012}, number={12}, journal={Information Processing Letters}, publisher={Elsevier}, author={Monien, Burkhard and Mavronicolas, Marios}, year={2015}, pages={927–931} }
Monien, Burkhard, and Marios Mavronicolas. “The Complexity of Pure Equilibria in Mix-Weighted Congestion Games on Parallel Links.” Information Processing Letters 115, no. 12 (2015): 927–31. https://doi.org/10.1016/j.ipl.2015.07.012.
B. Monien and M. Mavronicolas, “The complexity of pure equilibria in mix-weighted congestion games on parallel links,” Information Processing Letters, vol. 115, no. 12, pp. 927–931, 2015.
Monien, Burkhard, and Marios Mavronicolas. “The Complexity of Pure Equilibria in Mix-Weighted Congestion Games on Parallel Links.” Information Processing Letters, vol. 115, no. 12, Elsevier, 2015, pp. 927–31, doi:10.1016/j.ipl.2015.07.012.
Main File(s)
File Name
244-Mavronic_Monien2015_01.pdf 239.98 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T09:48:16Z


Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar