A Puzzle for Pirates

Intro

In this webpage a description and an implementation of the mathematical game "A Puzzle for Pirates" is shown. It has been made by 3 students attending the master in Artificial Intelligence at the Rijksuniversiteit Groningen for the course of Multi-Agent Systems. The students are namely:

  • Matthia Sabatelli: s2847485
  • Zhenwei Shi: s2435993
  • Francesco Bidoia: s2693607
  • Game description

    Our project takes inspiration from a mathematical game that was published on the Scientific American Journal in 1999 by Ian Stewart called "A Puzzle for Pirates". The scenario he proposed in his article was the following: There are five rational pirates (A,B,C,D and E) that just found 100 gold coins and have to decide how to distribute this money, there is a strict order of seniority between them, this means that pirate A is superior to B, who is superior to C, who is superior to D and who is superior to E. The most senior pirate has the privilege to propose the distribution of the coins as first one, the other pirates can decide to accept it or not, in case of a tie vote the pirate who is making the proposal has the casting vote. If the distribution is accepted the game ends and the coins are distributed, on the other side if this doesn’t happen the proposal pirate is thrown overboard and dies. All pirates are perfectly rational and base their decisions on three factors:

  • Every pirate wants to survive
  • Every pirate wants to have as much money as possible
  • Each pirate would prefer to kill one of the others
  • The goal of the game is to find a proposal that satisfies all pirates and how we will demonstrate in our project how counter-intuitive this possible solution will be. The idea is to make a simulation program that acts like the pirates in order to find the correct proposal of the 100 coins.

    Our Work

    There are basically two strategies that may be used to resolve the problem and come up with the correct solution. The first approach consists in thinking which all the possible combinations of worlds that can represent the problem are and then through the use of the 3 rules starting to delete all the possible worlds that wouldn't resolve the problem. This possible strategy is shown hereafter where the case with only 3 pirates is represented:

  • The problem of this approach is that it doesn't really deal with knowledge information and epistemic logic, in fact it's just a way to resolve the puzzle in a computational way, calculating every possible case, but this is far from real reasoning. This conduced us to the second approach in which some epistemic logic elements can be found. The first of these elements regards "Common Knowledge" and is represented by the case in which only 2 pirates are left on board and its relative money distribution. No matter which pirate has to make the decision on how to split the gold, during all his reasoning process he will always bear this situation in mind just because he doesn't want to make it happen. Then it comes to decide how to split the 100 coins of gold and how to do this in a way to get as much votes as possible, to do this the pirate who can propose as first starts thinking about the proposal that his successor will make and knows that he has to do better. The way he can do it is by offering some money to the pirates that wouldn't be bribed next round, he also knows that he has just to offer some money in order to satisfy half of the pirates on board because in case of an equal number of votes he will have the casting vote. The final step regards how to make as much money as possible and this is very simple, the pirate who makes the proposal is going to give just 1 coin to the pirates that will vote for him because they all know they won't get anything better with the next pirate making the proposal and hold all the rest for himself.