How To Split A Pizza

[luke_s]

You can divide the pizza fairly with N players as follows:

   * 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

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.

[agf]

If there were two players, and A was cutting, B would just wait until the "cut" was the whole pie, then take it.

If there were three players, B and C would both call at half, cutting out player A.

You can't solve this by letting the cutter also call out, because you can't trust him to both cut and choose at the same time.

[coryl]

How does that work if multiple people call out "Yes" at the same time?

[agf]

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

[cschmidt]

Oh, fun! This is sometimes called an envy free division. A nice book on this topic is

Fair Division: From Cake-Cutting to Dispute Resolution www.amazon.com/Fair-Division-Cake-Cutting-Dispute-Resolution/dp/0521556449

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:

Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis http://www.amazon.com/Two-Sided-Matching-Game-Theoretic-Econ...

(* yes, that may make me weird)

[Cogito]

An interesting and related problem, from the Sydney University Maths Competition [0] 2007 [1] goes as follows:

  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?

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.

[0] http://www.maths.usyd.edu.au/u/SUMS/

[1] http://www.maths.usyd.edu.au/u/SUMS/sums2007.pdf

[Cogito]

Applying the concept from this problem to the one at hand, try the following scheme:

Alice picks an arbitrary point A on the pizza.

Bess picks a second point B, and Cath then picks a point C.

Cut the pizza from the centre to those points. Alice then picks the piece either to the left or right of her point A. Everyone else has to take the piece in the same direction of their point.

Under this scheme, if Cath makes a bad choice she will get the smallest piece, and either Alice or Beth gets a bigger piece then the other depending on which way Cath's choice was bad.

If Beth makes a poor choice, assuming Cath makes the best choice, she will always get the smallest piece.

If Beth and Cath conspire against Alice they can force her to have a tiny piece, however one of them will have an even smaller piece. If each instead tries to get the most for herself then it will work out roughly even.

[Xcelerate]

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.

For instance, the "fair" way to split a pizza into two is to let one person cut, and the other chooses.

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.

[clintonc]

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.

The book's page is

http://www.opentextbookstore.com/mathinsociety/

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.

[JDShu]

"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."

Unrelated to the intellectual pursuit of the problem, but this algorithm is a bit of a silly sore point for me.

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!

[benjiweber]

I find that typically the person choosing will pick the smaller half out of politeness.

For the same reason everyone is reluctant to take the last slice of a pizza or cake if they feel they will have had more than others.

Is this just a British thing?

[aaron695]

So who ever cuts is always worse off since they always get the smaller piece of pizza.

Unless they can use tricky psychology to make the small piece look bigger, possibly.

Fair to me is I thought obvious, you cut it then flip a x sided coin.

[eru]

Oh, you just have to make your model more interesting. If the involved parties have different value functions for the pizza, cutting can be more advantageous.

Suppose you really like tomatoes and I like everything equally. Than I will make a cut that has slightly more than half of the tomatoes in one set, and everything else in the other. This way I will gain almost all of the pizza (minus half the tomatoes plus epsilon).

Even more extreme, if your utility functions are `context-sensitive'. I.e. suppose there's a grid pattern on the pizza: horizontal mozzarella stripes and vertical ham stripes. I care about getting long mozzarella stripes, but don't want short stripes. Same applies to you and the ham stripes. Of course, the cutter has an advantage there.

[logicallee]

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?

i'm not sure the protocol is a good answer, the assumption bothers me.

[marshray]

If there's a limit to the precision to which one can compare slices of pizza, any algorithm that can meet or beat that precision can be successful.

But the game gets more interesting if the perceptions of the players are subject to influence! Say player A can choose to buy a pitcher of beer for player B, or cause him to travel at relativistic speeds with respect to the pizza . . .

[davidw]

> I have solved a problem that smarter people have already solved for more general cases.

Yes, here in Italy, everyone gets their own pizza, rather than the US-style large pizza that gets divided :-)

[babesh]

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

[roryokane]

Having a random person cut slices and then randomly allocating slices is not a bad idea, but has a problem too. That procedure is unfair to those who value reliably-sized slices.

Say A and B use this procedure. A and B both hate each other and want to make the pizza selection turn out bad for the other person. But while A is just normally hungry, B is at death’s door from starvation and needs at least 1/3 of a pizza to live. This procedure gives a 1/4 possibility that A can starve B to death, by letting A cut a tiny piece and a huge piece, and randomly assigning A the huge piece. Whereas no matter what B does, even if he is lucky enough to cut and receive a huge piece, A is not going to die. So A has the advantage. But a truly fair procedure would assure both A and B at least 1/2 a pizza, a property that would assure that B would live.

[soamv]

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.

[tolmasky]

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.

[garrettlarson]

That's good for most cases, but I don't think it works for groups of prime cardinality. In addition, the problem often allows each participant to have a different value function (e.g., one person wants lots of pepperoni but the others prefer mushrooms). In such a variant, a team might have problems agreeing on which piece is most desirable.

[agf]

Four person game: A1 says to B1 and B2, "Hey, give me a bigger piece and I'll make the cut in your favor". This doesn't solve collusion.

[mileswu]

There is also the Pizza Theorem[1] which says that even 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.

[1] https://en.wikipedia.org/wiki/Pizza_theorem

[peripetylabs]

In the case of three people sharing one pizza:

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.

I would never actually do this, but it's a good illustration of limits of geometric series.

[xentronium]

You assume that any pizza can be reliably sliced into four more or less even parts. Also you assume that cutter is interested in getting the best share. That is not always the case.

Imagine that slicer makes 1 huge and 3 tiny pieces. He obviously won't get the biggest one, but the second chooser will be mistreated too. Thus, evil divider can starve the second chooser to death.

[rubinelli]

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.

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.

[pantaloons]

But A and C can still collude against B, no?

[rquantz]

For most pizza, the pie arrives at the table already sliced, thus the problem is generally just one of negotiating fair distribution.

P.S., I just read the first chapter of Concrete Mathematics, and I thought this was going to be about lines on the plane.

[pcl]

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

[marshray]

"Yes, we''' have two of the large veggie specials, to be called 'left' and 'right', divided evenly with 16x oversampling. And a box of toothpicks."

[twymer]

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

[Qantourisc]

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