Fair Division Problems: How to Cut Your Cake and Eat It Too

Rahul Swamy

by Rahul Swamy
Department of Industrial and Enterprise Systems Engineering, University of Illinois Urbana-Champaign

If there is a commodity that needs to be divided within a group of people, often times, this seemingly simple problem isn’t an easy task. Each person may have a different preference on different parts of the commodity, one person may not know another person’s preferences, the commodity may not even be divisible, and so on. This is a classical problem in game theory, aptly named fair division, which deals with keeping every person “happy” with their slices. From splitting rent between roommates when the rooms are of different sizes, to redrawing congressional districts for the nation’s top legislative body, fair division problems are ubiquitous. Decades of research has studied and classified fair division based on the divisibility of the commodity, and the utility (or preference) distribution over the commodity.

But what exactly does ‘fair’ mean?

A key area of research in fair division is in designing algorithms (or “protocols”) that ensure certain fairness properties. It is often times important to allocate parts of a cake to people in such a way that no person would rather have another person’s allocation, called envy freeness. In some applications, it is also prudent to ensure that the utility each person receives from their allocation is not less than the fractional weight of each person, called proportionality. These two criteria are mutually exclusive, and a solution to a fair division problem tries to satisfy both. Other fairness measures are also explored, such as group-envy, equitability, exactness, and so on. In addition to fairness, the efficiency of a division is also important. A solution is Pareto-efficient if it cannot be made better for one person without making it worse for another person. These notions dictate the design and analysis of fair division algorithms under suitable settings.

Cake cutting is a fundamental part of fair division when the commodity is indivisible (i.e. can be represented in a continuous space), and the utility is heterogenous (i.e. each person values different parts of the commodity/cake differently). Cake cutting is rich in applications and mathematical theory, with many open questions to this date. For example, an interesting open question is to determine the minimum number of “cuts” required to divide a cake fairly (Magdon-Ismail et al., 2003)

How about you cut and I choose?

Algorithms for cake cutting typically involves the players taking turns at cutting the cake, or one player moves a “knife” while the other players decide when to stop (Brams & Taylor, 1996). The I-cut-you-choose algorithm is a popular protocol that works as follows for two players: Starting with the entire cake, one player divides it into two slices, and the other player chooses (freezes) the slice that they like best. This simple procedure is guaranteed to be envy-free. When the utility functions are additive functions, this also ensures proportionality. Although, when more than two players are involved, these fairness properties are not guaranteed.

Illustration of a cake cutting application to political redistricting (Spice, 2017).

A recent application of cake-cutting in a real-world setting has been in the redistricting problem. Once every ten years, the boundaries for congressional districts need to be re-drawn in order to account for migrations in populations. These districts must have roughly equal population, be geographically contiguous, and satisfy certain other legal requirements. This problem is a variation of the NP-Complete graph partitioning problem (Garey & Johnson, 2002), and has been an active research topic in the ORMS literature for several decades. Recent work by Pegden et al. (2017) adapted the I-cut-you-choose protocol to the redistricting problem. This setting considers a game between two political parties, where at every turn, one party (A) draws the districts, and the other party (B) freezes one of the districts. In the next turn, party B draws districts from the rest of the region, and party A freezes one district, and so on. This work shows theoretical guarantees when the parties optimally “pack” and “crack” their opponent, and conditions for preserving communities of interest within the districts.

Rental harmony

 A more day-to-day variation of cake-cutting is the chore division problem, which is also dubbed the “mirror-image of cake-cutting” since each player wants as little chore as possible. In addition to resolving conflicts among apartment room-mates, this abstract problem even has applications in dividing climate change responsibilities amongst nations (Traxler, 2002). On the algorithmic side, many cake-cutting algorithms preserve proportionality in chore-division. For two players, there is a non-trivial divide and choose algorithm called the Selfridge-Conway protocol which ensures envy-freeness (Robertson & Webb, 1998).  For an arbitrary number of players, Peterson & Su (2009) was the first to provide an envy-free protocol.

As the computational world progresses towards the pursuit of fairness in automation and algorithms, the study of fair division has broadly transformable lessons in problems involving multiple conflicting stakeholders. Even though they themselves are one among several interesting game theoretic problems, the notions involved in ensuring a certain level of “happiness” among all the stakeholders is fundamental to the way we approach conflict management – at home, and outside.

References

 Brams, S. J., & Taylor, A. D. (1996). Fair Division: From cake-cutting to dispute resolution. Cambridge University Press.

 Garey, M. R., & Johnson, D. S. (2002). Computers and intractability (Vol. 29). wh freeman.

 Magdon-Ismail, M., Busch, C., & Krishnamoorthy, M. S. (2003). Cake-cutting is not a piece of cake. In Annual Symposium on Theoretical Aspects of Computer Science (pp. 596–607). Springer.

 Pegden, W., Procaccia, A. D., & Yu, D. (2017). A partisan districting protocol with provably nonpartisan outcomes. ArXiv Preprint ArXiv:1710.08781.

 Peterson, E., & Su, F. E. (2009). N-person envy-free chore division. ArXiv Preprint ArXiv:0909.0303.

 Robertson, J., & Webb, W. (1998). Cake-cutting algorithms: Be fair if you can. AK Peters/CRC Press.

 Spice, B. (2017). "I-Cut-You-Choose" Cake-Cutting Protocol Inspires Solution to Gerrymandering. Carnegie Mellon University News. Retrieved from https://www.cmu.edu/news/stories/archives/2017/november/i-cut-you-choose-cake-cutting-protocol-inspires-solution-to-gerrymandering.html

 Traxler, M. (2002). Fair chore division for climate change. Social Theory and Practice, 28(1), 101–134.