What am I thinking today?

Saturday, July 04, 2009

Fair Resource Allocation Policy

Do you remember the story of 2 cats and a monkey from school? Refresh your memory using this story and also see here. This is an interesting problem and it demonstrates how government operates. When 2 cats cannot solve a problem, they think a third person can solve it in whom they have vested all power. The cats don't stop to think that the monkey can misuse its power and they stand to lose all that they have gained.

The monkey in this fable consumed everything that the cat had, but in real life politics work differently. The government has to live beyond the fable and hence it consumes only a part of what the cats have.

If the cats live in a socialist society, the government would consume a large part of the cheese for its purposes and give the rest to the thinest cat. If the cats are in certain kind of class segregated societies, the government would give the cheese to the cat based on its class. If the cats are in a libertarian society, they would be wise enough to solve it themselves. Can there be a non-government solution to this issue? See below for answer.

Solution to 2 cat problem
One cat splits the cheese and the other cat choses one of the halves. The first cat cannot be selfish. If it splits unequally, there is a good chance that the second cat will chose the larger half. The first cat can get the best outcome by splitting equally.

Solution to N cat problem
How would you extend this solution to multiple cats? If there are N cats, you will do this:
  1. for i = 1 to N-1
    1. cat i splits a whole piece of cheese into 2 parts
  2. for i = N to 1
    1. cat i choses the best piece
How does this work? Since the last cat gets to chose which fraction it is going to take, the former cats cannot be selfish. They have to split the cheese such that there is 1/N part separated out at each step. If cat i tries to be selfish, there will be some cat j > i which will get a bigger share of the cheese.

The assumption here is that cats don't collaborate during the splitting process. Can M of the N cats collaborate and get a better outcome than 1/N for each one of them? I think it is doable but need to work out some strategy. Also, is there a solution for avoiding such collaboration?

0 Comments:

Post a Comment

<< Home