--- _id: '244' abstract: - lang: eng text: 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. author: - first_name: Burkhard full_name: Monien, Burkhard last_name: Monien - first_name: Marios full_name: Mavronicolas, Marios last_name: Mavronicolas citation: ama: 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 apa: 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 bibtex: '@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} }' chicago: '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.' ieee: 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. mla: 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. short: B. Monien, M. Mavronicolas, Information Processing Letters 115 (2015) 927–931. date_created: 2017-10-17T12:41:39Z date_updated: 2022-01-06T06:56:20Z ddc: - '040' doi: 10.1016/j.ipl.2015.07.012 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T09:48:16Z date_updated: 2018-03-21T09:48:16Z file_id: '1494' file_name: 244-Mavronic_Monien2015_01.pdf file_size: 239984 relation: main_file success: 1 file_date_updated: 2018-03-21T09:48:16Z has_accepted_license: '1' intvolume: ' 115' issue: '12' language: - iso: eng main_file_link: - url: http://www.sciencedirect.com/journal/information-processing-letters/vol/115/issue/12 page: 927-931 project: - _id: '1' name: SFB 901 - _id: '7' name: SFB 901 - Subprojekt A3 - _id: '2' name: SFB 901 - Project Area A publication: Information Processing Letters publisher: Elsevier status: public title: The complexity of pure equilibria in mix-weighted congestion games on parallel links type: journal_article user_id: '42447' volume: 115 year: '2015' ...