Fair Division
Given a cake, how can a group of people divide the cake among themselves so that everyone is happy with their share? The problem of dividing goods has a long and rich history. This page explores the mathematical results on fair division since the 1940s, when Hugo Steinhaus began the mathematically rigorous study of this problem. Fair division touches upon many different topics and has surprising connections with the fields of combinatorics, mathematical induction, graph theory, algorithms, and topology.
Contents
2-Person Division
We begin by considering the case of fair division between two people: given a cake, how can two people divide the cake so that both people are happy with their share? What does it mean for both people to be happy with their share? We will study these questions by analyzing a well known method known as the cut-and-choose method.
2 Person Cut-and-choose Method: One person divides the cake into two parts and the other person chooses one of the resulting parts.
To understand whether or not this results in a division that everyone is happy with, we must first consider the preferences of the players. In general, people may have different preferences and the value of different portions of the cake may vary. For example, one person may prefer the piece at the center of the cake with the strawberry topping, while another person may love chocolate frosting and wants the corner piece of the cake with the most frosting.
In addition to different preferences, there are several ways to interpret fairness. A division of cake among \(2\) people is a proportional division if each person believes she or he has received at least \(\frac{1}{2}\) of the cake. A division of cake among \(2\) people is an envy-free division if each person believes she or he received the piece of largest value (or one of the pieces of largest value if there is a tie).
If Alice and Bob carry out the 2 Person Cut-and-choose Method, is the resulting division a proportional division? Is it an envy-free division?
Solution: Suppose Alice is the cutter and Bob is the chooser. From Alice's point of view, she knows that Bob will have the choice of either of the two pieces in her division, so her best strategy is to cut the cake into two pieces she believes have equal value. Then whichever piece she receives in the end, she believes this piece to have value exactly \(\frac{1}{2}\) of the cake and does not have a stronger preference for the other piece. From Bob's point of view, he is allowed to choose the piece he prefers, so in the end, he will not have a stronger preference for Alice's piece, and he receives a piece he believes to be at least \(\frac{1}{2}\) of the cake. This shows the result is both a proportional and envy-free division of the cake.
Moving Knife Procedures
We can generalize the definitions above to say that a division of cake among \(n\) people is a proportional division if each person believes she or he has received at least \(\frac{1}{n}\) of the cake, and is an envy-free division if each person believes she or he received the piece of largest value. Another way to think about an envy-free division is that no person has a strictly stronger preference for any other person's piece of cake.
Are all proportional divisions envy-free? Are all envy-free divisions proportional?
Moving Knife Procedures
Now that we have considered the problem of dividing a cake among two people, how do we divide a cake among three people, Alice, Bob, and Carol? We begin with the problem of proportional division: how do we divide a cake into thirds so that all three people are satisfied they have received at least \(\frac{1}{3}\)rd of the cake? The moving knife procedure works as follows. One person moves a knife slowly over the cake, so that the amount of cake on the left of the knife increases continuously from zero to the entire cake. As soon as either Alice, Bob, or Carol believes that the piece of cake to the left of the knife is equal to \(\frac{1}{3}\) of the cake, this person shouts "Cut!" The first person to shout out gets the piece to the left of the knife (if multiple people shout out at the same time, then any one of them can be chosen at random to receive this piece.) Then the person who has received a piece of cake goes off to get a glass of milk for their cake and the moving knife procedure continues with the remaining two people and the remaining portion of cake.
tinypic
We can analyze this procedure as follows:
- In both the first and second stages, the two people who shout "Cut!" receive pieces of cake they believe to be exactly \(\frac{1}{3}\) of the cake
- For the person who does not shout out during the process, this person believes that the piece to be cut from the cake in both the first and second stages are each less than \(\frac{1}{3}\) of the cake. Then the piece this person receives is at least \(1 - \frac{1}{3} - \frac{1}{3} = \frac{1}{3}\) of the cake.
This shows that the moving knife procedure gives a proportional division for \(3\) people. If Alice, Bob, and Carol would like to invite their friends to join the party, does the moving knife procedure also give a proportional division for everyone? Suppose \(n \geq 4\) people are dividing a cake with a knife moving continuously across the cake, and as soon as any person believes that the piece of cake to the left of the knife is equal to \(\frac{1}{n}\) of the cake, he/she shouts "Cut!" Now, the first person receives what they believe to be \(\frac{1}{n}\) of the cake and everyone else believes the remaining piece is at least \(1 - \frac{1}{n} = \frac{n-1}{n}\) of the cake. Now, by mathematical induction, the problem reduces to dividing \(\frac{n-1}{n}\) of the cake among \(n-1\) people and by the induction hypothesis, the moving knife procedure will give each of the remaining people at least \(\frac{1}{n-1}\) of the remaining cake, so each person receives what she/he believes to be at least \(\frac{1}{n-1} \times \frac{n-1}{n} = \frac{1}{n}\) of the original cake. This gives a proportional division for \(n\) people.
Does the moving knife procedure give an envy-free division of cake for all \(n\) people? In other words, if the procedure is carried out and in the end, all the pieces are placed on the table, would each person choose the piece they received during the moving knife process?
Solution: We show that the moving knife procedure gives a division that is proportional but not necessarily envy-free. Suppose Alice, Bob, and Carol are dividing a cake and Alice is the first to yell "Cut!" Then she takes the piece to the left of the knife, which she believes to have value \(\frac{1}{3}\) of the cake. Now, when the moving knife procedure continues with the remaining cake, there is a point where Alice believes the knife has moved over another \(\frac{1}{3}\) of cake, and she would yell "Cut!" (except that according to the procedure, she has now left the room to get a glass of milk and is no longer involved in the moving knife process). However, suppose Bob and Carol both believe the moving knife has not yet moved past the \(\frac{1}{3}\) value mark, so neither of them yell for the knife to stop. Then in the end, Alice believes the second piece of cake is larger than the first piece, so she does not receive what she believes to be the largest piece. This shows the moving knife procedure is not necessarily envy-free.
Mathematical Results
Observe that the moving knife procedure is not discrete (since the knife is assumed to move continuously across the cake in order to cut at any location) and does not necessarily result in an envy-free division. This leads us to the following questions: does there exist an envy-free division procedure for \(n\) people? Are there procedures that are discrete and require only a finite number of cuts?
Envy-free division using discrete methods was first solved for the 3 player case in 1960 by John Selfridge of Northern Illinois University and John Horton Conway at Cambridge University. The method requiring fewest cuts is the Selfridge–Conway discrete procedure, which uses at most 5 cuts.
For general \(n\), Brams and Taylor gave the first envy-free division method for four or more players in 1995. Other methods are due to Robertson and Webb, and Brams and Kilgour. The Brams and Kilgour method, called the gap procedure, uses the concept of an auction for each participant to place bids on the pieces in the proposed division. The procedure then finds an allocation of the items according to the participant's bids. However, these algorithms for general \(n\) have the property that the number of cuts required is unbounded and an arbitrarily large number of steps may be required to find the division, depending on player preferences. A longstanding open question is whether there is a procedure with a finite number of steps for envy-free cake division among \(n\) people.
Open Problem: Does there exist an envy-free fair division procedure for \(n\) players with a finite number of steps?
The fair division problem also has a counterpart, in which an undesirable good is to be distributed among \(n\) people, such as in dividing chores or splitting rent. Martin Gardner introduced the problem of dividing a set of chores (indivisible, undesirable items) among multiple people. In the rental division problem, a group of housemates must decide a fair allocation of rents for rooms which may have different features: Alice may prefer windows and Bob may like hardwood floors and the goal is to find a way to decide how best to split the rent based on their preferences.
There are also issues that require other notions of fairness. Consider a cake that is half strawberry and half chocolate. Suppose Alice likes only chocolate, and Bob only likes strawberry, and they apply the 2-person cut-and-choose method. If Alice is the cutter and does not know Bob's preference, then she would divide the cake so that each piece contains half chocolate, half strawberry. But then, both players receive pieces that contain only half of what they would like. On the other hand, if Alice knows Bob's preference, then she would divide the cake into the chocolate piece and the strawberry a piece, so they both get their entire preference. This is the notion of Pareto efficiency; the first solution in which Alice does not know Bob's preference is Pareto inefficient because it is possible to find another division that makes one person better off without making another person worse off.
In addition to these problems, there are many applications of fair division in auctions, economics, social choice theory, and game theory. Fair division algorithms can be used to resolve disputes over the splitting up of goods by taking into account preferences of all the people involved.
Advanced Topic: Combinatorial Topology
We now journey into the world of combinatorial topology and show how fixed point theorems from topology can be applied to solve envy-free fair division problems. We first give the following definitions. The \(n\)-dimensional simplex is the set
\[\Delta_n = \{ (x_0, x_1, x_2, \ldots x_n) \in \mathbb{R}^{n+1} : 0 \leq x_i, \sum x_i = 1 \}.\]
Let \(e_i \in \mathbb{R}^{n+1}\) denote the vector with \(i\)th coordinate equal to 1 and all other coordinates equal to 0. Then \(e_i\) are vertices of \(\Delta_n\). Intuitively, each point on the simplex can be thought of as a division of the cake into \(n+1\) pieces, where coordinate \(i\) is the fraction of the cake for piece \(i\). Vertex \(e_i\) of \(\Delta_n\) is then the division of the cake where piece \(i\) is the entire cake and all other pieces have size \(0\). The simplices for \(n=0,1,\) and \(2\) can be visualized geometrically as shown:
We will focus on the case \(n=2,\) which is a triangle. Label the vertices of this triangle by \(1,2, 3\) and consider a decomposition of this triangle into smaller triangles, where the smallest triangles are called cells. Suppose the vertices along the side connecting \(1\) and \(2\) have labels either \(1\) or \(2\), the vertices along the side connecting \(2\) and \(3\) have labels either \(2\) or \(3\), the vertices along the side connecting \(1\) and \(3\) have labels either \(1\) or \(3\), and the vertices in the interior are labeled by any one of \(1,2,\) or \(3\). A labeling satisfying these conditions is called a Sperner labeling:
We first show the following result from graph theory.
In a graph \(G\), the degree of a vertex \(v\) is the number of edges adjacent to \(v\). The number of odd degree vertices in any graph must be even.
Solution: Consider the sum of degrees of all vertices of the graph. Because each edge has two endpoints, the sum of degrees of all vertices is equal to twice the number of edges. Since the sum of the degrees is even and the sum of the degrees of vertices with even degree is even, the sum of the degrees of vertices with odd degree must be even. This shows there must be an even number of vertices with odd degree.
We give a statement and proof of Sperner's Lemma for \(n=2,\) which corresponds to a triangle; the proof for higher dimensional simplices follows the same reasoning with a few modifications.
Sperner's Lemma: If a triangle is decomposed into cells and all vertices are labeled by a Sperner labeling, then there are an odd number of cells with all different labels.
Proof: Create an auxiliary graph by introducing a vertex for each cell of the triangulation and a special vertex \(v^*\) for the outside of the triangle. Now, connect any two vertices by an edge if the intersection of their boundaries is an edge of a cell with endpoints labeled by \(1\) and \(2\). The vertices adjacent to vertex \(v^*\) are the cells on the boundary whose endpoints have labels \(1\) and \(2\), as shown in this example:
Now, when traveling along the boundary from vertex \(1\) and \(2\) of the large triangle, there are an odd number of edges with labels \(1\) and \(2\), since we start from a vertex labeled by \(1\) and end at a vertex labeled by \(2\). This implies the degree of \(v^*\) is odd (in the figure above, the degree of \(v^*\) is equal to three). By the result above, the graph has an even number \(k\) of odd degree vertices, and since \(v^*\) has odd degree, there are \(k-1\) odd degree vertices remaining in the interior of the triangle. Now, the vertices in the interior of the triangle can have degree one, two, or three, so the only possible odd degree for an interior vertex is degree one. If a vertex has degree one, then it corresponds to a cell \(c\) such that \(c\) has an edge labeled by \(1,2\) and the other edges of \(c\) cannot be labeled by \(1,2\). This implies the other edges of \(c\) must have labels \((1,3)\) and \((2,3)\), so \(c\) is a cell with labels \(1,2,3\). This shows there are \(k-1\) cells labeled by \(1,2,3,\) which is an odd number, proving Sperner's Lemma.
(Check that in the above figure, each of the five interior vertices of degree one corresponds to a cell with labels \(1,2,\) and \(3\).)
For general \(n\), Sperner's Lemma proceeds by induction on \(n\).
In particular, Sperner's Lemma shows there exists at least one triangle with labels \(1,2,3\) in any Sperner labeling. We now prove the Envy-Free Fair Division Theorem for three people (the proof for the general case can be obtained in the same manner with a few modifications).
Envy-Free Fair Division Theorem for three people (Simmons): For three people, there exists a division of cake such that each player receives a piece she/he believes to be of largest value.
Proof: Given \(\epsilon > 0,\) construct a triangulation of the simplex such that distances between cell vertices is at most \(\epsilon,\) and consider a labeling \(L\) of the triangulation such that each cell has labels \(A, B,\) and \(C\).
Now, construct a second labeling of the triangulation as follows. For each vertex \(x\), consider the label given by triangulation \(L\) and ask the person corresponding to this label which piece they prefer if the cake is divided into parts \(x = (x_1, x_2, x_3)\) corresponding to the coordinates of this point in the simplex. Label the vertex with \(1\) if the person prefers piece \(1\), \(2\) if the person prefers piece \(2\), and \(3\) if the person prefers piece \(3\). The result is a Sperner labeling, since along each boundary \((e_i, e_j)\), only pieces \(i\) and \(j\) are nonempty, so only they will be preferred. Then by Sperner's Lemma, there exists a cell labeled by \(1, 2, 3\), which corresponds to a cell where each player chooses a different piece of the cake. Now, we recurse on this cell to obtain a sequence of cells with vertices closer and closer (\(\epsilon\) tending to 0) such that the corresponding cells have nonempty intersection and each player chooses the same piece each time his name occurs as a label of a cell. In the limit, a point in the intersection is a division in which each player prefers a different piece of the divided cake.
Note that this proof gives an approximate algorithm for finding fixed points and fair divisions. For the problem of dividing rents or splitting chores, Francis Su developed an algorithm that repeatedly queries each housemate in turn on which room she or he would prefer if the total rent were divided in certain ways among the rooms (or chores were distributed in certain ways). Then a procedure based on Sperner's lemma determines room rents to propose after each housemate's turn. These methods have been implemented in several online tools:
Spliddit: Online Calculator for Sharing Rent, Dividing Goods, Assigning Credit
Sperner's Lemma also implies a well-known theory in combinatorial topology known as Brouwer's Fixed Point Theorem.
Brouwer Fixed-Point Theorem: Any continuous map \(f\) from the simplex to itself has a fixed point \(x\), i.e., \(f(x) = x\).
Other results from combinatorial topology also apply to fair division problem. For example, the Ham Sandwich Theorem shows that for \(n\) people with possibly different preferences, there is always a single cut of the cake so that all \(n\) people believe both sides of the cake have equal value.
As we have shown, the cake cutting problem touches upon many different areas, ranging from combinatorics and graph theory, to algorithms and topology. It also has many applications in economics, game theory, and decision theory, and there has been a great deal of mathematical study on this problem over the past few decades. Many open questions still remain -- perhaps you will be the person to think of new ideas to solve these problems!
References
S. Brams, A. Taylor, "An Envy-Free Cake Division Protocol". The American Mathematical Monthly 102 (1): 9–18 (1995).
M. Gardner, "Aha! Insight", W.F. Freeman and Co., New York (1978).
F. Su, “Rental Harmony: Sperner’s Lemma in Fair Division”, American Mathematical Monthly 106, pp. 930–942 (December 1999).
F. Su, Fair Division Page.