Game Theory (Part 7) - Functions, Limits and Derivatives

This post is part of my course on game theory. For an index see here. The course follows the one by Ben Polak on the Open Yale website.

Over the last few posts we’ve been working our way through the concept of best response. We’ve now reached an impasse: to take our analysis to the next level we’ll need to know how to find the maximum value of a function. This requires some elementary calculus. Some readers might be fluent in this area of mathematics. If so, they can skip the next few parts (there will probably be three of them). For those who aren’t au fait with calculus, I’m going to quickly run through the basics and provide links to some other resources.

Listen, I’m not particularly comfortable with calculus myself, and I certainly wouldn’t offer myself up as an internet oracle on this topic. But the level of calculus required for the types of game theory problem covered in this course is pretty low. If I can understand it, anyone can.

(Oh and incidentally, if there are any calculus gurus reading this, they might be kind enough to let me know if I make a mistake.)


1. What is a function?
Since our goal is to learn how to find the maximum value of a function, we must first ask: what is a function? This needn’t detain us too long. A function is simply a mathematical way of depicting the relationship between two variables: an independent variable (usually denoted by an “x”) and a dependent variable (usually denoted by a “y” or “f(x)”).

As the value of the independent variable changes, so too does the value of the dependent variable. In other words, every value of x is associated with one value of y. The domain of a function is the set of all x where the function can be meaningfully applied. The range of a function is the set of y or f(x) values that result.

Here’s an example:




According to this function, as the value of x increases (or decreases) the value of y increases in such a way that it is equal to the square of the x value. This function can be depicted graphically as follows.

Here’s another function:



According to this function, every unit increase in x leads to ten unit increase in y. This can be depicted graphically as follows:

2. What is a Limit?
So much for functions, now we move on to limits. Here’s a classic example of a limit in action:

Achilles wants to cross the road. The road is 10m wide. Before he does so, a rather annoying tortoise waddles up beside him and tells him its impossible to cross the road. The tortoise reasons as follows: in order to cross a road which is 10m in width, Achilles will first have to cross half that distance (5m); and in order to cross the remaining distance of 5m, Achilles will first have to cross half that distance (2.5m); and of course in order to cross the remaining 2.5m after that, he’ll first have to cross 1.25m; and so on ad infinitum. Since there are infinite number of half distances to cross, and since it is impossible to cross an infinite space, Achilles will never be able to cross the road.

What we have here is a limit. There is an infinite series (5 + 2.5 + 1.25.....) which has a limiting value of 10. By repeatedly crossing half distances, Achilles gets closer and closer to the full 10m distance, but never quite reaches it.

Although a little weird, limits are mathematically tractable. Indeed, when calculating the derivative of a function -- something that must be done when finding its maximum value -- one is finding a limit of a certain sort.


3. What is a Derivative?
Finally, we have the concept of a derivative. Put simply, a derivative is the rate of change of a function. More properly, it’s the rate at which the dependent variable changes with respect to the rate at which the independent variable changes. It’s easiest to understand this with an example in mind. And an easy example to work with is the y = 10x one from above.

Imagine this function depicts a runner (like Achilles) running along a road. The independent variable here is time and it is represented on the x-axis; the dependent variable is distance travelled and it is represented on the y-axis. Now let’s ask the question: what is the rate of change of y with respect to x? The answer, obviously, is 10: there are ten unit changes in y with respect. This is the derivate of this particular function.

That was pretty easy. An even easier example would be where the function depicts a runner who is standing still 10 meters from the start line. In this case y = 10 at all times. And so the dependent variable does not change at all with respect to the independent variable. Consequently, the derivative of this function is zero. There is a generalisable lesson from this as well: the derivate of any constant is always equal to zero.

A far more interesting derivative is that which can be calculate the accelerating force of gravity. This is discussed at length in the second episode of the 1980s TV series The Mechanical Universe . You can find it here.

Okay, that’s it for now. In the next part, we’ll go through the basic method for calculating a derivative in more detail.


Resources
In terms of books, I would recommend Calculus Made Easy by Silvanus Thompson. This is a classic text that was updated a few years back by Martin Gardner. It focuses heavily on facilitating comprehension of calculus, i.e explaining the rationale behind the various calculations. Most of the examples used in this post were taken from this book. I’d also recommend the Schaum’s Outlines books dealing with calculus. They focus more on practical applications and problem-solving.

In terms of videos, Salman Khan has quite a number of tutorials on calculus over at the Khan Academy website. I also found the youtube series by the Calculus Tutor to be helpful.

Game Theory (Part 6) - The Penalty Kick Game

This post is part of my course on game theory. For an index, see here. The series follows the Ben Polak course on the Open Yale website.

In the previous entry, we introduced the whole idea of best response, and showed how you could calculate your best response for all possible probabilities that you might attach to your opponent’s strategies.

Now we can have a little fun with idea by looking at the penalty kick game. After that, we can give a formal definition of best response.




1. Penalty Kicks
The penalty kick game is a subgame within football (soccer). One player (the kicker) must kick the ball from the penalty spot towards the goal; the other player (the goalie) must try to prevent the ball from going in the net. Here’s a pretty spectacular example of this.



In the game, the kicker must choose which part of the goal he is going to kick the ball towards. The goalie must anticipate this and dive in the direction in thinks the ball is going to go. Suppose, for sake of illustration, that the kicker has three options (left, middle, right) and the goalie has two (left, right). The relevant payoffs are measured in terms of the % chance of scoring. So, working with the following payoff matrix, the kicker has a 90% chance of scoring if he kicks to the left and the goalie dives to the right. The goalie’s payoffs are given as negative percentages. The game is definitely skewed in favour of the kicker, which seems to be true in the real world as well.

Without taking into account the probability with which the goalie will dive in a particular direction, we can see that L is a best response (for the kicker) to r; R is a best response to l; and M is never a best response.


2. Calculating Best Response
Once again, the foregoing analysis is incomplete. We need to draw a graph plotting the best response curves relative to the different probabilities of the goalie diving in one direction or the other. The following graph does exactly that.

In this graph, the red line represents the expected payoff of kicking to the right; the blue line represents the expected payoff of kicking to the left; and the green line represents the expected payoff of kicking to the middle.

Notice anything interesting?

Kicking to the middle is never a best response (the green line always yields a lower payoff than blue or red). If you want to maximise your expected payoff, then you should never kick to the middle. This is an important lesson, one that’s worth repeating with added emphasis:

Lesson: You should not choose a strategy that is never a best response.

3. Penalty Kicks in the Real World
Of course, all this advice about never kicking to middle is a function of the model we created. We don’t actually know that kicking to the left when the goalie dives to the right leads to a 90% chance of scoring - we’re just guessing.

Fortunately, some economists actually went out into the real world and collected some data on penalty kicks. One obvious thing they had to correct for in their model was the footedness of the players. Players will either be left footed or right footed (or maybe equally good with both feet). In general, it’s easier for a right footed player to kick to the left and vice versa for a left-footed player. This means that the probability of scoring when kicking to your preferred side is likely to be higher.

So correcting for footedness and ignoring the middle, the following are the percentage chances of scoring as discovered in the real world. (The data comes from this paper by Chiappori et al). In case your wondering, "left" on this model just means “naturally preferred direction”.

As you can see, the payoffs are not all that different from those in the original model.

There are other ways in which this model may be deficient. In particular it might fail to take into consideration other decisions that the kicker has to make, e.g. the flight of the ball (high or low) or the strength of the kick.

It might turn out that kicking to the middle is a best response if the kicker can get a lot of pace on the ball but must sacrifice accuracy when doing so. This is depicted in the following graph.

4. Formal Definition of Best Response
I think we’ve had enough of the penalty kick game by now. One thing remains to be done: provide a formal definition of best response. Here we go:

Best Response: Player i’s strategy Si* is a best response to the strategy S-i of the other player(s) if: 

• Ui (Si*, S-i) ≥ Ui (Si’ , S-i) for all Si’ ∈ Si (the set of all strategies for i)

