TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2010

COGA 5-Wheel

Page Content

to Navigation

Preprints 2010

Congestion Games with Variable Demands
Citation key Report-017-2010
Author Tobias Harks and Max Klimm
Year 2010
Number 017
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe