Mathematical Game Theory and Applications

VLADIMIR MAZALOV, Research Director of the Institute of Applied Mathematical Research, Karelia Research Center of Russian Academy of Sciences, Russia

• Preface xiIntroduction xiii1 Strategic-Form Two-Player Games 1Introduction 11.1 The Cournot Duopoly 21.2 Continuous Improvement Procedure 31.3 The Bertrand Duopoly 41.4 The Hotelling Duopoly 51.5 The Hotelling Duopoly in 2D Space 61.6 The Stackelberg Duopoly 81.7 Convex Games 91.8 Some Examples of Bimatrix Games 121.9 Randomization 131.10 Games 2 ×2 161.11 Games 2 × n and m ×2 181.12 The Hotelling Duopoly in 2D Space with Non-Uniform Distribution of Buyers 201.13 Location Problem in 2D Space 25Exercises 262 Zero-Sum Games 28Introduction 282.1 Minimax and Maximin 292.2 Randomization 312.3 Games with Discontinuous Payoff Functions 342.4 Convex-Concave and Linear-Convex Games 372.5 Convex Games 392.6 Arbitration Procedures 422.7 Two-Point Discrete Arbitration Procedures 482.8 Three-Point Discrete Arbitration Procedures with Interval Constraint 532.9 General Discrete Arbitration Procedures 56Exercises 623 Non-Cooperative Strategic-Form n-Player Games 64Introduction 643.1 Convex Games. The Cournot Oligopoly 653.2 Polymatrix Games 663.3 Potential Games 693.4 Congestion Games 733.5 Player-Specific Congestion Games 753.6 Auctions 783.7 Wars of Attrition 823.8 Duels, Truels, and Other Shooting Accuracy Contests 853.9 Prediction Games 88Exercises 934 Extensive-Form n-Player Games 96Introduction 964.1 Equilibrium in Games with Complete Information 974.2 Indifferent Equilibrium 994.3 Games with Incomplete Information 1014.4 Total Memory Games 105Exercises 1085 Parlor Games and Sport Games 111Introduction 1115.1 Poker. A Game-Theoretic Model 1125.2 The Poker Model with Variable Bets 1185.3 Preference. A Game-Theoretic Model 1295.4 The Preference Model with Cards Play 1365.5 Twenty-One. A Game-Theoretic Model 1455.6 Soccer. A Game-Theoretic Model of Resource Allocation 147Exercises 1526 Negotiation Models 155Introduction 1556.1 Models of Resource Allocation 1556.2 Negotiations of Time and Place of a Meeting 1666.3 Stochastic Design in the Cake Cutting Problem 1716.4 Models of Tournaments 1826.5 Bargaining Models with Incomplete Information 1906.6 Reputation in Negotiations 221Exercises 2287 Optimal Stopping Games 230Introduction 2307.1 Optimal Stopping Game: The Case of Two Observations 2317.2 Optimal Stopping Game: The Case of Independent Observations 2347.3 The Game ΓN(G) Under N ≥ 3 2377.4 Optimal Stopping Game with Random Walks 2417.5 Best Choice Games 2507.6 Best Choice Game with Stopping Before Opponent 2547.7 Best Choice Game with Rank Criterion. Lottery 2597.8 Best Choice Game with Rank Criterion. Voting 2647.9 Best Mutual Choice Game 269Exercises 2768 Cooperative Games 278Introduction 2788.1 Equivalence of Cooperative Games 2788.2 Imputations and Core 2818.3 Balanced Games 2858.4 The -Value of a Cooperative Game 2868.5 Nucleolus 2898.6 The Bankruptcy Game 2938.7 The Shapley Vector 2988.8 Voting Games. The Shapley–Shubik Power Index and the Banzhaf Power Index 3028.9 The Mutual Influence of Players. The Hoede–Bakker Index 309Exercises 3129 Network Games 314Introduction 3149.1 The KP-Model of Optimal Routing with Indivisible Traffic. The Price of Anarchy 3159.2 Pure Strategy Equilibrium. Braess’s Paradox 3169.3 Completely Mixed Equilibrium in the Optimal Routing Problem with Inhomogeneous Users and Homogeneous Channels 3199.4 Completely Mixed Equilibrium in the Optimal Routing Problem with Homogeneous Users and Inhomogeneous Channels 3209.5 Completely Mixed Equilibrium: The General Case 3229.6 The Price of Anarchy in the Model with Parallel Channels and Indivisible Traffic 3249.7 The Price of Anarchy in the Optimal Routing Model with Linear Social Costs and Indivisible Traffic for an Arbitrary Network 3289.8 The Mixed Price of Anarchy in the Optimal Routing Model with Linear Social Costs and Indivisible Traffic for an Arbitrary Network 3329.9 The Price of Anarchy in the Optimal Routing Model with Maximal Social Costs and Indivisible Traffic for an Arbitrary Network 3359.10 The Wardrop Optimal Routing Model with Divisible Traffic 3379.11 The Optimal Routing Model with Parallel Channels. The Pigou Model. Braess’s Paradox 3409.12 Potential in the Optimal Routing Model with Indivisible Traffic for an Arbitrary Network 3419.13 Social Costs in the Optimal Routing Model with Divisible Traffic for Convex Latency Functions 3439.14 The Price of Anarchy in the Optimal Routing Model with Divisible Traffic for Linear Latency Functions 3449.15 Potential in the Wardrop Model with Parallel Channels for Player-Specific Linear Latency Functions 3469.16 The Price of Anarchy in an Arbitrary Network for Player-Specific Linear Latency Functions 349Exercises 35110 Dynamic Games 352Introduction 35210.1 Discrete-Time Dynamic Games 35310.2 Some Solution Methods for Optimal Control Problems with One Player 35810.3 The Maximum Principle and the Bellman Equation in Discrete- and Continuous-Time Games of N Players 36810.4 The Linear-Quadratic Problem on Finite and Infinite Horizons 37510.5 Dynamic Games in Bioresource Management Problems. The Case of Finite Horizon 37810.6 Dynamic Games in Bioresource Management Problems. The Case of Infinite Horizon 38310.7 Time-Consistent Imputation Distribution Procedure 388Exercises 402References 405Index 411