---
_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'
...