ABSTRACT
CONTENTS 2.1 Definition of a Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2.2 Example of a Basic Game: Prisoner’s Dilemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 2.3 Best Response Dynamic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 2.4 Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 2.5 Other Games Similar to Prisoner’s Dilemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 2.6 Examples of Other Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
2.6.1 Coordination Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 2.6.2 Battle of the Sexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
2.7 A Game of Matching Pennies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 2.8 Strategy Domination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
2.8.1 Example: Competition between Firms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 2.9 Cournot Competition: Strategic Substitutes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 2.10 Regulation versus Competition: Tragedy of Commons . . . . . . . . . . . . . . . . . . . . . . . . . 92 2.11 Mixed Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
2.11.1 Intuition for Mixed-Strategy Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 2.12 Battle of the Sexes: Another Example of Mixed-Strategy Equilibrium . . . . . . . . . . . . . . 97
2.12.1 Mixed-Strategy Equilibrium through Best Responses . . . . . . . . . . . . . . . . . . . . 98 2.13 Formal Definition of a Mixed-Strategy Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . 100 2.14 Mixed-Strategy Nash Equilibrium for Two-Player Zero-Sum Games . . . . . . . . . . . . . . 101 2.15 Minimax Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 2.16 Solving Zero-Sum Games through Linear Programming . . . . . . . . . . . . . . . . . . . . . . 104
2.16.1 Zero-Sum Game Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 2.17 Bayesian Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 2.18 Another Example: Yield versus Fight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 2.19 Cournot Duopoly with Cost Uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 2.20 Bayesian Game with Multiplayer Uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 2.21 Bayesian Nash Equilibrium: Formal Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 2.22 Mixed Bayesian Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 2.23 Bayesian Mixed-Strategy Nash Equilibrium: Formal Definition . . . . . . . . . . . . . . . . . 117 2.24 Introduction to Fundamentals of Probability Distributions . . . . . . . . . . . . . . . . . . . . . 117 2.25 Bayesian Auction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 2.26 Second-Price Bayesian Auction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 2.27 Revenue in First-Price Auction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 2.28 Expected Revenue in Second-Price Bayesian Auction . . . . . . . . . . . . . . . . . . . . . . . . 122 2.29 Example: All-Pay Auction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 2.30 Vickrey-Clarke-Groves Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 2.31 Illustration of the Optimality of the VCG Procedure . . . . . . . . . . . . . . . . . . . . . . . . . 127
2.32 VCG Example: Second-Price Auction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 2.33 Games on Networks: Potential Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 2.34 Network Routing Potential Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 2.35 Dynamic Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 2.36 Extensive-Form Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
2.36.1 Game Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 2.36.2 Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
2.36.2.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 2.36.3 Actions and Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
2.36.3.1 Behavior Strategies and Mixed Strategies . . . . . . . . . . . . . . . . . . . . . 142 2.36.4 Nash Equilibrium of Extensive-Form Games . . . . . . . . . . . . . . . . . . . . . . . . . 143
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
ABSTRACT The focus of this chapter is game theory and its various applications. This chapter is divided into two parts dealing with static games and dynamic games. The first part of the chapter begins with a mathematical formulation of games followed by the description of a strategic-form game. This chapter subsequently describes the various solutions and related concepts, including domination, rationalizability, Nash equilibrium, and their refinements. An elaborate description of the concept and procedure to evaluate a mixed-strategy Nash equilibrium follows, in which the players use randomized strategies or randomly mix various possible actions. This also includes a discussion of a special form of games termed as zero-sum games. The next topic deals with games in which the players are not certain of the characterization of the game, which leads to the formulation of Bayesian games. This gives rise to the novel paradigm of Bayesian-Nash equilibria to analyze the behavior in such games. An offshoot of the Bayesian game framework is auction theory, which is subsequently developed separately. An analysis of various auction forms such as first-price, secondprice, and all-pay auctions is described next, along with the central principle of revenue equivalence that governs such auctions. The next section deals with the Vickrey-Clarke-Groves (VCG) procedure for a competitive resource allocation and its application in the design of pricing mechanisms. This chapter then proceeds to cover a different form of games, termed as potential games, which arise in the context of networks. An application of this is illustrated in the context of road planning and traffic congestion, followed by elaboration of the key properties of such games. The second part of the chapter deals with dynamic games. This part begins with the description and mathematical formulation of an extensive-form game. The description emphasizes the graph-theoretic representation of extensive-form games followed by the technique of backward induction and the concept of a sub-game-perfect equilibrium.