Okay, that’s it for now. We’re going to have to take a detour into some elementary calculus in the next entry. It’s very straightforward but it is necessary for understanding some of the models we’re going to be looking at in the future.

Game Theory (Part 5) - Best Response and Expected Utility

This post is part of my course on game theory. For an index, see here. The course follows the one by Ben Polak on the Open Yale website.

Over the past few entries we have been considering domination and the iterated deletion of dominated strategies. In today’s entry we move away from those concepts and begin our inexorable journey to the Nash Equilibrium. We do so by studying two key ideas: (i) best response and (ii) expected utility.



1. Best Response
Consider, for a moment, the following game. There is no story motivating its structure, so you’ll need to analyse it in the abstract.

The interesting thing about this game, for our purposes, is that it features no dominated strategies. This means we can’t utilise the method of iterated deletion when trying to solve it. So what can we do?

Well, we can appeal to the notion of best response. In other words, we can work out which strategies are the best responses for one player to the strategies of the other player. A strategy is a best response if it yields the highest possible payoff for one player, holding the other player’s choice of strategy fixed.

Looking at the game matrix above, and analysing it from the perspective of Player 1, we can say the following:

U is a best response to L. In other words, if Player 2 chooses L, then Player 1 does best by choosing U in response. 

M is a best response to R. In other words, if Player 2 chooses R, then Player 1 does best by choosing M in response. 

D is neither a best response to R or to L. However, it does better than M against L and better than U against R.

We can perform a similar analysis from the perspective of Player 2. This would show that L is a best response to M, and R is a best response to U and D.



2. Expected Utility
That seems straightforward enough, but how useful is this information? One obvious problem is that whether a strategy is a best response or not depends entirely on what you think the other player is doing. And since you usually face some uncertainty or doubt about what the other player is going to do, this means you have to incorporate probabilities into your analysis.

If probabilities have to be incorporated into the analysis of a game, then we are confronted with the notion of expected utility. The expected utility of a payoff is the payoff attached to a particular outcome multiplied by some relevant probability. In game theory, the relevant probabilities are assumptions or beliefs about what the other player(s) are going to do.

Looking back once more to the game matrix given above, let’s assume that we are Player 1 and we believe Player 2 switches between his strategies with probability (0.5, 0.5). In other words, he plays L half of the time and R half of the time. This affects how we calculate our expected payoffs in the following manner:

The Expected Utility of:

• U vs. (0.5, 0.5) = (0.5)(5) + (0.5) (0) = 2.5

• M vs. (0.5, 0.5) = (0.5)(1) + (0.5)(4) = 2.5

• D vs. (0.5, 0.5) = (0.5)(4) + (0.5)(2) = 3

Notice anything interesting about this? All of sudden, D has become the best response. Of course, this is only because of the specific probabilities we attached to Player 2’s strategies. It could be that 2 switches between his strategies with probability (1/3, 2/3) or (2/3, 1/3). Indeed, there are a potentially infinite number of different probability combinations.



3. Expected Utility and Best Response
It would be impossible to work our way through all of these different combination in the same manner as we did for the combination (0.5, 0.5). So is there any other way we can work out the best response for player 1 to all possible probability combinations of player 2? Yes there is: by drawing the following picture.

As you can see, this picture depicts the expected utility for each strategy of Player 1 (U, M, D) against every possible probability combination of Player 2’s strategies (p, 1-p). We can now use this graph to work out all of Player 1’s best responses. As in the following diagram.

This diagram shows that for all probability combinations to the left of x, U is Player 1’s best response; for all probability combinations to the right of y, M is Player 1’s best response; and for all probability combinations between x and y, D is Player 1’s best response.

This seems like useful information, and it can be made even more useful by solving for x and Y. Here’s how you would solve for x:

1) Replace p(R) with x in your expected utility calculations e.g. 

• Expected Utility (EU) of (D, p(R)) = (1-x) (4) + x(2)
• Expected Utility (EU) of (U, p(R)) = (1-x) (5) + x(0)

