Evolutionary Networking Games

Contents 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

7.1.1 Biology and Economics Meet Computer Science: The Birth of Evolving Games and Biologically Inspired Evolutionary Game Dynamics . . . . . . . . . . . . . . . . . 135

7.2 Evolving Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 7.2.1 Homogeneous Population. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

7.2.1.1 Equilibrium and Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 7.2.2 Price of Anarchy in Population Games. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.2.3 Heterogeneous Population . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.2.4 Evolutionary Game Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.2.5 Delayed Evolutionary Game Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

7.2.5.1 Examples of Delayed Game Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.2.5.2 ESS Can Be Unstable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.2.5.3 Stability Bounds for ESS under Regular DDE . . . . . . . . . . . . . . . . . . . . . . . . . . 143

7.3 Intrusion Detection in Ad Hoc Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 7.3.1 Description of Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

7.3.1.1 Pure Actions of the Incomplete Information Game . . . . . . . . . . . . . . . . . . . . . 145 7.3.1.2 Payoffs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

7.4 Interference Control in Distributed ALOHA Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

7.5 Resource Selection with an Unknown Number of Users . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 7.5.1 Convergence to Equilibrium and Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

7.6 Open Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 7.6.1 Dynamics of Multiobjective Evolutionary Networking Games. . . . . . . . . . . . . . . . . . . 154 7.6.2 Evolutionary Network Formation Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 7.6.3 Multilevel Hierarchical Evolutionary Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 7.6.4 Mean Field Game Dynamics for Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

7.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

We develop a framework for analyzing evolving games in large populations of players, in which each player interacts with the other random number of players, that is, the number of players that a given player can meet is unknown and varies in time. The actions of each player in an interaction together determine the instantaneous costs for all involved players. They also determine the rate of transition to use pure actions. We present various classes of evolutionary game-theoretic models (evolutionary stability and evolutionary game dynamics) and apply them to networking problems including intrusion detection, resource selection, and interference control in wireless networks. We will discuss some challenges and limitations in the application of game theory to the analysis of wireless communications and networks.