https://www.cantorsparadise.com/envy-free-cake-cutting-procedures-de3cf13c5d3d

How to Ensure Fairness as a Mechanistic Outcome

Jørgen VeisdalFollowNov 25, 2019 · 12 min read

In the context of economics and game theory, envy-freeness is a criterion of fair division where every person feels that in the division of some resource, their share is at least as good as the share of any other person — thus they feel no envy. For n=2 people, the protocol proceeds by the so-called divide and choose procedure:

The Envy-Free Cake-Cutting procedure states that if two people are to share a cake in way in which each person feels that their share is at least as good as any other person, 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.

For cases where the number of people sharing is larger than two, n > 2, the complexity of the protocol grows considerably. The procedure has a variety of applications, including (quite obviously) in resource allocation, but also in conflict resolution and artificial intelligence, among other areas. Thus far, two types of envy-free caking cutting procedure have been studied, for:

• Cakes with connected pieces, where each person receives a single sub-interval of a one dimensional interval; and
• Cakes with general pieces, where each person receives a union of disjoint sub-intervals of a one dimensional interval

This essay takes you through examples of the various cases (n = 2, 3, …) of how to fairly divide a cake into connected- and general pieces, with and without the additional property of envy-freeness. Happy reading!

History

Interesting mathematical problems arise if we are to determine the minimal numbers of “cuts” necessary for fair division. — Hugo Steinhaus

The earliest reference to the envy-free cake-cutting protocol is from the Book of Genesis, where the character of Abraham divides the land of Canaan and the character Lot chooses which of the two lands he wants. In modern times, the problem was first studied in the 1940s by Polish mathematicians Stefan Banach, Bronisław Knaster and in particular, their doctoral advisor Hugo Steinhaus. The first fairness criterion studied by Steinhaus was proportional division, which simply involves dividing a resource among agents with subjective valuations of each share of the resource. Steinhaus was also the first to generalize the problem definition to three or more people, by inviting the proportional division criterion. He first presented the cake cutting problems in 1947 at a meeting of the Econometric Society in Washington D.C.

A stronger criterion of envy-freeness was introduced in 1958 by George Gamow and Marvin Stern. Their criterion states that each agent believes their share is at least as small as any other share, implying that no agent would wish to swap their share with any other agent. Duncan Foley in 1967 introduced the concept of envy-freeness to economics, where it would later become the so-called ‘dominant fairness criterion’, used among other places in the existence theorems of Google’s chief economist Hal Varian on Pareto-efficient envy-free division (Varian, 1974). In the 1960s, the first procedure for envy-free cake cutting for three partners and general pieces was proposed by John Selfridge and John Horton Conway.

The Mathematics of Cake-Cutting

The cake is a metaphor for a divisible heterogeneous resource

Formally, we may define the “cake” to be divided in the following way, with the following properties:

A cake is represented by the interval [0,1] where a piece of cake is a union of subintervals of [0,1]. Each agent in N = {1,...,n} has their own valuation of the subsets of [0,1]. Their valuations are- Non-negative: Vᵢ(X) ≥ 0
- Additive:     for all disjoint X, X' ⊆ [0,1]
- Divisible:    for every X ⊆ [0,1] and 0 ≤ λ ≤ 1, there exists X' ⊂ X with Vᵢ(X') = λVᵢ(X)where Xᵢ is the allocation of agent i.The envy-free property in this model may be defined simply as:Vᵢ(Xᵢ) ≥ Vᵢ(Xⱼ) ∀ i,j ∈ N.

In general, we distinguish between two types of cake-cutting:

• Proportional division, in which a resource is divided among n people with subjective evaluations, giving each person ate least 1/n of the resource by his/her own subjective valuation.
• Envy-free division, proportional division with the added property that every person feels that their share is at least as good as the share of any other agent.

The concept of “fairness” may further formalized as satisfying the following conditions (Pacuit, 2007):

Proportionality: Each player receives at least 1/n of the resource according to their own estimation of its utilityEnvy-freeness: No player is willing to give up its allocation in exchange for the other players' allocationsEquity: Each player values his/her allocation the same as the other allocations, according to their own utility functionEfficiency: There does not exist any other division which better maximizes the collective utilities of everyone, or someone

Moving Knife procedures

Several methods of division are called ‘moving-knife procedures’ described by Austin (1982) as:

A Moving-Knife Cake-Cutting Procedure
For two people, Alice and Bob:1. One player moves the knife across the cake, conventionally from left to right2. The cake is cut when either person calls "stop"3. If each player calls stop when he or she perceives the knife to be at the 50-50 point, then the first player to call stop will produce an envy-free division if the caller gets the left piece and the other player gets the right piece

Proportional Division

For proportional division (proportionality), a resource is divided among n people with subjective evaluations, giving each person ate least 1/n of the resource by his/her own subjective valuation. It has been showed that for n people with additive valuation, a proportional division always exists and there are several known protocols for achieving such allocations, including:

