کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427232 | 686474 | 2015 | 5 صفحه PDF | دانلود رایگان |
• We introduce a new model of congestion games on parallel links where players have negative weights.
• We prove that deciding the existence of a pure equilibrium in this model is strongly NP-complete.
• We present a pseudopolynomial algorithm for the case of two links.
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 NPNP-complete when the number of links is part of the input; the problem is NPNP-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 NPNP-complete unless P=NPP=NP; the algorithm works for any number of negative weights.
Journal: Information Processing Letters - Volume 115, Issue 12, December 2015, Pages 927–931