* 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
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 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.
The guy does have a knife after all ... what are the others going to do to stop him!
* 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
* Repeat until all the pizza is gone.
Fair Division: From Cake-Cutting to Dispute Resolution
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
(* yes, that may make me weird)
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?
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.
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.
The book's page is
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.
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!
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?
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.
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.
i'm not sure the protocol is a good answer, the assumption bothers me.
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 . . .
Yes, here in Italy, everyone gets their own pizza, rather than the US-style large pizza that gets divided :-)
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.
Those people can simply pay for the services of a liquidity provider. (Buy soda.)
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.
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.
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.
P.S., I just read the first chapter of Concrete Mathematics, and I thought this was going to be about lines on the plane.