How To Split A Pizza | Hacker News Reader

How To Split A Pizza

schani.wordpress.com

48 pointsgebe44 comments

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.

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

Use a system where you say "yes" by slapping your hand down onto a beverage coaster. Whoever's hand is on the bottom of the hand stack gets it.

Heh, but then you're introducing a bunch of variables that affect fairness, ie. arm length, reaction time (muscle twitch speed), proximity/position, etc.

Well, this system is somewhat optimised for practicality. A truly 'fair' system would allow people to submit blind bids, for how wide a slice they would like, with the smallest bid taking the slice. Eg:

   * Everybody writes down how much pizza they would like on a folded piece of paper.
     You put down 15 degrees, I put down 25 degrees, etc.  

   * The papers are opened and the person who bid the lowest gets their 
     requested slice

   * Repeat until all the pizza is gone.

Essentially you are running a blind auction to split up a limited resource. While being a fairer adaption of my original solution, it does turn out somewhat more unwieldy in practise :-)

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.

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

You can with certain types of pizza cutters. With this sort (http://www.amazon.com/RSVP-World-Class-Pizza-Cutter/dp/B0000...) for example you can propose a cut by aligning the cutter before actually performing the cut.

If you can't trust the cutter to cut the slice he said he was going to cut for himself, after demonstrating the proposed cut, then you can't trust the cutter to not simply devour the entire pizza right there in front of everybody.

"then you can't trust the cutter to not simply devour the entire pizza right there in front of everybody"

The guy does have a knife after all ... what are the others going to do to stop him!

If A is also allowed to call, it solves the problem of B and C splitting the pizza.

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

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)

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

  The sisters Alice, Bess, and Cath are ﬁghting 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

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.

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.

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.

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

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?

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.

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.

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.

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

> 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 :-)

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.

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.

> That procedure is unfair to those who value reliably-sized slices.

Those people can simply pay for the services of a liquidity provider. (Buy soda.)

The important question here is how you define fairness.

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.

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.

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.

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

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.

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.

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.

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

Good point, I didn't consider collusion. If A cuts a smaller slice on purpose, B can cut the remainder so that A and B still get the same amount, but C gets more. But if A can trust C to give a part of his share later, then B can't do anything.

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.

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

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

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?

Are they discrete toppings, or is the path of the pizza cutter allowed to traverse through them?

As you suggest, size is not necessarily the appropriate quantity to consider. The general idea would be that each player has "valuations" of slices, and that a player chooses based on this valuation. This might result in a sort of sliding scale: a player might choose one piece over another, even though it's smaller, because he prefers the toppings strongly enough.

Reply on news.ycombinator.com