How To Split A Pizza

You can divide the pizza fairly with N players as follows:<p><pre><code> * The cutter proposes to cut a small slice (say 5 degrees) and asks who wants it * If nobody does, he proposes to cut a slightly larger slice and asks who wants it? The proposed slice gets larger and larger until somebody calls out 'yes' * Once somebody says they want the slice, it is actually cut and given to them. * The game continues until all the pizza is divided up </code></pre> This balances peoples 'greediness' against their desire to get a slice. You can keep waiting and waiting for the proposed slice to get larger, but the risk is somebody else will call for it first. If you keep waiting for a large slice, the pizza will eventually be gone and you will have none. It forces everybody to choose the smallest size they would be satisfied with, until all the pizza is gone.

Commonly called fair division or cake-cutting. There are "fair" algorithms for the general n-person case:<p><a href="http://en.wikipedia.org/wiki/Cake_cutting" rel="nofollow">http://en.wikipedia.org/wiki/Cake_cutting</a> <a href="http://en.wikipedia.org/wiki/Brams-Taylor_procedure" rel="nofollow">http://en.wikipedia.org/wiki/Brams-Taylor_procedure</a>

Oh, fun! This is sometimes called an envy free division. A nice book on this topic is<p>Fair Division: From Cake-Cutting to Dispute Resolution www.amazon.com/Fair-Division-Cake-Cutting-Dispute-Resolution/dp/0521556449<p>Stable matchings are a related problem (sometimes called the stable marriage problem), where you want to match men and women to "marry", such that no two couples would want to swap partners. It is applied in real life to matching medical interns to hospital placements. One of my all time favorite technical books* is on this subject:<p>Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis <a href="http://www.amazon.com/Two-Sided-Matching-Game-Theoretic-Econometric-Monographs/dp/0521437881" rel="nofollow">http://www.amazon.com/Two-Sided-Matching-Game-Theoretic-Econ...</a><p>(* yes, that may make me weird)

An interesting and related problem, from the Sydney University Maths Competition [0] 2007 [1] goes as follows:<p><pre><code> The sisters Alice, Bess, and Cath are fighting over a triangular pizza, which may be imagined as a triangle PQR. Their father David proposes the following procedure for sharing it between the four of them. Alice will select a point A on the edge PQ, then Bess will select a point B on the edge PR, then Cath will select a point C on the edge QR. David will then cut the pizza along the lines AB, BC, and AC, and take the centre piece ABC for himself, leaving three corner pieces (some possibly empty, if endpoints of edges have been chosen). The sisters will then either all take the corner piece to the left of the point they selected, or all take the corner piece to the right of their point; Alice (as the eldest) will get to choose left or right. As everyone knows, each sister will make her choices purely to maximize the area of her own share, except that Alice and Bess, if their own shares are unaffected, will act to the advantage of the youngest sister Cath. If they all reason perfectly, what will they do? </code></pre> The constraints on this problem lead to an interesting result, but the fun is in teasing out a logical argument to why that result is the case, so I will leave it for those who want to try it.<p>[0] <a href="http://www.maths.usyd.edu.au/u/SUMS/" rel="nofollow">http://www.maths.usyd.edu.au/u/SUMS/</a><p>[1] <a href="http://www.maths.usyd.edu.au/u/SUMS/sums2007.pdf" rel="nofollow">http://www.maths.usyd.edu.au/u/SUMS/sums2007.pdf</a>

We discussed this fair splitting problem when I was in high school. I understood the theoretical implications of the problem, but I never liked the splitting method in a practical sense.<p>For instance, the "fair" way to split a pizza into two is to let one person cut, and the other chooses.<p>But if you've ever cut pizza, you know how hard it is to cut it evenly. So clearly the person who gets to choose has the better end of the deal.

There's an open textbook (David Lippman's Math in Society -- "a survey of mathematics for the liberal arts major") which covers several topics like this. The chapter on fair division is bite-sized, so you can read it without investing a lot of time.<p>The book's page is<p><a href="http://www.opentextbookstore.com/mathinsociety/" rel="nofollow">http://www.opentextbookstore.com/mathinsociety/</a><p>from whence you can download the entire book or just the fair division chapter. The method discussed in the post and a separate method discussed in a comment are both covered by this book.

"The standard way to avoid all such problems is to let one person cut the pizza in two halves, and the other person choose who gets which half."<p>Unrelated to the intellectual pursuit of the problem, but this algorithm is a bit of a silly sore point for me.<p>Several years ago I used to periodically split a giant burrito with my friend and I proposed the above algorithm. So I cut it and my friend would choose a half. After a couple times I realized that thanks to the fact that it's not humanly possible to cut it in half perfectly, the person choosing will always get the bigger half. Clearly my friend realized the same thing as he always insisted that I do the cutting!

So who ever cuts is always worse off since they always get the smaller piece of pizza.<p>Unless they can use tricky psychology to make the small piece look bigger, possibly.<p>Fair to me is I thought obvious, you cut it then flip a x sided coin.

what if it's harder to cut a perfect half than it is to tell which half is bigger? what if the pizza usually 'splits' into a bigger and smaller half?<p>i'm not sure the protocol is a good answer, the assumption bothers me.

&#62; I have solved a problem that smarter people have already solved for more general cases.<p>Yes, here in Italy, everyone gets their own pizza, rather than the US-style large pizza that gets divided :-)

What if B &#38; C collude to make A think that A &#38; B are colluding so that A cuts an unequal slice? Just draw random slices instead. Works for any n.

Or, A cuts the pizza down the middle, B chooses a half, A and B cut their halves into thirds and C chooses one third each from A's and B's halves.

Seems like after you have the solution for 2 and 3 people, the N-solution is just to split up in teams. Say you have 8 people, split in to two teams of 4. Team 1 (With 4 people) now represents "Person A" in the 2 person scenario, so Team 1 gets to cut, Team 2 gets to choose. Now Team 1 and Team 2 repeat the process internally for their halves of the pizza, and so forth.

There is also the Pizza Theorem[1] which says that <i>even</i> if you don't cut the pizza through the middle but so long as the slices are of equal angles, you can divide it equally by area by choosing alternating slices.<p>[1] <a href="https://en.wikipedia.org/wiki/Pizza_theorem" rel="nofollow">https://en.wikipedia.org/wiki/Pizza_theorem</a>

In the case of three people sharing one pizza:<p>Slice the pizza in four, and eat three of the quarters (the two people who aren't slicing picking first of course). Repeat with the remaining quarter until what's left is not worth being disappointed about.<p>I would never actually do this, but it's a good illustration of limits of geometric series.

Can't you simply generalize the "I cut, you choose" algorithm? A cuts the first slice, then B divides the remainder in half, then C picks a slice, then A picks a slice.<p>If A cuts a slice bigger than 1/3, C will pick that. Likewise, B, as the last one to pick a slice, has an incentive to split evenly.

For most pizza, the pie arrives at the table already sliced, thus the problem is generally just one of negotiating fair distribution.<p>P.S., I just read the first chapter of Concrete Mathematics, and I thought this was going to be about lines on the plane.

It seems like a Nyquist-rate of slices would do the trick, but is probably not the lower bound on number of slices.

Personally I think such a dilema means it is time to find new friends.

I'm just not that hungry/greedy to care about this error margin.

But what about a fair distribution of toppings?