Sunday, December 23, 2007

Your half is bigger than mine...... NOT! -- On fair division

The problem of fair division can be traced back a full 3000 years in history. Stated in simple terms, the problem is:
How do you divide a cake between n people such that each person gets a fair share of the cake? An additional clause is that if someone thinks they got lesser than someone else, then it should be such that, that person alone is to bear the blame.

Lets first consider the case of n=2. If there are two people involved, say Alice and Bob, the solution is simple -- "Alice cuts, Bob chooses". So the best solution for Alice in this scenario is to cut such that she feels both shares are equal halves, so that no matter which piece Bob chooses, she's happy with the other one. Best solution for Bob is that he chooses the piece he thinks is bigger. Now, if Alice didnt cut it into equal halves, and Bob chooses the bigger one, she has only herself to blame for being left with the smaller piece.

If you now extend this to n=3, the problem becomes extemely complicated. You can imagine how the above solution can be extended. Say Tom, Dick, and Harry are trying to divide the cake equally between themselves. You can imagine a solution where Tom cuts the cake into what he thinks are 1/3rd and 2/3rds. Then Dick cuts the 2/3rd piece into two halves. Harry picks one of the three pieces. Tom picks next, and the left over piece goes to Dick.

Some elementary analysis will reveal that this is fair to Tom and Harry, and not fair to Dick. Now, clearly, Harry is satisfied. There are three pieces and he picks the biggest of the three. Tom comes next. If Harry picked one of the pieces that Dick cut, then Tom can take the piece that he cut (as 1/3rd) and be satisfied. If Harry picks the 1/3rd piece that Tom cut, then Tom can take whichever of the other two he thinks is bigger -- at this stage it is a two-person problem betwen Tom and Dick, since he thinks the 2/3rd really was a 2/3rds.

The story for Dick though is very different. If Dick initially thought Tom's cut was fair, then he has no issues, and the solution works for all. However, if Dick thinks Tom's cut was unfair and the 2/3rd was smaller than actual 2/3rd, then no matter what, he will end up with an unfair deal.

The way to fix the solution is to not let Dick think Tom's cut was unfair. This is achieved by allowing Dick to "trim" Tom's 1/3rd version and adding that into the 2/3rd share before making the second cut. Now if Harry thought Tom's cut was fair, then he will pick from Dick's cut since he thinks that is bigger. Tom will also pick from Dick's cut. And Dick can take the "trimmed" 1/3rd since he thought that was a fair 1/3rd. The deal with this solution is it will take 3 cuts (one by Tom, one "trim" by Dick, and another by Dick). If you generalize this to the n player version, then this algorithm will take n*(n-1)/2 cuts.

This problem has been addressed by a lot of mathematicians in history. The first (erroneous) solution for the 3 person problem was provided by Robertson and Webb. The corrected n*(n-1)/2 cuts solution was provided in 1944 by Hugo Steinhaus. Since then advanced concepts in mathematics have chosen this problem to purvey their theories. We'll see a non-envy version of this problem later in this post. Fair division is a very practical problem in the real world. Be it geek-ish like bandwidth sharing, or esoteric like dividing Jerusalem and West Bank. As a twist, the problem gets very intricate and interesting when different parties believe different parts of the cake are better than other parts.

We extend the original problem to fair division without envy. In the earlier case, everyone got a fair deal, but we potentially still had people imagining that others got more than them. In fact, that was the case in all solutions except the 2 person scenario. The two person "I cut, you choose" scenario is guaranteed to be envy-free.

Lets define a cake-division as envy-free if no one thinks that someone else got a larger piece than they did. An envy-free division is always guaranteed to be fair. However a fair division need not be envy-free at all.

Lets look at a solution for the 3-person case envy-free fair division -- same drill: Tom, Dick, and Harry want to divide a cake fairly between them in an envy-free fashion -
  • First, Tom divides the cake into three parts which he thinks are equal 1/3rds.
  • Next, (a) if Dick thinks the two largest pieces are equal, he does nothing, otherwise (b) Dick trims one piece to achieve two equal largest pieces.
  • Now, Harry, Dick, and Tom in that order pick. If Dick trimmed a piece earlier, then he has to pick the trimmed piece unless Harry has already picked it.
At this stage, you have an envy-free fair division of three pieces. What is leftover is the problem of dividing the "trimming".
  • Now, if Dick didnt trim, then there is nothing to do. If he did trim, then either Dick or Harry took the trimmed piece. We'll assume Dick took the trimmed piece. (Substitute Harry for Dick in the rest of the solution if Harry took the trimmed piece.) Dick now divides the "trimming" into three equal parts.
  • Harry, Tom, and Dick in that order now pick. Harry picks first, so he's not envious at all. Tom picks next, but he's absolutely not envious since this trimming is already a bonus for him -- he thought his first three way cut was already equal 1/3rds. Dick picks the last one, but he isnt envious either since he divided the "trimmings" 3-ways.

When you extend this to a n-person scenario, the problem becomes extremely complicated. Found a wikipedia link on Fair Division. Wikipedia talks about many versions of the problem and how after a century of solutions Steven Brams and Alan Taylor finally solved it in 1995. That was the solution for the general n-person envy-free fair division. That came 30 years after the first 3-person envy-free fair division solution. The first I came across this problem was when I heard Alan Taylor give a rather animated talk on this at Yale back in 1998.

No comments: