Advances in Dynamic Games : Games of Conflict, Evolutionary Games, Economic Games, and Games Involving Common Interest

This contributed volume collects talks originally given at the 18th International Symposium on Dynamic Games and Applications, held in Grenoble, France from July 9-12, 2018. Chapters present state-of-the-art research in the field of dynamic games and are written by leading experts in this active area. Featuring a broad overview of recent advances as well as a wide range of applications, this book is organized into four sections: games of conflict, evolutionary games, economic games, and games involving common interest. Within these sections, specific topics covered include:* Pursuit-evasion games * Partnership formation games * Replicator dynamics * Load balancing congestion games * Equilibrium coalition structures __Advances in Dynamic Games__ will be of particular interest to researchers and doctoral students studying game theory. Preface 6 Nikolai Botkin Memorial 9 Contents 11 Games of Conflict 13 Quick Construction of Dangerous Disturbances in Conflict Control Problems 14 1 Introduction 14 2 Problem Formulation 15 3 Construction of Repulsive Tubes 16 4 Numerical Implementation of Repulsive Feedback Disturbances 20 5 Application: Simple Example 22 6 Application: Nonlinear Model of Take-Off 24 6.1 Model Equations 25 6.2 Relaxed Nonlinear Model 26 6.3 Linearization of the Relaxed Model 27 6.4 Linear Conflict Control Problem 27 6.5 Generation of Disturbances 28 7 Application: Linear Model of Aircraft Lateral Dynamics 30 7.1 Model Equations 30 7.2 Construction of the Disturbance 31 7.3 Validation Using Optimal Control Theory 32 7.4 Simulation Results 33 8 Conclusion 35 References 35 Isaacs' Two-on-One Pursuit-Evasion Game 36 1 Introduction 36 2 The Geometric Method 38 2.1 Apollonius Circle 38 2.2 Isaacs' Geometric Solution 39 3 Geometric Solution in Reduced State Space 42 3.1 Game of Kind in Reduced State Space 44 3.2 Game of Degree in Reduced State Space 49 4 Isaacs' Method 53 5 Conclusion and Extensions 65 References 66 A Normal Form Game Model of Search and Pursuit 67 1 Introduction 67 2 Literature Review 68 3 Single Period Game with General Search Times 69 3.1 An Example 70 3.2 The Game with ti Constant 71 3.3 The Game with ti=i, pi Decreasing, k=n Odd 71 3.4 An Example with k=10, n=5 73 3.5 Illustrative Examples 73 3.6 Game with Two Types of Locations 75 4 Game Where Capture Probabilities Are Unknown But Learned 77 4.1 Normal Form of the Two-Period Learning Game 78 4.2 An Example with l = 1/3 and h= 2/3 80 5 Summary 81 References 82 Computation of Robust Capture Zones Using Interval-Based Viability Techniques in Presence of State Uncertainties 84 1 Introduction 84 2 Problem Statement and Preliminaries 85 2.1 Engagement Model 85 2.2 Robust ε-Capture Zone 87 2.3 Linearized Model 87 2.4 Problem Scalarization 88 2.5 Robust Capture Zone for Linear System 89 2.6 Connections Between Optimal Capture Zones and Robust Capture Zones 91 3 Interval Algorithm Approximation 92 3.1 Viability Kernel and Capture Basin 92 3.2 Capture Basin Enclosure 93 3.3 Interval Arithmetics 94 3.4 Contractor Programming 95 3.5 Interval-Based Backward Reachable Set Computation 96 3.6 Numerical Results 99 4 Conclusions 102 References 108 Convergence of Numerical Method for Time-Optimal Differential Games with Lifeline 110 1 Introduction 110 2 Problem Formulation 112 3 Numerical Scheme 114 3.1 Discrete Scheme 114 3.2 Viscosity Solution of Boundary Problem for HJE 119 4 Numerical Scheme Convergence 120 5 Connection Between Value Functions of Problems with and Without Lifeline 125 6 Numerical Examples 128 6.1 Homicidal Chauffeur Game 129 6.2 Dubins' Car 133 6.3 Material Point with Shifted Target 135 7 Conclusion 137 References 137 Evolutionary Games 140 A Partnership Formation Game with Common Preferences and Scramble Competition 141 1 Introduction 141 2 The Model 143 3 Some General Results 148 4 Games with Three Types of Player 150 5 Examples 154 5.1 Random Mating—No Switching Times 155 5.2 One Switching Time 155 5.3 Two Switching Times 158 5.4 Three Switching Times 160 5.5 Four Switching Times 162 5.6 Multiple Equilibria 163 6 Conclusion 164 References 166 The Replicator Dynamics for Games in Metric Spaces: Finite Approximations 168 1 Introduction 168 2 Technical Preliminaries 170 2.1 Spaces of Signed Measures 170 2.2 The Kantorovich–Rubinstein Metric 170 2.3 Product Spaces 171 2.4 Differentiability 172 3 The Replicator Dynamics and Evolutionary Games 172 3.1 Asymmetric Evolutionary Games 172 3.2 The Symmetric Case 174 4 Discrete Approximations to the Replicator Dynamics 175 4.1 Games with Strategies in an Real Interval 175 4.2 Games with Strategies in Compact Metric Spaces 176 5 An Approximation Theorem in the Strong Form 177 6 An Approximation Theorem in the Weak Form 180 7 Examples 183 7.1 A Linear-Quadratic Model: Symmetric Case 183 7.2 Graduated Risk Game 184 8 Comments 186 References 190 Eco-evolutionary Spatial Dynamics of Nonlinear Social Dilemmas 192 1 Introduction 192 2 Model and Results 193 2.1 Nonlinear Public Goods Game 193 2.2 Spatial Nonlinear Public Goods Games 195 3 Discussion 200 Appendix 202 References 203 Applications to Economics 206 Heuristic Optimization for Multi-Depot Vehicle Routing Problem in ATM Network Model 207 1 Introduction 207 2 Multi-Depot Location Routing Problem (MDLRP) 210 3 Solving Methods of the Multi-Depot Location Routing Problem (MDLRP) 214 4 Multi-Depot Vehicle Routing Problem (MDVRP) 218 5 Solution Methods for MDVRP 218 5.1 Genetic Algorithm 1 219 5.2 Genetic Algorithm 2 221 6 Numerical Simulations 221 7 Conclusion and Discussion 225 References 233 Load Balancing Congestion Games and Their Asymptotic Behavior 235 1 Introduction 235 2 Model and Notations 236 3 Atomic Non-splittable (F3 Framework) Case and Its Non-atomic Limit (F1 Framework) 239 3.1 Non-uniqueness of the Equilibrium 239 3.2 The Potential and Asymptotic Uniqueness 241 3.3 Efficiency 243 4 Atomic Semi-splittable Case and Its Splittable Limit (F4 Framework) 245 4.1 Efficiency 246 4.2 Case of N = 1 247 4.3 Case a-2b 0) 248 4.5 Case a-2b>0 249 4.6 Limit Case: Perfectly Splittable Sessions 250 5 Conclusions 251 References 257 Non-deceptive Counterfeiting and Consumer Welfare: A Differential Game Approach 258 1 Introduction 258 2 Model 262 3 No Counterfeiting 266 4 Counterfeiting 269 4.1 The Duopoly Equilibrium 269 4.2 The First-Stage Optimal Solution 272 5 Comparison 277 5.1 Profit Comparison 277 5.2 Consumer Welfare Comparison 280 6 Concluding Remarks 282 References 299 Games where Players have Common Interests 302 Equilibrium Coalition Structures of Differential Games in Partition Function Form 303 1 Introduction 303 2 General Approach 304 2.1 Differential Games 304 2.2 Partition Function 305 2.3 Equilibrium Coalition Structure 307 3 Cake Eating 309 4 Example 315 5 Conclusion 318 References 319 A Model for Partial Kantian Cooperation 320 1 Introduction 320 1.1 Contribution 321 1.2 Related Notions 322 2 The r-Kant-Nash Equilibrium 323 2.1 The Model 323 2.2 Special Cases and Relation to Other Concepts 325 3 Finite Number of Individual and Social Types 327 4 Examples of r-Kant-Nash Equilibrium 330 4.1 A Vaccination Game 330 4.2 A Static Fishing Game with Two Types of Players 332 4.3 A Dynamic Resource Game 333 4.4 An Opinion Game 336 4.5 A Fishing Game with Overlapping Virtual Groups 337 4.6 Electric Vehicle Charging with Uniform Pricing 339 5 Infinite Number of Types 342 5.1 Reformulation as Optimal Control Problems 342 5.2 Equilibrium in a Quadratic Game 344 6 Conclusion and Future Directions 347 7 Appendix 347 References 348 Front Matter ....Pages i-xii Front Matter ....Pages 1-1 Quick Construction of Dangerous Disturbances in Conflict Control Problems (Kirill Martynov, Nikolai D. Botkin, Varvara L. Turova, Johannes Diepolder)....Pages 3-24 Isaacs’ Two-on-One Pursuit-Evasion Game (Meir Pachter)....Pages 25-55 A Normal Form Game Model of Search and Pursuit (Steve Alpern, Viciano Lee)....Pages 57-73 Computation of Robust Capture Zones Using Interval-Based Viability Techniques in Presence of State Uncertainties (Stéphane Le Ménec, Vladimir Turetsky)....Pages 75-100 Convergence of Numerical Method for Time-Optimal Differential Games with Lifeline (Nataly V. Munts, Sergey S. Kumkov)....Pages 101-130 Front Matter ....Pages 131-131 A Partnership Formation Game with Common Preferences and Scramble Competition (David M. Ramsey)....Pages 133-159 The Replicator Dynamics for Games in Metric Spaces: Finite Approximations (Saul Mendoza-Palacios, Onésimo Hernández-Lerma)....Pages 161-184 Eco-evolutionary Spatial Dynamics of Nonlinear Social Dilemmas (Chaitanya S. Gokhale, Hye Jin Park)....Pages 185-198 Front Matter ....Pages 199-199 Heuristic Optimization for Multi-Depot Vehicle Routing Problem in ATM Network Model (Valeria Platonova, Elena Gubar, Saku Kukkonen)....Pages 201-228 Load Balancing Congestion Games and Their Asymptotic Behavior (Eitan Altman, Corinne Touati, Nisha Mishra, Hisao Kameda)....Pages 229-251 Non-deceptive Counterfeiting and Consumer Welfare: A Differential Game Approach (Bertrand Crettez, Naila Hayek, Georges Zaccour)....Pages 253-296 Front Matter ....Pages 297-297 Equilibrium Coalition Structures of Differential Games in Partition Function Form (Simon Hoof)....Pages 299-315 A Model for Partial Kantian Cooperation (Ioannis Kordonis)....Pages 317-346