TY - GEN

T1 - Tight inefficiency bounds for perception-parameterized affine congestion games

AU - Kleer, Pieter

AU - Schäfer, Guido

PY - 2017/1/1

Y1 - 2017/1/1

N2 - We introduce a new model of congestion games that cap-tures several extensions of the classical congestion game introduced by Rosenthal in 1973. The idea here is to parameterize both the perceived cost of each player and the social cost function of the system designer. Intuitively, each player perceives the load induced by the other players by an extent of ρ ≥ 0, while the system designer estimates that each player perceives the load of all others by an extent of σ ≥ 0. For specific choices of ρ and σ, we obtain extensions such as altruistic player behav-ior, risk sensitive players and the imposition of taxes on the resources. We derive tight bounds on the price of anarchy and the price of stability for a large range of parameters. Our bounds provide a complete picture of the ineﬃciency of equilibria for these games. As a result, we obtain tight bounds on the price of anarchy and the price of stability for the above mentioned extensions. Our results also reveal how one should “design” the cost functions of the players in order to reduce the price of anarchy. Somewhat counterintuitively, if each player cares about all other players to the extent of ρ = 0.625 (instead of 1 in the standard setting) the price of anarchy reduces from 2.5 to 2.155 and this is best possible.

AB - We introduce a new model of congestion games that cap-tures several extensions of the classical congestion game introduced by Rosenthal in 1973. The idea here is to parameterize both the perceived cost of each player and the social cost function of the system designer. Intuitively, each player perceives the load induced by the other players by an extent of ρ ≥ 0, while the system designer estimates that each player perceives the load of all others by an extent of σ ≥ 0. For specific choices of ρ and σ, we obtain extensions such as altruistic player behav-ior, risk sensitive players and the imposition of taxes on the resources. We derive tight bounds on the price of anarchy and the price of stability for a large range of parameters. Our bounds provide a complete picture of the ineﬃciency of equilibria for these games. As a result, we obtain tight bounds on the price of anarchy and the price of stability for the above mentioned extensions. Our results also reveal how one should “design” the cost functions of the players in order to reduce the price of anarchy. Somewhat counterintuitively, if each player cares about all other players to the extent of ρ = 0.625 (instead of 1 in the standard setting) the price of anarchy reduces from 2.5 to 2.155 and this is best possible.

UR - http://www.scopus.com/inward/record.url?scp=85018370831&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85018370831&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-57586-5_32

DO - 10.1007/978-3-319-57586-5_32

M3 - Conference contribution

AN - SCOPUS:85018370831

SN - 9783319575858

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 381

EP - 392

BT - Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings

A2 - Fotakis, Dimitris

A2 - Pagourtzis, Aris

A2 - Paschos, Vangelis Th.

PB - Springer Verlag

T2 - 10th International Conference on Algorithms and Complexity, CIAC 2017

Y2 - 24 May 2017 through 26 May 2017

ER -