Misplaced Pages

Divide and choose

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from I cut, you choose) Two-person envy-free cake-cutting method

Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. 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") selects one of the pieces; the cutter receives the remaining piece.

The procedure has been used since ancient times to divide land, cake and other resources between two parties. Currently, there is an entire field of research, called fair cake-cutting, devoted to various extensions and generalizations of cut-and-choose.

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" (northern) part and a "right" (southern) 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, Bethel, and Shechem.

The United Nations Convention on the Law of the Sea applies a procedure similar to divide-and-choose for allocating areas in the ocean among countries. A developed state applying for a permit to mine minerals from the ocean must prepare two areas of approximately similar value, let the UN authority choose one of them for reservation to developing states, and get the other area for mining:

Each application... shall cover a total area... sufficiently large and of sufficient estimated commercial value to allow two mining operations... of equal estimated commercial value... Within 45 days of receiving such data, the Authority shall designate which part is to be reserved solely for the conduct of activities by the Authority through the Enterprise or in association with developing States... The area designated shall become a reserved area as soon as the plan of work for the non-reserved area is approved and the contract is signed.

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 partner's share.

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.

Generalizations and improvements

Dividing among more than two parties

Divide-and-choose works only for two parties. When there are more parties, other procedures such as last diminisher or Even–Paz protocol can be used. Martin Gardner popularized the problem of designing a similarly fair procedure for larger groups in his May 1959 "Mathematical Games column" in Scientific American. See also proportional cake-cutting. A newer method was reported in Scientific American. It was developed by Aziz and Mackenzie. While faster in principle than the earlier method, it is still potentially very slow. See envy-free cake-cutting.

Efficient allocations

Divide-and-choose might yield 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. 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 latter, and Bob would get all the chocolate. On the other hand, if he does not like Carol, he can cut the cake with slightly less than half the vanilla part 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. More practical solutions that can't guarantee optimality but are much better than divide and choose have been devised, in particular the adjusted winner procedure (AW) and the surplus procedure (SP). See also Efficient cake-cutting.

Dividing with a single point

Wagener studies a variant of Divide and Choose on a two-dimensional cake, in which the divider is disadvantaged: instead of making a cut, he can only mark a point on the cake. The chooser can then make a straight cut through that point, and choose the piece he prefers. He proves that, if the cake is bounded, the divider can always secure at least 1/3 of the cake. If the cake is both bounded and convex, the divider can secure 4/9 of the cake.

See also

  • Market maker – Stock market trading entity, 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. Steinhaus, Hugo (1948). "The problem of fair division". Econometrica. 16 (1): 101–4. JSTOR 1914289.
  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. ^ Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. ISBN 978-1-56881-076-8. LCCN 97041258. OL 2730675W.
  4. Young, H. Peyton (1995-01-01). Equity. Princeton University Press. doi:10.1515/9780691214054. ISBN 978-0-691-21405-4.
  5. Walsh, Toby (2011). "Online Cake Cutting". In Brafman, Ronen I.; Roberts, Fred S.; Tsoukiàs, Alexis (eds.). Lecture Notes in Computer Science. Vol. 6992. Berlin, Heidelberg: Springer. pp. 292–305. doi:10.1007/978-3-642-24873-3_22. ISBN 978-3-642-24873-3. S2CID 501890. {{cite book}}: |journal= ignored (help); Missing or empty |title= (help)
  6. United nations (1982-12-10). "Annex III: Basic conditions of prospecting, exploration and exploitation. Article 8". un.org. Archived from the original on 2001-09-14.
  7. Gardner, Martin (1994). My Best Mathematical and Logic Puzzles. Dover Publications. ISBN 978-0486281520.
  8. Klarreich, Erica (October 13, 2016). "The Mathematics of Cake Cutting". Quanta Magazine (Scientific American).
  9. 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}}: Cite journal requires |journal= (help)
  10. Cake Cutting with Full Knowledge David McQuillan 1999 (not reviewed)
  11. Steven J. Brams and Alan D. Taylor (1999). The Win/win Solution: Guaranteeing Fair Shares to Everybody Norton Paperback. ISBN 0-393-04729-6
  12. 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.
  13. Wagener, Andreas (2006-01-01). "Geometric division with a fixed point: Not half the cake, but at least 4/9". Group Decision and Negotiation. 15 (1): 43–53. doi:10.1007/s10726-005-9000-z. ISSN 1572-9907.
Categories: