This version of cake-cutting reminds me of the Gift Exchange problem, see our paper in 'Lectronic J. Combin, *Analysis of the Gift Exchange Problem <http://neilsloane.com/doc/Moa10.pdf>*, 2017. Also arXiv:1701.08394 <http://arxiv.org/abs/1701.08394>, Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Fri, Dec 15, 2017 at 12:01 PM, Andy Latto <andy.latto@pobox.com> wrote:
What you characterize as a "best solution" purports to solve a much easier problem than the one discussed in the SA article
The spin-the-cake algorithm is ill-defined; if we define the "places where the people are sitting" as n evenly-spaced points around the circle, it doesn't tell us what to do if to people are sitting in front of the same piece of cake after the spin.
Even if you patch it up, the simplest way to do so being just having one person divide the cake, and a randomization procedure applied to decide who gets which piece, this solves only the problem "no-one is in a position to complain about the fairness of the procedure", a much simpler goal than the one being studied.
This algorithm doesn't even satisfy the weaker criterion "each player believes that they have gotten at least 1 nth of the pie", a problem with a fairly simple solution (given below after spoiler space) that I first saw in a Martin Gardner Mathematical Games column in Scientific American decades ago.
The more difficult criterion in the problem being discussed in the current SciAm article is that the division be "envy-free". That is, no player believes that his any other player's piece of cake is better than his own.
The spinning algorithm also specifies that the players are to make their cuts "with the aim of making equal-sized pieces", which is another misunderstanding of how the criteria for an algorithm in this sort of problem are to be specified. Once the algorithm for cutting and distributing is specified, it then up to the players to cut and decide as they choose. That's why "one cuts and the other chooses" is a good algorithm, while "one player cuts, with the aim of making the pieces as equal as possible; then the same player chooses a piece" is a poor one; the non-cutter may feel the cutter has not honestly tried to make the pieces equal. The one cuts and the other chooses algorithm makes no requirement on the aims of players in doing the cutting and choosing, but each player is nonetheless satisfied that his piece is at least as big as the other, even if the other player makes his cutting and choosing decisions with the aim of making that not true.
Solution to the n-player "at least 1 nth" problem, without the envy-free criteria.
. . . .
. . . . . . . . . Order the players 1 through n. The lowest-numbered player who has not yet been assigned a piece cuts a piece off of the pie (his best strategy will be to cut a piece he values as a fair slice). Then in order, each other player who has not yet been assigned a slice can either pass, or reduce the size of the proposed piece by cutting some off and returning it to the unassigned portion. The resulting piece is assigned to the last person to use the knife. Repeat until all players but one have been assigned a piece, and give what remains to the remaining player. (while I have numbered the players for definiteness, the consistency of ordering is not required for the correctness of the algorithm; the cutter and order of the other players may be chosen arbitrarily each round.
Andy
On Fri, Dec 15, 2017 at 10:23 AM, Guy Haworth <g.haworth@reading.ac.uk> wrote:
The problem is usually expressed as one of dividing a cake (or pie) and distributing it so that no-one is in a position to complain about the size of their slice ...
There's this ... https://www.scientificamerican.com/ article/the-mathematics-of-cake-cutting/
... and then there's this by Ian Stewart https://www.amazon.co.uk/How- Cut-Cake-Mathematical-Conundrums/dp/0199205906
However, the best solution I know of (which Ian Stewart confirmed he had not heard of) came from the 13-year-old son of a colleague of mine ....
Everyone gets a knife and makes a cut in a circular cake which is standing on a turntable ... with the aim of making equal-size slices.
The cake is then spun, and everyone gets the slice opposite them.
[ In other words, the randomness takes the decision about who gets what away from the hungry mathematicians ]
Guy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun