Problem Solving, Working Backwards and Pirate Game

“If I had an hour to solve a problem I’d spend 55 minutes thinking about the problem and 5 minutes thinking about solutions.”

― Albert Einstein

Psychologists have done lot of research in area of problem solving. They have come up with number of methods like hill climbing (reach one goal at a time, then go for next one till you reach the final goal), mean-end analysis (identify current state and end state, now work out what needs to be done to reach final state), forward chaining (identify the givens and work directly towards goal), considering analogous problem (used in Tata Innovista, where idea from one industry is used to solve similar problem in another industry ex. technique of drying of plaster used by Tata Projects was used by Titan to reduce cycle time for drying objects post gold plating) etc.

One of the techniques is to solve problem working backwards i.e. working backwards from final goal through all steps necessary to reach that goal.

Game theory has one such interesting game called as Pirate Game, which when solved backwards can give an interesting and unexpected result.

Game is like this. Suppose there are 5 pirates (it can be any number) and they find chest with 100 gold coins, now pirates have to distribute it among themselves. Solution is not as simple as each taking 20 coins each, because pirates have their own laws and traditions and distribution has to be done as per traditions.

pirates[1]

Let us give number to pirates starting from 1 to 5, with 1 being senior most and 5 being junior most.

As per tradition, senior most pirate will propose distribution. The pirates, including the proposer, then vote on whether to accept this distribution. In case of a tie vote the proposer has the casting vote (i.e. at least half of them should support proposer). If the distribution is accepted, the coins are disbursed and the game ends. If not, the proposer is thrown overboard from the pirate ship and dies, and the next most senior pirate makes a new proposal and game starts again.

Now as per game theory, we have to assume that all pirates are rational; hence will base their decisions on three factors.

  1. Each pirate wants to survive.
  2. Each pirate wants to maximize the number of gold coins he receives.
  3. Each pirate would prefer to throw another overboard.

coins

Game will start with pirate #1 as proposer (being senior most), we may conclude that pirate #1 will allocate little for himself for fear of being voted out and thrown in sea. But actual solution is quite different from what we are assuming.

Actual solution( distribution) is shown below.

#1: 98 coins

#2: 0 coins

#3: 1 coin

#4: 0 coins

#5: 1 coin

So #1 gives away only 2 coins, keeps 98 coins and manages to survive.

For solution we need to work backward, suppose #1,#2 & #3 are thrown overboard and only #4 and #5 remain, here# 4 will take all 100 coins ( he has casting vote in case of tie) and given #5 nothing.

Now if #3,#4 & #5 are left, #3 knows very well that if he is thrown overboard, #5 gets nothing, so he offers one coin to #5 and gets his vote and gives #4 nothing, so #3 gets 99 coins , #4 nothing and #5 one coin.

If #2, #3, #4 & #5 remain, #2 being a rational player knows what will happen if he is thrown overboard. To avoid being thrown overboard, he can simply offer one coin to #4 and gets his vote. Because he has the casting vote, the support from #4 is sufficient. Thus he proposes himself 99 coins, #3 nothing, # 4 one coin and #5 nothing.

Since #1 is a rational player, hence knows all these things, so he gets votes from #3 and #5 by giving them one coin each and gives #2 and #4 nothing and keeps remaining 98 coins with himself.

The game can be played for n number of players; the pattern of distribution is as follows.

No of Pirates (n)              No of coins got by each (nth, n-1 th …)

1                                                      100

2                                                            100, 0

3                                                           99, 0, 1

4                                                            99, 0, 1, 0

5                                                            98, 0, 1, 0, 1

6                                                           98, 0, 1, 0, 1, 0

7                                                 97, 0, 1, 0, 1, 0, 1

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s