2
$\begingroup$

For the fair cutting of a cake into n pieces for n people, is it sufficient for one person to cut the cake, and for them to get the last pick of piece?

If any one piece is bigger than 1/n, another person will take that piece. If any one piece is smaller than 1/n, then the cutter may end up with that piece. Therefore the cutter has an incentive to cut the cake fairly.

Is this correct?

$\endgroup$
3

2 Answers 2

Reset to default
2
$\begingroup$

No your solution is not an acceptable one, as the order in which the people would pick the slices will introduce jealousy among them.

This is a highly non trivial problem for which a general algorithm was only given recently, by Haris Aziz and Simon Mackenzie (2016). In particular, their envy-free protocol has an complexity upper bounded by $n^{n^{n^{n^{n^{n}}}}}$. So when considering cake, be prepared for a lot of cutting, and do not hope your slices to look like anything you would actually want to eat afterwards.

You can take a look at this introductory article on the subject that gives a reference to the general algorithm, or on arxiv directly for a rigorous analysis.

$\endgroup$
5
  • $\begingroup$ @ArnaudMortier Given that there are several books and research papers written on the topic of cake sharing, I'm willing to bet that your less-than-one-day-long investigation might have missed some of the specifics covered over the last couple of decades by what probably adds up to at least hundreds of researchers... $\endgroup$
    – 5xum
    Aug 24, 2018 at 8:15
  • 1
    $\begingroup$ There might be different answers to this question from the different ways the question can be formulated. For example do we want all of them to have the same "mass" of cake or do we want each of them not to be "jealous" (envy-free algorithms) of the other based on their personal preferences. $\endgroup$
    – ippiki-ookami
    Aug 24, 2018 at 8:19
  • $\begingroup$ @5xum Perhaps you could explain what is wrong with my solution then. $\endgroup$
    – Arnaud Mortier
    Aug 24, 2018 at 8:42
  • $\begingroup$ @ArnaudMortier As a user already explained under your answer, the protocol you propose does not neccessarily result in an envy-free division. $\endgroup$
    – 5xum
    Aug 24, 2018 at 8:44
  • $\begingroup$ @5xum A user stated that indeed, yet they didn't explain why. $\endgroup$
    – Arnaud Mortier
    Aug 24, 2018 at 8:45
0
$\begingroup$

You want to make it so that it is impossible for any number of people to conceive a plan so that the $k$ of them altogether get more than a fraction of $\frac kn$ of the cake.

That's why the method you suggest doesn't answer the question, because the person who cuts and the first person who picks can arrange so that one part is huge and the other $n-1$ are tiny.

A correct version with $3$ people that can be straightforwardly generalised:

  • Person $1$ splits the cake in $2$ parts.

  • Person $2$ chooses one, Person $1$ gets the other.

  • Each of $1$ and $2$ splits their own part into $3$ parts.

  • Person $3$ picks one (of the three parts) from each of them.

You can easily check that each person can selfishly ensure that they will get at least a third of the cake.

$\endgroup$
3
  • $\begingroup$ This is known as the Fink protocol. It produces a proportional division though not necessarily an envy-free one. $\endgroup$
    – user856
    Aug 24, 2018 at 8:21
  • $\begingroup$ @Rahul How is it not envy-free? $\endgroup$
    – Arnaud Mortier
    Aug 24, 2018 at 8:43
  • $\begingroup$ @ippiki-ookami Thanks. However, this explanation introduces concepts that are not part of the OP, like subjectivity as to what is or isn't a third. My answer is a mathematical one where a third is a third. $\endgroup$
    – Arnaud Mortier
    Aug 24, 2018 at 9:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.