Pages

Saturday, April 9, 2011

Game Theory (Part 1) - First Four Lessons



As announced, I will be writing a series of posts outlining the basic concepts in game theory. The series will follow Ben Polak’s lectures, which are available here. This first post covers the first of Polak’s lectures. Although officially Polak’s lecture offers five lessons, I have reduced this to four since the fifth is just a joke about Yale students.

We begin, as we should, with a game. And since the source material comes from a college course, what better way to get the students enthused than with a game about their grades.


1. Grading Game
Two players (A and B) must play a game in order to determine which grade they will get in a course. They do so by choosing to put either α or β in a box. Their choice will then be paired with the choice of the other player. As a result, there are four possible outcomes in this game:

  • (a) If A puts α in the box and B puts β in the box, then A gets an A-grade while B gets a C-grade.
  • (b) If both A and B put α in the box they will both get B-minus grades.
  • (c) If A puts β in the box and B puts α in the box, then A gets a C-grade while B gets an A-grade.
  • (d) If both A and B put β in the box then they will both get B-plus grades.

This information can be a little difficult to follow when expressed in these terms. We can make things easier by arranging it in a box (called either a payoff or outcome matrix). In this box, A is the row-player and B is the column-player. The grades that are written in the four different boxes represent the “payoffs” to the respective players, with player A’s grades being written first.


If you’ve never come across any game theory before, you might like to stop reading at this point and think about what you would do if you were playing this game.


2. Solving the Game
So, what did you choose to do? The prediction (and, indeed, the recommendation) from game theory is that you would choose α. Furthermore, the prediction is that your opponent will also choose α. This means, of course, that you will both end up with B-minus grades. This is disappointing since if you both played β you would have received a higher grade.

Why do we assume that both will choose α? The answer is that α strictly dominates β. A more formal definition of strict domination will be given in a subsequent post. For now, an informal definition will suffice:


  • Strict Domination = a strategy (α) strictly dominates a strategy (β) if the payoff from α is greater than the payoff from β, regardless of what the other player chooses to do.


It should be apparent from the payoff matrix given above that α strictly dominates β because it always yields a higher grade than β, irrespective of what the other player does. This brings us to our first lesson:
Lesson 1: You should not play a strictly dominated strategy.
The grading game as described has the structure of a Prisoners’ Dilemma. This means that there is a “temptation payoff” (the A-grade in this case) and a “sucker’s payoff” (the B-grade) that brings about the strict domination. It also yields a sub-optimal outcome for both players. This gives us our second lesson:
Lesson 2: Rational choice can lead to outcomes that are sub-optimal (Pareto Inefficient)
This is a significant lesson since PDs arise in many socially important situations.


3. Evil Gits and Indignant Angels
The grading game outlined above can be depicted using numbers instead of grades as in the following matrix. The numbers are supposed to represent the utilities that players attach to the respective outcomes.



Note that this has been called the “evil gits”-version of the grading game. Why is this? Well, it is because the solution to a game is determined by the payoffs that the players attach to the respective outcomes. In this case, we assume that the players want to secure as high as possible a grade for themselves, even if this comes at the expense of others. This assumption could be wrong.

It could be that the players, far from being evil gits, are indignant angels. This would mean that they get upset (experience a disutility) if they profit at someone else’s expense, and, similarly, they get indignant if someone else profits at their expense. In the context of the grading game, this results in the following change in the game:



This dramatically alters our proposed solution to the game. It is no longer the case that one strategy strictly dominates another. To jump the gun a little bit, α would be your best response if your opponent played α, whereas β would be your best response if your opponent played β. What you end up choosing depends entirely on your assumption about your opponent. This gives us our third lesson:

Lesson 3: Payoffs matter - changing the payoffs changes the strategy

We can now imagine a final variant of the game. This one involves an evil git (A) playing against an indignant angel (B). It has the following structure:



The analysis of this game is slightly more complicated than previous two.

First, look at it from the perspective of the evil git. It’s pretty clear that from his/her perspective α strictly dominates β.

The indignant angel might reason his/her way through the game in the following manner:

  • (1) If A plays α, my best response would be to play α.
  • (2) If A plays β, my best response would be to play β.
  • (3) A is almost certainly going to play α, since that is a strictly dominant strategy for him/her.
  • (4) Therefore, I should also play α.


Again, this leads to a sub-optimal result and provides us with our fourth and final lesson:

Lesson 4: When analysing a game, put yourself in the other player’s shoes and try to figure out what they would do.

Okay, that’s it for this first post on game theory. In the next entry, we will look in more detail at the formal ingredients of a game.

1 comment: