Game theory and the prisoner’s dilemma

3 05 2009

Hi, everyone!

As some people know, I have got interest in theory of games. Well, this post is going to be dedicated to this subject.
My aim here is to introduce some aspects of game theory and the prisoner’s dilemma, presupposing no previous knowledge.

First of all, it would be nice to explain a little bit about a model of game.

For simplicity, the components of a game are: Players, Actions, Payoffs.

Players

urss1USSR and USA played a game known as Arms Race in the Cold War

In theory of games we must have a minimum of 2 players. If you are dealing with just one player, you have to try another one: decision theory.
To identify who are the players, a good question is: “Does the action of one player affect the other?” If the answer is ‘yes’, there is a good chance that he/she is actually a player.

If you want a better explanation why a minimum of 2 players take a look at the Robinson Crusoe’s citation in the foundation book of theory of games from von Neumann (R. 1)


Actions

chessmoveThe rules of chess give the set of actions for each player

If we don’t have a set of actions, we don’t have any strategy to follow, so we don’t have a game. Actions are an essential part of a game. There must have a set of actions for each player.

Payoffs

power-of-giving-5

Payoffs roughly speaking are functions that map what players get given a strategy profile. It is another essential piece of the puzzle. Payoffs may represent the player’s preferences (utility function) too.

Now, let’s see the prisoner’s dilemma situation.

The game

prisoner

“Two men suspected of commiting a crime together are arrested and placed in separate cells by the police. Each suspect may either confess or remain silent, and each one knows the possible consequences of his action. These are: (1) If one suspect confesses and his partner does not, the one who confessed turns state’s evidence and goes free and the other one goes to jail for twenty years. (2) If both suspects confess, they both go to jail for five years. (3) If both suspects remain silent, they both go to jail for a year for carrying concealed weapons – a lesser charge.” ( R.2 ) Communication between the suspects is not allowed and they have to decide simultaneously.

Well, this is the story.
Let’s try to model the situation:

Players:
{Suspect I, Suspect II}

Actions:
Suspect I: {confess, don’t confess}
Suspect II: {confess, don’t confess}

Payoffs:
If we define a strategy profile as a tuple where the first coordinate represents the action for Suspect I and the second for the Suspect II, we have the following possibilities for outcomes:

(suspect I action, suspect II action) -> suspect I payoff
(confess, confess) -> 5 years
(confess, don’t confess) -> 0 years
(don’t confess, confess) -> 20 years
(don’t confess, don’t confess) -> 1 year

As you can see, the payoff of the suspect I depends on the suspect II action. There is a mathematical function that could be better formalized, but it’s ok like that for our purpose here.
We did not name the suspects, so the same payoff function is symmetric for the other player.

It’s common in game theory books use a table to organize the information:

prisoners_dilemma0

It’s done! We modeled the prisoner’s dilemma from scratch!

Solving the game

Now, what do you think that it’s going to happen? What would each suspect do? What would you do?
Well, there are a lot of explanations and considerations in this game.

To begin our analysis, let’s simplify the model:

prisoners_dilemma1

Let’s analyze the table.
If Suspect II does confess, Suspect I take 5 years choosing confess. If Suspect I chooses DC he/she gets 20 years, therefore is better to confess.
If Suspect II don’t confess, Suspect I go free choosing confess. If Suspect I chooses DC he/she gets 1 year, therefore is better to confess.
Thus, choosing to confess is the best response no matter what Suspect II does.

The jargon used in the literature is C ‘strictly dominates’ DC.

screenshot-5Action C strictly dominates DC for Suspect I

So, reasoning the same way for the other player:

prisoners_dilemma3Action C strictly dominates DC for Suspect II

Rational Players:

There is one hypothesis in theory of games that must be true in order to make it useful. The hypothesis is that the players are rational. What means by being rational is something that I’ll let for another post. But essentially it means that the players have consistent preferences (transitive relation). It doesn’t follow that being rational implies that there is only one preference order, that is, the theory doesn’t tell what players want. Only the players can tell what they want (their goals and preferences).

In the prisoner’s dilemma, the players prefer to stay away from the jail. It would be ok if they liked to be on jail, but the game would be other, because once you change a component of the game, you changed the game.

The prisoners want to minimize their time in the jail. Then, backing to our problem, if the 2 suspects are rationals they wouldn’t play a dominated strategy. So, the game ends with an equilibrium, the (Confess, Confess) strategy profile:

prisoners_dilemma4(C, C) is the Nash Equilibrium for the game

The paradox

The paradox that someone may claim is that both would do better if both collaborated, choosing (Don’t confess, Don’t confess). Nevertheless, no one is secured that the other will collaborate. Even if they both could communicate, in the last move one could deviate. So, it’s better to choose confess.

