Game Theory (Part 9)

Last time we talked about independence of a pair of events, but we can easily go on and talk about independence of a longer sequence of events. For example, suppose we have three coins. Suppose:

• the 1st coin has probability of landing heads up and of landing tails up;
• the 2nd coin has probability of landing heads up and of landing tails up;
• the 3rd coin has probability of landing heads up and of landing tails up.

Suppose we flip all of these coins: the 1st, then the 2nd, then the 3rd. What’s the probability that we get this sequence of results:

If the coin flips are independent, the probability is just this product:

See the pattern? We just multiply the probabilities. And there’s nothing special about coins here, or the number three. We could flip a coin, roll a die, pick a card, and see if it’s raining outside.

For example, what’s the probability that we get heads with our coin, the number 6 on our die, an ace of spades with our cards, and it’s raining? If these events are independent, we just calculate:

the probability that we get heads, times
the probability that we roll a 6, times
the probability that we get an ace of spades, times
the probability that it’s raining outside.

Let’s solve some puzzles using this idea!

Three flips of a fair coin

Example 1. Suppose you have a fair coin: this means it has a 50% chance of landing heads up and a 50% chance of landing tails up. Suppose you flip it three times and these flips are independent. What is the probability that it lands heads up, then tails up, then heads up?

We’re asking about the probability of this event:

Since the flips are independent this is

Since the coin is fair we have

so

So the answer is 1/8, or 12.5%.

Example 2. In the same situation, what’s the probability that the coin lands heads up exactly twice?

There are 2 × 2 × 2 = 8 events that can happen:

We can work out the probability of each of these events. For example, we’ve already seen that is

since the coin is fair and the flips are independent. In fact, all 8 probabilities work out the same way. We always get 1/8. In other words, each of the 8 events is equally likely!

But we’re interested in the probability that we get exactly two heads. That’s the probability of this subset:

Using the rule we saw in Part 7, this probability is

So the answer is 3/8, or 37.5%.

I could have done this a lot faster. I could say “there are 8 events that can happen, each equally likely, and three that give us two heads, so the probability is 3/8.” But I wanted to show you how we’re just following rules we’ve already seen!

Three flips of a very unfair coin

Example 3. Now suppose we have an unfair coin with a 90% chance of landing heads up and 10% chance of landing tails up! What’s the probability that if we flip it three times, it lands heads up exactly twice? Again let’s assume the coin flips are independent.

Most of the calculation works exactly the same way, but now our coin has

We’re interested in the events where the coin comes up heads twice, so we look at this subset:

The probability of this subset is

So now the probability is just 24.3%.

Six flips of a fair coin

Example 4. Suppose you have a fair coin. Suppose you flip it six times and these flips are independent. What is the probability that it lands heads up exactly twice?

We did a similar problem already, where we flipped the coin three times. Go back and look at that if you forget! The answer to that problem was

Why? Here’s why: there were 3 ways to get two heads when you flipped 3 coins, and each of these events had probability

We can do our new problem the same way. Count the number of ways to get two heads when we flip six coins. Then multiply this by

The hard part is to count how many ways we can get two heads when we flip six coins. To get good at probabilities, we have to get good at counting. It’s boring to list all the events we’re trying to count:

(H,H,T,T,T,T), (H,T,H,T,T,T), (H,T,T,H,T,T), …

So let’s try to come up with a better idea.

We have to pick 2 out of our 6 flips to be H’s. How many ways are there to do this?

There are 6 ways to pick one of the flips and draw a red H on it, and then 5 ways left over to pick another and draw a blue H on it… letting the rest be T’s. For example:

(T, H, T, T, H, T)

So, we’ve got 6 × 5 = 30 choices. But we don’t really care which H is red and which H is blue—that’s just a trick to help us solve the problem. For example, we don’t want to count

(T, H, T, T, H, T)

as different from

(T, H, T, T, H, T)

So, there aren’t really 30 ways to get two heads. There are only half as many! There are 15 ways.

So, the probability of getting two heads when we flip the coin six times is

where the squiggle means ‘approximately’. So: about 23.4%.

Binomial coefficients

Now for some jargon, which will help when we do harder problems like this. We say there are 6 choose 2 ways to choose 2 out of 6 things, and we write this as

This sort of number is called a binomial coefficient.

We’ve just shown that

Why write it like this funky fraction: ? Because it’ll help us see the pattern for doing harder problems like this!

Nine flips of a fair coin

If we flip a fair coin 9 times, and the flips are independent, what’s the probability that we get heads exactly 6 times?

