Game Theory (Part 2)

Last time we classified games in a few ways. This time we’ll start by looking at a very simple class of games: simultaneous noncooperative two-player games.

Simultaneous games

Remember that in a simultaneous game, each player makes their moves without knowing anything about the other player’s move. Thanks to this, we can condense each player’s move into a single move. For example, in a card game, if one player lays down a king and then an ace, we can mathematically treat this as a single move, called “lay down a king and then an ace”. So, we’ll say each player makes just one move—and they make it without knowing the other player’s move.

In class we’ll play these games like this. I will decide on my move and write it down on a piece of paper. You’ll make your move and click either A,B,C,D, or E on your clicker.

Then I’ll reveal my piece of paper! At that point, we’ll each know what both of us did… but neither of us can change our move.

So, we each make our move without knowing each other’s move.

Two-player games

Since lots of you will be clicking your clicker at once, you could say there are more than two players in this game. But your payoff—the number of points you win or lose—will depend only on what you did and what I did. So, we can treat this game as a bunch of independent two-player games—and that’s what we’ll do.

Noncooperative games

Remember, we use words in funny ways in mathematics! An ‘imaginary’ number is not imaginary in the usual sense; a ‘partial’ differential equation isn’t just part of a differential equation, and so on. In game theory we use the word ‘noncooperative’ in a funny way. We say a game is noncooperative if the players aren’t able to form binding commitments. This means that when we play our games, you and I can’t talk before the game and promise to do certain things.

There will, however, be games where both of us win if we make the right choice, and both of us lose if we don’t! In games like this, if we can figure out how to cooperate without communicating ahead of time and making promises, that’s allowed!

Chicken

Now let’s actually look at an example: the game of chicken. In this game we drive toward each other at high speed along a one-lane road in the desert. The one who swerves off the road at the last minute gets called a chicken, and the other driver gets called a hero. If we both swerve off the road at the last minute, we’re both called chickens. But if neither of us does, our cars crash and we both die!

Sounds fun, eh?

In real life we could each wait as long as possible and see if the other driver starts to swerve. This makes chicken into a sequential rather than simultaneous game! You could also promise that you wouldn’t swerve. This makes chicken into a cooperative game!

Indeed there are all sorts of variations and complications in real life. You can see some in the famous movie Rebel Without a Cause, starring James Dean. Take a look at what happens:

This movie version actually involves driving toward a cliff and jumping out at the last possible moment.

But mathematics, as usual, is about finding problems that are simple enough to state precisely. So in our simple mathematical version of chicken, we’ll say each player has just two choices:

1: stay on the road.
2: swerve off the road at the last second.

Also, we’ll express our payoffs in terms of numbers. A negative payoff is bad, a positive one is good:

• If either player swerves off the road they get called a chicken, which is bad, so let’s say they get -1 points.

• If one player stays on the road and other swerves off the road, the one who stays on the road gets called a hero, so let’s say they get 1 point.

• If both players stay on the road they both die, so let’s say they both get -10 points.

We can summarize all this in a little table:

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

Let’s say the players are you and me. Your choices 1 and 2 are shown in in black: you get to pick which row of the table we use. My choices 1 and 2 are in red: I get to pick which column of the table we use.

There are four possible ways we can play the game. For each of the four possibilities we get a pair of numbers. The first number, in black, is your payoff. The second, in red, is my payoff.

For example, suppose you choose 1 and I choose 2. Then you’re a hero and I’m a chicken. So, your payoff is 1 and mine is -1. That’s why we get the pair of numbers (1,-1) in the 1st row and 2nd column of this table.

Now let’s play this game a bit! Later we’ll study it in different ways.

Rock-paper-scissors

Here’s another famous game: rock-paper-scissors.

Each player can choose either rock, paper or scissors. Paper beats rock, scissors beats paper, and rock beats scissors. In these cases let’s say the winner gets a payoff of 1, while the loser gets a payoff of -1. If both players make the same choice, it’s a tie, so let’s say both players get a payoff of 0.

Here’s a table that describes this game:

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

Your choices and payoffs are in black, while mine are in red.

