Traditional network optimization focuses on a single control objective in a network populated by obedient users and limited dispersion of information. However, most of today's networks are large-scale with lack of access to centralized information, consist of users with diverse requirements, and are subject to dynamic changes. These factors naturally motivate a new distributed control paradigm, where the network infrastructure is kept simple and the network control functions are delegated to individual agents which make their decisions independently ("selfishly"). The interaction of multiple independent decision-makers necessitates the use of game theory, including economic notions related to markets and incentives. This monograph studies game theoretic models of resource allocation among selfish agents in networks. The first part of the monograph introduces fundamental game theoretic topics. Emphasis is given to the analysis of dynamics in game theoretic situations, which is crucial for design and control of networked systems. The second part of the monograph applies the game theoretic tools for the analysis of resource allocation in communication networks. We set up a general model of routing in wireline networks, emphasizing the congestion problems caused by delay and packet loss. In particular, we develop a systematic approach to characterizing the inefficiencies of network equilibria, and highlight the effect of autonomous service providers on network performance. We then turn to examining distributed power control in wireless networks. We show that the resulting Nash equilibria can be efficient if the degree of freedom given to end-users is properly designed. Table of Contents: Static Games and Solution Concepts / Game Theory Dynamics / Wireline Network Games / Wireless Network Games / Future Perspectives
Author(s): Ishai Menache, Asuman Ozdaglar
Series: Synthesis Lectures on Communication Networks
Edition: 1
Publisher: Morgan & Claypool Publishers
Year: 2011
Language: English
Pages: 160
Tags: Библиотека;Компьютерная литература;Разработка игр;
Preface......Page 14
Game Theory Background......Page 18
Strategic Form Games......Page 20
Solution Concepts......Page 22
Dominant and Dominated Strategies......Page 23
Iterated Elimination of Strictly Dominated Strategies......Page 25
Nash Equilibrium......Page 27
Correlated Equilibrium......Page 33
Existence of a Nash Equilibrium......Page 36
Games with Finite Pure Strategy Sets......Page 39
Games with Infinite Pure Strategy Sets......Page 41
Continuous Games......Page 43
Discontinuous Games......Page 46
Uniqueness of a Nash Equilibrium......Page 49
Appendix: Metric Spaces and Probability Measures......Page 52
Appendix: Nonlinear Optimization......Page 54
Extensive Form Games......Page 56
Learning Dynamics in Games – Fictitious Play......Page 62
Convergence of Fictitious Play......Page 63
Non-convergence of Fictitious Play......Page 67
Convergence Proofs......Page 68
Supermodular Games......Page 73
Potential Games......Page 80
Appendix: Lattices......Page 84
Network Games......Page 86
Selfish Routing, Wardrop Equilibrium and Efficiency......Page 88
Routing Model......Page 90
Wardrop Equilibrium......Page 91
Inefficiency of the Equilibrium......Page 92
Background and Motivation......Page 95
The Model......Page 96
Efficiency of Partially Optimal Routing......Page 98
Extensions......Page 104
Pricing and Efficiency with Congestion Externalities......Page 105
Model......Page 107
Oligopoly Pricing and Equilibrium......Page 108
Efficiency Analysis......Page 109
Extensions......Page 110
Concluding Remarks......Page 113
Wireless Network Games......Page 116
Noncooperative Transmission Scheduling in Collision Channels......Page 119
The Model and Preliminaries......Page 120
Equilibrium Analysis......Page 126
Achievable Channel Capacity......Page 130
Best-Response Dynamics......Page 131
Discussion......Page 133
Noncooperative Power Control in Collision Channels......Page 134
The Model......Page 135
Equilibrium Analysis......Page 137
Best-Response Dynamics and Convergence to the Power Efficient Equilibrium......Page 142
Equilibrium (In)Efficiency and Braess-Like Paradoxes......Page 143
Discussion......Page 145
Related Work and Extensions......Page 146
Future Directions......Page 148
Future Perspectives......Page 150
Bibliography......Page 152
Authors' Biographies......Page 160
