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

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

8) the ultimatum game

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 $n$ years of jail time counts as a payoff of $-n.$

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 $m \times n$ matrices $A$ and $B.$ Remember from Part 2 of our course notes that if player A chooses strategy $i$ and player B chooses strategy $j$, $A_{ij}$ is the payoff to player A and $B_{ij}$ is the payoff to player B.

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

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

5 Responses to Game Theory (Part 5)

1. Stuart Presnell says:

In your Prisoner’s Dilemma problem, Alice and Bob’s alleged crime has switched from “armed robbery” (1st paragraph) to “murder” (2nd paragraph).

• John Baez says:

Whoops! I stuck in the “armed robbery” joke at the last minute, long after writing the original homework problem. I’ll remove the murder, which is a bit too grim anyway.

By the way, I was delighted to discover that Wikipedia’s page on solitaire shows a picture of a woman in prison playing solitaire. So, I could form a nice visual connection between that game and the Prisoner’s Dilemma.

She’s dressed in a suspiciously attractive way for a prisoner, though.

2. Tim van Beek says:

Slightly off topic, but isn’t the information available to each player also an important category for classifying games? With the possible values

every player has complete information about the situation (chess),

every player has the same but incomplete information (betting in a horse race),

every player has incomplete information, which differs from player to player (poker).

• John Baez says:

Yes, this is important too! I don’t feel I understand this quite as well as I’d like, because beside the games you mention, there are games without any of what we’d normally call ‘chance’ or ‘randomness’, but where some players have incomplete information about other player’s moves.

In America a famous game like this is called ‘Battleship’—it’s a simple model of a war.

In war, incomplete information is of fundamental importance; there’s chance but also lots of deliberate concealment.

In Part 1, I posed this puzzle:

Puzzle. What’s a ‘game of perfect information’ and what’s a ‘game of complete information’? What’s the difference?

and Antifilon replied:

A game is of complete information if the players know who the other players are and also their best strategies and the payoffs. A game is of perfect information if all the players have perfect knowledge of the sequence of moves performed in the game.

• Joseph Benedetti says:

There is also a funny strategic game called stratego
http://en.wikipedia.org/wiki/Stratego
where sometimes it is better to sacrifice some material to gain some information. The price of information is valuable !