Congestion Games with Variable Demands

Tobias Harks and Max Klimm

not available

congestion games, variable demand, Cournot games, game theory, existence of pure Nash equilibria

We initiate the study of congestion games with variable demands where the (variable) demand has to be assigned to exactly one subset of resources. Each player's incentive to use higher demands is stimulated by a non-decreasing and concave utility function. The payoff for a player is defined as the difference between the utility of the demand and the associated congestion cost on the used resources. Although this basic class of non-cooperative games captures many elements of real-world applications, it has not been studied, to our knowledge, in the past.

We study the existence of pure Nash equilibria (PNE for short) in congestion games with variable demands subject to the cost functions of the resources. We call a set of cost functions C consistent if every congestion game with variable demands and cost functions in C possesses a PNE. We say that C is FIP-consistent if every such game possesses the alpha-Finite Improvement Property for every alpha > 0. Our main results are structural characterizations of consistency and FIP-consistency for twice continuously differentiable cost functions: 1. If C is consistent then C contains either affine functions or exponential functions. 2. Affine functions are both consistent and FIP-consistent. 3. Homogeneously exponential functions (c(x) = a exp(px) ) are consistent, but not FIP-consistent. 4. Inhomogeneously exponential functions (c(x) = a exp(px) + b, b >= a) are neither consistent nor FIP-consistent. Our results provide an almost complete characterization of consistency of cost functions leaving only a small gap for the case of inhomogeneously exponential functions c(x) = a exp(px) + b with b < a. The gained insights reveal structural differences to congestion games with fixed demands (weighted congestion games) where in the latter even inhomogeneously exponential functions are FIP-consistent.

Finally, we study consistency and FIP-consistency of cost functions in a slightly different class of games, where every player experiences the same cost on a resource (uniform cost model). We prove that homogeneously exponential functions are consistent. Most surprisingly, these games need not possess a PNE, if costs are affine.

Download as [PDF]