Congestion games are a fundamental class of games widely considered and studied in non-cooperative game theory, introduced to model several realistic scenarios in which people share a limited quantity of goods or services. In congestion games there are several selfish players competing for a set of resources, and each resource incurs a certain latency, expressed by a congestion-dependent function, to the players using it. Each player has a certain weight and an available set of strategies, where each strategy is a non-empty subset of resources, and aims at choosing a strategy minimizing her personal cost, which is defined as the sum of the latencies experienced on all the selected resources. The impact of selfish behavior in congestion games generally deteriorates the social welfare, thus reducing their performance. This deterioration is generally estimated by the price of anarchy, a metric that compares the worst Nash equilibrium configuration with the optimal social welfare, so that the larger the price of anarchy for a game, the higher the impact of selfish behavior.
The book derives from the first author's thesis, which won the Best Italian PhD Thesis in Theoretical Computer Science in 2019, awarded by the Italian chapter of the EATCS. The book will be revised for broader audience, and the thesis supervisor is joining as coauthor following the suggestion of the series. The authors will introduce examples for initial definitions with detailed explanations, and expand the scope to the broader results in the area rather than their specific work.
Author(s): Vittorio Bilò, Cosimo Vinci
Series: Monographs in Theoretical Computer Science. An EATCS Series
Publisher: Springer
Year: 2023
Language: English
Pages: 187
City: Cham
Preface
Acknowledgements
Contents
Part I Introduction
Chapter 1 Coping with Selfishness in Congestion Games
The Impact of Selfish Behavior in Congestion Games
How Can We Reduce the Impact of Selfishness?
Scope of the Book
Organization of the Book
Notation
Part II Preliminaries
Chapter 2 The Performance of Congestion Games: A Brief Survey
Preliminary Notation
Atomic Congestion Games
Solution Concepts
Efficiency Metrics
Non-atomic Congestion Games
Load Balancing with Unrelated Machines
Related Work
Chapter 3 Bounding the Inefficiency via the Primal-Dual Method
The Primal-Dual Method
The Effectiveness of the Primal-Dual Method
Concluding Remarks and Related Work
Part III Analysis of Selfish and Greedy Outcomesin Congestion Games
Chapter 4 Congestion and Load Balancing Games with General Latency Functions
Upper Bounds for General Congestion Games
Load Balancing Instances as Tight Lower Bounds
Application to Polynomial Latency Functions
Application to Load Balancing Problems with Unrelated Machines
The Unweighted Case
Concluding Remarks and Related Work
Chapter 5 Uniform Mixed Equilibria
Uniform Mixed Equilibria and Fault-Tolerant Systems
Model and Definitions
Equilibrium Existence in -Uniform Unweighted Games
Performance of -Uniform Unweighted Games
Concluding Remarks and Related Work
Chapter 6 Non-atomic Congestion Games with -Similar Strategies
Model and Definitions
PoA for General Games
The Case of Pigou's Networks
Concluding Remarks and Related Work
Chapter 7 Non-Atomic One-Round Walks
Model and Definitions
Competitive Ratio
Upper Bound
Tight Lower Bound
Application to Polynomial Latency Functions
Concluding Remarks and Related Work
Part IV Taxes and Other Strategies to Cope with Selfish Behavior
Chapter 8 Taxes for Congestion Games: Preliminaries
Tax Functions
Efficiency of Taxation
Mathematical Background on Combinatorics
Related Work
Chapter 9 Dynamic Taxes for Congestion Games with Polynomial Latencies
Primal Formulation and Characteristic Inequalities
Refundable Taxes for Atomic Games
Taxes for Nash Equilibria
Taxes for One-Round Walks
Refundable Taxes for Non-atomic One-Round Walks
Static versus Dynamic Taxes
Non-Refundable Taxes
Concluding Remarks and Related Work
Chapter 10 Dynamic Taxes for Unweighted Congestion Games
Refundable Taxes for Unweighted Games and Pure Nash Equilibria
Refundable Taxes for One-Round Walks
Unweighted Games
Non-atomic Games
Concluding Remarks and Related Work
Chapter 11 Stackelberg Strategies for Affine Unweighted Congestion Games
Stackelberg Strategies: Preliminaries
Price of Anarchy of Largest Latency First
Price of Anarchy of -Cover
Price of Anarchy of Scale
Concluding Remarks and Related Work
Appendix
Other Strategies to Improve the Efficiency of Selfish Outcomes
Coordination Mechanisms
Cost-sharing Protocols
Miscellaneous
Duality Theory in Linear Programming
Smoothness Framework
References