2) Set the EU equations for D and U equal to each other. Why? Because, looking back to our diagram, these two lines intersect at x. The resulting calculation looks like this: 

• (1-x)(4) + x(2) = (1-x)(5) + x(0) 
• 4 - 4x + 2x = 5 - 5x 
• 3x = 1 
• x = 1/3

You can follow a similar procedure when solving for y, just set the the EU-equations for D and M equal to each other.

Okay, that’s all for today. In the next entry we’ll look at penalty kicks.

Game Theory (Part 4) - The Median Voter Theorem

This post is part of my course on game theory. For an index, see here. The course follows the lectures by Ben Polak which are available on the Open Yale Courses website.

In the previous post we discussed the iterated deletion of dominated strategies and the concept of common knowledge. In this post, we will continue to explore these two issues by looking at an easy, but famous theorem from political science: the Median Voter Theorem.


1. The Set Up
There are two candidates running for president. Each candidate must position themselves along the ideological left-right axis in order to appeal to voters. Suppose there are ten possible ideological locations along this axis. Suppose further that voters are evenly distributed along this axis, i.e. approx. 10% of the pool of voters are located at each of the ten ideological positions. See the following diagram.

This election can be modelled as a game. The candidates are the players; the strategies are the positions they can choose along the ideological spectrum; and the payoffs are the percentages of the vote they manage to capture. Obviously the goal of each player is to maximise their share of the vote.

To help them decide what their strategy should be we need first to introduce a couple of rules about the voting patterns of the electorate. Suppose that voters always prefer the candidate that is closest to their own ideological position. This means that an extreme right wing voter will vote for a left wing candidate provided that candidate is less left wing than their rival. In addition, suppose that if the two candidates are an equal distance from the voter’s preferred position, the vote will be split evenly between the two candidates. In other words, one candidate will get 5% of the available 10%, and the other candidate will get the remaining 5%.

For some reason, as I write this down, it sounds very complicated. But it’s really not.


2. Iterated Deletion of Dominated Strategies
Now that we have the set up for the game, we can proceed to solve it for both candidates. To do this, we will once again make use of the iterated deletion of dominated strategies. Remember, this involves putting yourself (if you are a player) in the shoes of your opponent and thinking about how they would respond to your choices.

Let’s start with candidate A and see what would happen to him if he decided to position himself at location number 1 (i.e. he chooses the extreme left wing position).

It’s pretty clear that this would be a silly thing to do. Why? Because location 2 dominates location 1: it yields a higher payoff no matter what candidate B does. To see this, work out the expected payoff for A of location 2 compared to location 1, against all possible strategies of candidate B. We’ll go through some of the relevant calculations here. An obvious pattern will emerge after a few, thereby rendering the rest of the calculation unnecessary:

Assuming B plays location 1 

• Ua (1, 1) → A gets 50% of the vote, B gets 50% of the vote 
• Ua (2, 1) → A gets 90% of the vote, B gets 10% of the vote

Assuming B plays location 2 

• Ua (1, 2) → A gets 10% of the vote, B gets 90% of the vote 
• Ua (2, 2) → A gets 50% of the vote, B gets 50% of the vote

Assuming B plays location 3 

• Ua (1, 3) → A gets 15% of the vote, B gets 85% of the vote 
• Ua (2, 3) → A gets 20% of the vote, B gets 80% of the vote

Assuming B plays location 4 

• Ua (1, 4) → A gets 20% of the vote, B gets 80% of the vote 
• Ua (2, 4) → A gets 25% of the vote, B gets 75% of the vote

We could continue on through all ten locations, but its pretty clear by now that no matter what B does, A is always better off playing location 2 instead of location 1. Thus, 1 can be considered a dominated strategy.

Since 1 is dominated, we should eliminate it from the pool of viable strategies. What happens then? Location 2 becomes dominated by location 3. In other words, A will find that it’s always better to choose location 3, irrespective of what his opponent does. Thus, 2 should also be removed from the pool of viable choices. I leave the proof of this to the reader.

It is important to note that 3 only becomes a dominant strategy after 1 has been removed from the pool of viable strategies.

The reasoning that underlies the deletion of 1 and 2 works from the opposite side as well, i.e. for locations 10 and 9. What’s more, the reasoning works until all strategies apart from 5 and 6 are eliminated for both candidates.

This is the prediction of the median voter theorem: both candidates end up positioning themselves in the middle of the ideological spectrum.

3. Problems with the Model
Although the Median Voter Theorem is sometimes thought to work well in predicting the behaviour of U.S. presidential candidates, there are certain key weaknesses in the model.

First, the model assumes that voting preferences are arrayed along a single dimension. It could be argued in response that political preferences are in fact multidimensional. Strangely, although I think political preferences should be multidimensional, I find, in practice, there is much to be said for the idea that people align themselves along a simple, single left-right dimension.

Second, the model assumes that preferences are equally distributed along the spectrum when in reality they might be skewed towards one end or the other. Actually, it turns out that this isn’t that big of a problem. It just means that candidates will/should position themselves in the middle of whatever the actual distribution is.

Third, the model assumes that candidates can simply pick the ideological position that suits their needs. In reality, candidates come with histories (voting records, policy statements etc.) that might make it difficult for such positioning to be credible to the electorate.

Finally, the model assumes that every voter actually votes. If not-voting is an option, things become more complicated. The model also becomes more complicated when there are more than two candidates running for election.

Game Theory (Part 3) - Weak Dominance, Iterated Deletion and Common Knowledge

This is part 3 of my series on game theory. For an index, see here. The series follows the lectures of Ben Polak which are available on the Open Yale Courses website.

In the previous entry, we introduced some of the formal notation needed for game theory and used it to give a formal definition of the concept of strict dominance. In this entry, we continue by first examining the concept of weak dominance and by then exploring the iterated deletion of dominated strategies, as well as the concept of common knowledge.


1. The Hannibal Game
Hannibal Barca was a famous Carthaginian military commander and tactician. He is most renowned for marching an army, complete with war elephants, through the Pyrenees and the Alps into Northern Italy, during the Second Punic War. Following his arrival in Italy he won a number of notable victories over the Roman army.

His choice of invasion route is widely held-up as an example of shrewd military planning. But was it really that shrewd? We can’t provide a definitive analysis here, but we can construct a simple game theoretic model that provides some insight.