For example, if you choose rock and I choose paper, we can look up what happens, and it’s (-1,1). That means your payoff is -1 while mine is 1. So I win!

To make this table look more mathematical, we can make up numbers for our choices:

1: rock
2: paper
3: scissors

Then the table looks like this:

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

Let’s play this game a bit, and then discuss it!

Normal form

In the games we’re studying now, each player can make various choices. In game theory these choices are often called pure strategies. We’ll see why later on in this course.

In our examples so far, each player has the same set of pure strategies. But this is not required! You could have some set of pure strategies and I could have some other set.

For now let’s only think about games where we both have a finite set of pure strategies. For example, you could have 4 pure strategies and I could have 2. Then we could have a game like this:

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

This way of describing a game using a table of pairs of numbers is called normal form, and you can read about it here:

• Normal-form game, Wikipedia.

There are other ways to describe the same information. For example, instead of writing

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

we can write everything in black:

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

All the information is still there! It’s just a bit harder to see. The colors are just to make it easier on you.

Mathematicians like matrices, which are rectangular boxes of numbers. So, it’s good to use these to describe normal-form games. To do this we take our table and chop it into two. We write one matrix for your payoffs:

and one for mine:

The number in the ith row and jth column of the matrix is called , and similarly for . For example, if you pick choice 3 in this game and I pick choice 2, your payoff is

and my payoff is

Definition

Let’s summarize everything we’ve learned today! Remember, an matrix has rows and columns. So, we can say:

Definition. A 2-player normal-form game consists of two matrices of real numbers, and

This definition is very terse and abstract. That’s what mathematicians like! But we have to unfold it a bit to understand it.

Let’s call you ‘player A’ and me ‘player B’. Then the idea here is that player A can choose among pure strategies while player B can choose among pure strategies Suppose player A makes choice and player B makes choice Then the payoff to player A is and the payoff to player B is

Game Theory (Part 1)

I’m teaching an undergraduate course on game theory and I thought I’d try writing my course notes on this blog. I invite students (and everyone else in the universe) to ask questions, correct my mistakes, add useful extra information and references, and so on.

However, I should warn the geniuses who usually read this blog that these notes will not be filled with deep insights: it’s just a introductory course and it’s the first time I’ve taught it.

I should also warn the students in my class that these notes are not a substitute for taking notes in class! I’ll tell you a lot of other stuff in class!

Let’s get started.

Examples of games

Mathematicians use words differently from normal people. When you hear the word ‘game’ you probably think about examples like:

• board games like checkers, chess, go, Scrabble, Monopoly, Risk and so on.

• card games like solitaire, poker, bridge, blackjack, and so on.

• sports involving athletic skill like football, basketball, baseball, hockey, tennis, squash, golf, croquet, horseshoes and so on.

• video games and computer games—I’m too much of an old fogey to even bother trying to list some currently popular ones.

• game shows on TV—ditto, though Jeopardy is still on the air.

• role-playing games—ditto, though some people still play Dungeons and Dragons.

• ‘war games’ used by armies to prepare for wars.

Game theory is relevant to all these games, but more generally to any situation where one or more players interact, each one trying to achieve their own goal. The players can be people but they don’t need to be: they can also be animals or even other organisms! So, game theory is also used to study

• biology

• economics

• politics

• sociology

• psychology

For example, here is a ‘game’ I often play with my students. Some students want to get a passing grade while coming to class as little as possible. I want to make them come to every class. But, I want to spend as little time on this task as possible.

What should I do? I don’t want to take attendance every day, because that takes a lot of time in a big class. I give quizzes on random days and make it hard for students to pass unless they take most of these quizzes. I only need to give a few quizzes, but the students need to come to every class, since they don’t know when a quiz will happen.

How do the students respond? Lots of them come to class every time. But some try to ‘bend the rules’ of the game, mainly trying to get my sympathy. They invent clever excuses for why they missed the quizzes: dying grandmothers, etc. They try to persuade me to ‘drop the lowest quiz score’. They try to convince me that it’s unreasonable to make quizzes count for so much of the grade. After all, it’s easy to get a bad score on a quiz, when there’s not much time to answer a question about something you just learned recently.

