Section 1 : Normal Form Games and Strategic Reasoning

ECON 201B, Spring 2013 GSIs: Mich` ele M uller and Takeshi Murooka

These notes build upon previous section material from Matt Leister and Takeshi Murooka. We are grateful for the permission to continue using these resources this semester.

Summary
Today well set up the most basic form of a game called Normal Form Game and discuss why we would want to use such a formal framework to discuss real-life situations. Based on some examples, well then consider some strategic arguments that we expect to govern the players behavior.

1.1
1.1.1

Predicting Behavior in Complex Situations

In 201A, we spent a lot of time trying to formalize an individuals decision process by modeling an underlying preference structure and translating it (under certain conditions) into an utility function. We also derived testable predictions from our theory that were based on the assumption that agents always choose their preferred option from the set of available alternatives or in other words, they maximize their utility. For some abstract experimental settings, we discussed how to t our model to observed choice data, and how to use the tted model to predict behavior in similar yet new situations. At the end of the day, it all remained pretty abstract.

1.1.2

What we might want to do

On the other end of the spectrum, there are real-life situations that we might care to make predictions about, or even alter the current behavior. Maybe you plan to introduce a new product into a market and are concerned about its take-up, you try to understand the possibly perverse impact of a recent policy implementation, or you are allocating funds for an NGO with a social focus.

1-1

Section 1: Normal Form Games and Strategic Reasoning

1-2

In a typical business class, you might be taught to perform a stakeholder analysis, which might be summarized in the following steps:1 1. Identify the stakeholders, that is all the people who are aected by the situation and have some measure of impact. Specically, this might be potential customers, sales representatives, competing business owners, politicians, donors or rural communities somewhere in a remote developing country. 2. Identify the individual tradeos and the available actions that each stakeholder is faced with. A villager might weigh the potential benets of safe water against its purchasing cost and a politician may be caught between bribe-taking and re-election. An NGO might have to decide between a high-impact project with low visibility and one with moderate impact that looks good on fundraising leaets and might secure additional funds, and a business owner might have the choice to sabotage his competition, lower his own sales price or go out of business. 3. Determine the rational behavior for each stakeholder. Consider the individual tradeos and predict the utility-maximizing action of each agent. Depending on the circumstances and the study objective, adapt incentives such as prices, ownership, monitoring or punishment to achieve the desired result. Ideally, this framework helps us formalize our analysis and oers a more structured approach to thinking about a novel situation, with the end goal of returning more realistic predictions.

1.1.3

How the two meet

However, the interaction of real people is rarely as straightforward as the above process seems to suggest. For example, if a competing water vendor sabotages your supply, this aects your own cost of staying in business as well as the villagers tradeo between buying or collecting water. If a politician starts accepting bribes, this sets o a whole slew of incentive distortions for a wide range of market participants. In all of these situations, it is not possible to determine the agents rational behavior individually. Rather, we need to model the (potentially complex) interplay of their actions, their expectations about others behavior, and the exact timing of the individual decisions. This is exactly where game theory starts. It is a precise mathematical framework that species all of the above ingredients. As any mathematical model, it will be very specic about the kinds of assumptions that are made, and it may look very abstract at times. But this is mainly for the sake of clarity. We will see many examples of how we can add realism to the initial models, and somewhere along the way you too might start to develop an appreciation for some of the simplistic game structures. Even if explaining real-life
1 Im far from being an expert in these things, so if Im not doing justice to the business profession, please forgive my ignorance.

Section 1: Normal Form Games and Strategic Reasoning

1-3

situations is the end goal, starting only with the key traits is usually the best (if not the only feasible) way to go.

1.2

Formal Denitions
iN

Denition 1.1. A normal form game is a triplet N, A =

Ai , u = (ui )iN :

N = {1, ..., n} is a nite set of players. Ai is the set of actions (pure strategies) of player i. ui : A R is player is expected utility index over action proles, where A = iN Ai . Players choose their actions simultaneously. The game is common knowledge among the players. A normal form game is nite if A is nite. Regarding the utility indices, remember that as long as the preferences { i }iN are rational (complete and transitive) and continuous, we can express them with utility functions {ui }iN (according to Debreus Theorem from 201A). Another sucient condition for existence of utility functions would be that the actions sets {Ai }iN are countable. Another simplifying assumption that we make here is that the utilities are specied over deterministic outcomes. When we introduce mixed strategies, we fundamentally change the game by introducing strategy sets consisting of lotteries over the pure actions and extending the preferences by using the vNM-Utilities. Denition 1.2. Let X denote the set of probability distributions over a set X . Then we call Ai the set of mixed strategies of player i.2 A mixed strategy prole can be independent if = (1 , ..., n ) A1 ... An or correlated if A. Payos are extended to mixed strategies by taking expectations, ui ( ) = E ui =
aA

(a)ui (a).

Again, we can link this to results from 201A: Such a utility representation exists if and only if the underlying preference relations (over lotteries of outcomes) are independent and satisfy the Archimedean property. It is important to note however that risk-neutrality is not a requirement (more on that later). Example 1.3. One of the most famous examples of a 2 2 normal form game is the Battle of the Sexes :
2 This may stem from deliberate randomization by i, reect j s belief about is play, describe steady state population proportions, or pure strategies in a perturbed game.

Section 1: Normal Form Games and Strategic Reasoning

1-4

Opera Boxing

Opera (1,2) (0,0)

Boxing (0,0) (2,1)

In this game, there are two players Pat and Chris who want to go out together. Pat (the row player) prefers to go boxing, while Chris (the column player) would rather spend the evening at the opera. However, they have no way of communicating their choices before the two events start, and so individually have to decide at which venue theyll show up. In each possible contingency, we follow the convention and note rst the corresponding payo to Pat, then the one to Chris. We note that both would prefer to meet at their preferred event, but would rather suer through an undesired program than to miss out on each others company. For this specic game, write down the normal form game by specifying N, A, u . When it comes to predicting the agents behavior, we use the concept of the best reply : Denition 1.4. Player i is rational if he maximizes his expected payo subject to a belief about others play. We say that a i is a pure best reply to i Ai if ui (a i , i ) ui (ai , i )
is a mixed best reply to Similarly, i i if ui (i , i ) ui (i , i )

ai Ai .

i Ai .

p Since there may be multiple best replies, we denote by Bi (i ) the set of is pure best replies to i and by Bi (i ) the set of is mixed best replies. p Exercise 1.5. Show that Bi (i ) = Bi (i ).

Example 1.6. Consider a situation where to kids simultaneously put down a coin that is facing either heads or tailsthe row player receives a dollar if they match and the column player if they dont: Heads ($1,$0) ($0,$1) Tails ($0,$1) ($1,$0)

Heads Tails

Is this a game? Why (not)? And if not, how could you transform it into a game? Are these games equivalent? What about the predicted behavior?

Section 1: Normal Form Games and Strategic Reasoning

1-5

1.3

Iterated Elimination of Strictly Dominated Strategies

So far, our concept of best responses always assumes that an agent already knows the behavior of his opponents. Now we will start making predictions about the simultaneous behavior of the agents. To begin, we formalize the simple intuition that if a player has two options A and B , where option A is always better than option B , no matter the decisions by other players, then that player would never play B . Moreover, having full knowledge of his payo structure and his rationality, the other players can anticipate this behavior.
p +1 Denition 1.7. Let A0 A. Inductively, let At = Bi ((At i )). i t t AIESDS = t=0 A (= lim A ), t

where IESDS stands for Iterated Elimination of Strictly Dominated Strategies. To be precise, this denition does not convey exactly the same message as the above intuition. In fact, it iteratively rules out actions that are never a best response (to a smaller and smaller set of reasonable beliefs about opponents actions) rather than eliminating actions that are always worse than a specic alternative strategy no matter the opponents actions. Luckily, the two denitions are equivalent thanks to the following theorem proven in class: Theorem 1.8. In a nite normal form game, an action a i is never a best reply to any (possibly correlated) conjecture i of i if and only if ai is strictly dominated to a mixed strategy i . Moreover, when there are multiple strictly dominated strategies, the order of elimination doesnt matter: Theorem 1.9. The outcome of IESDS is independent of the order of elimination of the strictly dominated strategies. Proof. See O&R, section 4.2.2. To become familiar with this concept, we will nish with two exercises: Exercise 1.10. Consider the following game (OR Exercise 56.3): B1 0,7 5,2 7,0 0,0 B2 2,5 3,3 2,5 0,-2 B3 7,0 5,2 0,7 0,0 B4 0,1 0,1 0,1 10,-1

A1 A2 A3 A4

Section 1: Normal Form Games and Strategic Reasoning

1-6

Which actions survive IESDS? Exercise 1.11. Consider the following game (OR Exercise 56.3): B1 2,0 0,2 1,1 B2 0,2 2,0 1,1

A1 A2 A3 Which actions survive IESDS?