Here’s the set up: An invader is thinking of invading a country and there are two passes through which they can choose to invade. One of the passes is hard and one is easy (from the invader's perspective). The defender must defend but only has enough troops to defend one pass.

Payoffs in this game will be measured in terms of the number of battalions that the invader will arrive with (or are captured by the defender). There is a maximum of two battalions. Suppose that if both players choose the easy path, the defender can expect to win one battalion from the invader. Suppose that if both choose the hard pass, the defender will win both battalions. Finally, suppose that the hard pass is so difficult that even if the invader is unimpeded, he can expect to lose a battalion.

The following is the game matrix for this game:

If you were the defender in this game, what would you choose to do? Think about it for a moment or two and then come back to me....


What did you decide? It is suggested that you should choose to defend the easy pass even though it is not a strictly dominant strategy. Why do we make this suggestion? Well consider the following:

• (i) If you defend the easy pass, then the invader is indifferent between the easy pass and the hard pass. In other words, he could choose either since they both yield the same payoff for him.

• (ii) If you defend the hard pass, then the invader definitely prefers the easy pass.

Technically, what we say is that for the invader, the easy pass weakly dominates the hard pass. Which gives us the following definition:

Weak Dominance: Player i’s strategy Si* is weakly dominated by strategy Si if: 

• Ui (Si, S-i) ≥ Ui (Si*, S-i) for all S-i and; 

• Ui (Si, S-i) > Ui (Si*, S-i) for some S-i.

Clearly, this holds true for the invaders strategy e relative to strategy h.

According to this model, Hannibal’s decision to invade via the Alps seems irrational. But the model is only as good as the assumptions that go into it. In our case, we simplified massively from the original set of circumstances. In reality, it is likely that there were uncertainties about the payoffs associated with the different routes. These uncertainties could have made Hannibal’s decision more rational.


2. The Numbers Game
One of the key ideas in game theory is dominance solvability. This is when you solve a game through the iterated deletion of dominated strategies. Here’s a simple game that illustrates this phenomenon:

Suppose you are in a class of 50 students (the precise number doesn’t matter) and you are all asked to play the following game. You are given a sheet of paper on which you must write a number between 1 and 100. You are told that the average number for the class will be calculated and the person who writes the number that is closest to being 2/3 of that average will win a prize of some kind. Assuming you would like to win, what number should you write on the sheet of paper?

This game forces you to make use of one of the lessons from part one: namely, putting yourself in other people’s shoes, imagining what they are likely to do, and then determining your own strategy in response to your assumptions about the other player.

To solve the game, I suggest picking an expected average number (pretty much at random) and see whether writing a number that is two thirds of this average holds up to scrutiny. As follows:

• (1) If everyone were to write a number at random, then we might expect the average number in the class to be 50, thus if you wrote a number that was roughly two thirds of 50, you could expect to win. Therefore, you should write 33 or 34.

• (2) The problem is that people don’t choose at random. If they follow the same reasoning pattern as you do, then 33-34 would be the expected average. So you should write a number that is two thirds of this average, i.e. approx. 22.

• (3) But, of course, this reasoning process is available to all players, and if they follow it, then 22 would be the expected average. So you should write a number that is two thirds of this.

• (4) This reasoning process continues on and on until you reach the number 1.

What’s happening in this game? The answer: an iterated deletion of dominated strategies. To see this in more detail, start the analysis once again from scratch. Note that any number chosen above 67 is going to be weakly dominated by 67, so you can remove any number above 67 from the set of viable strategies. Once you do this, any number above 45 becomes weakly dominated and so must be removed from the set of viable strategies. This process of elimination continues until you reach the number one.

Of course, if you really did have to play this game, you should take into account how strategically savvy your opponents are.


3. Common Knowledge
The numbers game illustrates another important phenomenon in game theory: common knowledge. Two examples will help us to understand this phenomenon.

Consider first the following diagram. It depicts two people wearing pink hats. Person X can see that person Y is wearing a pink hat; person Y can see that person X is wearing a pink hat; but neither knows the colour of their own hat. In this case, the fact that both are wearing pink hats is not common knowledge, it is only mutual knowledge.

This example suggests that common knowledge is a pretty subtle thing. Formally, it is defined as follows:

Common Knowledge: Proposition P is common knowledge between X and Y, iff X knows P and Y knows P, X knows that Y knows P and Y knows that X knows P, X knows that Y knows that X knows P and so on ad infinitum.

Common knowledge is thought to underly much of social life and can create enormous problems. This is humorously illustrated by our second example: a famous scene from the movie The Princess Bride.

Game Theory (Part 2) - The Formal Ingredients

This is part two of my series on game theory. For an index, see here. The series follows the lectures of Ben Polak, which are available on the Open Yale Courses website.

Last time out, we had a gentle introduction to the kind of thinking required in game theory. Game theory can be a lot of fun since it frequently involves playing games. But there is also some serious mathematics underpinning the whole field. Game theorists use the formal language of mathematics to build models of real world situations. In this post we’ll introduce some of this formal language.


1. The Ingredients of a Game
A game is any interaction between two or more rational (or purposive) agents. In any such interaction, a rational decision-maker will have to take into consideration what the other agent is likely to do. In other words, he will have to anticipate the actions and choices of others. This differentiates a game from a decision problem, which involves no anticipation.

Whenever you set about modelling a strategic interaction, you must ask yourself four key questions:

• (1) Who are the players?
• (2) What are their strategies or actions?
• (3) What are their payoffs?
• (4) What kinds of information do the players have at their disposal?

A word or two must be said about these questions.

The first question is relatively straightforward and simply forces us to consider who the decision-making entities are in the game. One thing to be wary of is that the player in a game is not necessarily isomorphic with an individual human being or organism. Players could be entire organisations who, for the purposes of building the model, can be treated as one agent.

The second question raises the distinction between an action and a strategy. An action is simply a choice that an agent can take at a particular round or node in a game. A strategy is a set of actions covering every round or node in a game. In games which have only one round, actions and strategies are equivalent. In games that have two or more rounds, they are distinct.

The third question raises the thorny issue of what exactly is a payoff. For the purpose of this series we won’t get into this issue. A payoff is taken as a measure of the satisfaction or desirability of an outcome for a player. One distinction to keep in mind is that between ordinal and cardinal payoffs. An ordinal payoff is a ranking; a cardinal payoff is supposed to be some kind of real number value. If one is dealing with uncertainties or probabilities, cardinal payoffs are required.

The fourth question is about the knowledge that the players have of the formal structure of the game. For the first part of this series, we will assume that the players have perfect information about the games. This means that they know who the other players are, what actions and strategies are available to them, and what payoffs they associate with particular outcomes.

Formally, we use the notation in the following diagram to represent each of these elements (minus information).

2. Notation in Action
We can now employ this notation in the analysis of a game. We can also use it to define some of the concepts, such as strict domination, that we introduced in part 1. Consider the game in the following diagram. There is no particular story or scenario motivating the model; it is purely an abstract mathematical entity.

Now ask yourself, are there any strictly dominated strategies in this game? Consider it first from the perspective of player 1. Hold player 2’s strategies fixed and determine which of 1’s strategies is best response to each of player 2’s. It is pretty clear when you perform this exercise that none of player 1’s strategies are strictly dominated. Each is a best response under different assumptions about player 2.

Now look at the game from the perspective of player 2. Again, hold player 1’s strategies fixed and work out which of player 2’s strategies are best responses. If we perform this exercise it becomes clear that although no single one of 2’s strategies dominates all the others, the strategy “centre” does strictly dominate “right”. This is because centre always yields a higher payoff than right, irrespective of what player 1 does.

This leads us to the following definition of strict dominance. It is stated in the diagram above but since it is so important it deserves to be repeated here:

Strict Dominance: Player i’s strategy Si* is strictly dominated by player i’s strategy Si if: 

• Ui (Si, S-i) > Ui (Si*, S-i) for all S-i

If we were to continue our analysis of the game given in the previous diagram, we would delete player 2’s strictly dominated strategy (Right) and continue to solve it as a 2 x 2 game, instead of as a 3 x 2. This leads us to the concept of iterated deletion of strictly dominated strategies, which we’ll be discussing in future entries.

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.

Course on Game Theory

I think I’ve mentioned, on occasion, the role that game theory plays in my own thinking. Despite my fascination with this analytical tool, I have never actually taken a formal course in game theory. Instead, I dabble with various elements of it as they seem relevant to my own research work.

To make up for my lack of training in this area, I have gone through several of the online video lecture series on game theory. In particular, the following three:

Ben Polak, Open Yale Courses - Game Theory

John Fountain, University of Canterbury, New Zealand

Kathleen Bawn, UCLA - Politics, Strategy and Game Theory

Of these three courses, I found Ben Polak’s to be, by far and away, the best. He is an engaging lecturer and, on the whole, his classes are fun to watch. That said, the other courses cover some areas that he doesn’t and so can be beneficial as supplements. For example, Bawn’s course focuses on political examples, which I happen to like.

Anyway, in order to consolidate what I have learned from these courses, and to share it with those who would like to learn more about this topic, I have decided to write up my own introductory series on game theory. This series will follow the format and sequence of Polak’s Yale lectures, but will hopefully be self-contained (i.e. you won’t need to watch the lectures to fully understand it). It will not shy away from the formal and mathematical concepts employed in game theory, but it will try to explain those concepts in a fairly elementary way.

This post will serve as an index to the entire series.

1. The First Four Lessons
2. The Formal Ingredients
3. Weak Dominance, Iterated Deletion and Common Knowledge
4. The Median Voter Theorem