Price of Anarchy of Congestion Games with Player-Specific Constants
We consider a resource allocation game with heterogenous players competing for several limited resources. We model this as a congestion game, where the share of each player is a decreasing function of the number of players choosing the same resource. In particular, we consider player-specific payoffs that depend not only on the shares of resource, but also on playerspecific preference constants.We study the price of anarchy (PoA) for three families of this congestion game: identical, symmetric, and asymmetric games.We characterize the exact PoA in terms of the number of players and resources. By comparing the values of PoA for different games, we show that performance loss increases with the heterogeneity of games (i.e., the identical game has a better PoA in general). From the system design point of view, we identify the worst-case Nash Equilibrium, where all players are competing for a single resource.
Lok Man Law Jianwei Huang Mingyan Liu
Information Engineering Department, Chinese University of Hong Kong Department of Electrical Engineering and Computer Science, University of Michigan
国际会议
南京
英文
1-5
2011-11-09（万方平台首次上网日期，不代表论文的发表时间）