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.
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.
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 :-)
Heh, but then you're introducing a bunch of variables that affect fairness, ie. arm length, reaction time (muscle twitch speed), proximity/position, etc.
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:
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.
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.
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!
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.
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 . . .
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.
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.
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.
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.
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.
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.
