game theory chapter 1 2 3 4 5 6 parts 1 and 2

Chapter 1 The Single-Person Decision Problem

I magine yourself in the morning, all dressed up and ready to have breakfast. You might be lucky enough to live in a nice undergraduate dormitory with access to an impressive cafeteria, in which case you have a large variety of foods from which to choose. Or you might be a less-fortunate graduate student, whose studio cupboard offers the dull options of two half-empty cereal boxes. Either way you face the same problem: what should you have for breakfast? This trivial yet ubiquitous situation is an example of a decision problem.Decision problems confront us daily, as individuals and as groups (such as firms and other organizations). Examples include a division manager in a firm choosing whether or not to embark on a new research and development project; a congressional representative deciding whether or not to vote for a bill; an undergraduate student deciding on a major; a baseball pitcher contemplating what kind of pitch to deliver; or a lost group of hikers confused about which direction to take. The list is endless. Some decision problems are trivial, such as choosing your breakfast. For example, if Apple Jacks and Bran Flakes are the only cereals in your cupboard, and if you hate Bran Flakes (they belong to your roommate), then your decision is obvious: eat the Apple Jacks. In contrast, a manager’s choice of whether or not to embark on a risky research and development project or a lawmaker’s decision on a bill are more complex decision problems. This chapter develops a language that will be useful in laying out rigorous foundations to support many of the ideas underlying strategic interaction in games. The language will be formal, having the benefit of being able to represent a host of different problems and provide a set of tools that will lend structure to the way in which we think about decision problems. The formalities are a vehicle that will help make ideas precise and clear, yet in no way will they overwhelm our ability and intent to keep the more practical aspect of our problems at the forefront of the analysis. In developing this formal language, we will be forced to specify a set of assumptions about the behavior of decision makers or players. These assumptions will, at times, seem both acceptable and innocuous. At other times, however, the assumptions will be almost offensive in that they will require a significant leap of faith. Still, as the analysis unfolds, we will see the conclusions that derive from the assumptions 3 4 . Chapter 1 The Single-Person Decision Problem that we make, and we will come to appreciate how sensitive the conclusions are to these assumptions. As with any theoretical framework, the value of our conclusions will be only as good as the sensibility of our assumptions. There is a famous saying in computer science—“garbage in, garbage out”—meaning that if invalid data are entered into a system, the resulting output will also be invalid. Although originally applied to computer software, this statement holds true more generally, being applicable, for example, to decision-making theories like the one developed herein. Hence we will at times challenge our assumptions with facts and question the validity of our analysis. Nevertheless we will argue in favor of the framework developed here as a useful benchmark.

1.3 Summary . A simple decision problem has three components: actions, outcomes, and preferences over outcomes. . A rational player has complete and transitive preferences over outcomes and hence can always identify a best alternative from among his possible actions. These preferences can be represented by a payoff (or profit) function over outcomes and the corresponding payoffs over actions. . A rational player chooses the action that gives him the highest possible payoff from the possible set of actions at his disposal. Hence by maximizing his payoff function over his set of alternative actions, a rational player will choose his optimal decision. . A decision tree is a simple graphic representation for decision problems.

Chapter 2 Introducing Uncertainty and Time

Introducing Uncertainty and Time Now that we have a coherent and precise language to describe decision problems, we move on to be more realistic about the complexity of many such problems. The cereal example was fine to illustrate a simple decision problem and to get used to our formal language, but it is certainly not very interesting. Consider a division manager who has to decide on whether a research and development (R&D) project is worthwhile. What will happen if he does not go ahead with it? Maybe over time his main product will become obsolete and outdated, and the profitability of his division will no longer be sustainable. Then again, maybe profits will still continue to flow in. What happens of he does go ahead with the project? It may lead to vast improvements in the product line and offer the prospect of sustained growth. Or perhaps the research will fail and no new products will emerge, leaving behind only a hefty bill for the expensive R&D endeavor. In other words, both actions have uncertainty over what outcomes will materialize, implying that the choice of a best action is not as obvious as in the cereal example. How should the player approach this more complex problem? As you can imagine, using language like “maybe this will happen, or maybe that will happen” is not very useful for a rational player who is trying to put some structure on his decision problem. We must introduce a method through which the player can compare uncertain consequences in a meaningful way. For this approach, we will use the concept of stochastic (random) outcomes and probabilities, and we will describe a framework within which payoffs are defined over random outcomes.

