The price of anarchy in nonatomic consumption-relevance congestion games

We present an extension to nonatomic congestion games (NCG). An NCG models a large number of players depending on a set of resources (e.g., network links) in certain combinations (e.g., paths or multicast trees) called strategies. The rate of consumption Z(eS) specifies how aggressively resource e is consumed when used via strategy S, but it also effects how strongly the resource's latency is experienced by the players. Our extension allows essentially unrelated factors C-eS and R-eS instead of Z(eS). Factor C-eS is the actual rate of consumption, whereas R-eS expresses the amplification of the resource latency of e for players choosing strategy S, or, in other words, the relevance of resource e for strategy S. We call the extended model nonatomic consumption-relevance congestion games (NCRCG). NCRCGs exhibit new phenomena, including multiple Nash equilibria of different social cost andeven from a worst-case point of viewa dependence of the price of anarchy on structural parameters not limited to the class of resource latency functions used. We prove almost tight lower, upper, and bicriteria bounds for the price of anarchy for polynomial latency functions with nonnegative coefficients. We conjecture that the lower bound is the best possible. (c) 2013 Wiley Periodicals, Inc.