Divide and choose

From Wikipedia, the free encyclopedia

In problems of fair division, divide and choose (also I cut, you choose) is a two-party proportional envy-free allocation protocol.[1] The protocol also works for dividing an undesirable, as in chore division.

In the method, one person divides a good or resource into what they believe are equal halves, and the other person chooses the "half" they prefer. Thus, the person making the division has an incentive to divide as fairly as possible: for if they do not, they will likely receive an undesirable portion. This rule is a concrete application of the veil of ignorance concept. Unlike those for more people, 2 person fair divisions are also automatically envy-free.

Analysis of the method becomes more difficult if two players place different values on some subsets of the resource. One commonly used example is a cake that is half vanilla and half chocolate. Suppose Bob likes only chocolate, and Carol only vanilla. If Bob is the cutter and he is unaware of Carol's preference, his optimal strategy is to divide the cake so that each half contains an equal amount of chocolate. But then, regardless of Carol's choice, Bob gets only half the chocolate and the allocation is clearly not Pareto efficient. It is entirely possible that Bob in his ignorance would put all the vanilla in one portion so Carol gets everything she wants, whilst he only gets half what he could have got by negotiating.

In 2006 Steven J. Brams, Michael A. Jones, and Christian Klamler detailed a new way to cut a cake called the surplus procedure (SP) that satisfies equitability and so solves the above problem.[2] Both people's subjective valuation of their piece as a proportion of the whole is the same.

If Bob knew Carol's preference and liked her, he could cut the cake into an all-chocolate piece, and an all-vanilla piece, Carol would choose the vanilla piece, and Bob would get all the chocolate. On the other hand if he doesn't like Carol he can cut the cake into slightly more than half vanilla in one portion and the rest of the vanilla and all the chocolate in the other. Carol might also be motivated to take the portion with the chocolate to spite Bob. There is a procedure to solve even this but it is very unstable in the face of a small error in judgement.[3] More practical solutions that can't guarantee optimality but are much better than divide and choose have been devised by Steven Brams and Alan Taylor, in particular the Adjusted Winner procedure (AW).[4][5]

The divide and choose method does not guarantee each person gets exactly half the cake by their own valuations, and so is not an exact division. There is no finite procedure for exact division but it can be done using two moving knives. [6]

[edit] See also

[edit] Notes and references

  1. ^ More plainly, a method whereby two people may divide a resource (such as a cake or pie), such that neither person feels the division caused one person to get more than a "fair share" of the resource.
  2. ^ Better Ways to Cut a Cake by Steven J. Brams, Michael A. Jones, and Christian Klamler in the Notices of the American Mathematical Society December 2006.
  3. ^ Cake Cutting with Full Knowledge David McQuillan 1999 (not reviewed)
  4. ^ Steven J. Brams and Alan D. Taylor (1996). Fair Division - From cake-cutting to dispute resolution Cambridge University Press. ISBN 0-521-55390-3
  5. ^ Steven J. Brams and Alan D. Taylor (1999). The Win/win Solution: Guaranteeing Fair Shares to Everybody Norton Paperback. ISBN 0-393-04729-6
  6. ^ Jack Robertson and William Webb (1998). Cake-Cutting Algorithms - Be Fair if You Can. A K Peters ISBN 1-56881-076-8