How do I respond? Only the last idea moves me. So, I set things up so missing a quiz gives you a much worse score than taking the quiz and getting it completely wrong. In fact, just to dramatize this, I give students a negative score if they miss a quiz.

How the students respond? Some of them argue that it’s somehow evil to give people negative scores. But at this point I bare my fangs, smile, and nod, and the game ends.

It’s important to emphasize that other students have different goals: some want to come to class every time and learn as much as possible! In this case my goals and the students’ goals don’t conflict very much. As we’ll see, in mathematical game theory there are plenty of games where the players cooperate as well as compete… or even just cooperate.

Mathematical game theory tends to focus on games where the most important aspect of the game is choosing among different strategies. Games where the most important aspect is physical ability are harder to analyze using mathematics. So are games where it’s possible to ‘bend the rules’ in a huge number of different ways.

Game theory works best when we can:

• list the set of choices each player can make,

• clearly describe what happens when each player makes a given choice.

• clearly describe the ‘payoff’ or ‘winnings’ for each player, which will of course depend on the choices all the players make.

Classifying games

We can classify games in many different ways. For example:

• The number of players. There are single-player games (like solitaire), two-player games (like chess or ‘rock, paper, scissors’), and multi-player games (like poker or Monopoly).

• Simultaneous versus sequential games. There are games where all players make their decisions simultaneously, or if they do not move simultaneously, the later players are unaware of the earlier players’ actions, making them effectively simultaneous. These are called simultaneous games. There are also games
where some players make decisions after knowing something about what other players have decided. These are called sequential games.

The games people play for fun are very often sequential, but a surprisingly large part of the game theory we’ll discuss in class focuses on simultaneous games. ‘Rock, paper, scissors’ is an example of a simultaneous game, but we’ll see many more.

• Zero-sum versus nonzero-sum games. A zero-sum game is one where the total payoff to all the players is zero. Thus, any player benefits only at the expense of others.

An example of a zero-sum game is poker, because each player wins exactly the total amount their opponents lose (ignoring the possibility of the house’s cut). Chess, or any other two-player game with one winner and one loser, can also be seen as a zero-sum game: just say the winner wins $1 and the loser loses $1.

In nonzero-sum games, the total payoff to all players is not necessarily zero. An example is ‘chicken’, the game where two people drive their cars at each other, and both cars crash if neither pulls off the road. When this happens, both players lose. There are also games where both players can win.

In two-person zero-sum games, the players have no reason to cooperate, because whatever one wins, the other loses. In two-person nonzero-sum games, cooperation can be important.

• Symmetric and non-symmetric games. In a symmetric game the same rules apply to each player. More precisely, each player has the same set of strategies to choose from, and the payoffs to each player are symmetrical when we interchange which player chooses which strategy.

In a non-symmetric game, this is not the case. For example, we can imagine a non-symmetric version of poker where my hand always contains at least two aces, while no other player’s does. This game is ‘unfair’, so people don’t play it for fun. But games in everyday life, like the teacher-student game I mentioned, are often non-symmetric, and not always fun.

• Cooperative and non-cooperative games. A game is cooperative if the players are able to form binding commitments. That is, some players can promise to each that they will choose certain strategies, and these promises must be kept. In noncooperative games there is no way to make sure promises are kept.

Our legal system has the concept of a ‘contract’, which is a way people can make binding commitments.

Warning

There’s a lot more to say about these ways of classifying games. There are also other ways of classifying games that we haven’t discussed here. But you can already begin to classify games you know. Give it a try! You’ll run into some interesting puzzles.

For example, chess is a two-person zero-sum sequential non-cooperative game.

Is it symmetric? The strategies available to the first player, white, are different from those available to the second player, black. This is true of almost any sequential game where the players take turns moving. So, we can say it’s not symmetric.

Or, we can imagine that the first move of chess is flipping a coin to see which player goes first! Then the game becomes symmetric, because each player has an equal chance of becoming white or black.

Puzzle

I may put some puzzles on this blog, which are different than the homework for the course. You can answer them on the blog! If you’re a student in the course and you give a good answer, I’ll give you some extra credit.

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