How to Divide the Loot Fairly?
Consider this problem: two robbers who teamed up for more than three years decided to split up, due to various reasons. None of them was like O'Henry's Shark Dodson. So they took a fair road and elected to share their accumulated loot. The first divided the booty into two piles he thought equal. The second did not quite agree with his friend. In his opinion, one pile was a little bigger than the other. He thought himself very clever to pick the bigger pile. The first had no problem with the remaining one. So each was under impression he got at least one half of the booty.
O'Henry wrote about two friends but we may not stop here. What if there were 3 of them? Or even an arbitrary number n? Is it possible for them to find a way to share their loot in such a way that each will leave with the impression of getting at least 1/n-th part?
The following solution was sent to me by Richard Beigel.
One robber divides the loot into n piles that he considers equal size. For each pile he asks, "any takers." Each pirate must indicate if he would be satisfied with that pile, i.e., whether he considers that pile to be at least 1/n-th of the total.
For each set S of piles, let takers(S) be the set of pirates that is satisfied with at least one pile in S. Let P be the smallest nonempty set of piles satisfying
|takers(P)| ≥ |P|.
If |P| = 1, this is true because the first robber is in takers(P). If |P| > 1 then let x be any element of P. Then
Therefore |takers(P)| = |P|. Thus if R is any subset of P then
The second solution has been kindly provided by Yuri Kifer of the Hebrew University.
As before, the first robber divides the loot into n piles which he considers to be equal. A robber likes a pile if he thinks that it is at least 1/n-th of the whole booty. If, for any k,
Denote by R the set of all robbers, by B the whole booty of piles, and, for a set A of robbers, by covet(A), the set of all piles which robbers from A like (together). By our assumption, there are sets A of robbers with the property
Clearly, |Q|< |R| since the first robber (who divided the booty) cannot be in Q (otherwise,
Since all robbers from Q think that each pile from B - covet(Q) is less than 1/n-th of the whole loot, they will think that robbers from
So we have two proofs: one concentrating on the desired piles, the other on the robbers' desires. A comparison of the two proofs raises an interesting question. Is there any connection between the minimal set P of piles that satisfies
There is a third, quite elementary solution for which thanks are due to Michael Kifer from SUNY,
Let N-1 robbers divide the whole pile the way they agree is equitable. Then the Nth robber steps in and asks each of the N-1 robbers to divide his share in N equal pieces (ie, each robber must think that he divided his share in N equal pieces).
Finally, the Nth robber goes around and collects the largest (in his view) N-th piece from each robber.
Clearly, each must think that he's got at least 1/N of the whole pile.
Since we know how to divide for N = 2, the problem is solved by induction.
There are great many ways to approach and solve the problem of fair division. There is an interesting example where the solution is utterly unfair (unbalanced), although it is accepted by consensus.