The Banach-Knaster “Last Diminisher” Procedure (Steinhaus, 1948)

Inspired by the divide and choose protocol for dividing a cake between two partners, Hugo Steinhaus in 1947 challenged two of his doctoral students, Stefan Banach and Bronisław Knaster to find a procedure that could work for any number of people. Their solution was published in the paper The Problem of Fair Division in Econometrica 16 (1) in 1948. In the words of the authors, the protocol works as follows (Steinhaus, 1948 p. 102):

The partners being ranged A, B, C,.. N, A cuts from the cake an arbitrary part. B has now the right, but is not obliged, to diminish the slice cut off. Whatever he does, C has the right (without obligation) to diminish still the already diminished (or not diminished) slice, and so on up to N. The rule obliges the "last diminisher" to take as his part the slice he was the last to touch. This partner being thus disposed of, the remaining n−1 persons start the same game with the remainder of the cake. After the number of participants has been reduced to two, they apply the classical rule for halving the remainder.- Excerpt, The Problem of Fair Division (Steinhaus, 1948)

Explained somewhat more neatly:

The Banach-Knaster "Last Diminisher" Procedure
For three people Alice, Bob, Carol:1. Alice begins by cutting from the cake, a part of an arbitrary size according to her individual utility function2. Bob next has the right, but is not obliged to, cut a part from Alice's slice. Carol then next also has the right, but is not obliged to, cut another part from Alice's slice3. Each person has to take the slice they were the last to cut from, and thus exit the game4. The procedure repeats with the remainder of the cake among the people who have yet to receive a piece

The procedure is equitable but not envy-free because, although all players can ensure themselves to at least 1/n pieces by not diminishing a piece, all except the last two players may envy those who receive pieces later — i.e., although players exist the game satisfied with their piece, they cannot guarantee that they would not have preferred a piece later obtained by someone else (Brams & Taylor, 1996).

The Dubin-Spanier “Moving Knife” Method

A continuous-time version of the “Last Diminisher” method is the Dubin-Spanier “moving knife” method, proposed by Lester E. Dubins and Edwin H. Spanier (1961). It is the first moving-knife procedure described in the literature (although, as pointed out by Brams & Taylor, an earlier “pouring procedure” was published in Davis, 1955).

The Dubin-Spanier Moving-Knife Method1. A referee holds the knife on the left side of the cake, and then moves the knife towards the right side at a continuous pace2. At any point, any of the three players can call out "cut", and receive the piece to the left of the knife, existing the game3. The procedure repeats with the remainder of the cake. If the remaining two players yell cut simultaneously, the cut piece is given to one of the players at random

The Dubin-Spanier procedure is equitable (each player values his/her allocation to be the same as the others, according to his/her own utility function) but not envy-free. A key difference between the procedure and the last diminisher is that each player still in the game has to make continuous choices, rather than by turns.

The Steinhaus-Kuhn “Lone Divider” Procedure

The so-called “lone divider procedure” is a fair division procedure which, like the last diminisher and the moving-knife method above, also results in a proportional division of the resource among an arbitrary number of people. It was proposed by game theorist Harold Kuhn in 1967 and works as follows (Brams & Taylor, 1996), in the case of n=3 for simplicity’s sake:

The Steinhaus-Kuhn "Lone Divider" Procedure
For three people Alice, Bob and Carol:1. Let Alice cute the cake into three pieces of equal value based on her utility function2. Now let Bob and Carol indicate which pieces are acceptable to them (at least of value 1/3 based on their own utility functions)This leads two two mutually exclusive cases:1. Either Bob or Carol finds two or more pieces are acceptable. If Bob finds more than one piece acceptable, then choosing in the order: Carol, Bob and Alice will result in a proportional allocation2. Or, both Bob and Carol indicate that at most one piece is acceptable. We then give the piece that both Bob and Carol find unacceptable to Alice, then do a divide and choose procedure between Bob and Carol. This will also result in a proportional allocation

Because it is impossible for either Carol or Bob to think that all three pieces cut by Alice are unacceptable (of sizes smaller than 1/3), case two must prevail if case one does not, as they are the only two possible situations.

The “lone divider” procedure is not envy-free either because in case one, although Alice and Bob will not envy anyone, Alice will envy Bob if he took the larger of the two pieces she considered acceptable. In case two, if the redivision by Bob and Carol is not exactly 50/50 according to Bob, then he will be envious of one of the other two (Brams & Taylor, 1996).

Kuhn published the result in a book chapter entitled On games of fair division in the 1967 book Essays on Mathematical Economics in Honor of Oskar Morgenstern edited by Martin Shubik for Princeton University Press. In the book, Kuhn presents the case of an arbitrary number of players, and proves fair proportional division by making use of the Frobenius-König theorem.