2.7 Summary . When prospects are uncertain, a rational decision maker needs to put structure on the problem in the form of probability distributions over outcomes that we call lotteries. . Whether the acts of Nature evolve over time or whether they are chosen once and for all, a rational player cares only about the distribution over final outcomes. Hence any series of compound lotteries can be compressed to its equivalent simple lottery. . When evaluating lotteries, we use the expected payoff criterion. Hence every lottery is evaluated by the expected payoff it offers the player. . Unlike certain outcomes in which only the order of preferences matters, when random outcomes are evaluated with expected payoffs, the magnitude of payoffs matters as well. The difference in payoff values between outcomes will also be related to a player’s risk preferences. . Rational players will always choose the action that offers them the highest expected payoff. . When decisions need to be made over time, a rational player will solve his problem “backwards” so that early decisions take into account later decisions. . Payoffs that are received in future periods will often be discounted in earlier periods to reflect impatience, costs of capital, or uncertainty over whether future periods will be relevant.

PART II STATIC GAMES OF COMPLETE INFORMATION

Chapter 3 preliminaries

The language and tools of analysis that we have developed so far seem to be ideal to depict and analyze a wide variety of decision problems that a rational individual, or an entity with well-defined objectives, could face. The essence of our framework argues that any decision problem is best understood when we set it up in terms of the three elements of which it is made up: the possible actions, the deterministic or probabilistic relationship between actions and outcomes, and the decision maker’s preferences over the possible outcomes. We proceeded to argue that a decision maker will choose those actions that are in his best interest. This framework offers many attractive features: it is precise, well structured, and generally applicable, and most importantly it lends itself to systematic and consistent analysis. It does, however, suffer from one drawback: the world of a decision problem was described as a world in which the outcomes that determine our well-being are consequences of our own actions and some randomness that is beyond our control. Let’s consider for a moment a decision problem that you may be facing now if you are using this text as part of a university course, which you are taking for a grade. It is, I believe, safe to assume that your objective is some combination of learning the material and obtaining a good grade in the course, with higher grades being preferred over lower ones. This objective determines your preferences over outcomes, which are the set of all possible combinations of how much you learned and what grade you obtained. Your set of possible actions is deciding how hard to study, which includes such elements as deciding how many lectures to attend, how carefully to read the text, how hard to work on your problem sets, and how much time to spend preparing for the exams. Hence you are now facing a well-defined decision problem. To complete the description of your decision problem, I have yet to explain how the outcome of your success is affected by the amount of work you choose to put into your course work. Clearly as an experienced student you know that the harder you study the more you learn, and you are also more likely to succeed on the exams. There is some uncertainty over how hard a given exam will be; that may depend on many random events, such as how you feel on the day of the exam and what mood the professor was in when the exam was written. Still something seems to be missing. Indeed you must surely know that grades are often set on a curve, so that your grade relies on your success on the exam as an absolute measure of not only how much you got right but also how much the other students in the class got right. In other words, if you’re having a bad day on an exam, your only hope is that everyone else in your class is having a worse day! 43 44 . Chapter 3 Preliminaries The purpose of this example is to point out that our framework for a decision problem will be inadequate if your outcomes, and as a consequence your well-being, will depend on the choices made by other decision makers. Perhaps we can just treat the other players in this decision problem as part of the randomness of nature: maybe they’ll work hard, maybe not, maybe they’ll have a bad day, maybe not, and so on. This, however, would not be part of a rational framework, for it would not be sensible for you to treat your fellow players as mere random “noise.” Just as you are trying to optimize your decisions, so are they. Each player is trying to guess what others are doing, and how to act accordingly. In essence, you and your peers are engaged in a strategic environment in which you have to think hard about what other players are doing in order to decide what is best for you—knowing that the other players are going through the same difficulties. We therefore need to modify our decision problem framework to help us describe and analyze strategic situations in which players who interact understand their environment, how their actions affect the outcomes that they and their counterparts will face, and how these outcomes are assessed by the other players. It is useful, therefore, to start with the simplest set of situations possible, and the simplest language that will capture these strategic situations, which we refer to as games. We will start with static games of complete information, which are the most fundamental games, or environments, in which such strategic considerations can be analyzed. A static game is similar to the very simple decision problems in which a player makes a once-and-for-all decision, after which outcomes are realized. In a static game, a set of players independently choose once-and-for-all actions, which in turn cause the realization of an outcome. Thus a static game can be thought of as having two distinct steps: Step 1: Each player simultaneously and independently chooses an action. By simultaneously and independently, we mean a condition broader and more accommodating than players all choosing their actions at the exact same moment. We mean that players must take their actions without observing what actions their counterparts take and without interacting with other players to coordinate their actions. For example, imagine that you have to study for your midterm exam two days before the midterm because of an athletic event in which you have to participate on the day before the exam. Assume further that I plan on studying the day before the midterm, which will be after your studying effort has ended. If I don’t know how much you studied, then by choosing my action after you I have no informational advantage over you; it is as if we are making our choices simultaneously and independently of each other. This idea will receive considerable attention as we proceed. Step 2: Conditional on the players’ choices of actions, payoffs are distributed to each player. That is, once the players have all made their choices, these choices will result in a particular outcome, or probabilistic distribution over outcomes. The players have preferences over the outcomes of the game given by some payoff function over outcomes. For example, if we are playing rock-paper-scissors and I draw paper while you simultaneously draw scissors, then the outcome is that you win and I lose, and the payoffs are what winning and losing mean in our context—something tangible, like $0.10, or just the intrinsic joy of winning versus the suffering of losing. Chapter 3 Preliminaries . 45 Steps 1 and 2 settle what we mean by static. What do we mean by complete information? The loose meaning is that all players understand the environment they are in—that is, the game they are playing—in every way. This definition is very much related to our assumptions about rational choice in Section 1.2. Recall that when we had a single-person decision problem we argued that the player must know four things: (1) all his possible actions, A; (2) all the possible outcomes, X; (3) exactly how each action affects which outcome will materialize; and (4) what his preferences are over outcomes. How should this be adjusted to fit a game in which many such players interact? Games of Complete Information A game of complete information requires that the following four components be common knowledge among all the players of the game: 1. all the possible actions of all the players, 2. all the possible outcomes, 3. how each combination of actions of all players affects which outcome will materialize, and 4. the preferences of each and every player over outcomes. This is by no means an innocuous set of assumptions. In fact, as we will discuss later, they are quite demanding and perhaps almost impossible to justify completely for many real-world “games.” However, as with rational choice theory, we use these assumptions because they provide structure and, perhaps surprisingly, describe and predict many phenomena quite well. You may notice that a new term snuck into the description of games of complete information: common knowledge. This is a term that we often use loosely: “it’s common knowledge that he gives hard exams” or “it’s common knowledge that green vegetables are good for your health.” It turns out that what exactly common knowledge means is by no means common knowledge. To make it clear, Definition 3.1 An event E is common knowledge if (1) everyone knows E, (2) everyone knows that everyone knows E, and so on ad infinitum. On the face of it, this may seem like an innocuous assumption, and indeed it may be in some cases. For example, if you and I are both walking in the rain together, then it is safe to assume that the event “it is raining” is common knowledge between us. However, if we are both sitting in class and the professor says “tomorrow there is an exam,” then the event “there is an exam tomorrow” may not be common knowledge. Despite me knowing that I heard him say it, perhaps you were daydreaming at the time, implying that I cannot be sure that you heard the statement as well. Thus requiring common knowledge is not as innocuous as it may seem, but without this assumption it is quite impossible to analyze games within a structured framework. This difficulty arises because we are seeking to depict a situation in which players can engage in strategic reasoning. That is, I want to predict how you will make your choice, given my belief that you understand the game. Your understanding incorporates your belief about my understanding, and so on. Hence common knowledge will assist us dramatically in our ability to perform this kind of reasoning.

3.4 Summary . A normal-form game includes a finite set of players, a set of pure strategies for each player, and a payoff function for each player that assigns a payoff value to each combination of chosen strategies. . Any two-player finite game can be represented by a matrix. Each row represents one of player 1’s strategies, each column represents one of player 2’s strategies, and each cell in the matrix contains the payoffs for both players. . A solution concept that proposes predictions of how games will be played should be widely applicable, should restrict the set of possible outcomes to a small set of reasonable outcomes, and should not be too sensitive to small changes in the game. . Outcomes should be evaluated using the Pareto criterion, yet self-enforcing behavior will dictate the set of reasonable outcomes.

Chapter 4 Rationality and Common Knowledge

Rationality and Common Knowledge I n this chapter we study the implications of imposing the assumptions of rationality as well as common knowledge of rationality. We derive and explore some solution concepts that result from these two assumptions and seek to understand the restrictions that each of the two assumptions imposes on the way in which players will play games.

4.4 Summary . Rational players will never play a dominated strategy and will always play a dominant strategy when it exists. . When players share common knowledge of rationality, the only strategies that are sensible are those that survive IESDS. . Rational players will always play a best response to their beliefs. Hence any strategy for which there are no beliefs that justify its choice will never be chosen. . Outcomes that survive IESDS, rationalizability, or strict dominance need not be Pareto optimal, implying that players may not be able to achieve desirable outcomes if they are left to their own devices.

chapter 5 Pinning Down Beliefs: Nash Equilibrium

