At its core, the cake-cutting problem is about finding the best way to divide a cake among the people at the table so that everyone goes away happy with their share.
In its simplest version, the problem is about the best way to divide that cake between two people. In this case, the best method is the so-called “I cut, you choose” method, whereby one party cuts the cake into two equal portions and offers the other party the opportunity to choose the one they prefer.
Why has such a seemingly trivial or anecdotal question fascinated mathematicians for eight decades? The answer lies in the fact that the cake is really a metaphor or representation of any good or resource that can be shared. From this point of view, the problem of dividing the cake can be reformulated in much more transcendental and immediate terms, such as the best way to distribute humanitarian aid among the affected population or to divvy up food among disadvantaged groups; the fishing quotas allocated to each fleet; the number of political representatives corresponding to each district; the distribution of an inheritance or of the common goods in a divorce; or the pool of productivity among the workers of a company…
Seen in this light, it is clear that the problem of dividing up the cake, far from being a puzzle or brainteaser that only concerns mathematicians (and perhaps the organisers or hosts of a birthday party), is about something as miserly as someone taking the best part of the cake at the expense of others. Or rather, how to avoid it.
Game 1: “Sorry, a geometry issue has come up.”
In fact, the problem of dividing the cake is really just the showy tip of the iceberg—in addition to the foundational problem—of a sub-branch of mathematics associated with game theory that focuses on the fair division of resources. It is, specifically, the one concerned with finding procedures that ensure that a good is divided among N parties in such a way that all parties feel that they have received a fair share, and that none envy the share that has gone to another.
Game 2: “I’m really sorry, a geometry question has come up. Don’t give it another thought.”
First formulated by Polish mathematicians in the 1940s, the cake-cutting problem has since attracted fellow mathematicians, game theorists, social justice experts, economists, computer scientists and politicians alike. This, in turn, has led to the formulation of a whole series of increasingly complex algorithms as new factors and conditions have been introduced: the number of participants among whom the cake is to be shared; whether the cake is homogeneous or heterogeneous (all chocolate or part cream, part chocolate and part coffee); how much each party has contributed to the preparation of the treat; the particular preferences of each party; or their honesty.
These last two aspects introduce a particularly contentious yet intriguing issue that complicates the problem enormously: in many cases it can be advantageous to be dishonest. Consider the case of two people (A and B) sharing a chocolate and cream cake. If A knows that B prefers chocolate, he can divide the cake into two pieces of different sizes, knowing that B will prefer to take the smaller piece if it is all chocolate. But what if B has lied about preferring chocolate? Then he will choose the larger piece with all the cream.
Game 3: Is there a cheater in the group?
Imagine you have to divide a round cake into four equal portions. And one of the people involved suggests cutting it as shown in the image, and keeping one of the non-circular portions for herself. Is she trying to cheat you or is she not only a good friend, but also a geometry geek?
With all this in mind, it is easier to understand why the problem has proved unsolvable, at least so far. No definitive solution or algorithm has been found—indeed, it is doubtful that one exists. In the absence of such a solution, experts strive to find the best possible solution or the least bad one. In this endeavour, especially in recent years, and thanks to the help of computers with enormous computing power, significant progress has been made, such as the determination of the minimum number of steps necessary to divide a cake among N diners (N2 or N^2); as well as the maximum number—meaning that the participants will eventually reach a fair distribution and will not be dividing the cake ad infinitum—which has been calculated to be N^N^N^N^N^N.
Perhaps a small step (or a surreal one, since it is an unattainable number in practice) in the eyes of any of us, but surely a giant leap in the eyes of mathematicians in their quest to find an algorithm for fairness.
Game 4: A fair distribution?
A person goes to visit her grandmother for her birthday and wants to bring her a cake to celebrate together. The problem is that, on the way, she passes the respective houses of five other relatives. Of course, she is obliged to stop at each one to say hello and share the dessert. So at each stop she ends up giving half the cakes she is carrying; but in exchange, each relative gives her another cake to take to the guest of honour. How many cakes must she leave the house with to be sure that she can give two to her grandmother? And how many to guarantee that she will give her grandmother exactly one (so that her grandmother’s sugar levels don’t spike)?
Solutions
Comments on this publication