In today’s article, we are going to tackle a real-life question: Imagine you have a pizza that you would like to share among several people. How should you cut it so that everyone gets a fair share and no one is jealous of the others?
At first, the solution to this puzzle seems almost trivial. In a situation with N people – or ‘players’, as we will think of the pizza division as a game – you could just divide the pizza into N equally sized slices. But what if the resource is not homogeneous, e.g., we have a pizza with many different and unevenly distributed toppings, and the players have different preferences? For instance, you could imagine that one person loves mushrooms, while another avoids them, and a third is mainly interested in the extra cheese in the middle. The notion of fairness is then defined, not only in terms of the size of the pieces, but according to their value, as perceived by the different players. In mathematics and economics, a subjective value function can be used to quantify how much a player values a given resource. According to different value functions, a piece that seems fair to one person may seem like a bad deal for another, so how can we divide a pizza with many different toppings as fairly as possible?
In mathematics, problems of this kind belong to the field of fair division, which is an area of game theory. The aim is to divide a resource among several people according to some previously defined notion of fairness. In mathematics this class of problems is also known informally as “cake cutting problems”. The ‘cake’ is a convenient stand-in for any continuously divisible resource. Here, to illustrate that the same methods apply to non-homogeneous resources, I will use a pizza with different toppings as an example. The pizza can be divided as finely as necessary, without any loss in value due to the cuts. In other words, cutting a piece into smaller parts never changes its total value. Consequently, the values of the smaller pieces add up to the value of the original piece.
A fair division does not necessarily mean that two players are receiving the same amount of pizza, especially if they value different toppings differently. Instead, it means receiving a share that is sufficiently valuable according to their own preferences. The so-called proportional fairness criterion is fulfilled if, considering a game with N players, each has received a piece of pizza which is worth at least 1/N of the worth they assign to the whole. (It may not seem obvious that such a division even exists, but we will see an algorithm that establishes this below.) In fair division, envy-freeness is a stronger criterion than proportionality, also implying that you don’t think that any other player’s share is more valuable than yours.
i) Two people: divide and choose
For two people, there is a wonderfully elegant solution to the fair-pizza-cutting-problem, known as divide and choose. Variations of this idea are so old that they have even been mentioned in the biblical story of Abraham and Lot. In this story, Abraham first proposes a division of land into a left and a right part and then lets his nephew, Lot, choose his preferred part first. The same procedure can be applied to our pizza. Following physics conventions, we will name our two players Alice and Bob. First, Alice cuts the pizza into two pieces that she considers equally valuable. Bob then chooses whichever piece he prefers, while Alice receives the remaining one. In this setup, neither has reason to envy the other. In fact, Alice would have been happy with receiving either piece because, in the first place, she made them equally valuable in her own eyes. Bob should be happy, as well, since he was allowed to choose his favourite piece. Interestingly, this procedure even works if the players are not benevolent or do not trust one another, because each of them has a “safe strategy”.
In Alice’s case, if she actually cuts the pizza in two pieces she values equally, Bob’s decision cannot make her envious. Similarly, Bob cannot become envious over Alice’s division if he chooses the piece he truly prefers.Notice that the notion of ‘equal value’ is completely subjective here. Perhaps one piece is physically smaller but covered in pineapple pieces, which happen to be Bob’s favourite topping, and thus preferable to him. These subtleties do not matter for the arguments involved in the fair division procedure; what actually matters is how each player subjectively values the pieces. In the way it is set up, the divide and choose prescription guarantees us two kinds of fairness at once. First, it is proportional, meaning that each player believes that they received at least half of the pizza’s total value. Second, it is also envy-free because neither would prefer the other person’s share over their own. With three or more people, however, the two criteria of proportionality and envy-freeness no longer automatically come together. This makes it a lot more difficult to generalise fair division algorithms to situations with more participants.
ii) Three or more people: The last diminisher
It took until the twentieth century before the Polish mathematician Hugo Steinhaus made progress with extending ‘divide and choose’ to more than two people. During World War II, he challenged his students Stefan Banach and Bronisław Knaster, who actually found a solution for the three-person-problem. Steinhaus then generalised his students’ elegant solution, now known as the last-diminisher procedure, to arbitrary many players and published the result in 1948 [1].
Dividing a pizza according to the last diminisher procedure works as follows: Suppose there are N people in the game. Alice first cuts off a piece for herself, which she considers to be worth exactly 1/N of the whole pizza. The piece then passes from person to person in sequence. Anyone who thinks that the piece proposed by Alice is worth more than 1/N, may trim it until it is worth exactly 1/N in their eyes. The last person to trim the piece, also known as the last diminisher, must eventually take it. That person then leaves the game with their piece, and the same procedure is repeated with the remaining pizza and players. If nobody chooses to trim the piece, Alice gets to keep the slice she originally cut. Eventually, once only two people remain, the situation should be resolved according to the familiar divide and choose prescription. The clever part is that this procedure guarantees everyone a share they value at least as highly as their fair proportional entitlement, i.e. 1/N of the cake. Even if everybody else were conspiring against you, they could not force you to accept less than 1/N of the pizza’s value, according to your own judgement. (I challenge you to convince yourself of this!)
But, despite its elegance, there is still a catch to this division protocol: Suppose that Alice receives a piece that she values at 34 per cent of the whole pizza. With three players, that is more than her guaranteed third, so the division is for sure proportional. However, suppose that Alice looks at Bob’s piece and values that at 50 per cent, according to her own value function. Thus, even though Alice has received her proportionally fair share, she would much rather have Bob’s piece of pizza, leaving her envious. For three or more players, the last diminisher procedure thus guarantees proportionality but it does not necessarily imply envy-freeness after the division.
iii) Can three people all be envy-free?
Fortunately, for three (or even any number N) people there is another ingenious solution which leaves all participants envy-free. Around 1960, John Selfridge discovered a procedure, which John Conway later also found independently. Although neither originally published it, it became known as the Selfridge–Conway procedure [2].
In the following, I would like to describe how the Selfridge-Conway procedure achieves fair division of a pizza among three parties. For this, let us bring back Alice and Bob and introduce their friend, Charlie. Alice begins by cutting the pizza into three pieces; we can refer to them as X, Y, and Z; which she considers equal according to her subjective valuation.
Next, Bob examines the pieces and tries to identify a piece which he values more highly than the other ones. If Bob does not consider any one piece to be more valuable than the others, he does not trim anything. The three then simply choose pieces in the order Charlie, Bob, Alice. However, suppose Bob thinks Y is clearly the best piece. He then trims some pizza from Y until the piece that remains, which we will call Y1, is worth exactly as much to him as his second-favourite piece. The trimmings, Y2, are then temporarily put aside. Charlie now gets first choice among the pieces X, Y1, and Z. Bob chooses next, with one special rule: if Charlie did not take the trimmed piece Y1, then Bob must take it. Alice receives whichever piece remains.
After this first step, the allocation of the pieces X, Y1, and Z should already be envy-free. Charlie cannot envy anyone because Charlie could pick their piece first. Bob cannot envy Alice because the piece he leaves her – either X or Z – in his eyes is not more valuable than the piece he picks himself, and he cannot envy Charlie because, by trimming his original favourite, he deliberately made Y1 equal in value to his second choice. Alice cannot envy either of the others because she originally regarded pieces X, Y, and Z as equal, while Y1, which is never the piece she receives, has only become smaller. Thus, at this point, the division is envy-free but not yet proportional, as each player can still be left feeling that their share is worth less than the ⅓ they are entitled to.
In the end, the issue of proportional fairness will be fixed since there are still the trimmings Y2 to distribute.This is where the procedure has one final trick, i.e. a carefully chosen order of cutting and choosing, that guarantees an ultimately envy-free and fair division. Between Bob and Charlie, one previously received the trimmed piece Y1; we shall call this person P1 and call the other P2. Player P2 next divides the trimmings into three pieces that they consider equal. Player P1 chooses one out of the three trimming pieces first, which we shall call Y21, Alice chooses second and gets Y22, and P2 receives the remaining piece of the trimmings, Y23.
This ordering ensures that distributing the leftover trimmings does not reintroduce envy. The result is a complete division in which all three players believe that they got at least the piece they deserved and nobody else received a preferable share. Why does this work? As a challenge, can you reason and prove why this is the case? I may explain the solution in an upcoming article. As a hint, you might like to consider the figure below which schematically represents an example division coming out of this protocol:
iv) What about more than three people?
The existence of the previously described fair-division procedures naturally raises a question: If we can do it for three people, can we also find an envy-free fair division for four or more participants? Nowadays we know that the answer is yes; however, proving it turned out to be surprisingly difficult. In a breakthrough in 1995, Steven Brams and Alan Taylor published an envy-free procedure that works for any number of players [2]. Their procedure always finishes after a finite number of steps. However, this step-number is unbounded in their method, meaning that knowing only the number of players does not tell you in advance how many steps the procedure might require. In terms of mathematical complexity, there is an important difference between saying ‘this process will eventually stop’ and saying ‘this process is guaranteed to stop within at most this many steps’.
For years, it thus remained unknown whether a bounded envy-free procedure existed for an arbitrary number of people. This question was answered quite recently in 2016, when Haris Aziz and Simon Mackenzie constructed the first discrete, bounded envy-free cake-cutting protocol for any number N of players [3]. In other words, the number of operations required could finally be bounded in advance using only N as an input. There was, however, a practical problem with their finding: the upper bound was enormous and required at most N^(N^(N^(N^(N^N)))) queries in the worst case, with the ^-symbol meaning ‘to the power’ [3]. Here, a query is a request for a player either to evaluate a particular piece or to make a cut that gives a piece a specified value. The bound forms a six-level tower of powers, implying that the number of interactions required in the division procedure becomes unimaginably large, even for fairly small N .So, after mathematicians had learned that a bounded procedure existed, the next important question was: how complicated does envy-free cake cutting really have to be?
The upper bound was improved substantially in 2023 by Georgy Sokolov, who showed that the Aziz–Mackenzie protocol requires at most N8N^2(1+c) , with c a constant of order 1, queries [4]. This replaced the enormous tower of powers with a much more manageable, although still very rapidly growing, bound. So could one possibly do any better? Remarkably, there has been major progress in answering this question even as recently as a few months ago, in 2026. Qilin Ye and Yannan Bai found a new protocol requiring at most Nc2N queries, with c a constant of order 1, to achieve a fair and envy-free division [5]. This single-exponential upper bound (see also this recent article by Pim van den Heuvel about exponential growth) is an extraordinary reduction, compared with the towers of exponentials bound of the earlier protocol. However, it is still not necessarily the final answer, as the best known general lower bound is only of order N2, i.e., the number of queries that is known to always be necessary grows quadratically, as was proven in [6]. A very large gap therefore remains between the bounds of what is known to be necessary and what is required by the best current protocol. Whether envy-free division can always be achieved with only a polynomial number of queries, or whether exponential complexity is in fact unavoidable, thus remains an important open question for future research in the field.
Conclusion
Our pizza problem illustrates something deep about fair division. The difficulty lies not only in finding clever ways to cut the pizza so that everyone is happy. Especially in contexts where we want to divide a non-homogenous resource among people with different preferences, another big part of it is deciding what we mean by fair, in the first place. Should everyone merely receive at least 1/N of the value of the whole, so the division is proportional? Should the division be such that nobody envies anybody else? Should the outcome also be pareto efficient, a more stringent criterion than envy-freeness, meaning that there is no alternative division that could make somebody better off without making somebody else worse off? And what happens if players are malicious or have an incentive to lie about their preferences?
Different answers to these questions inevitably lead to different mathematical problems and different optimal division algorithms. Starting from the simple rule ‘I cut, you choose’, we quickly arrive at questions that have occupied mathematicians, economists, and computer scientists for decades. And, more than seventy years after Steinhaus described the last-diminisher procedure, researchers still keep discovering better ways to cut their cake. Or a pizza, in our case.
References
[1] “Report of the Washington Meeting, September 6–18, 1947.” Econometrica 16, no. 1 (1948): 33–111.
[2] Steven J. Brams and Alan D. Taylor, “An Envy-Free Cake Division Protocol,” The American Mathematical Monthly102, no. 1 (1995): 9–18.
[3] Haris Aziz and Simon Mackenzie, “A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents,” in 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2016), 416–427.
[4] Sokolov, Georgy. “An Exponential Envy-Free Cake Cutting Protocol for $ n $ Agents.” arXiv preprint arXiv:2306.03854(2023).
[5] Qilin Ye and Yannan Bai, “Cutting Down the Tower: Single-Exponential Envy-Free Cake Cutting,” arXiv preprintarXiv:2609.05191 (2026).
[6] Procaccia, Ariel D. “Thou Shalt Covet Thy Neighbor’s Cake.” In IJCAI, pp. 239-244. 2009.