Pinning Down Beliefs: Nash Equilibrium We have seen three solution concepts that offer some insights into predicting the behavior of rational players in strategic (normal-form) games. The first, strict dominance, relied only on rationality, and in some cases, like the Prisoner’s Dilemma, it predicted a unique outcome, as it would in any game for which a dominant strategy equilibrium exists. However, it often fails to exist. The two sister concepts of IESDS and rationalizability relied on more than rationality by requiring common knowledge of rationality. In return a solution existed for every game, and for some games there was a unique prediction. Moreover, whenever there is a strict dominant equilibrium, it also uniquely survives IESDS and rationalizability. Even for some games for which the strict-dominance solution did not apply, like the Cournot duopoly, we obtained a unique prediction from IESDS and rationalizability. However, when we consider a game like the Battle of the Sexes, none of these concepts had any bite. Dominant strategy equilibrium did not apply, and both IESDS and rationalizability could not restrict the set of reasonable behavior:

For example, we cannot rule out the possibility that Alex goes to the opera while Chris goes to the football game, because Alex may behave optimally given his belief that Chris is going to the opera, and Chris may behave optimally given his belief that Alex is going to the football game. Yet there is something troubling about this outcome. If we think of this pair of actions not only as actions, but as a system of actions and beliefs, then there is something of a dissonance: indeed the players are playing best responses to their beliefs, but their beliefs are wrong! In this chapter we make a rather heroic leap that ties together beliefs and actions and results in the most central and best-known solution concept in game theory. As already mentioned, for dominant strategy equilibrium we required only that players be rational, while for IESDS and rationalizability we required common knowledge- Now we introduce a much more demanding concept, that of the Nash equilibrium, first put forth by John Nash (1950a), who received the Nobel Prize in Economics for this achievement.

5.3 Summary . Any strategy profile for which players are playing mutual best responses is a Nash equilibrium, making this equilibrium concept self-enforcing. . If a profile of strategies is the unique survivor of IESDS or is the unique rationalizable profile of strategies then it is a Nash equilibrium. . If a profile of strategies is a Nash equilibrium then it must survive IESDS and it must be rationalizable, but not every strategy that survives IESDS or that is rationalizable is a Nash equilibrium. . Nash equilibrium analysis can shed light on phenomena such as the tragedy of the commons and the nature of competition in markets and in politics.

Chapter 6 mixed strategies

Mixed Strategies I n the previous chapters we restricted players to using pure strategies and we postponed discussing the option that a player may choose to randomize between several of his pure strategies. You may wonder why anyone would wish to randomize between actions. This turns out to be an important type of behavior to consider, with interesting implications and interpretations. In fact, as we will now see, there are many games for which there will be no equilibrium predictions if we do not consider the players’ ability to choose stochastic strategies. Consider the following classic zero-sum game called Matching Pennies.1 Players 1 and 2 each put a penny on a table simultaneously. If the two pennies come up the same side (heads or tails) then player 1 gets both; otherwise player 2 does. We can represent this in the following matrix:

The matrix also includes the best-response choices of each player using the method we introduced in Section 5.1.1 to find pure-strategy Nash equilibria. As you can see, this method does not work: Given a belief that player 1 has about player 2’s choice, he always wants to match it. In contrast, given a belief that player 2 has about player 1’s choice, he would like to choose the opposite orientation for his penny. Does this mean that a Nash equilibrium fails to exist? We will soon see that a Nash equilibrium will indeed exist if we allow players to choose random strategies, and there will be an intuitive appeal to the proposed equilibrium. Matching Pennies is not the only simple game that fails to have a pure-strategy Nash equilibrium. Recall the child’s game rock-paper-scissors, in which rock beats 1. A zero-sum game is one in which the gains of one player are the losses of another, hence their payoffs always sum to zero. The class of zero-sum games was the main subject of analysis before Nash introduced his solution concept in the 1950s. These games have some very nice mathematical properties and were a central object of analysis in von Neumann and Morgenstern’s (1944) seminal book. and a similar (symmetric) list would be the best-response correspondence of player 2. Examining the two best-response correspondences immediately implies that there is no pure-strategy equilibrium, just like in the Matching Pennies game. The reason is that, starting with any pair of pure strategies, at least one player is not playing a best response and will want to change his strategy in response.

6.5 Summary . Allowing for mixed strategies enriches both what players can choose and what they can believe about the choices of other players. . In games for which players have opposing interests, like the Matching Pennies game, there will be no pure-strategy equilibrium but a mixed-strategy equilibrium will exist. . Allowing for mixed strategies enhances the power of IESDS and of rationalizability. . Nash proved that for finite games there will always be at least one Nash equilibrium.