Congestion Games with Variable Demands

Tobias Harks, Max KlimmMath. Oper. Res 2016 · DOI · OpenReview

TL;DR

This paper introduces and analyzes congestion games where players can adjust their demand for resources, a more realistic model than previous work. The authors provide a complete characterization of cost functions that guarantee the existence of stable equilibria (Nash equilibria) and predictable convergence dynamics, finding that only simple affine or homogeneously exponential cost functions work.

What Problem Does This Paper Address?

Congestion games are a powerful framework for modeling resource allocation where the cost of using a resource increases with the number of users. However, most existing models assume players have a fixed demand. This is unrealistic, as in many real-world scenarios (like traffic or telecommunications), players can adjust their demand based on resource congestion. If resources are too crowded, demand might decrease, and vice-versa. This paper tackles the fundamental question: for what types of cost functions do these "congestion games with variable demands" guarantee stable outcomes (pure Nash equilibria) and predictable convergence of player behavior?

Methods

The authors introduce a formal model for congestion games with variable demands and proportional costs. They then establish crucial connections between these games and existing "weighted congestion games" (which have fixed demands) to derive necessary conditions for cost functions. A key technique involves constructing specific utility functions for players that guide their demand choices within certain ranges, allowing them to analyze the impact of different cost function shapes. They also introduce the concept of "essential generalized ordinal potentials" to prove the existence of Nash equilibria. The paper systematically analyzes different classes of cost functions (affine, exponential, etc.) to determine their consistency properties.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and characterization of cost functions, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Variable Demand is Crucial: The ability for players to adjust their demand significantly alters the game's dynamics and the conditions for stable equilibria, differentiating it from fixed-demand models.
  • Affine and Homogeneously Exponential Costs are Special: Only these two classes of cost functions guarantee the existence of pure Nash equilibria across all possible games with variable demands.
  • Inhomogeneously Exponential Costs are Problematic: These functions, where the exponential growth is not uniform across all resources or players, can lead to games with no stable equilibria or unpredictable behavior.
  • Uniform Cost Model Differences: The paper highlights surprising differences in the uniform cost model (where cost is independent of demand) compared to the proportional cost model. For instance, even simple affine costs don't guarantee Nash equilibria in the uniform cost setting.
  • Potential Functions are Key: The existence of "essential generalized ordinal potentials" is shown to be a powerful tool for proving the existence of Nash equilibria.

Key Results

  • Consistency (PNE Existence): A set of cost functions is consistent for congestion games with variable demands if and only if it contains either only affine functions (c(l) = al + b, a>0, b≥0) or only homogeneously exponential functions (c(l) = ae^(φl), a, φ > 0, with a universal φ).
  • Finite Improvement Property (FIP): A set of cost functions guarantees the FIP (meaning player improvements eventually stop) if and only if it contains only affine functions.
  • Uniform Cost Model: For uniform cost games, consistency is achieved only by homogeneously exponential functions. Affine functions do not guarantee consistency in this model.
  • Inhomogeneously Exponential Functions: The paper proves that these functions never lead to consistent games for either proportional or uniform cost models, as they can be constructed to have improvement cycles.

Limitations and Future Work

The authors acknowledge that their analysis primarily focuses on the cost structure and assumes standard economic assumptions for utility functions. Future work could explore:

  • Combinatorial Properties: Investigating how specific strategy space structures (like singletons or matroid bases) can guarantee Nash equilibria for general cost functions.
  • Feasible Utility Functions: Analyzing equilibrium existence under restricted utility function classes (e.g., linear utilities).
  • Player Symmetry: Studying the impact of player symmetry on equilibria.
  • Price of Anarchy: Characterizing the price of anarchy for affine cost functions, where PNE always exist.
  • Improvement Dynamics: Further investigating the stability and scalability of improvement dynamics, especially in contexts like TCP/IP routing.

Summary updated

BibTeX
@article{harks2016congestion,
  author = {Tobias Harks and Max Klimm},
  title = {{Congestion Games with Variable Demands}},
  journal = {Math. Oper. Res.},
  year = {2016},
  doi = {10.1287/moor.2015.0726},
}
Figure