The Pirate game is about a number of commonly known to be rational pirates p1,...,pn. They have found a treasure chest with an integer number of coins M in it. How can these coins best be divided? We know that the pirates are ranked in the following way: p1 has higher rank than p2, p2 has higher rank than p3, and so on until pn. No two pirates have the same rank. The highest ranked pirate has to propose a division of the coins over all pirates. All pirates, including the proposer, vote on accepting this division. If 50 percent or more are in favour, the proposal is accepted and the coins are divided. This means that the game has ended. If the proposal is not accepted, the proposer is thrown overboard and dies. Now the next highest ranked pirate can propose a division of the coins, and so on.
Some factors play a role in making their decisions.
The first three factors were already in the original pirate game by Stewart [1999], together with the fact that pirates do not trust each other. We added the other points to our version of the pirate game. We added public announcements and subgroup announcements. We will look what happens if we change the number of coins or the number of pirates in cases with or without public and subgroup announcements. Notice that in a case with only one pirate, there is no game to be played. We assume that there are at least two pirates.
An important thing we noticed is that when the number of pirates exceeds 2M, the proposer must give himself zero coins. When it exceeds 2M + 2 it is often the case that he will be thrown overboard, because there are not enough coins to get enough pirates accepting your proposal. But as Ian Stewart noticed, you can also have pirates accepting your proposal, because they know they will be thrown overboard in the next round (for example because they do not have enough coins to have their proposal accepted). Ian Stewart concluded that in a case in which there are 100 coins “[t]he pirates who avoid this fate [of being thrown overboard] are [...] pirates whose number equals 200 plus a power of 2” [Stewart, 1999]. We will not look at these cases in detail, but they do work in our program. Feel free to experiment.
In case we have only two pirates, p1 and p2, where p1 is the highest ranked pirate, the number of coins is not important. Since, in a tie vote, p1 decides. Thus, it doesn’t matter whether p2 accepts or declines the proposal, p1 can always give all the coins to himself, without being thrown overboard. So, the game becomes interesting when we have more than two pirates.
We now look at the case in which we have at least three pirates and three coins. To prevent edge cases we consider at most 2 ⋅ 3 = 6 pirates. The optimal strategy (which is a sort of prediction of what the pirates will accept) of dividing the coins is given in Table 1. This table can be read as follows. Row i represents the case with i pirates, with i = 1,..,6. The pirates are ordered from left to right with the highest ranked pirate on the diagonal element of that specific row. So, in the first column the amount of money that the lowest ranked pirate gets is given. The sum of the elements in each row must add up to the number of coins, in this case 3. We added the cases with one and two pirates to make the table complete. This table can be seen as common knowledge among all pirates. The pirates are ideal agents in this game.
But how is this optimal strategy obtained? In the cases of one and two pirates the optimal strategy is obvious. If we look at the third row in the table we see that the highest ranked pirate, p1, gives two coins to himself and one coin to the lowest ranked pirate, p3. Pirate p1 cannot give all the coins to himself, because then the other two pirates would vote against his proposal which means that he is thrown overboard. Thus he must get at least one other pirate to vote for his proposal. This can be done by giving p3 one coin, because p3 knows that if p1 is thrown overboard he will get nothing (row 2, column 1). For p2 to be satisfied, p1 needs at least four coins (which is impossible), because p2 knows that he can get all three coins in the next round. Three coins is not enough to get p2 on your side, because the pirates prefer to throw a pirate overboard if they can get the same amount of coins in the next round. Thus, it is wise for p1 to give p3 one coin, so that his proposal will be accepted.
In case of four pirates (row 4), the highest ranked pirate has to look at what the division will be when he is thrown overboard (the previous row in the table). From this he can choose the “cheapest” pirate(s) and give them one coin more than they will get in the row above. This leads to the result 0 1 0 2. Pirate p1 only needs one other pirate to accept his proposal, because then it is a tie vote in which his own vote is decisive. Continuing in this way we also get the optimal strategy for the cases with five and six pirates.
Thus, we see that the pirates only have to look at the row above (i.e. what will happen in the future) to find out their optimal strategy. But, if a proposal cannot be accepted, all pirates know that the highest ranked pirate will be thrown overboard. This means that they have to look at rows higher up in the table until a proposal that will be accepted. It is that specific row they should base their voting on. This happens in cases in which there are more than 2M + 2 pirates. Stewart [1999] is right by saying that only with 2M plus a power of two pirates, the highest ranked pirate survives.
The optimal strategy of dividing the coins can easily be extended to the case in which there are n ≤ 2M pirates and M coins. This can be found in Table 2. The process in Table 2 continues as long as the highest ranked pirate can give himself one coin. As soon as the proposer has to give himself zero coins to stay alive, the table stops (our program continues in the way described by Stewart [1999]).
| M - 0 | |||||
| 0 | M - 0 | ||||
| 1 | 0 | M - 1 | |||
| 0 | 1 | 0 | M - 1 | ||
| 1 | 0 | 1 | 0 | M - 2 | |
| 0 | 1 | 0 | 1 | 0 | M - 2 |
 |