This works just like the last problem, only the numbers are bigger. So, I’ll do it faster!

When we flip the coin 9 times there are possible events that can happen. Each of these is equally likely if it’s a fair coin and the flips are independent. So each has probability

To get the answer, we need to multiply this by the number of ways we can get heads exactly 6 times. This number is called ‘9 choose 6’ or

for short. It’s the number of ways we can choose 6 things out of a collection of 9.

So we just need to know: what’s 9 choose 6? We can work this out as before. There are 9 ways to pick one of the flips and draw a red H on it, then 8 ways left to pick another and draw a blue H on it, and 7 ways left to pick a third and draw a orange H on it. That sounds like 9 × 8 × 7.

But we’ve overcounted! After all, we don’t care about the colors. We don’t care about the difference between this:

(T, H, T, T, H, T, T, H, T)

and this:

(T, H, T, T, H, T, T, H, T)

In fact we’ve counted each possibility 6 times! Why six? The first H could be red, green or blue—that’s 3 choices. But then the second H could be either of the two remaining 2 colors… and for the third, we just have 1 choice. So there are 3 × 2 × 1 = 6 ways to permute the colors.

So, the actual number of ways to get 6 heads out of 9 coin flips is

In other words:

To get the answer to our actual problem, remember we need to multiply by this. So the answer is

If you’re a pure mathematician, you can say you’re done now. But normal people won’t understand this answer, so let’s calculate it out. I hope you know the first ten powers of two: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. So:

I hope you can also do basic arithmetic like this:

So, the probability of getting 6 heads when you do 9 independent flips of a fair coin is

or 16.4025%. I broke down and used a calculator at the last step. We’re becoming serious nerds here.

Okay, that’s enough for now. We’ve been counting how many ways we can get a certain number of heads from a certain number of coin flips. What we’re realy doing is taking a set of coin flips, say of them, and choosing a subset of of them to be heads. So, we say

Definition. The binomial coefficient

called choose is the number of ways of choosing a subset of things from a set of things.

We have seen in some examples that

Here there’s a product of consecutive numbers on top, and on bottom too. We didn’t prove this is true in general, but it’s not hard to see, using the tricks we’ve used already.

Game Theory (Part 8)

Last time we learned some rules for calculating probabilities. But we need a few more rules to get very far.

For example:

We say a coin is fair if it has probability 1/2 of landing heads up and probability 1/2 of landing tails up. What is the probability that if we flip two fair coins, both will land heads up?

Since each coin could land heads up or tails up, there are 4 events to consider here:

It seems plausible that each should be equally likely. If so, each has probability 1/4. So then the answer to our question would be 1/4.

But this is plausible only because we’re assuming that what one coin does doesn’t affect that the other one does! In other words, we’re assuming the two coin flips are ‘independent’.

If the coins were connected in some sneaky way, maybe each time one landed heads up, the other would land tails up. Then the answer to our question would be zero. Of course this seems silly. But it’s good to be very clear about this issue… because sometimes one event does affect another!

For example, suppose there’s a 5% probability of rain each day in the winter in Riverside. What’s the probability that it rains two days in a row? Remember that 5% is 0.05. So, you might guess the answer is

But this is wrong, because if it rains one day, that increases the probability that it will rain the next day. In other words, these events aren’t independent.

But if two events are independent, there’s an easy way to figure out the probability that they both happen: just multiply their probabilities! For example, if the chance that it will rain today in Riverside is 5% and the chance that it will rain tomorrow in Singapore is 60%, the chance that both these things will happen is

or 3%, if these events are independent. I could try to persuade that this is a good rule, and maybe I will… but for now let’s just state it in a general way.

Independence

So, let’s make a precise definition out of all this! Suppose we have two sets of events, and Remember that , the Cartesian product of the sets and , is the set of all ordered pairs where and :

So, an event in consists of an event in and an event in . For example, if

and

then

Now we can define ‘independence’. It’s a rule for getting a probability distribution on from probability distributions on and :

Definition. Suppose is a probability distribution on a set of events and is a probability distribution on a set of events If these events are independent, we use the probability distribution on given by

People often call this probability distribution instead of .

Examples

Example 1. Suppose we have a fair coin. This means we have a set of events

and a probability distribution with

Now suppose we flip it twice. We get a set of four events:

Suppose the two coin flips are independent. Then we describe the pair of coin flips using the probability measure on with

So, each of the four events—“heads, heads” and so on—has probability 1/4. This is fairly boring: you should have known this already!

But now we can do a harder example:

Example 2. Suppose we have an unfair coin that has a 60% chance of landing heads up and a 40% chance of landing tails up. Now we have a new probability distribution on say :

Now say we flip this coin twice. What are the probabilities of the four different events that can happen? Let’s assume the two coin flips are independent. This means we should describe the pair of coin flips with a probability measure on This tells us the answer to our question. We can work it out:

Puzzle 1. In this situation what is the probability that when we flip the coin twice it comes up heads exactly once?

Puzzle 2. In this situation what is the probability that when we flip the coin twice it comes up heads at least once?

For these puzzles you need to use what I told you in the section on ‘Probabilities of subsets’ near the end of Part 7.

Puzzle 3. Now suppose we have one fair coin and one coin that has a 60% chance of landing heads up. The first one is described by the probability distribution while the second is described by How likely is it that the first lands heads up and the second lands tails up? We can answer questions like this if the coin flips are independent. We do this by multiplying and to get a probability measure on Remember the rule for how to do this:

where each of and can be either or

What are these probabilities:

Puzzle 4. In this situation what is the probability that exactly one coin lands heads up?

Puzzle 5. In this situation what is the probability that at least one coin lands heads up?

Next time we’ll go a lot further…

Game Theory (Part 7)

We need to learn a little probability theory to go further in our work on game theory.

We’ll start with some finite set of ‘events’. The idea is that these are things that can happen—for example, choices you could make while playing a game. A ‘probability distribution’ on this set assigns to each event a number called a ‘probability’—which says, roughly speaking, how likely that event is. If we’ve got some event we’ll call its probability

For example, suppose we’re interested in whether it will rain today or not. Then we might look at a set of two events:

If the weatherman says the chance of rain is 20%, then

since 20% is just a fancy way of saying 0.2. The chance of no rain will then be 80%, or 0.8, since the probabilities should add up to 1:

Let’s make this precise with an official definition:

Definition. Given a finite set of events, a probability distribution assigns a real number called a probability to each event such that:

1)

and

2)

Note that this official definition doesn’t say what an event really is, and it doesn’t say what probabilities really mean. But that’s how it should be! As usual with math definitions, the words in boldface could be replaced by any other words and the definition would still do its main job, which is to let us prove theorems involving these words. If we wanted, we could call an event a doohickey, and call a probability a schnoofus. All our theorems would still be true.

Of course we hope our theorems will be useful in real world applications. And in these applications, the probabilities will be some way of measuring ‘how likely’ events are. But it’s actually quite hard to say precisely what probabilities really mean! People have been arguing about this for centuries. So it’s good that we separate this hard task from our definition above, which is quite simple and 100% precise.

Why is it hard to say what probabilities really are? Well, what does it mean to say “the probability of rain is 20%”? Suppose you see a weather report and read this. What does it mean?

A student suggests: “it means that if you looked at a lot of similar days, it would rain on 20% of them.”

Yes, that’s pretty good. But what counts as a “similar day”? How similar does it have to be? Does everyone have to wear the same clothes? No, that probably doesn’t matter, because presumably doesn’t affect the weather. But what does affect the weather? A lot of things! Do all those things have to be exactly the same for it count as similar day.

And what counts as a “lot” of days? How many do we need?

And it won’t rain on exactly 20% of those days. How close do we need to get?

Imagine I have a coin and I claim it lands heads up 50% of the time. Say I flip it 10 times and it lands heads up every time. Does that mean I was wrong? Not necessarily. It’s possible that the coin will do this. It’s just not very probable.

But look: now we’re using the word ‘probable’, which is the word we’re trying to understand! It’s getting sort of circular: we’re saying a coin has a 50% probability of landing heads up if when you flip it a lot of times, it probably lands head up close to 50% of the time. That’s not very helpful if you don’t already have some idea what ‘probability’ means.

For all these reasons, and many more, it’s tricky to say exactly what probabilities really mean. People have made a lot of progress on this question, but we will sidestep it and focus on learning to calculate with probabilities.

If you want to dig in a bit deeper, try this:

• Probability interpretations, Wikipedia.

Equally likely events

As I’ve tried to convince you, it can be hard to figure out the probabilities of events. But it’s easy if we assume all the events are equally likely.

Suppose we have a set consisting of events. And suppose that all the probabilities are equal: say for some constant we have

for all Then by rule 1) above,

since we’re just adding the number to itself times. So,

and thus

for all .

I made this look harder than it really is. I was just trying to show you that it follows from the definitions, not any intuition. But it’s obvious: if you have events that are equally likely, each one has probability

Example 1. Suppose we have a coin that can land either heads up or tails up—let’s ignore the possibility that it lands on its edge! Then

If we assume these two events are equally probable, we must have

Note I said “if we assume” these two events are equally probable. I didn’t say they actually are! Are they? Suppose we take a penny and flip it a zillion times. Will it land heads up almost exactly half a zillion times?

Probably not! The treasury isn’t interested in making pennies that do this. They’re interested in making the head look like Lincoln, and the tail look like the Lincoln national monument:

Or at least they used to. Since the two sides are different, there’s no reason they should have the exact same probability of landing on top.

In fact nobody seems to have measured the difference between heads and tails in probabilities for flipping pennies. For hand-flipped pennies, it seems whatever side that starts on top has a roughly 51% chance of landing on top! But if you spin a penny, it’s much more likely to land tails up:

• The coin flip: a fundamentally unfair proposition?, Coding the Wheel.

Example 2. Suppose we have a standard deck of cards, well-shuffled, and assume that when I draw a card from this deck, each card is equally likely to be chosen. What is the probability that I draw the ace of spades?

If there’s no joker in the deck, there are 52 cards, so the answer is 1/52.

Let me remind you how a deck of cards works: I wouldn’t want someone to fail the course because they didn’t ever play cards! Here are the 52 cards in a standard deck. Here’s what they all look like (click to enlarge):

As you can see, they come in 4 kinds, called suits. The suits are:

• clubs: ♣

• spades: ♠

• diamonds: ♦

• hearts: ♥

Two suits are black and two are red. Each suit has 13 cards in it, for a total of 4 × 13 = 52. The cards in each suit are numbered from 1 to 13, except for four exceptions. They go like this:

A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K

A stands for ‘ace’, J for ‘jack’, Q for ‘queen’ and K for ‘king’.

Probabilities of subsets

If we know a probability distribution on a finite set , we can define the probability that an event in some subset will occur. We define this to be

For example, I usually have one of three things for breakfast:

I have an 86% chance of eating oatmeal for breakfast, a 10% chance of eating waffles, and a 4% chance of eating eggs and toast. What’s the probability that I will eat oatmeal or waffles? These choices form the subset

and the probability for this subset is

Here’s an example from cards:

Example 2. Suppose we have a standard deck of cards, well-shuffled, and assume that when I draw a card from this deck, each card is equally likely to be chosen. What is the probability that I draw a card in the suit of hearts?

Since there are 13 cards in the suit of hearts, each with probability 1/52, we add up their probabilities and get

This should make sense, since there are 4 suits, and as many cards in each suit.

Card tricks

This is just a fun digression. The deck of cards involves some weird numerology. For starters, it has 52 cards. That’s a strange number! Where else have you seen this number?

A student says: “It’s the number of weeks in a year.”

Right! And these 52 cards are grouped in 4 suits. What does the year have 4 of?

A student says: “Seasons!”

Right! And we have 52 = 4 × 13. So what are there 13 of?

A student says: “Weeks in a season!”

Right! I have no idea if this is a coincidence or not. And have you ever added up the values of all the cards in a suit, where we count the ace as 1, and so on? We get

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13

And what’s that equal to?

After a long pause, a student says “91.”

Yes, that’s a really strange number. But let’s say we total up the values of all the cards in the deck, not just one suit. What do we get?

A student says “We get 4 × 91… or 364.”

Right. Three-hundred and sixty-four. Almost the number of days in year.

“So add one more: the joker! Then you get 365!”

Right, maybe that’s why they put an extra card called the joker in the deck:

One extra card for one extra day, joker-day… April Fool’s Day! That brings the total up to 365.

Again, I have no idea if this is a coincidence or not. But the people who invented the Tarot deck were pretty weird—they packed it with symbolism—so maybe the ordinary cards were designed this way on purpose too.

Puzzle. What are the prime factors of the number 91? You should know by now… and you should know what they have to do with the calendar!

Game Theory (Part 6)

We’ve been looking at games where each player gets a payoff depending on the choice that both players make. The payoff is a real number, which I often call the number of points. When we play these games in class, these points go toward your grade. 10% of your grade depends on the the total number of points you earn in quizzes and games. But what do these points mean in other games, like Prisoner’s Dilemma or Battle of the Sexes?

This leads us into some very interesting and deep questions. Let’s take a very quick look at them, without getting very dep.

Maximizing the payoff

The main thing is this. When we’re studying games, we’ll assume each player’s goal is to earn as many points as possible. In other words, they are trying to maximize their payoff.

