Mostly Software

April 27, 2013

How to Split a Pizza

Filed under: Uncategorized — schani @ 9:35 pm

Assume two people want to split a pizza in a fair way. In our context, fair means that if both people follow the procedure, each person gets half a pizza, or, if not, only has themselves to blame. The obvious answer seems to be “split it in the middle”, but that leads to all kinds of further questions and complications: Who does the splitting? How is “the middle” determined? Even if we had protocols for that, it would still leave the possibility of one person not being satisfied with how they were carried out—sloppy measurements or sloppy cutting.

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. If the cutter thinks they got the smaller piece it’s because they didn’t cut fairly or precisely enough, and if the chooser thinks their piece is smaller, they should have chosen the bigger one.

What if there are three people? Before we try to come up with a procedure, let’s consider people’s motivations first. In the case of two people, whatever one person wins, the other loses. With three people, one person might elect to get a smaller piece for themselves in order to also make one of the other two worse off. Or, more realistically, two people might collude against the third. We’d like a procedure that ensures that even under those circumstances, fairness is guaranteed.

One generalization of the two-people procedure that comes to mind is to let one person—let’s call them “A”—cut, and then let the two others choose, first B, then C. Unfortunately, if A cuts in such a way that there is one large piece and two pieces that are each less than 1/3, and B chooses the large piece, C doesn’t get their fair share (neither does A, but that’s A’s fault). Randomizing the order of cutter and choosers is not a solution, either, because there is still the possibility of somebody getting the short end of the stick.

Here’s a procedure that works: A cuts the pizza, B chooses their slice. C has two options: they can either choose one of the remaining two slices, or they can call shenanigans. In the latter case, B picks a second slice[1], then both slices are put together and C divides them into two halves. B picks one half, C gets the other.

To see why this procedure is fair, let’s consider each person in turn. A will always get the piece that B and C didn’t pick, so if A cut fairly, they get their fair share. B will either get the piece they pick, or at least half of two pieces they pick, so if they pick the two largest pieces, they will get at least one third of the pizza. C will either get the piece they pick, or, in the case of shenanigans, half of the two pieces that B picked. It’s not obvious that they will get at least a third in the latter case. We assume that C only calls shenanigans if the two pieces that are left after B picked one are both smaller than one third—if one piece is at least a third, C should of course just pick it, thereby getting their fair share. The larger of the two pieces will have size 1/3-x, the smaller one 1/3-x-y, where x>0 and y>=0. If the two pieces are the same size, y is zero. The piece that B picked therefore has size 1/3+2x+y. B now picks one of the smaller pieces. If B wants to minimize C’s share, B must pick the smallest piece, i.e.1/3-x-y, which then gets put together with B’s original piece for C to cut. The two pieces together have size 2/3+x, so if C cuts fairly, they will actually get a size larger than their fair share.

I don’t know whether this procedure can be generalized to a larger number of people.

Update: As many commenters have thankfully pointed out, I have solved a problem that smarter people have already solved for more general cases. For a good overview of a few methods, read this article. My personal favorite is the Last Diminisher algorithm. The method I came up with is a variant of the three-person Lone Divider procedure.


  1. It is important that it is B, not C, who picks the second slice when C calls shenanigans.  ↩

About these ads

