Game Theory

Lecture Notes By Y. Narahari

Department of Computer Science and Automation Indian Institute of Science Bangalore, India February 2008

Chapter 1: Introduction to Game Theory

Note: This is a only a draft version, so there could be aws. If you nd any errors, please do send email to hari@csa.iisc.ernet.in. A more thorough version would be available soon in this space.

According to Myerson [1], game theory may be dened as the study of mathematical models of conict and cooperation between rational, intelligent decision makers. Game theory provides general mathematical techniques for analyzing situations in which two or more individuals (called players or agents) make decisions that inuence one anothers welfare. More appropriate phrases to describe game theory are: Conict Analysis Interactive Decision Theory According to Osborne and Rubinstein [2], a game is a description of strategic interaction that occurs among decision-making entities. A game can be described by four elements according to Mascollel, Whinston, and Green [3]: 1. Players (also called agents): an individual or a group of individuals making a decision 2. Rules specify who moves when what can they do what do they know when they move 3. Outcomes: What happens when each player plays in a particular way? 4. Preferences: What are the players preferences over the possible outcomes.

Example 1: Matching Pennies (1) Players: {1,2}

(2) Rules: Each player simultaneously puts down a coin, heads up or tails up (3) Outcomes: {(H,H), (H,T), (T,H), (T,T)} (4) Preferences: If the two coins match, player 1 pays Rs. 100 to player 2; otherwise player 2 pays Rs. 100 to player 1. This game is called the Matching Pennies game.

Example 2: Tick-Tack-Toe (1) Players {X, O} (2) Rules There is a board that consists of 9 squares in 3 rows and 3 columns Players take turns putting their marks (either X or O) into an unmarked square. Player X moves rst The players observe all the choices made by the players so far. (3) Outcomes: win , loss , or draw The rst player to have 3 marks in a horizontal row or a vertical column or along the diagonal wins and the other one loses If no one succeeds even after all 9 squares are marked, it is a draw. (4) Preferences The player who wins will receive a certain amount of money from the player who loses No payments are made if it is a draw. Figure 1 shows a sequence of moves in a tick-tack-toe game.

Important Assumptions and Issues in Game Theory

Utility Theory Utility theory enables the preferences of the players to expressed in terms of payos in some utility scale. Utility theory is the science of assigning numbers to outcomes in a way that reects a players preferences. Utility theory is one of the landmark contributions of von Neumann and Morgenstern. They stated and proved in [4], a crucial theorem called the expected utility maximization theorem . This theorem shows for any rational decision maker that there must exist some way of assigning utility numbers to dierent outcomes in a way that the decision maker would always choose the option 2

O X

O X O

X X

O X O

X X

O X O O

X wins X X X O O loses X O O

Figure 1: A sequence of moves in Tick-Tack-Toe

that maximizes his expected utility. This theorem holds under fairly weak assumptions about how a rational decision maker should behave. For example, one of the key assumptions is the sure-thing or the substitution axiom. This axiom informally means the following: If a decision maker prefers option 1 over option 2 when event A occurs and he prefers option 1 over option 2 when event A does not occur, then he should prefer option 1 over option 2 even before learning whether event A will occur or not. Using the above assumption and certain technical regularity conditions, von Neumann and Morgenstern showed that there exists some utility scale such that the decision maker always prefers the options that give him the highest expected value. Rationality The players are assumed to be rational . A decision maker is said to be rational if the agent makes decisions consistently in pursuit of his own objectives. It is assumed that each players objective is to maximize the expected value of his own payo measured in some utility scale. This is the selsh part of rationality. The above notion of rationality (maximization of expected utility payo) is attributed to Bernoulli (1738) and von Neumann and Morgenstern (1944) [4]. It is important to note that maximizing expected utility payo is not necessarily the same as maximizing expected monetary payo. For example, a certain amount of money may be of signicant utility to a person desperately in need of the money. The same amount of money may be of insignicant utility to a person who does not need it because he is already rich. In general

utility and monetary payo are non-linearly related. Specically, it depends on the nature of the agent: risk-loving or risk-averse or risk-neutral. When there are two or more decision makers, it would be the case that the rational solution to each individuals decision problem depends on the others individual problems and vice-versa. None of the problems may be solvable without understanding the solutions of the other problems. When such rational decision makers interact, their decision problems must be analyzed together, like a system of simultaneous equations. Game theory precisely deals with such analysis. It is to be noted that selshness or self-interest is an important implication of rationality. Intelligence The players are assumed to be intelligent. This assumption means that each player in the game knows everything about the game that a game theorist knows and the player can make any inferences about the game that a game theorist can make. In particular, an intelligent player is strategic , that is, fully takes into account his knowledge or expectation of behavior of other agents in guring out what his best response strategy should be. Each player has enough computational resources to do any required computations for determining his best response strategy. Justication for Rationality and Intelligence Assumptions Myerson provides a very convincing explanation to show that the assumptions of rationality and intelligence are reasonable. According to him, the assumption that all individuals are rational and intelligent may not exactly be satised in a typical real-world situation. However, any theory that is not consistent with the assumptions or rationality and intelligence is fallible for the following reason. If a theory makes the prediction that some individuals will be systematically fooled or misled into making mistakes, then such a theory will tend to lose validity when individuals learn through mistakes to better understand the situations. On the other hand, a theory based on rationality and intelligence assumptions is credible and will stand the test of time due to its consistency. Common Knowledge This is an important implication of intelligence . Aumann (1976) dened common knowledge as follows: A fact is common knowledge among the players if every player knows it, every player knows that every player knows it, and so on. That is, every statement of the form ( every player knows that) k every player knows it is true for k = 0, 1, 2, . . .. The intelligence assumption means that whatever a game theorist may know or understand about the game must be known or understood by the players of the game. Thus the model of the game is also known to the players. Since all the players know the model and they are intelligent, they also know that they all know the model. Thus the model is common knowledge. A players private information is any information that he has that is not common knowledge among all the players.