They are not, for example, trying to make their payoff bigger than the other player’s payoff. Indeed, in class you should not be trying to earn more points than me! One student said he was trying to do that. That’s a mistake. You should be happier if

• you get 10 points and I get 20

than if

• you get -10 points and I get -20.

After all, it’s only your total number of points that affects your grade, not whether it’s bigger than mine.

So, you should always try to maximize your payoff. And I promise to do the same thing: I’ll always try to maximize my payoff. You have to take my word on this, since my salary is not affected by my payoff! But I want to make your task very clear: you are trying to maximize your payoff, and you can assume I am trying to maximize mine.

(If I were doing something else, like sadistically trying to minimize your payoff, that would affect your decisions!)

Rational agents and utility

We can’t understand how people actually play games unless we know what they are trying to do. In real life, people’s motives are very complicated and sometimes mysterious. But in mathematical game theory, we start by studying simpler: rational agents. Roughly speaking, a rational agent is defined to be a person or animal or computer program or something that is doing the best possible job of maximizing some quantity, given the information they have.

This is a rough definition, which we will try to improve later.

You shouldn’t be fooled by the positive connotations of the word ‘rational’. We’re using it in a very specific technical way here. A madman in a movie theater who is trying to kill as many people as possible counts as ‘rational’ by our definition if they maximize the number of people killed, given the information they have.

The whole question of what really should count as ‘rationality’ is a very deep one. People have a lot of interesting ideas about it:

• Rationality, Wikipedia.

Utility

So: we say a rational agent does the best possible job of maximizing their payoff given the information they have. But in economics, this payoff is often called utility.

That’s an odd word, but comes from a moral philosophy called utilitarianism, which says—very roughly—that the goal of life is to maximize happiness. Perhaps because it’s a bit embarrassing to talk about maximizing happiness, these philosophers called it ‘utility’.

But be careful: while the moral philosophers often talk about agents trying to maximize the total utility of everyone, economists focus on rational agents trying to maximize their own utility.

This sounds very selfish. But it’s not necessarily. If you want other people to be happy, your utility depends on their utility. If you were a complete altruist, perhaps maximizing your utility would even be the same as maximizing the total utility of everyone!

Again, there are many deep problems here, which I won’t discuss. I’ll just mention one: in practice, it’s very hard to define utility in a way that’s precise enough to measure, much less add up! See here for a bit more:

• Utility, Wikipedia.

• Utilitarianism, Wikipedia.

The assumption of mutual rationality

Game theory is simplest when

• all players are rational agents,

and

• each player knows all the other players are rational agents.

Of course, in the real world nobody is rational all the time, so things get much more complicated. If you’re playing against an irrational agent, you have to work harder to guess what they are going to do!

But in the games we play in class, I will try to be a rational agent: I will try my best to maximize my payoff. And you too should try to be a rational agent, and maximize your payoff—since that will help your grade. And you can assume I am a rational agent. And I will assume you are a rational agent.

So: I know that if I keep making the same choice, you will make the choice that maximizes your payoff given what I do.

And: you know that if you keep making the same choice, I will make the choice that maximizes my payoff given what you do.

Given this, we should both seek a Nash equilibrium. I won’t try to state this precisely and prove it as a theorem… but I hope it’s believable. You can see some theorems about this here:

• Robert Aumann and Adam Brandenburger, Epistemic conditions for Nash equilibrium
.

Probabilities

All this is fine if a Nash equilibrium exists and is unique. But we’ve seen that in some games, a Nash equilibirum doesn’t exist—at least not, if we only consider pure strategies, where each player makes the same choice every time. And in other games, the Nash equilibrium exists but there is more than one.

In games like this, saying that players will try to find a Nash equilibrium doesn’t settle all our questions! What should they do if there’s none, or more than one?

We’ve seen one example: rock-paper-scissors. If we only consider pure strategies, this game has no Nash equilibrium. But I’ve already suggested the solution to this problem. The players should use mixed strategies, where they randomly make different choices with different probabilities.

So, to make progress, we’ll need to learn a bit of probability theory! That’ll be our next topic.

Game Theory (Part 5)

Here are a bunch of puzzles about game theory, to see if you understand the material so far.

Classifying games

For each of the following games, say whether it is:

a) a single-player, 2-player or multi-player game

b) a simultaneous or sequential game

c) a zero-sum or nonzero-sum game

d) a symmetric or nonsymmetric game

e) a cooperative or noncooperative game

