Communications of the ACM
Home/Magazine Archive/April 2020 (Vol. 63, No. 4)/Technical Perspective: An Answer to Fair Division's.../Full Text
Research highlights
Technical Perspective: An Answer to Fair Division's Most Enigmatic Question
The cake-cutting problem is the brainchild of the noted mathematician Hugo Steinhaus, who formulated and studied it in the early 1940s, even as he was hiding from the Nazis who occupied his native Poland. The question Steinhaus asked is one that must have occurred to many others too (albeit probably under circumstances that afford greater accessibility to cake): How does one fairly divide a cake between multiple people? The difficulty is that the cake is heterogeneous, and the participants have different preferences, so simply giving them pieces of equal size will not do.
On a conceptual level, Steinhaus' main insight was that fairness—an ostensibly abstract idea—can be specified mathematically. One particular notion has emerged as the epitome of fairness: envy-freeness, which means that each participant prefers her piece of cake to the piece given to any other participant.
So, what is an algorithm that would produce an envy-free division of the cake for two players? Easy: I cut; you choose. I am not envious because I am indifferent between the two pieces, and you get the piece that you prefer. And for three players? That is already tricky. The general case was open for decades and considered a major open problem, until it was solved in 1995 by Steven Brams and Alan Taylor.
The envy-free protocol of Brams and Taylor is guaranteed to terminate with an envy-free allocation of the cake. However, the running time of this algorithm is unbounded: by carefully tuning the preferences of the participants, it is possible to make the protocol perform an arbitrarily large number of steps. Consequently, as soon as Brams and Taylor solved the envy-free cake-cutting problem, they immediately launched a new problem to the top of fair division's most wanted list: the existence of a bounded envy-free cake-cutting protocol.
The allocation of indivisible goods gives rise to questions that are both mathematically challenging and deeply practical.
This problem stood its ground for two decades, until it was cracked by Aziz and Mackenzie in 2016. Their solution is presented in the following paper; it is an intricate protocol, which builds on previous ideas while adding several ingenious ingredients into the mix.
So, should aspiring cake cutters hang up their spurs? Not quite yet. The number of steps required by the Aziz-Mackenzie protocol is bounded by a function of the number of participants—but that function grows comically fast. In fact, for just two participants, the bound is a number whose number of digits is so large that it itself has almost 20,000 digits! This begs the question of whether there exists a cake-cutting protocol that is both envy free and computationally efficient.
Looking beyond cake cutting, fair division algorithms have been transitioning from theory to practice. For example, envy-free solutions to the rent division problem—assigning rooms to housemates and dividing the rent between them— are used widely. Other applications include allocating computational resources, assigning seats in college courses to students, and even eliminating gerrymandering through provably fair political redistricting procedures.
The allocation of indivisible goods, in particular, gives rise to questions that are both mathematically challenging and deeply practical. A paradigmatic use case is dividing a jewelry or art collection between several heirs. Since the goods cannot be split between participants, envy-freeness cannot be guaranteed. Instead, let us allow one participant to prefer the bundle of goods allocated to another, but it must be the case that removing any good from the bundle of the latter participant will always eliminate the former's envy; this property is known as envy-freeness up to any good, or EFX for short. Furthermore, suppose the value each participant has for a bundle of goods is simply the sum of values of individual goods. Is an EFX allocation guaranteed to exist? This fundamental and deceptively accessible question is open. In my view, it is the successor of envy-free cake cutting as fair division's biggest problem.
Taking a broader perspective, in recent years the term "fairness" is being used by machine learning researchers to refer to lack of bias or discrimination. This viewpoint is rooted in Rawlsian ethics and might seem to be at odds with the preference-based notions of fairness favored by eight decades of research in fair division. Nevertheless, there are strong synergies between the two fields. In particular, well-established fairness notions like envy-freeness can—and should—help guide the design of ethical AI.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2020 ACM, Inc.
No entries found