The complexity of pure equilibria in mix-weighted congestion games on parallel links
Monien, Burkhard
Mavronicolas, Marios
ddc:040
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.
Elsevier
2015
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://ris.uni-paderborn.de/record/244
Monien B, Mavronicolas M. The complexity of pure equilibria in mix-weighted congestion games on parallel links. <i>Information Processing Letters</i>. 2015;115(12):927-931. doi:<a href="https://doi.org/10.1016/j.ipl.2015.07.012">10.1016/j.ipl.2015.07.012</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.ipl.2015.07.012
info:eu-repo/semantics/closedAccess