19 Comments

  1. Thanks for the interesting puzzle. But there are two things I don’t understand.
    * You write “if one piece is at least a third, B should of course just pick it, thereby getting their fair share”. But do you actually mean “C” instead of “B” there?
    * You write “A will always get the piece that B and C didn’t pick, so if they cut fairly, they get their fair share.” Does “they” mean “B and C” (as grammatical accord would suggest) or “A” (as the proof seems to require)? I’m frankly not sure. I already browsed http://en.wikipedia.org/wiki/Singular_they and more, but I’m still confused here on what you mean, let alone what’s the best solution; I feel I’d just avoid pronouns (by repeating the referent or rephrasing to need no word at all). And I also feel I already wasted too much time on this, so sorry for bothering you there.

    Comment by Paolo G. Giarrusso — April 27, 2013 @ 10:48 pm

    • Just choose the answer that logically makes sense, not grammatically.

      Comment by patrickturmala — April 28, 2013 @ 5:41 am

    • Thank you.

      Comment by schani — April 28, 2013 @ 7:11 am

  2. Commonly called fair division or cake-cutting. There are “fair” algorithms for the general n-person case:

    http://en.wikipedia.org/wiki/Cake_cutting
    http://en.wikipedia.org/wiki/Brams-Taylor_procedure

    Comment by Adam Forsyth — April 28, 2013 @ 1:59 am

  3. There’s a simpler, more general solution to this.

    Each person takes turning cutting what they think is a fair portion. If someone else thinks the portion is too large, that person can cut the portion down to what they think is a fair size and then keep that portion. Otherwise the portion goes to the person who originally sliced it.

    Comment by Rohan Singh — April 28, 2013 @ 2:03 am

  4. Paolo, I believe its a singular ‘they’ in a reference to gender neutrality. Not only boys eat pizza.

    Comment by Julian — April 28, 2013 @ 2:24 am

  5. Can you keep your personal/cultural biases out? Do you realize that if a pizza is split half-way, the “splitter” has nothing to lose at all? The first person who claims a slice will pick the smallest piece. That’s how everyone with a culture does it. http://www.psmag.com/magazines/pacific-standard-cover-story/joe-henrich-weird-ultimatum-game-shaking-up-psychology-economics-53135/

    Comment by Anon — April 28, 2013 @ 2:41 am

    • I’m not sure what you’re trying to say, or how it is relevant to the problem stated.

      Comment by schani — April 28, 2013 @ 7:40 am

  6. This problem is very well-studied in math and is called the “Fair Division” problem. Wikipedia has more. There are many such algorithms that generalize, they become harder and harder to understand “at a glance”, however. You kind of just have to trust the proof.

    Comment by Peter Boothe (@pboothe) — April 28, 2013 @ 2:43 am

  7. My solution: cut friendship-ties with people who haven’t get even a remotely sane perception of what “half” or “one third” of something is. Seriously, you nerds…

    Comment by Marcus — April 28, 2013 @ 3:14 am

    • Marcus, you’re missing the point – this generalizes to many practical problems like competing districts splitting water rights, for example.

      Comment by Sven — April 28, 2013 @ 4:31 am

  8. It is true that this is the subject of Fair Division. Your solution generalizes to an arbitrary number of people, and it is known as the “Lone Divider” method. The suggestion by Rohan Singh is known as the “Last Diminisher” method.

    Comment by Clinton Curry — April 28, 2013 @ 3:56 am

  9. you can just use induction – person n+1 cuts a piece off of size 1/(n+1). Any of the remaining people may pick that for their own. If it is too large, you lose one from the group. Too small or equal you lose the cutter. iterate…

    Comment by JJ — April 28, 2013 @ 5:17 am

    • That won’t work. Let’s say you have three people. Person A cuts off a piece that’s 90% of the pizza. Of course both B and C will want to have that piece. What’s the procedure for determining who gets it? And once either B or C get it, the other certainly can’t their third of the pizza.

      Comment by schani — April 28, 2013 @ 7:03 am

  10. What if persons B and C know that person A has the inability to cut a pizza evenly and are motivated by that knowledge to select him as the first slicer?

    Comment by patrickturmala — April 28, 2013 @ 5:43 am

    • In that case it’s A’s own fault if they get a smaller share, which is consistent with my criterion for fairness (which you might not agree with, which is a separate problem).

      Comment by schani — April 28, 2013 @ 6:58 am

  11. Much more important than how to split it, is the question of the pizza-oven – this is by far the most important component in your pizza-baking-process; i’d rater prefer a not 50:50 split of a good pizza over any pizza-cut of a pizza from a bad-oven. :-)

    Comment by Lelala — April 28, 2013 @ 8:17 am

  12. I think Rohan has the best solution. Keep cutting the questionable pieces and repeat the process. This will spread the cutting error across all consumers.

    Comment by @TheSandyWalsh — April 29, 2013 @ 12:33 pm

  13. Classic way to do that: one cuts the pizza in two the other one chooses which slice to eat ;)

    Comment by adc — May 7, 2013 @ 3:44 pm


RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

The Shocking Blue Green Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: