SAS

Solve “A Puzzle for Pirates” with SAS

by  •  • Comments Off on Solve “A Puzzle for Pirates” with SAS

This post was kindly contributed by SAS Users - go there to comment and to read the full post.

In May of 1999, Ian Stewart issued the article “A Puzzle for Pirates” in that month’s edition of Scientific American (pp.98-99). This mathematical game then went on to become a worldwide hit, especially for puzzlers who like a good challenge. The rules of the pirate game are described below:

Five rational pirates have found 100 gold coins on an island and need to decide how to distribute them. They are a democratic bunch and they ask the fiercest pirate to propose a plan of distribution. Then, all of the living pirates (including the proposer) vote on whether to accept the distribution plan. If the majority (50% or more) accepts that proposal, then coins are dispersed and the game ends. Otherwise, the proposer is thrown overboard and killed, then the procedure is repeated with the next fiercest pirate until a proposal is accepted or only one pirate is left. If there is a tie vote, then the proposer (say, the fiercest pirate) has the casting vote.

At first glance, the proposer may offer the most favorable terms to all voters to pass the proposal, but this is not the case. The pirates are not only rational but also greedy and want to maximize their personal gain. Due to the game’s rules and how the order of pirate fierceness is known to all in advance, these rational pirates prioritize surviving first, then maximizing gold coins for themselves. They would love to kill off as many pirates as possible to make more coins for themselves through future distribution proposals. This logic may become surprisingly complicated due to the changes in the numbers of pirates and coins.

Suppose N is the number of pirates, and G is the number of gold coins. We number the pirates in order from meekest to fiercest, the greater the number, the fiercer the pirate. So P1 is the least fierce pirate, and PN is the fiercest pirate. Due to there being too many branches from the beginning, we can think of the problem backward from the end, that is, starting from the game results to reverse the entire distribution process.

If there are only two pirates (N=2), then obviously the fierce pirate is going to propose G coins for himself, and none for the meek pirate (P1=0, P2=G). Any proposal will pass no matter what it is for this case, so the fierce pirate would take all the coins while the meek pirate has no choice but to accept it. The fierce pirate doesn’t need to please meek pirate at all!

If there are three pirates (N=3), and all of them are aware of an inevitable positive result, then the fiercest pirate P3 is going to make a proposal pass to guarantee his own survival first, so he needs at least one vote from P1 or P2. Due to P2 having the possibility of getting G coins, so he can’t be bribed with gold coins; P1 knows he is going to get 0 coins if the game goes onto the next round, and P3 knows what P1 is thinking, so P3 can offer the least amount of coins, e.g., just 1 coin to buy the vote of P1, and P1 also would love to support P3 accordingly as he can get a better result: survival plus coins. So, the final proposal by P3 is P1=1, P2=0, P3=G-1, where G>1.

From the two trial calculations above, we can conclude the following decision-making patterns or rules for a player of the pirate game. The rules apply to all pirates and it is the rationality of a pirate, that is the pirate game recursive solving algorithm (click here to download the precompiled code).

  1. For any N, G, both N and G must be greater than zero for game, to avoid the possibility of unlimited bribing, we usually define them as both integer and 2*G < N, but this is not required.
  2. If the number of pirates N is 2, then proposal is P1=0, P2=G.
  3. Otherwise, count the proposer’s vote out and let the rest of the pirates (N-1) to distribute G gold coins. For its trial result proposal, count the number of votes supported:
    • The fiercest pirate whose proposal is impossible to pass in the next round. Because this pirate is going to die in the next round, he is the inevitable supporter of the current proposal to avoid making a proposal and being killed in the next round.
    • The pirates who are going to receive 0 coins in the next round. Try to buy this kind of pirate as a supporter with the least coins (e.g., 1 coin) from total G coins. For those pirates who received coins in the trial calculation, take their coins away!
  4. Check if the current proposal is going to pass the vote and return that flag.
    • If the number of votes supported plus 1 vote of the current proposer is equal to or greater than the N/2, then the proposal is passed. So the current proposer takes all the remaining gold coins after buying supporters in 3.b and make all those pirates going to die in the next round alive because they avoid the further distribution process.
    • If the current proposal cannot be passed, then throw the current proposer overboard, marking PN as a must-die pirate.

