Game Theory – The Prisoner’s Dilemma and Golden Balls

May 14, 2009

It’s hard to come in contact with Game Theory without coming across The Prisoner’s Dilemma which is a non-zero-sum game played between two people who are seemingly pitted against eachother. The following is the form in which I was introduced to The Prisoner’s Dilemma recently:

Alice and Bob are gangsters in the Chicago of the 1920s. The District Attorney knows that they are guilty of a major crime, but is unable to convict either unless one of them confesses. He orders their arrest, and seperately offers each the following deal:

  1. If you confess and your accomplice fails to confess, then you go free.
  2. If you fail to confess but your accomplice confesses, then you will be convicted and sentence to the maximum term in jail.
  3. If you both confess, then you will both be convicted, but the maximum sentence will not be imposted.
  4. If neither confesses, you will both be framed on a tax evasion charge for which a conviction is certain (but the sentence is not great).

There are then two possibilities for each gangster, either to cooperate with the other gangster, or to betray the other gangster. This for quite some time confused me as I wasn’t sure if cooperate was to cooperate with the police, or to cooperate with the other gangster. We can now build the following matrix for The Prisoner’s Dilemma.

Coop Betray
Coop
Short
Short
Free
Max
Betray
Max
Free
Long
Long

I’ve used the terms ‘Free’, ‘Short’, ‘Long’ and ‘Max’ to give you an idea of the length of time they will stay in jail for, the only one that needs explanation, I would hope, is ‘Free’ which means they spend no time in jail at all and only occurs if they Betray (Confess) and the other party Cooperates (Stays quiet).

The Dominant Strategies are marked in bold and contrary to what we would like to think, the rational solution is always to betray humanity even though you’d both get a shorter sentence if you both cooperated. This is because if I know you’re going to Cooperate I should always Betray you, that way I get off free, it is my best strategy. It must be noted that this is based on a one off game where we will never meet again and probably have never met in the first place, it makes it more interesting if you change things to say that both parties know eachother and therefore have a reason to cooperate.

I won’t go in to the specifics as I want to talk about Golden Balls which is very interesting, but you can make both players of The Prisoner’s Dilemma have cooperation as their dominant strategy by repeating the game indefinatley. This way if I betray you this time I know you’ll betray me next time and we’ll both just end up betraying each other, so, to save this happening, we both cooperate forever.

After looking in to The Prisoner’s Dilemma a bit more I discovered what most people call a real-world example of The Prisoner’s Dilemma in the final round of a gameshow called Golden Balls. This was a TV game-show that aired on ITV in the United Kingdom in 2007 and was hosted by a comedian called Jasper Carrot. The main workings of the game are unimportant, what matters here is the final round. Each contestant, of which there are two, chooses a ball, either Split, which means they try and split the money or Steal which means they try and steal the money. There are three outcomes as follows:

  1. Both players choose Split:- The winnings are split equally between them.
  2. One player chooses Steal, the other Split:- The player who Stole gets all the money.
  3. Both players choose Steal:- No-one gets any money.

To compare it to The Prisoner’s Dilemma, (1) is the same as both gangsters cooperating and getting a short sentence, (2) is the same as one gangster choosing to betray the other and the other gangster cooperating and (3) is the same as both gangsters betraying eachother and both getting a long sentence. From this we can build a simple table that gives payoffs of 100% for winning all the money, 50% if they split the money and 0% if they don’t get anything.

Split
(coop)
Steal
(betray)
Split
(coop)
50%
50%
100%
0%
Steal
(betray)
0%
100%
0%
0%

The problem is the same as The Prisoner’s Dilemma except it is not quite as pure. This is a one time thing, but the players are in the same room, in fact, they’re looking right at each other, their friends and family are watching and they are given the opportunity to convince the other person of their intention to either Split or Steal. There is more at stake than some money, their reputation amongst all people for one. On top of all of this they have been playing a game for the past half hour and have had the chance to betray eachother already, this is not now a case of a pure game, this is now a case of a sub-game.

The best and most amusing example of this follows in this youtube video. I think, more than anything, this video explains The Prisoner’s Dilemma and why it’s a dilemma and causes so much pain and heartache for so many economists, philosophers, psychologists and humanitarians around the world.


Game Theory – Nash Equilibrium

April 24, 2009

In my last post on Game Theory I started by introducing Game Theory and the Matching Pennies game. In this post I’m going to explore the Nash Equilibrium to try and further my knowledge about Game Theory. In a game of two or more players where there isn’t a definative winner and looser the two players might be able to find a middle ground. This ‘middle ground’ might be described as the Nash Equilibrium, it occurs when all the players in a game are getting the best payoff for the move they make (i.e. no player can benefit by deviating from his strategy).

An example of this can be found in a Game where a couple who fail to make a decision about what to do in the evening get split up and so they each have to decide which event to go to. It just so happens that each person in the couple has a favourite activity which they may have wanted to do in the eveing. The man favours going to watch sports and the woman favours going to the cinema. If the man chooses to go to watch sports then he is getting the most enjoyment out of the activity and likewise, if the woman goes to the cinema she will get her best payoff.  If they meet then the woman will enjoy the sports slightly and the man will enjoy the cinema slightly, however, if they fail to meet then they will both not enjoy the activity.

Following is the payoff table for this game.

Male
Sport
Male
Cinema
Female
Sport
+2
+1
0
0
Female
Cinema
0
0
+1
+2

Here you can see that there are two Nash Equilibrium for this Game if either player knows what the other person is going to do. If the Male knows the Female will go to the Cinema it is in his best interest to go to the Cinema as well. This simply shows what a Nash Equilibrium is and it requires that each participant knows what the other persons best payoff is and so what they are going to do.


Game Theory – An Introduction

March 27, 2009

Game theory, as with most logical and mathematical disciplines has interested me for a long time but until recently I haven’t had time or the motivation to look in to it very far. On my reading list from Christmas I have a small introduction to Game Theory. So far it’s been really quite interesting, I’ve lost the plot a few times and not understand one of the very basic concepts because of some of the wording, but it’s got all the information and there are no hard to understand formula.

Game Theory then, from what I understand of it so far, is the maths that can be used to determine what a ‘rational’ thing (or things) would do in a given situation. It’s applied across the board from the decisions animals and insects make and why they should make one decision over another all the way to what I should do in a game of poker.

In a basic game like Matching Pennies you can explain the very basics of Game Theory. The game involves two players, each has to choose either Heads or Tails on a penny and when they reveal their choice the first player wins if both pennies are the same (Heads, Heads/Tails, Tails) and the second player wins if the pennies are missmatched (Heads, Tails/Tails, Heads). It is known as a Zero-Sum Game because one player wins and the other player loses, i.e both players ‘payoffs’ are balanced, I win, you lose, visa versa, or a draw occurs in which all players get 0 payoff. A Zero-Sum game is therefore a game of pure-conflict, to maximize my payoff I have to try and make you lose by winning and visa versa. You could change Matching Pennies so that it was no longer Zero-Sum by giving some of the options benefit for both parties or the opposite. If we say that anything with a Tail in it means that both players win then it might be beneficial, if you know your opposition will play Heads, to always play Tails.

Game Theory is used to demonstrate what the best strategy is for both players, should the first player always go Heads, choose Heads two-thirds, one-half, one-quarter of the time, or maybe not at all? A decision matrix can be drawn up for the Matching Pennies game whereby if you win you get 1 and if you lose you get -1, that way the payoffs are balanced at a round 0.

Player 1
Heads
Player 1
Tails
Player 2
Heads
+1
-1
-1
+1
Player 2
Tails
-1
+1
+1
-1

In the top left you can see that if both player choose Heads then player one gets +1 and player two gets -1. We can understand from simple common sense that there isn’t really a best strategy unless you know what the other player is going to do, so I’m best off choosing Heads/Tails with an equal probability of 50%. This is called a mixed strategy as opposed to a pure strategy which will determine what a rational person should do in any situation of a Game.

Game Theory seems like it could be very useful in lots of situations where one should make a decision, the more I think about it the more I believe I’m going to start pondering options I take in terms of Game Theory.