The complexity of pure equilibria in mix-weighted congestion games on parallel links
Ημερομηνία
2015Συγγραφέας
Mavronicolas, MariosMonien, Burkhard
Source
Information Processing LettersVolume
115Issue
12Pages
927-931Google Scholar check
Keyword(s):
Metadata
Εμφάνιση πλήρους εγγραφήςΕπιτομή
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 single negative 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. © 2015 Elsevier B.V. Allrightsreserved.