Divide and choose

Divide and choose (also Cut and choose or I cut, you choose) is a procedure for envy-free cake-cutting between two partners. It involves a heterogeneous good or resource ("the cake") and two partners who have different preferences over parts of the cake. The protocol proceeds as follows: one person ("the cutter") cuts the cake into two pieces; the other person ("the chooser") chooses one of the pieces; the cutter receives the remaining piece.

History

Divide and choose is mentioned in the Bible, in the Book of Genesis (chapter 13). When Abraham and Lot come to the land of Canaan, Abraham suggests that they divide it among them. Then Abraham, coming from the south, divides the land to a "left" (western) part and a "right" (eastern) part, and lets Lot choose. Lot chooses the eastern part which contains Sodom and Gomorrah, and Abraham is left with the western part which contains Beer Sheva, Hebron, Beit El, and Shechem.

Analysis
A cake cut into two pieces

Divide and choose is envy-free in the following sense: each of the two partners can act in a way that guarantees that, according to their own subjective taste, their allocated share is at least as valuable as the other share, regardless of what the other partner does. Here is how each partner can act:

  • The cutter can cut the cake to two pieces that they consider equal. Then, regardless of what the chooser does, they are left with a piece that is as valuable as the other piece.
  • The chooser can select the piece they consider more valuable. Then, even if the cutter divided the cake to pieces that are very unequal (in the chooser's eyes), the chooser still has no reason to complain because they chose the piece that is more valuable in their own eyes.

To an external viewer, the division might seem unfair, but to the two involved partners, the division is fair—no partner envies the other.

If the value functions of the partners are additive functions, then divide and choose is also proportional in the following sense: each partner can act in a way that guarantees that their allocated share has a value of at least 1/2 of the total cake value. This is because, with additive valuations, every envy-free division is also proportional.

The protocol works both for dividing a desirable resource (as in fair cake-cutting) and for dividing an undesirable resource (as in chore division).

Divide and choose assumes that the parties have equal entitlements and wish to decide the division themselves or use mediation rather than arbitration. The goods are assumed to be divisible in any way, but each party may value the bits differently.

The cutter has an incentive to divide as fairly as possible: if they do not, they will likely receive an undesirable portion. This rule is a concrete application of the veil of ignorance concept.

The divide and choose method does not guarantee that 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; see Austin moving-knife procedure.

Efficiency issues

Divide and choose might produce inefficient allocations.

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 safe 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 (and some amount of chocolate) in one larger portion, so Carol gets everything she wants while he would receive less than what he could have gotten by negotiating.

Alternatives

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.[1] 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).[2][3]

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.[4] Both people's subjective valuation of their piece as a proportion of the whole is the same.

Dividing among more than two parties

Martin Gardner popularized the problem of designing a similarly fair procedure for larger groups in his May 1959 "Mathematical Games column" in Scientific American.[5] One procedure begins with one person cutting what they consider a fair share. Anyone can then trim it down to be smaller. But whoever is the last person to trim it has to take it. See also the last diminisher.

A newer method is reported in Scientific American.[6] It was developed by Aziz and Mackenzie.[7] While faster in principle than the earlier method, it is still potentially very slow: O(n2n+3), where n is the number of divisions desired.

gollark: osmarkscalculator™.
gollark: How would *you* do it?
gollark: Well, except the Python ones; everyone knows Python can't `write` and you have to construct an ELF binary to call out to to do that instead.
gollark: And my last ones.
gollark: Even *I* know that the right way to do it would be to write the data to a file, use a hexdump program on the file, pipe that to the `printf` command or something to convert that to decimal, and then redirect the output of *that* to a file which you then memory-map and call `write` on.

See also
  • Fair division – Problem of sharing resources
  • Market maker, players in financial markets who offer to either buy or sell at a given price (plus a spread)
  • Resource allocation – Assignment of resources among possible uses

Notes and references
  1. Cake Cutting with Full Knowledge David McQuillan 1999 (not reviewed)
  2. Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press. ISBN 0-521-55644-9.
  3. Steven J. Brams and Alan D. Taylor (1999). The Win/win Solution: Guaranteeing Fair Shares to Everybody Norton Paperback. ISBN 0-393-04729-6
  4. 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.
  5. Gardner, Martin (1994). My Best Mathematical and Logic Puzzles. Dover Publications. ISBN 978-0486281520.
  6. Klarreich, Erica (October 13, 2016). "The Mathematics of Cake Cutting". Quanta Magazine (Scientific American).
  7. AZIZ, HARIS; MACKENZIE, SIMON (2017). "A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents". arXiv:1604.03655. Bibcode:2016arXiv160403655A. Cite journal requires |journal= (help)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.