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]

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.

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

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.

April 21, 2020 1:58 pm