An Example for Illustrating Common Knowledge This example is a variation of the one presented by Myerson [1]. Assume that there are ve rational and intelligent mothers A, B, C, D, and E and let a, b, c, d, and e be their sons, respectively. The kids go the school every day, escorted by their respective mothers and the mothers get an opportunity everyday to indulge in some conservation. The conversation invariably centers around the performance and behavior of the kids. Everyday when the 5 mothers meet, the conversation protocol is the following. If a mother thinks her boy is good boy , she will praise the virtues of her boy. On the other hand, if a mother knows that her son is not a good boy , then she will cry. All mothers follow this protocol. None of the boys is a good boy but they are smart in that their bad ways are not known to their respective mothers. Whenever a mother nds that the kid of another mother badly behaved, she would immediately report it to all mothers except the kids mother. For example, if A nds b badly behaved, then A would report it to C,D, and E, but not to B. This protocol is also known to all the mothers. Since all the kids are badly behaved, the fact that a kid is not well behaved is common knowledge among all the mothers except the kids own mother. Since each mother does not know that her boy is badly behaved, it turns out that every mother keeps praising her son everyday. One ne day, the class teacher meets all the mothers and makes the following statement: one of the boys is a bad boy. Thus the fact that one of the boys is not a good boy is common knowledge among all the mothers. Thereafter, when the ve mothers meet the next day, all of them praise their respective boys; the same happens on the 2nd day, 3rd , and the 4th day. On the 5th day, however, all the mothers cry together because all of them realize that their respective sons are bad boys. Note that the announcement made by the class teacher is common knowledge and that is what makes all the mothers cry on the fth day. Bounded Rationality Osborne and Rubinstein [2] provide the following explanation regarding the important notion of bounded rationality. Game theory, in its existing form, assumes that all the players are symmetric; that is, they have identical capabilities of perception and computation. It does not model asymmetries in abilities or perceptions of situations. An outstanding example of this is the game of chess. When analyzed using game theory, the game of chess can be solved using an algorithm. This was in fact shown by Zermelo in 1913. Thus chess becomes a trivial game for rational players. Zermelos Result was that the game of chess has a unique equilibrium outcome with the property that a player who follows the suggested strategy can be sure that the outcome will be at least as 5

good as the equilibrium outcome. Only the existence of the equilibrium outcome has been shown and the equilibrium outcome is yet to be computed. A game theoretic model of chess reveals therefore reveals an important fact about the game and suggests that it is not at all interesting for rational players. However, the game theoretic model does not capture the asymmetric abilities of the players which is what makes it interesting. Bounded rationality grapples with the problem of asymmetric abilities of the players and the fact that the players do not have innite computational resources at their disposal.

Classication of Games
Non-cooperative Games and Cooperative Games Non-cooperative games are those in which the possible actions of individual players are the primitives; in cooperative games, joint actions of groups of players are the primitives. John Harsanyi (1966) explained that a game is cooperative if commitments (agreements, promises, threats) are enforceable and that a game becomes non-cooperative if the commitments are not enforceable. Dierent Representational Forms A strategic form game (also called simultaneous move game or normal from game) is a model or a situation where each player chooses his plan of action once and for all and all players exercise their decision simultaneously. An extensive form game species a possible order of events and each player can consider his plan of action whenever a decision has to be made. A coalitional form game or characteristic form game is one where every subset of players of players is represented, by associating a value with each subset of players. This form is appropriate for cooperative games. Perfect Information and Games with Imperfect Information When the players are fully informed about each others moves (each player, before making a move, knows the past moves of all other players as well as his own past moves), the game is said to be of perfect information. Otherwise the game is said to be with imperfect information. Complete Information and Incomplete Information A game with incomplete information is one in which, at the rst point in time when the players can begin to plan their moves, some players already have private information about the game that other players do not know. In a game with complete information, every aspect of the game is common knowledge. Other Categorizations There are many other categories of games, such as dynamic games, repeated games, stochastic games, games with communication, multi-level games (Stackelberg games), dierential games, etc. These will be discussed in due course of time. 6

To Probe Further
The material discussed in this chapter draws upon mainly from three sources, namely the books by Myerson [1], Mascolell, Whinston, and Green [3], and Osborne and Rubinstein [2]. The classic treatise by John von Neumann and Oskar Morgenstern [4], published in 1944, provides a comprehensive foundation for game theory. To this day, even after seven decades of its rst appearance, the book continues to be a valuable reference. The rst chapter of Myersons book [1] presents a detailed treatment of decision theory and utility theory. For an undergraduate level treatment of game theory, we recommend the books by Osborne [5], Stran [6], and Binmore [7]. For a graduate level treatment, we recommend the books by Myerson [1] and Osborne and Rubinstein [2].

References
[1] Roger B. Myerson. Game Theory: Analysis of Conict. Harvard University Press, 1997. [2] Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. Oxford University Press, 1994. [3] Andreu Mas-Collel, Michael D. Whinston, and Jerry R. Green. Micoreconomic Theory. Oxford University Press, 1995. [4] John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944. [5] Martin J. Osborne. An Introduction to Game Theory. The MIT Press, 2003. [6] Philip D. Stran Jr. Game Theory and Strategy. The Mathematical Association of America, 1993. [7] Ken Binmore. Fun and Games : A Text On Game Theory. D. C. Heath & Company, 1992.