---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Burkhard
foaf_name: Monien, Burkhard
foaf_surname: Monien
- foaf_Person:
foaf_givenName: Marios
foaf_name: Mavronicolas, Marios
foaf_surname: Mavronicolas
bibo_doi: 10.1016/j.ipl.2015.07.012
bibo_issue: '12'
bibo_volume: 115
dct_date: 2015^xs_gYear
dct_language: eng
dct_publisher: Elsevier@
dct_title: The complexity of pure equilibria in mix-weighted congestion games on
parallel links@
...