Please note step #3, we’re calling the pirate game-solving algorithm recursively, so it would reach the game-over condition. The following proposal plan table is generated by upper algorithm implementation by SAS for pirate games with N<=20 and G=100. You can see the best solution is, the fiercest pirate chooses the pirates with the same parity as him in the list ordered by fierce as his supporter. E.g., P3 would choose P1 as his supporter for a N=3 pirate game, and P5 would choose P3, P1 as his supporter for a N=5 game.

Will this pattern continue for any N pirate games with constant G gold coins? The answer is no because we have limited gold coins (G) to buy supporters. Anyway, it is true for N<= 2*G game, e.g., The P200 can take 1 coin and buy 99 supporters with another 99 coins, the detailed proposal plan for N=200 pirate game is show as below:

Interesting things happen while the number of pirates N exceed the 2*G. e.g., P201 and P202 pirates still can survive if he is taking no gold coins for himself and offering 1 gold coin each to 100 pirates with the same parity in the list ordered by fierceness. The detailed proposal for N=201, N=202 cases is show as below:

Unfortunately, P203 has no coins to buy supporters anymore in the pirate game (G=100, N=203), so P201 and P202 in this round would love to throw P203 overboard to earn more coins through future distribution proposals. In other words, P203 must die for this case (We use -1 to indicate death in detailed proposal).

P204 is a lucky guy who can survive. Since P203 must die in the next round, P203 is going to support any proposal made by P204 in the current round. P204 will apply the same strategy as P202 used in the N=202 pirate game above, so P204 takes no coins, and he gets support from P203 in this current round. So, P201, P202, P203 and P204 all survive with no coins. The detailed proposal is shown as below:

Accordingly, P205, P206 and P207 are all unlucky and doomed to die in their round, just like P203 in pirate game (G=100, N=203). The key reason is that they cannot get sufficient votes to make their proposals pass. The four rational pirates (P201 to P204) know they can survive and would love to throw these three pirates (P205 to P207) overboard to earn more coins through future distribution proposals. The detailed proposal for the game (G=100, N=207) is shown below:

Just as lucky as P204 in pirate game (G=100, N=204), P208 is also lucky enough to make a proposal pass because he can get sufficient support from P205, P206 and P207 who are doomed to die. P205, P206 and P207 must support P208 to avoid making a proposal and getting killed in the next round. The detailed proposal for the game (G=100, N=208) is shown below:

In general, suppose the number of the pirate I-th (I<= N) is PI in a pirate game (N, G), we have the following conclusion based on the recursive solving algorithm result:

  1. When I<=2*G, all pirates will survive, and they also have 50% possibility to get 1 or more gold coins.
  2. When I >2*G and I=N, the pirate PI (=PN, proposer) is going to survive only when (N – 2*G is the power of 2, otherwise they will die.
  3. When I>2*G and I<N, all pirates with number I <= (2*G + M) will survive but will receive no coins, all pirates whose number I>(2*G+M) will die, where M is the highest power of 2 that does not exceed N – 2*G. Please note that the survival for the PI is a possibility related to N value, those PI will survive again If N exceed 2*G + 2*M.

e.g., G=100, N=(205, 206, 207), N-2*G=(5, 6, 7), the M=4 (2^2<=4), so 2*G+M=204, so P201, P202, P203 and P204 will survive in pirate games N=(205, 206, 207). P205 must die in pirate game N=(205, 206, 207), and P206 must die in pirate game N=(206, 207), and P207 must die in pirate game N=207. But P205, P206, P207 will survive again if N is equal to or greater than 208.

In fact, there is no unique solution to distribute gold coins if a pirate already guarantees his survival. This means that the fiercest pirate has some freedom of selection when I>=2G+2, but the simplest solution is to select those pirates with the same parity by order of fierceness.

From the proposer’s perspective (I=N), if he attends a pirate game with different N, then his personal interest is different. For a game with a number of pirates that is less than or equal to 2*G, the proposer will always survive with coins. For games with greater than 2*G pirates, most proposers can’t survive except whose number minus 2*G happens to be an integer power of 2. We can visualize the solution for pirate game(N=500, G=100) with SAS as seen below.

Accordingly, we also can calculate the possibility of survival of a pirate game with N pirates (N<=500) and constant G=100. The survival curve below indicates how likely a pirate (proposer) is to survive if he participates in a game with N pirates. As expected, the curve is a non-linear line.

For the least fierce pirate, he has no chance to distribute gold coins, but he has most chances to vote on proposals. In other words, he can survive longer than other pirates. For the fiercest pirate, the survival rate appears as a cliff-like fall at some points for the pirate whose number PI is greater than 2*G. The survival curve below indicates how likely a pirate PI is to survive if he participates in a game with N pirates (N<=500).

e.g., For a game with 500 pirates, the first 44 pirates are doomed to be thrown overboard (P457 to P500), so the blue survival line falls to 0 at P456 (2*G+2^Y=2*100+2^8=456), accordingly the death rate(red) is suddenly increased to 100%.

Summary

We have figured out how to solve the pirate game with a recursive solving algorithm in SAS, and how to analyze and visualize the law behind the complex logic of the pirate game. Now the next time you join a pirate game, you will know your destiny ahead of time and reap the benefits while avoiding getting thrown overboard.

Solve "A Puzzle for Pirates" with SAS was published on SAS Users.

This post was kindly contributed by SAS Users - go there to comment and to read the full post.

SAS

Solve “A Puzzle for Pirates” with SAS

by  •  • Comments Off on Solve “A Puzzle for Pirates” with SAS

This post was kindly contributed by SAS Users - go there to comment and to read the full post.

In May of 1999, Ian Stewart issued the article “A Puzzle for Pirates” in that month’s edition of Scientific American (pp.98-99). This mathematical game then went on to become a worldwide hit, especially for puzzlers who like a good challenge. The rules of the pirate game are described below:

Five rational pirates have found 100 gold coins on an island and need to decide how to distribute them. They are a democratic bunch and they ask the fiercest pirate to propose a plan of distribution. Then, all of the living pirates (including the proposer) vote on whether to accept the distribution plan. If the majority (50% or more) accepts that proposal, then coins are dispersed and the game ends. Otherwise, the proposer is thrown overboard and killed, then the procedure is repeated with the next fiercest pirate until a proposal is accepted or only one pirate is left. If there is a tie vote, then the proposer (say, the fiercest pirate) has the casting vote.

At first glance, the proposer may offer the most favorable terms to all voters to pass the proposal, but this is not the case. The pirates are not only rational but also greedy and want to maximize their personal gain. Due to the game’s rules and how the order of pirate fierceness is known to all in advance, these rational pirates prioritize surviving first, then maximizing gold coins for themselves. They would love to kill off as many pirates as possible to make more coins for themselves through future distribution proposals. This logic may become surprisingly complicated due to the changes in the numbers of pirates and coins.

Suppose N is the number of pirates, and G is the number of gold coins. We number the pirates in order from meekest to fiercest, the greater the number, the fiercer the pirate. So P1 is the least fierce pirate, and PN is the fiercest pirate. Due to there being too many branches from the beginning, we can think of the problem backward from the end, that is, starting from the game results to reverse the entire distribution process.

If there are only two pirates (N=2), then obviously the fierce pirate is going to propose G coins for himself, and none for the meek pirate (P1=0, P2=G). Any proposal will pass no matter what it is for this case, so the fierce pirate would take all the coins while the meek pirate has no choice but to accept it. The fierce pirate doesn’t need to please meek pirate at all!

If there are three pirates (N=3), and all of them are aware of an inevitable positive result, then the fiercest pirate P3 is going to make a proposal pass to guarantee his own survival first, so he needs at least one vote from P1 or P2. Due to P2 having the possibility of getting G coins, so he can’t be bribed with gold coins; P1 knows he is going to get 0 coins if the game goes onto the next round, and P3 knows what P1 is thinking, so P3 can offer the least amount of coins, e.g., just 1 coin to buy the vote of P1, and P1 also would love to support P3 accordingly as he can get a better result: survival plus coins. So, the final proposal by P3 is P1=1, P2=0, P3=G-1, where G>1.

From the two trial calculations above, we can conclude the following decision-making patterns or rules for a player of the pirate game. The rules apply to all pirates and it is the rationality of a pirate, that is the pirate game recursive solving algorithm (click here to download the precompiled code).

  1. For any N, G, both N and G must be greater than zero for game, to avoid the possibility of unlimited bribing, we usually define them as both integer and 2*G < N, but this is not required.
  2. If the number of pirates N is 2, then proposal is P1=0, P2=G.
  3. Otherwise, count the proposer’s vote out and let the rest of the pirates (N-1) to distribute G gold coins. For its trial result proposal, count the number of votes supported:
    • The fiercest pirate whose proposal is impossible to pass in the next round. Because this pirate is going to die in the next round, he is the inevitable supporter of the current proposal to avoid making a proposal and being killed in the next round.
    • The pirates who are going to receive 0 coins in the next round. Try to buy this kind of pirate as a supporter with the least coins (e.g., 1 coin) from total G coins. For those pirates who received coins in the trial calculation, take their coins away!
  4. Check if the current proposal is going to pass the vote and return that flag.
    • If the number of votes supported plus 1 vote of the current proposer is equal to or greater than the N/2, then the proposal is passed. So the current proposer takes all the remaining gold coins after buying supporters in 3.b and make all those pirates going to die in the next round alive because they avoid the further distribution process.
    • If the current proposal cannot be passed, then throw the current proposer overboard, marking PN as a must-die pirate.

Please note step #3, we’re calling the pirate game-solving algorithm recursively, so it would reach the game-over condition. The following proposal plan table is generated by upper algorithm implementation by SAS for pirate games with N<=20 and G=100. You can see the best solution is, the fiercest pirate chooses the pirates with the same parity as him in the list ordered by fierce as his supporter. E.g., P3 would choose P1 as his supporter for a N=3 pirate game, and P5 would choose P3, P1 as his supporter for a N=5 game.

Will this pattern continue for any N pirate games with constant G gold coins? The answer is no because we have limited gold coins (G) to buy supporters. Anyway, it is true for N<= 2*G game, e.g., The P200 can take 1 coin and buy 99 supporters with another 99 coins, the detailed proposal plan for N=200 pirate game is show as below:

Interesting things happen while the number of pirates N exceed the 2*G. e.g., P201 and P202 pirates still can survive if he is taking no gold coins for himself and offering 1 gold coin each to 100 pirates with the same parity in the list ordered by fierceness. The detailed proposal for N=201, N=202 cases is show as below:

Unfortunately, P203 has no coins to buy supporters anymore in the pirate game (G=100, N=203), so P201 and P202 in this round would love to throw P203 overboard to earn more coins through future distribution proposals. In other words, P203 must die for this case (We use -1 to indicate death in detailed proposal).

P204 is a lucky guy who can survive. Since P203 must die in the next round, P203 is going to support any proposal made by P204 in the current round. P204 will apply the same strategy as P202 used in the N=202 pirate game above, so P204 takes no coins, and he gets support from P203 in this current round. So, P201, P202, P203 and P204 all survive with no coins. The detailed proposal is shown as below:

Accordingly, P205, P206 and P207 are all unlucky and doomed to die in their round, just like P203 in pirate game (G=100, N=203). The key reason is that they cannot get sufficient votes to make their proposals pass. The four rational pirates (P201 to P204) know they can survive and would love to throw these three pirates (P205 to P207) overboard to earn more coins through future distribution proposals. The detailed proposal for the game (G=100, N=207) is shown below:

Just as lucky as P204 in pirate game (G=100, N=204), P208 is also lucky enough to make a proposal pass because he can get sufficient support from P205, P206 and P207 who are doomed to die. P205, P206 and P207 must support P208 to avoid making a proposal and getting killed in the next round. The detailed proposal for the game (G=100, N=208) is shown below:

In general, suppose the number of the pirate I-th (I<= N) is PI in a pirate game (N, G), we have the following conclusion based on the recursive solving algorithm result:

  1. When I<=2*G, all pirates will survive, and they also have 50% possibility to get 1 or more gold coins.
  2. When I >2*G and I=N, the pirate PI (=PN, proposer) is going to survive only when (N – 2*G is the power of 2, otherwise they will die.
  3. When I>2*G and I<N, all pirates with number I <= (2*G + M) will survive but will receive no coins, all pirates whose number I>(2*G+M) will die, where M is the highest power of 2 that does not exceed N – 2*G. Please note that the survival for the PI is a possibility related to N value, those PI will survive again If N exceed 2*G + 2*M.

e.g., G=100, N=(205, 206, 207), N-2*G=(5, 6, 7), the M=4 (2^2<=4), so 2*G+M=204, so P201, P202, P203 and P204 will survive in pirate games N=(205, 206, 207). P205 must die in pirate game N=(205, 206, 207), and P206 must die in pirate game N=(206, 207), and P207 must die in pirate game N=207. But P205, P206, P207 will survive again if N is equal to or greater than 208.

In fact, there is no unique solution to distribute gold coins if a pirate already guarantees his survival. This means that the fiercest pirate has some freedom of selection when I>=2G+2, but the simplest solution is to select those pirates with the same parity by order of fierceness.

From the proposer’s perspective (I=N), if he attends a pirate game with different N, then his personal interest is different. For a game with a number of pirates that is less than or equal to 2*G, the proposer will always survive with coins. For games with greater than 2*G pirates, most proposers can’t survive except whose number minus 2*G happens to be an integer power of 2. We can visualize the solution for pirate game(N=500, G=100) with SAS as seen below.

Accordingly, we also can calculate the possibility of survival of a pirate game with N pirates (N<=500) and constant G=100. The survival curve below indicates how likely a pirate (proposer) is to survive if he participates in a game with N pirates. As expected, the curve is a non-linear line.

For the least fierce pirate, he has no chance to distribute gold coins, but he has most chances to vote on proposals. In other words, he can survive longer than other pirates. For the fiercest pirate, the survival rate appears as a cliff-like fall at some points for the pirate whose number PI is greater than 2*G. The survival curve below indicates how likely a pirate PI is to survive if he participates in a game with N pirates (N<=500).

e.g., For a game with 500 pirates, the first 44 pirates are doomed to be thrown overboard (P457 to P500), so the blue survival line falls to 0 at P456 (2*G+2^Y=2*100+2^8=456), accordingly the death rate(red) is suddenly increased to 100%.

Summary

We have figured out how to solve the pirate game with a recursive solving algorithm in SAS, and how to analyze and visualize the law behind the complex logic of the pirate game. Now the next time you join a pirate game, you will know your destiny ahead of time and reap the benefits while avoiding getting thrown overboard.

Solve "A Puzzle for Pirates" with SAS was published on SAS Users.

This post was kindly contributed by SAS Users - go there to comment and to read the full post.