## Sunday, November 1, 2009

### A real multi agent system problem .... !

5 pirates of different ages have a treasure of 100 gold coins.

On their ship, they decide to split the coins using this scheme:

The oldest pirate proposes how to share the coins, and all pirates remaining will vote for or against it.

If 50% or more of the pirates vote for it, then the coins will be shared that way. Otherwise, the pirate proposing the scheme will be thrown overboard, and the process is repeated with the pirates that remain.

Assuming that all 5 pirates are intelligent, rational, greedy, and do not wish to die, (and are rather good at math for pirates) what will happen?

1. Case I: All of them fight and sink the ship. (which is not so interesting for such "intelligent" pirate-mathematicians, and assuming that the system is not artificially intelligent)

Case II: The oldest pirate takes the maximum possible coins for himself (greedy principle) but also ensures that he secures a majority (else he is thrown overboard hehehe). The 2 others (atleast 2 out of remaining 4 must accept the oldest pirate's split) who agree to his condition may get very less coins compared to the oldest pirate, but atleast they have something more than the other 2 pirates who are against the oldest pirate's decision.

Hence, it all depends on the oldest pirate's "rational" thinking about retaining the maximum possible coins to himself and that should leave just enough coins to woo atleast 2 of the 4 remaining pirates.

Best case: 98 coins for oldest, and 2 each for his supporters. or many such splits in favour of the supporters till they are ready to support him, 34 coins for oldest and 33 each for his supporters. (assuming only 2 out of 4 pirates support the oldest pirate)

2. @Balkrishnan V ..... good try balki ... taking in consideration the fact that you are not the Multi Agent Student ..... but not fully correct ....

i am still awaiting answers from student of MAS course ... :)

3. I kinda agree to the approach taken by balki...Here is my solution.
Assumption: Absolute majority is necessary i.e 50% above and not inclusive.

Let the pirates be numbered in descending ages as 5 4 3 2 1.
Pirate 1: Will always disagree cos he will get all coins if all are thrown overboard.
Pirate 2: Will always disagree with pirate 1 cos hes the one to be axed by pirate 1 if no deal comes thro. So he will be willing to collaborate with Pirate 3 or 4 or 5.
Pirate 3: He has no incentive to collaborate with Pirate 4 or 5 cos he knows that Pirate 2 will always co-operate with his desicion.
Pirate 4: Theres no point in him making a decision in a absolute majority game as Pirate 3 and 1 are against him. So he will collaborate with Pirate 5.

Situation:
P1: Disagres , P2: Collaborates, P3: Disagrees, P4: Collaborates

Pirate5: Aware of the above eqn , he can quote any division with small incentives to P4 and P2.
So Division ::
P5 = 97 ; P4 = 1 ; P3=0 ; P2 = 2 ; P1 = 0.
[P2 gets 2 cos he will anyways get 1 if he collaborates with P3. So incentive of one coin more is essential.]

4. Now dropping the assumption:
50% or more is considered a majority !!

This is more simpler given the above solution.
Pirate 4 has absolutely no incentive to collaborate with Pirate 5 for he knows that if he woos in Pirate 2, the deal is done.

So , the eqn is:
P1: Disagrees, P2: Collaborates, P3: Disagrees, P4: Disgrees

In absence of P5, P4 division would have been:
P4= 98 ; P3=0; P2 = 2 ; P1 = 0.

So P5,inorder to stay alive will quote the same division as above and stay alive (this is taking no irrationality by P4 into account).

Final Division :
P1 = 0 ; P2 = 2; P3 =0 ; P4 = 98 ; P5 = 0

5. Since Raj has given a really good try .. and has got nearly the right answer ..... i am posting the correct answer .....

The eldest pirate will propose a 97 : 0 : 1 : 0 : 2 split.

Working backwards, splits in terms of younger to older:

2 Pirates: Pirate Two splits the coins 100 : 0 (giving all to the other pirate). Otherwise, and perhaps even then, Pirate One (the youngest) would vote against him and over he goes!

3 Pirates: Pirate Three splits the coins 0 : 1 : 99. Pirate One (the youngest) is going to vote against him no matter what (see above), but this way, Pirate Two will vote for him, to get at least one gold out of it.

4 Pirates: Pirate Four splits the coins 1 : 2 : 0 : 97. This way, Pirate One will vote for him, and so will Pirate Two - they're getting more than they would under 3 pirates.

5 Pirates: Pirate five splits the coins 2 : 0 : 1: 0 : 97. This way, Pirate One will vote for him, and so will Pirate Three - they're both getting better than they would under 4.