Envy-Free Division

The added criterion of envy-freeness requires that in addition to proportional division (equity), the allocation of the resource has the property of envy-freeness, namely that

Envy-freeness: No player is willing to give up its allocation in exchange for the other players' allocations

Selfridge-Conway Discrete Procedure

The first envy-free discrete cake-cutting procedure for three players was discovered by John Selfridge in 1960, without publishing its proof. It was later re-discovered by John Horton Conway independently, although he also chose not to publish it (Brams & Taylor, 1996). The procedure may be described in the following way for players Alice, Bob and Carol:

The Selfridge-Conway Envy-Free Cake-Cutting Procedure
For players Alice, Bob and Carol:1. Alice divides the cake into three pieces A,B,C she considers to be of equal size.2. Bob thinks piece A is the largest piece3. Bob now trims a bit off piece A to make it the same size as the second largest piece. Now, piece A is divided into: 1. The trimmed piece A₁ and the trimmings A₂4. Carol next chooses a piece among A₁ and the two other pieces B, C5. Bob next chooses a piece with the limitation that if Carol didn't choose A₁, he has to6. Alice finally chooses the last piece leaving only the trimmings A₂ to be divided among the threeThe trimmed piece A₁ was chosen by either Carol or Bob. Call the player that chose it Player A and the other Player B. To divide the trimmings A₂ among them:1. Player B first cuts the trimmings A₂ into three equal pieces A₂₁, A₂₂ and A₂₃2. Player A then chooses a piece of A₂, call it A₂₁3. Alice next chooses a piece of A₂, call it A₂₂4. Player B finally chooses the last remaining piece of A₂, call it A₂₃

The outcome of the procedure is:

• Player A received piece A₁ + A₂₁
• Player B received piece B + A₂₃
• Alice received piece C + A₂₂

The Selfridge-Conway procedure ensures envy-freeness because if Carol chooses first, she does so knowing what she has to choose from, and so will not envy anyone who chooses either of the other two pieces. Because Bob creates a two-way tie for the largest piece by trimming piece A, and at least one of these two is still available after Carol chooses, he will not either envy anyone. Finally, because if Carol didn’t choose A₁, Alice has to, the trimmed piece cannot be the one left over. Hence, Alice chooses among two untrimmed pieces which she herself cut, and so will not envy anyone.

The key observation is hence that Alice will not envy the player who receives the trimmed piece. Alice created a three-way tie among the pieces and received an untrimmed piece, while the trimmed piece, even with the trimmings added to it, would yield Carol only a piece that Alice considers to be exactly the same size as the one she received (Brams & Taylor, 1996)..

Stromquist “Moving-Knives” Procedure

For connected pieces, the so-called Stromquist moving-knives procedure first introduced by Walter Stromquist in 1980 ensures both proportionality and envy-freeness (). Similar to the Dubin-Spanier moving knife procedure, it requires that the players make continuous choices as to whether or not the slice to the left of the knife ensures them a piece which is proportional.

The Stromquist "Moving-Knives" Envy-Free Cake Cutting Procedure1. A referee moves a knife from left to right over a one-dimensional cake, hypothetically dividing it into a small left piece and a large right piece2. Each player has their own knife, kept parallel and to the right of the referee's knife, always positioning it so that it divides the remainder of the cake in half3. At any time, any player can call out "cut", receiving the piece to the left of the referee's knife. Simultaneously, a cut is made by whichever of the three players' knives is in the middle of the three players' knives4. The player that called cut receives the piece to the left of the referee's knife. The player whose knife was closest to the referee's knife receives the middle piece. The last player receives the right piece.

The Stromquist moving-knives procedure ensures envy-freeness because whoever receives the middle piece (of the two players who did not yell cut, had their knife closest to the referee’s knife) held either the second or third knife from the left. Hence, that player that received the middle piece thinks that the middle piece is either larger than the right piece (if his/her knife is closest to the referee’s knife) or tied with the right piece for largest (if his/her knife is the knife that divides the remainder of the cake). Similarly, the other player who did not yell cut held either the knife who cut the remainder of the cake, or the knife on the far right.

Epilogue

Hugo Steinhaus’ initial publication The problem of fair division set the scene for a century of ever-more complicated and complete cake-cutting procedures. A sub-branch of fair division, which itself is a sub-branch of game theory, cake-cutting today stands as an archetypal game which represents the incentives and limitations of certain kinds of social scientific conflicts of competition and cooperation in non-cooperative games.

Those interested in studying cake-cutting procedures further are encouraged to check out the book Fair Division by Steven J. Brams and Alan D. Taylor (1996). In addition, the YouTuber Numberphile, Brady Haran, has a video about cake-cutting procedures for n=3 which is quite good, available here.

This essay is part of a series of stories on math-related topics, published in Cantor’s Paradise, a weekly Medium publication. Thank you for reading!