We will look what happens if we add the possibility for every pirate to make one public announcement before the beginning of the game. Such announcements become common knowledge among all pirates. They are of the form “When I am the highest ranked pirate, I will divide the coins as follows: ...”. We assume that public announcements are always true and that they can also be fulfilled (i.e. the total number of coins should be correct). We immediately see that it is not useful if the lowest ranked pirate makes a public announcement of this form, because he will never become the highest ranked pirate (unless he is on his own). Do such announcements make any difference? Can they change the optimal strategy?
A public announcement from pirate pi can influence rows i + j with j ∈ ℕ. We will give an example based on at most 6 pirates and three coins. We will look what happens if the second lowest pirate makes the public announcement “When I am the highest ranked pirate, I will divide the coins as follows: 2 1”. He promises to give two coins to the other pirate and only one to himself. The influence of this public announcement can be found in Table 3. In the case of three pirates, you can see (in red) that, in comparison to the third row of Table 1, the pirate who made this announcement has increased the amount of money he will get by two coins. In the case of five pirates his amount of money increases by one coin (blue).
| 3 | |||||
| 2 | 1 | ||||
| 0 | 2 | 1 | |||
| 1 | 0 | 0 | 2 | ||
| 0 | 1 | 1 | 0 | 1 | |
| 1 | 0 | 0 | 1 | 0 | 1 |
The influence of this same pirate making the announcement 1 2 can be found in Table 4. You can see that the announcement is not useful in the case of three pirates (again comparing to Table 1) and in the cases of four or more pirates the table equals Table 1.
| 3 | |||||
| 1 | 2 | ||||
| 2 | 0 | 1 | |||
| 0 | 1 | 0 | 2 | ||
| 1 | 0 | 1 | 0 | 1 | |
| 0 | 1 | 0 | 1 | 0 | 1 |
Since a pirate does not give zero coins to himself, we see that for the second lowest ranked pirate it is useful to make the public announcement that he is going to divide the coins as 1 2. For other pirates, their optimal public announcement can be found using similar methods.
This can easily be extended to a case in which there are n pirates and M coins.
We can also add subgroup announcements. These announcements are of the same form as public announcements except that they are not common knowledge to everyone. The announcement is common knowledge only within the subgroup. Can such announcements affect the optimal strategy? Yes they can, they can even throw pirates overboard. We will look at the case in which we have 5 pirates and 3 coins. Suppose that {p2,p3,p4,p5} form a subgroup and p2 makes the announcement: “When I am the highest ranked pirate, I will divide the coins as follows: 1 1 0 1”. This is now common knowledge among these pirates. If we now start the game, the highest ranked pirate will propose the division 1 0 1 0 1 which will be accepted according to his knowledge (see Table 5). However pirate p5 will vote against the proposal, even though p1 expected his vote. Pirate p5 prefers receiving one coin and seeing pirate p1 being thrown overboard instead of just receiving one coin. Thus, the proposal of p1 does not pass the vote. We then arrive at the case in which there are only four pirates left. His proposal is exactly the subgroup announcement made by p2, because the pirates do not lie in subgroups. This proposal will be accepted. By making this announcement, p2 has gained one coin. To see this, compare the red element in Table 5 with the red element in Table 6. We see that for each subgroup we have a different table. The knowledge within a group is used to form these tables.
| 3 | ||||
| 0 | 3 | |||
| 1 | 0 | 2 | ||
| 0 | 1 | 0 | 2 | |
| 1 | 0 | 1 | 0 | 1 |
| 3 | ||||
| 0 | 3 | |||
| 1 | 0 | 2 | ||
| 1 | 1 | 0 | 1 | |
| 1 | 0 | 1 | 0 | 1 |
Another interesting example is the following. Consider 5 pirates and 4 coins. The second lowest ranked pirate makes the announcement that he will divide the coins as 2 2 if he becomes the highest ranked pirate. But, he only tells this to the lowest ranked pirate. The game starts by a proposal of the highest ranked pirate of 1 0 1 0 2. He thinks this will be accepted, but both pirates from the subgroup vote against this proposal and so does the second highest ranked pirate. Thus, the proposer is being thrown overboard. The next pirate proposes 0 1 0 3, because he is also not aware of the subgroup announcement. (He could conclude some things from the fact that the highest ranked pirate has been thrown overboard, but we leave that for further research). The result is that he is also being thrown overboard. The same happens to the next pirate, meaning that only the two lowest pirates are remaining. They split the money as promised in the subgroup: 2 2. Pirates do not lie when making announcements, so it is not possible for the proposer to keep all the money for himself (as a pirate probably would have done in real life). To clarify the example, you can find the tables for both groups below. Table 7 shows the optimal strategy for the pirates who are not aware of the subgroup announcement and Table 8 shows the optimal strategy for the pirates in the subgroup.
| 4 | ||||
| 0 | 4 | |||
| 1 | 0 | 3 | ||
| 0 | 1 | 0 | 3 | |
| 1 | 0 | 1 | 0 | 2 |
| 4 | ||||
| 2 | 2 | |||
| 1 | 0 | 3 | ||
| 0 | 1 | 0 | 2 | |
| 1 | 0 | 1 | 0 | 2 |
In our program you can type in any number of pirates and coins and add some announcements. Find out what happens and why it happens!
We wrote a model for these interactions in Python. At the center of this model lies the Pirate class. A pirate has a rank, and a set of predictions for rounds. It also has a Knowledge object that stores the number of coins in the game and all promises the pirate knows about.
A pirate can play by making an offer, or he can vote on an offer. Both of these actions depend on a Prediction object. When making an offer, a pirate ‘predicts’ his own offer. This offer is then optimized for that round, given his knowledge and is thus the offer he makes. When voting on an offer, a pirate predicts the outcome of a hypothetical next round. If he is offered more than this hypothetical outcome, he votes in favour of the offer. Otherwise he votes against the offer.
The meat of the work lies in the prediction objects. A prediction is made about a round based on certain knowledge. A prediction for a round predicts the following:
A prediction does this recursively, by creating predictions of predictions. To create a prediction of the prediction of pirate pi, one simply creates a new prediction based on a prediction of the knowledge of pirate pi. In this simulation, this prediction of knowledge of pirate pi is the knowledge of the superior prediction, and removing all promises that pi does not know about.
A prediction for a round contains the following predictions of predictions. To predict the expectations of the round, it contains predictions of the predictions for the next round of all pirates voting in the round. To predict the offer of the round, it contains a prediction of the prediction of the pirate making the offer this round.
The predicted outcome of a round is simply if the offer is predicted to be accepted. Otherwise, one predicts the outcome to be the predicted outcome of the next round, with one modification. The pirate who made the offer also dies. Here, dying is modeled as a gain of -1. It does not matter how it is modeled, as long as the outcome of dying compares as smaller than all other outcomes.
Now, each prediction objects requires many more prediction objects, which all require many prediction objects, which all require many prediction objects, and so on. One might therefore wonder just how much of an impact on performance this has. If done naively, the impact is huge.
Experimentally, we found the following numbers for 1 through 8 pirates: 1, 3, 13, 71, 505, 4 555, 50 117, 651 535 when simulating the normal game (i.e. without promises). A search of the online encyclopedia of integer sequences (oeis.org) tells us these are the even elements of sequence A047905 (oeis.org/A047905). This corresponds to the relation: pn+1 = 1 + (n ⋅ pn + 1). Which is worse than combinatoric growth. We only went up to 8 pirates because 8GB of RAM and 8GB of swap space was not able to support any more. 10 pirates already requires 166 141 715 predictions.
However, there is one massive opportunity for optimization. Two predictions of the same round, made based on the same knowledge are exactly identical. Therefore, whenever a new prediction is created, one can then store that prediction as the prediction for that combination of knowledge and round. This is done in a Python dict which is essentially a hash table. Each next time a new prediction is requested for the same round based on the same knowledge, we simply return a reference to the previously created object. The number of predictions then becomes: pn = (n - 1) ⋅ 2 for the normal case. Quite the improvement. Now, at most 91 pirates can be simulated. For more pirates, there is a recursion deeper than 1000 recursive calls. By default, Python does not allow recursions to go deeper than 1000.
We wrote a (rather basic) interface around this simulation. It allows the user to choose the number of coins and pirates. Then, they get to enter however many promises they want. After this, the game is run. It shows each round in order, by showing the offer, the expectations and the votes. Per round the user is asked if they want an explanation for the offer or an expectation. If they do, they are shown the relevant prediction by showing the outcome, offer and expectations. They are then asked if they want an explanation for the outcome, offer or expectation, which will then show the relevant prediction with the same procedure.
John-Jules Ch Meyer and Wiebe van der Hoek. Epistemic Logic for AI and Computer Science. Cambridge University Press, 1995.
Ian Stewart. A puzzle for pirates. Scientific American, 280, 1999.
Hans van Ditmarsch, Wiebe van der Hoek, and Barteld Kooi. Dynamic Epistemic Logic. Springer Verlag, 2007.
Wikipedia. Pirate game — wikipedia, the free encyclopedia, 2014. URL http://en.wikipedia.org/w/index.php?title=Pirate_game&oldid=631712423. [Online; accessed 27-February-2015].