Divide and choose


Divide and 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. 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.
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.

Description

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 and two partners who have different preferences over parts of the cake. The procedure proceeds as follows: one person cuts the cake into two pieces; the other person selects one of the pieces; the cutter receives the remaining piece.

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. 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" part and a "right" 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:

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

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 unequal, the chooser has no reason to complain because they chose the piece they wanted.
To an external viewer, the division might seem unfair, but to the two involved partners, the division is fair — no partner has cause to envy the other'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 and for dividing an undesirable resource.
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 -- the cutter may perceive the advantage of parts of the cake differently from the chooser and anyways the chooser chooses what he thinks is the better half. So the "divide and choose" procedure does not produce an exact division. There is no definite procedure for exact division, but it can be done using two moving knives; see Austin moving-knife procedure.

Generalizations and improvements

Symmetric version

The original cut-and-choose is not symmetric as the agents have different roles. This might lead to arguments regarding who will be the cutter and who will be the chooser. For a one-dimensional cake, there is a variant called symmetric cut-and-choose.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 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 and the surplus procedure. 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.