If it can be either one, or it is hard to decide, explain why! You will probably not know all these games. So, look them up on Wikipedia if you need to:

1) chess

2) poker

3) baseball

4) rock-paper-scissors

5) rock-paper-scissors-lizard-Spock

6) Prisoner’s Dilemma

    

7) solitaire with cards (also known as “patience”)

8) the ultimatum game

9) guess 2/3 of the average

10) Nim

Battle of the Sexes

Suppose that Alice and Bob are going to the movies. Alice wants to see the movie This is 40 while Bob wants to see Zero Dark Thirty. Let’s say Alice and Bob each have two strategies:

1. Watch the movie they really want to see.
2. Watch the movie the other one wants to see.

If they both watch the movie they really want, each goes out alone and gets a payoff of 5. If they both watch the movie the other wants to see, they again go out alone and now each gets a payoff of -5, because they’re both really bored as well as lonely. Finally, suppose one watches the movie they want while the other kindly watches the movie their partner wants. Then they go out together. The one who gets to see the movie they want gets a payoff of 10, while the one who doesn’t gets a payoff of 7. (They may not like the movie, but they get ‘points’ for being a good partner!)

Call Alice A for short, and call Bob B. Write down this game in normal form.

Prisoner’s Dilemma

Now suppose Alice and Bob have been arrested because they’re suspected of having conspired to commit a serious crime: an armed robbery of the movie theater!

They are interrogated in separate rooms. The detectives explain to each of them that they are looking at 3 years of jail even if neither of them confess. If one confesses and the other denies having committed the crime, the one who confesses will get only 1 year of jail, while the one who denies it will get 25 years. If they both confess, they will both get 10 years of jail.

Suppose the two strategies available to both of them are:

1. confess to the crime.
2. deny having done it.

Write down this game in normal form, where years of jail time counts as a payoff of

Game theory concepts

Now, for both the Battle of the Sexes and Prisoner’s Dilemma games, answer these questions:

a) Is this a zero-sum game?

b) Is this a symmetric game?

c) Does player A have a strictly dominant pure strategy? If so, which one?

d) Does player B have a strictly dominant pure strategy? If so, which one?

e) Does this game have one or more Nash equilibria? If so, what are they?

Zero-sum and symmetric games

For the next two problems, suppose we have a game in normal form described by two matrices and Remember from Part 2 of our course notes that if player A chooses strategy and player B chooses strategy , is the payoff to player A and is the payoff to player B.

a) What conditions on the matrices and say that this game is a zero-sum game?

b) What conditions on the matrices and say that the game is symmetric?

Game Theory (Part 4)

Last time we talked about Nash equilibria for a 2-player normal form game. We saw that sometimes a Nash equilibrium doesn’t exist! Sometimes there’s more than one! But suppose there is at least one Nash equilibrium. How do we find one? Sometimes it’s hard.

Strict domination

But there’s a simple trick to rule out some possibilities. Sometimes player A will have a choice that gives them a bigger payoff than some choice no matter what choice player B makes. In this case we say choice strictly dominates choice And in this case, there’s no way that could be A’s choice in a Nash equilibrium, because player A can always improve their payoff by switching to choice

For example, look at this game:

	1	2
1	(0,0)	(-1,1)
2	(2,-1)	(0,0)
3	(-2,1)	(1,-1)
4	(0,1)	(2,0)

For player A, choice 4 strictly dominates choice 3. No matter what player B does, player A gets a bigger payoff if they make choice 4 than if they make choice 3. Stare at the black numbers in the table in rows 3 and 4 until you see this.

You can also see it using the payoff matrix for player A:

Each number in row 4 here is bigger than the number directly above it in row 3. In other words:

and

Puzzle. Are there any other examples of a choice for player A that strictly dominates another choice?

And of course the same sort of thing works for player B. If player B has a choice that gives them a better payoff than some choice no matter what player A does, then can’t show up as B’s choice in a Nash equilibrium.

We can make our remarks more precise:

Definition. A choice for player A strictly dominates a choice if

for all Similarly, a choice for player B strictly dominates a choice if

for all

Theorem 1. If a choice for player A strictly dominates a choice then no choice for player B gives a Nash equilibrium Similarly, if a choice for player B strictly dominates a choice then no choice for player A gives a Nash equilibrium

Proof. We’ll only prove the first statement since the second one works the exact same way. Suppose strictly dominates This means that

for all In this case, there is no way that the choice can be part of a Nash equilibrium. After all, if is a Nash equilibrium we have

for all . But this contradicts the previous inequality—just take █

Strict dominance

Definition. We say a choice is strictly dominant if it strictly dominates all other choices for that player.

Let me remind you again that a pure strategy is a way for one player to play a game where they always make the same choice. So, there is one pure strategy for each choice, and one choice for each pure strategy. This means we can be a bit relaxed about the difference between these words. So, what we’re calling strictly dominant choices, most people call strictly dominant pure strategies. You can read more about these ideas here:

• Strategic dominance, Wikipedia.

We’ve seen that if one choice strictly dominates another, that other choice can’t be part of a Nash equilibrium. So if one choices strictly dominates all others, that choice is the only one that can be part of a Nash equilibrium! In other words:

Theorem 2. If a choice for player A is strictly dominant, then any Nash equilibrium must have . Similarly, if a choice for player B is strictly dominant, then any Nash equilibrium must have .

Proof. We’ll only prove the first statement since the second one works the exact same way. Theorem 1 says that if a choice for player A strictly dominates a choice then no choice for player B gives a Nash equilibrium So, if strictly dominates all other choices for player A, it is impossible to have a Nash equilibrium unless █

We can go even further:

Theorem 3. If choice for player A is strictly dominant and choice for player B is strictly dominant, then is a Nash equilibrium, and there is no other Nash equilibrium.

Proof. Suppose choice for player A is strictly dominant and choice for player B is strictly dominant. Then by Theorem 2 any Nash equilibrium must have and . So, there is certainly no Nash equilibrium other than

But we still need to check that is a Nash equilibrium! This means we need to check that:

1) For all

2) For all

Part 1) is true because choice is strictly dominant. Part 2) is true because choice is strictly dominant. █

We can restate Theorem 3 is a less precise but rather pretty way:

Corollary. If both players have a strictly dominant pure strategy, there exists a unique Nash equilibrium.

Here I’m saying ‘pure strategy’ instead of ‘choice’ just to prepare you for people who talk that way!

Domination

I realize that the terminology here has a kind of S&M flavor to it, with all this talk of ‘strict domination’ and the like. But there’s nothing I can do about that—it’s standard!

Anyway, there’s also a less strict kind of dominance:

Definition. A choice for player A dominates a choice if

for all Similarly, a choice for player B dominates a choice if

for all

But there is less we can do with this definition. Why? Here’s why:

Puzzle. Find a normal-form two player game with 2 choices for each player, where is a Nash equilibrium even though is dominated by the other choice for player A and is dominated by the other choice for player B.

Game Theory (Part 3)

Last time we started looking at 2-player normal form games. The idea is that player A has different choices of which move to make, while player B has choices, and we have two matrices of payoffs, and If player A makes choice and player B makes choice then the payoff to player A is while the payoff to player B is

What should you do if you’re playing a game like this? As we saw when playing rock-paper-scissors, sometimes the best thing is to adopt a strategy with some built-in randomness. In this game, if your opponent knows what you’re going to do, he can exploit that and beat you!

A strategy involving randomness is called a mixed strategy. They’re very important, and we’ll talk about them a lot. But today we’ll only consider pure strategies, where we definitely choose one of the choices available, with no randomness.

Notice: there are as many pure strategies as there are choices! For each choice, there’s a pure strategy where you always make that choice when playing the game. So, a lot of people say ‘pure strategy’ for what I call a ‘choice’. Other people use the word ‘action’.

Anyway: let’s try to figure out the best pure strategy for each player, if we can.

Sometimes this is impossible. For example, rock-paper-scissors has no best pure strategy. Could playing rock be best? No, because paper beats rock. Could playing paper be best? No, because scissors beats paper. Could playing scissors be best? No, because rock beats scissors.

But sometimes we can find a best pure strategy, and the ideas we meet will help us later when we study mixed strategies. So, let’s dive in!

Nash equilibria

Suppose player A makes choice and player B makes choice . Then we say is a Nash equilibrium if neither player can improve their payoff by changing their choice.

For example, look at this game:

	1	2
1	(10,10)	(9,-1)
2	(-1,1)	(-1,-1)

Here we are writing the matrices and together in one table, like last time, with in black and in red. But we could also separate them out:

It’s just a different way of conveying the same information.

Either way, it’s pretty clear what the players should do in this game! Both players should make choice 1. That way, they both win 10 points.

Furthermore, this pair of choices is certainly a Nash equilibrium. In other words: neither player can improve their payoff by unilaterally changing their choice! If player A switches to choice 2, their payoff drops to -1 points. If player B switches to choice 2, their payoff drops to 9 points.

Let’s give an official definition of Nash equilibrium and then look at some trickier examples. Remember, player A’s choices are while player B’s choices are

Definition. Given a 2-player normal form game, a pair of choices is a Nash equilibrium if:

1) For all ,

2) For all ,

Condition 1) says that player A can’t improve their payoff by switching their choice from to any other choice Condition 2) says that player B can’t improve their payoff by switching their choice from to any other choice

Examples

Let’s look at more examples of Nash equilibria, to see some funny things that can happen. First let’s modify the last game a little:

	1	2
1	(10,10)	(-1,10)
2	(10,-1)	(-1,-1)

Is there a Nash equilibrium? Yes—and just as before, it happens when both players pick pure strategy 1. Now player A’s payoff doesn’t get any worse when they switch to pure strategy 2. But it doesn’t improve, either! It stays equal to 10. Similarly, player B’s payoff doesn’t get any worse when they switch to pure strategy 2… but it doesn’t improve. So, neither player is motivated to change their strategy.

I said a Nash equilibrium is a situation where neither player can improve their payoff by changing their choice. But it might be clearer to say: neither player can improve their payoff by unilaterally changing their choice.

What do I mean by ‘unilaterally’ changing their choice? I mean that one player changes their choice while the other player does not change their choice.

But if both players change their choices simultaneously, sometimes they can improve both their payoffs! Lets see an example of that:

	1	2
1	(10,10)	(9,-1)
2	(-1,8)	(20,20)

Now it looks like both players will be happiest if they pick pure strategy 2. And it’s true! Moreover, this is a Nash equilibrium. Check and see.

But what if both players pick choice 1? This is also a Nash equilibrium! Shocking but true. If they both use pure strategy 1, neither player can improve their payoff by unilaterally changing their choice. If player A changes her choice, her payoff drops to -1. And if player B changes his choice, his payoff drops to -1.

Of course, they can improve their payoff if they both simultaneously change their choice to 2. But that’s not what the concept of Nash equilibrium is about.

This raises the question of whether Nash equilibrium is a good definition of ‘the best’ choice for each player. The big problem is figuring out what ‘best’ means—we’ll have to talk about that more. But we’re also seeing some problems with the word ‘the’. There may be more than one Nash equilibrium, so we can’t always talk about ‘the’ Nash equilibrium.

In other words, our example shows there isn’t always a unique Nash equilibrium.

Furthermore, a Nash equilibrium doesn’t always exist! Check out the game of rock-paper-scissors:

	rock	paper	scissors
rock	(0,0)	(-1,1)	(1,-1)
paper	(1,-1)	(0,0)	(-1,1)
scissors	(-1,1)	(1,-1)	(0,0)

It’s easy to see that there’s no Nash equilibrium. No matter what both players choose, at least one of them can always improve their payoff by switching to a different choice. If one of them wins the game, the loser can improve their payoff by switching to a different choice. If it’s a tie, either player can improve their payoff by switching to a different choice.

So: Nash equilibria are interesting, but they don’t always exist— at least not when we consider only pure strategies, as we’ve been doing. And even when they do, they’re not always unique! This is a bit frustrating. We’d like game theory to tell us how to play games well.

We can improve the situation by allowing mixed strategies, where a player picks different choices with different probabilities. If we do this, there is always at least one Nash equilibrium! This result was proved by—you guessed it!—John Nash. He did it in 1950, in this astoundingly short paper:

• John F. Nash, Jr., Equilibrium points in n-person games, Proceedings of the National Academy of Sciences 36 (1950), 48–9.

He eventually won the Nobel prize in economics for this work.

In fact, Nash was not the first to think about Nash equilibria; this idea goes back to the French economist Antoine Cournot, who wrote about it way back in 1838! However, Nash was the first to consider Nash equilibria for mixed strategies for general simultaneous multi-player games, and prove they always exist. (As we’ll see later, von Neumann and Morgenstern had already done this for the zero-sum 2-player games.)

John Nash

If you haven’t seen the movie about Nash called A Beautiful Mind, you should! Here’s the scene where Nash figures out something about multiplayer games:

It’s not very clear, mathematically speaking… but oh well. It’s a good movie and it gives you some sense of how Nash battled with mental illness for much of his life. He has now largely recovered and spends his time at Princeton University.

Here’s the young Nash—click for more details:

A ‘practical’ question

A student in my class asked what’s the best book or website on how to play blackjack well. I asked this on Google+ and got over 50 replies, which you can read here. If you know more, please tell me!