2017/01/26 by Pieter Kleer, Guido Schäfer, Kleer, Pieter +1
Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1701.07614
openalex publication_date 2017/01/26 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Congestion games constitute an important class of non-cooperative games which\nwas introduced by Rosenthal in 1973. In recent years, several extensions of\nthese games were proposed to incorporate aspects that are not captured by the\nstandard model. Examples of such extensions include the incorporation of risk\nsensitive players, the modeling of altruistic player behavior and the\nimposition of taxes on the resources. These extensions were studied intensively\nwith the goal to obtain a precise understanding of the inefficiency of\nequilibria of these games. In this paper, we introduce a new model of\ncongestion games that captures these extensions (and additional ones) in a\nunifying way. The key idea here is to parameterize both the perceived cost of\neach player and the social cost function of the system designer. Intuitively,\neach player perceives the load induced by the other players by an extent of\n\ρ, while the system designer estimates that each player perceives the load\nof all others by an extent of \σ. The above mentioned extensions reduce\nto special cases of our model by choosing the parameters \ρ and \σ\naccordingly. As in most related works, we concentrate on congestion games with\naffine latency functions here. Despite the fact that we deal with a more\ngeneral class of congestion games, we manage to derive tight bounds on the\nprice of anarchy and the price of stability for a large range of pa- rameters.\nOur bounds provide a complete picture of the inefficiency of equilibria for\nthese perception-parameterized congestion games. As a result, we obtain tight\nbounds on the price of anarchy and the price of stability for the above\nmentioned extensions. Our results also reveal how one should "design" the cost\nfunctions of the players in order to reduce the price of anar- chy.\n