The Fink lone-chooser procedure

This proportional cake-cutting procedure was proposed by Fink in 1964. It has a very nice property that the agent does not need to know the total number of agents before he cuts. Now we show the procedure on a 3 agents case.

Say the agents are Alice, Bob and Carol:

  1. Let Alice bisects the cake into two equal pieces based on his utility function.
  2. Bob chooses the larger piece for himself and leaves the other one for Alice.
  3. Now Alice and Bob trisect their pieces. Carol then selects the largest piece out of the three pieces from Alice and Bob. Leaving the remainder to Alice and Bob.

It is not hard to show that everyone gets a proportional piece from this allocation. If \(n=4\), Alice, Bob and Carol will quadrisect their three pieces at the next stage, and the fourth agent, say David, will piece the largest one from each of the three pieces. The algorithm continues in a similar way for any \(n\).


Reference: S. J. Brams, A. D. Taylor, 1996, Fair Division: From cake-cutting to dispute resolution, pp. 40, 2.6

The Steinhaus-Kuhn lone-divider Procedure

The lone-divider procedure is another classic proportional cake-cutting procedures. It was presented by Kuhn back in 1967. This procedure has an interesting property, that throughout the process, we only need one agent to make multiple cuts.

To illustrate the procedure, here we present an example for 3 agents, say Alice, Bob and Carol.

1. Let Alice cut the cake into 3 pieces of equal value based on her utility function.
2. Now let Bob and Carol to indicate which pieces are acceptable to them (at least of value 1/3 based on their own utility functions).
3. Then we have two mutually exclusive cases:
    Case I: Either Bob or Carol finds two or more pieces are acceptable. Say Bob finds more than 1 piece acceptable. Then choosing in order of Carol, Bob and Alice will result in a proportional allocation.
    Case II: Both Bob and Carol indicate at most one piece is acceptable. We first gives the piece that both Bob and Carol find unacceptable to Alice, then we do a Cut-and-Choose between Bob and Carol. In this way, we will end up with a proportional allocation.

Kuhn extended this procedure to any number of players in 1967 with the help of some combinatorial theorem. The basic logic still remains the same.

Reference: S. J. Brams, A. D. Taylor, 1996, Fair Division: From cake-cutting to dispute resolution, pp. 31, 2.2

Dubins-Spanier Moving-knife Method

This is one of the classic proportional procedures. It is proposed by L. E. Dubins and E. H Spanier back in 1961.

Given a group of \(n\) agents and a bar cake, a referee holds a knife parallel to edge of the cake and moves slowly across the whole cake from left to right. When an agent calls "cut", he will get the piece to the left of the blade. The claim is, in this way, the best strategy for agents is to call cut exactly at \(\frac{1}{n}\) position based on their own utility functions. For the last two agents, we do a cut-and-choose. This will give us a proportional allocation.

This procedure is based on one key assumption, that the agents are maximum risk averse. In other words, the agent care only about the maxmin value. Given this assumption, it is not hard to see that calling cut at \(\frac{1}{n}\) gives us the highest maxmin value.

As we can see earlier, the last two agents who call "cut" will get a piece larger than \(\frac{1}{n}\). Therefore, it is possible that all agents may wait for others to call "cut" at the same time, and thus it ends up no one calls throughout the whole procedure. To avoid this, we can simple make a random allocation if no one calls. Since agents are maximum risk averse, this will drive them to call "cut" in order to guarantee a \(\frac{1}{n}\) maxmin value.

Reference: L. E. Dubins, E. H. Spanier, 1961, How to Cut A Cake Fairly, The American Mathematical Monthly.