Well, that’s all for now.

I’d like to pardon all of you that master game theory since my language in this post was really imprecise, without rigor and maybe unpolite.

References:

R. 1 -> von Neumann, John; Morgenstern, Oskar (1944), Theory of games and economic behavior, Princeton University Press

R. 2 -> Davis, Morton. Game Theory – a nontechnical introduction





Curiosity about Finland

20 04 2009

lakeve

Today I was reading about the Linux operating system, and somehow I noticed that Linus Torvalds (linux creator) is finnish.
I asked my friend Cruzada: “what do you know about Finland ?”

After some talk, we figured out something that perhaps you may know.

Finland has more than 180 thousands of lakes!!! -> see a map

And the most interesting thing is that those lakes are represented in their flag:

finland_flag_232

There are a lot of signs around us =P

That’s all!
Till the next post, reader!





Game Theory Simulator

18 04 2009

Forget everything you’re thinking. Imagine an empty world.
Put inside the world some creatures and food.
This world has a custom (and classic newtonian view) one-direction time and it’s always increasing.
The creatures have energy and it decreases non-stopping.
The creatures feel hungry.
What you think that is gonna happen?
What would be the behavior of them? Easy to describe?

screenshot-gtsimulatorHi, everyone!

Today I uploaded the files of my project on game theory to a google code repository. It’s really far from finished, but it’s a beginning.

It’s a python project and I’m using the MVC design pattern. To make it really extensible, I’m trying to separate the geometry of the world from the core. So, in the future I’ll be able to put the creatures in another geometry. Another immediate advantage is that I can let the world advances in the time without viewing it, because the geometry module can calculate the collisions and all this kind of stuffs. This is a good gain because plotting pixels on the screen consumes processing time. It will be advantageous for a statistic treatment.

Well, now I’m trying to put intelligence in those creatures. They’re gonna reason following game theory precepts.
So, there are a lot of branches I could follow with this world, but the most exciting issue is that I could forget all this interpretation of the creature’s world and apply this model to other problems of the real world.

For a while, you can download it and see what is happening with the creatures without a game theoretical mind.

gtsimulator google code url: http://code.google.com/p/gtsimulator/





INTP ?

17 04 2009

050405_einstein_tonguewidec

Typealyzer says that I am an INTP person.

For those who don’t know typealyzer ( http://typealyzer.com ), it’s simply an app that tells a blogger’s personality. You just have to enter a blog url and it outputs a personality that would match with the owner.
I don’t know the algorithm that typealyzer uses, but it really surprised me. It’s everything ok with what I observe in myself (*).

Searching for INTP, I could find the entire list of the 16 personality types.
Here you can see a summary: http://www.personalitypage.com/high-level.html

If you want to learn more about this subject, here is a starting point:
http://en.wikipedia.org/wiki/Myers-Briggs_Type_Indicator

What’s yours? Write a blog and try typealyzer!

Note: Einstein was an INTP person too =P

See ya!

(*) But, but…it seems like an horoscope forecast! =P





Learning with Feynman

16 04 2009

I’m here to share with you a video with Richard Feynman, a scientist that I admire a lot.
Learn a lesson from the Great Feynman:

“…he knew the difference between knowing the name of something and knowing the something” – this kind of reasoning I miss in people nowadays…

Good watching!





Why so many clothes?

16 04 2009

clothing-outdoor-stall-2

Today I was walking in the Rio Sul Shopping Center* trying to stimulate new ideas, and I decided to make an experiment, a statistic experiment.

I started to count all the stores. While I was counting, I realized that there were so many clothing stores. After that, I walked throughout the shopping and…I figured out that from all the 340 stores, 136 were clothing stores. So, 0.4 is the percentage of clothing stores in the Rio Sul Shopping Center!!!

It’s a great piece of the cake; a great number for one category of business.

According to wikipedia:

“In history, clothes have been from many materials- ranging from grasses to furs to much more elaborate and exotic materials. Based on scientific research into lice it is estimated that humans have been wearing clothing for 650,000 years.”

It’s notoriously an ancient tradition. Now, I’m really curious whether these percentage is a constant between shopping centers or not.

Till the next post, readers!

*Rio Sul Shopping Center is located in Rio de Janeiro, Brazil.





Quick question about microblogging

15 04 2009

microblogging

Hey, everyone!

These days I was wondering….The limit of 140 characters can influence the way we communicate? We can limit our conversations in the real world with this constraint of the virtual world inconsciently?

That’s the question. Answer as a comment!








Follow

Get every new post delivered to your Inbox.