The price of anarchy of affine congestion games with similar strategies

摘要

Affine congestion games are a well-studied model for selfish behavior in distributed systems, such as transportation and communication networks. Seminal influential papers in Algorithmic Game Theory have bounded the worst-case inefficiency of Nash equilibria, termed as price of anarchy, in several variants of these games. In this work, we investigate to what extent these bounds depend on the similarities among the players' strategies. Our notion of similarity is modeled by assuming that, given a parameter theta >= 1, the costs of any two strategies available to a same player, when evaluated in absence of congestion, are within a factor theta one from the other. It turns out that, for the non-atomic case, better bounds can always be obtained for any finite value of theta. For the atomic case, instead, theta < 3/2 and theta < 2 are necessary and sufficient conditions to obtain better bounds in games played on general graph topologies and on parallel link graphs, respectively. It is worth noticing that small values of theta model the behavioral attitude of players who are partially oblivious to congestion and are not willing to significantly deviate from what is their best strategy in absence of congestion. (C) 2019 Elsevier B.V. All rights reserved.