Skip to content

Proof and Cake Envy

April 18, 2020


Our proofs can be big too

[Mackenzie and Aziz]

Haris Aziz and Simon Mackenzie are computer scientists at UNSW and CMU respectively. Of course UNSW is the University of New South Wales and CMU is the Carnegie Mellon University.

Today we will discuss cake cutting and more.

Aziz and Mackenzie have solved an open problem concerning how to cut cakes. Their paper is in the April issue of the CACM: “A Bounded and Envy-Free Cake Cutting Algorithm.”

Why Cake Cutting?

Before we talk about cake cutting from a theory viewpoint let’s take a look at why it is interesting. The real answer probably is it is a beautiful math problem. It is easy to state without lots of background. It is simple like Fermat’s Last Theorem:

\displaystyle  x^{n} + y^{n} = z^{n}

has no solutions over the integers with {xyz \neq 0} and n>2. Cake cutting is hard. We like problems that strike back: problems that are not easy to solve. This is a strange view. In real life we might prefer problems that we can easily solve. But not in math. We like problems that are not trivial. The cake cutting problem is hard, so we like it.

Cutting Cakes

We are theorists so our cakes are one-dimensional line segments. The problem involves a finite set of agents, say Alice, Bob, and so on. They want to divide the cake, the line segment, into a finite number of pieces. The pieces are then allocated to the agents. The goal is to get a fair division of the cake.

The notion of “fair” is what makes the problem interesting. Often agents will not have the same tastes: Some like icing more than others, some like the end pieces, while others do not. The fact that the agents assign different values to a piece of the cake is what makes the problem challenging.

If there are two agents the problem has long been solved. Let Bob divide the cake into two pieces, so that he is happy to get either of these pieces. Then have Alice chose which piece she wants. It is easy to see that both Bob and Alice are happy. Both are envy-free: neither would exchange their piece for the others piece.

There is a large literature on the cake-cutting problem. Its creator, Hugo Steinhaus, noted:

Interesting mathematical problems arise if we are to determine the minimal numbers of “cuts” necessary for fair division.

We have taken the quote from an article on Medium that neatly conveys details on various protocols. Some main results are:

  • The Selfridge-Conway discrete procedure produces an envy-free division for {3} people using at most {5} cuts.

  • The Brams-Taylor-Zwicker moving knives procedure produces an envy-free division for {4} people using at most {11} cuts.

  • Three different procedures produce an envy-free division for {n} people. Both algorithms require a finite but unbounded number of cuts. That is to say, the number of cuts may depend on details of their preference functions.

  • The procedure by Aziz and Mackenzie finds an envy-free division for {n} people in a bounded number of cuts.

The last is the result in the CACM paper. Note, the number of cuts can be large:

\displaystyle  n^{n^{n^{n^{n^{n}}}}}.

Even for {n=2} this is immense, galactic. This should be compared to the best lower bound that is order {n^{2}}. This gap is even larger than the usual gaps we find in complexity theory. The P=NP question is only one exponential not five.

This has started me thinking: what exactly is the relationship between this and proof complexity? The latter has well-established relationships to complexity-class questions. The link from proofs in various systems of bounded arithmetic goes through the heart of P=NP. See for instance these slides by Sam Buss and notes that were scribed by Ken and others. What I am puzzled by is that in most cases the blowup is only one or two exponentials. The setting with cake-cutting is different, but how different?

Easy Cases

The Aziz and Mackenzie algorithm takes a long time. It is a nontrivial result, but not one that applies in any practical case. It always takes way too long. The cake will be stale by the time the agents have agreed on their pieces.

This raises a question, that also applies to many computational problems. Is there a way cut a cake faster on some interesting examples? We can explain this by the analogy to sorting. The fastest sorting algorithms run in {O(n \log n)} time where there are {n} objects. But what happens if the objects are already in sorted order? Or at least close to sorted order? The answer is it depends:

  1. Some sorting algorithms always take the same time, independent of the input structure.

  2. There are other sorting algorithms that can take advantage of the nature of the input.

That is some sorting algorithms can run say in linear time if the input is almost sorted. For the cake cutting problem we ask:

Is there a way to cut cakes that is envy-free when the agents have some property {P}?

We do not know the answer, but we think it is an interesting question. Here is an example. Suppose that the agents have the same measures. That is, they evaluate every piece of cake in the same way.

If we know this—and if we continue our supposition above that Bob can cut with exact precision—then there is an easy answer: Have Bob do the cuts. Then all agents will be equally happy since they have the same measures. The question is, what if we do not know? I believe there should be some theorem like this:

Theorem 1 (Conjecture) There is an envy-free algorithm that operates in {O(n^{2})} time the algorithm so that either:

  1. It yields an envy-free solution, or

  2. It determines that some agents have different measures.

In the second case the cake will be cut as before.

Open Problems

I originally planned on discussing size and complexity of proofs. This is driven by the complexity of the cake cutting algorithms. They tend to have lots of cases and are difficult to understand.

They are also difficult to find—this is why cake cutting questions have been resistance to progress. More on this in the future.

[Edit n>2 in Fermat example]

6 Comments leave one →
  1. Peter Tennenbaum permalink
    April 18, 2020 1:26 pm

    3 squared + 4 squared = 5 squared. You’ve made a minor mistake stating Fermat’s Last Theorem. 2 isn’t = to 0. A typo, surely or else I am filled with virions and delusional.

    • rjlipton permalink*
      April 18, 2020 4:15 pm

      Dear Peter Tennenbaum:

      Thanks. Of course n is 3 or more. You are fine—I hope. Good to see you are alert.

      Best and stay safe.

      Dick

      • Peter Tennenbaum permalink
        April 19, 2020 1:49 pm

        Thanks. Note that my late-godfather, Lester E. Dubins who spent his entire career at Berkeley wrote the following article with Spanier (you allude to one result although I know little):

        How to Cut A Cake Fairly
        L. E. Dubins and E. H. Spanier
        The American Mathematical Monthly
        Vol. 68, No. 1 (Jan., 1961), pp. 1-17

        I remembered him telling me about this and the two-person solution of one person cutting and the other choosing. In any case, I think the paper is a reasonable historical reference and a start for someone who wants further background before directly attacking super-hard problems. Note, of course, that some problems can LOOK super-hard until an ingenious (and simple!) idea “appears” in someone’s brain. Later, everyone sees how obvious the solution is and the proof becomes “trivial”! Please stay safe too. Peter

  2. April 19, 2020 12:54 am

    Regarding Theorem 1 (Conjecture), what is the problem exactly? Are agents willing to risk potentially getting a smaller piece to hide their evaluation? If yes, this obviously cannot be solved. If no, then the algorithm of Bob cutting up the cake equally and everyone agreeing that all the pieces are equal (then distributing them in any way) is a good algorithm.

  3. Douglas permalink
    April 21, 2020 1:58 pm

    Great article, the first time I read about this proof by Aziz and Mackenzie was on Quanta Magazine, back in 2016:

    https://www.quantamagazine.org/new-algorithm-solves-cake-cutting-problem-20161006/

    Although the problem for 2 agents is apparently settled since a long time ago, there is something in the “I cut, you choose” procedure that I think limits its use in practical situations.
    Imagine that Alice and Bob are in a litigious divorce, and the judge decides that their jointly owned, disk-shaped estate shall be divided 50/50. Both plan to build houses on their divided lands after the divorce. Bob would like to never talk to Alice again, while Alice still wants to see him on a daily basis. Alice, a mathematician, is charged with the task to perform the division, and decides to cut the estate as follows: a disk and an annulus each one with half of the area, concentric to the original land. If Bob takes the disk, he will need to ask permission to Alice to enter and exit his land; if he takes the external area, he will be bothered by Alice, who will request access to her land. The two options are equally bad for Bob and equally good for Alice, so the division can be considered envy-free, but not anger-free (for him).
    Among all possible envy-free cuttings, is there an algorithm to find a division that optimizes the expectations for both agents? Can we make a link with game theory and try to find the equivalent of the ‘Nash equilibrium’ in the cake-cutting problem?
    Best regards and stay safe.

  4. April 22, 2020 1:35 am

    Historical note: the open problem was originally solved in 2016 by the authors in their paper “A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents”. They acknowledge as such in the footnote on the linked CACM article. The wording in paragraph 3 and later (e.g. “the result in the CACM paper”) suggests that this is a new result as of April 2020, when (as far as I can tell) there is nothing new.

    Still an amazing result though, and I’m glad to see it get more coverage.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s