Divide and choose

Divide and choose

• Divide and choose (also cut and choose or I cut, you choose**) is a procedure for [[fair-division]] of a continuous resource between two parties. It involves a heterogeneous good or resource and two partners who have different preferences over parts of the cake (both want as much of it as possible). The procedure proceeds as follows: one person divides the resource into two pieces; the other person selects one of the pieces; the cutter receives the remaining piece.

Divide and 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 (both want as much of it as possible). The procedure 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.

Since ancient times some have used the procedure to divide land, food 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. 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.

History Since ancient times some have used the procedure to divide land, food 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.

Divide and choose is mentioned in the Bible, in the Book of Genesis (chapter 13). When Abraham and Lot came to the land of Canaan, Abraham suggested that they divide it among them. Then Abraham, coming from the south, divided the land to a "left" (western) part and a "right" (eastern) part, and let Lot choose. Lot chose the eastern part, which contained Sodom and Gomorrah, and Abraham was left with the western part, which contained Beer Sheva, Hebron, Bethel, and Shechem.

In medieval literature, divide and choose is mentioned in the Italian tale La novella di Messer Dianese e di Messer Gigliotto, a variant of the grateful dead motif, where the knight, after spending his money on the burial, meets the dead in the form of a rich merchant who offers to become his sponsor in a tournament in exchange for half of the rewards. The merchant, when the time comes for the division, states he will divide and the knight will choose, and the choice turns out to be between the wife and the riches won. The knight is forced to choose the wife, after which the merchant gives the riches to the knight as well.

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: <blockquote> 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. </blockquote>

Analysis 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:In symmetric cut-and-choose, both agents mark their subjective mid-points; then, the cake is cut between the two mid-points, and each agent receives the piece containing his or her own mark. This version still guarantees proportionality.

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 * , players in financial markets who offer to either buy or sell at a given price (plus a spread) *

Notes and references