FairDivision

Created Monday 09 November 2020

I cut, you choose

The "I cut, you choose" method of dividing something fairly between two people is well known. Given some divisible resource, like a pizza, two people may divide the resource using the following protocol:

1. One person is chosen at random to cut the pizza in two pieces.
2. The person who did not cut takes a piece.
3. The person who cut takes the remaining piece.

This protocol is easy to remember and to explain. It is also efficient in the sense that the minimal number of pieces — two — are created.

If you haven't before, I encourage you to now take a moment to consider how a resource could be divided fairly between any number people, not just two.

I thought about this recently myself when I needed to divide a large cookie between myself, my wife, and our 4-year-old daughter. I excused myself to think about how to proceed. When I returned, the cookie had been eaten! That's one protocol I don't recommend.

The Fink protocol

Later (and after eating an entire large cookie without even telling my family about it) I sat down to research the problem. I consulted with my friend Micha Niskin and he suggested the following technique he had devised, which I discovered later is known as the Fink protocol:

1. If there are two people, perform "I cut, you choose".
2. If there are three people, two are chosen randomly. The two randomly chosen people perform "I cut, you choose".
3. The two people with a piece each cut their piece into thirds.
4. The third person without any pieces yet chooses one piece from each of the two with pieces.
5. All people now have two pieces each.
6. If a fourth person joins, each of the three with pieces cut each of their pieces in two.
7. The fourth person without any pieces yet chooses one piece from each of the three with pieces.
8. All people now have three pieces each.
9. ...and so on.

The biggest drawback of the Fink protocol is that each person ends up with n-1 pieces, where n is the number of people, instead of a single piece of size 1/n. On the other hand, like "I cut, you choose", this protocol is easy to remember, and is almost as easy to explain, even to children.

There are actually many approaches to problem, all with various tradeoffs. I didn't find any of them nearly as easy to remember or explain (especially to hungry children!) as Fink, but if you want to do your own research, Fair cake-cutting on Wikipedia is where I started.