Toronto Star Review of Jeff Edmonds

Cake Cutting. What's up with that?

Toronto Star. Toronto, Ont.: Feb 12, 2006. pg. D.16

Anyone who attended the recent cake-cutting seminar at the University of Toronto expecting to receive a big slice of Black Forest was in for a disappointment. Despite the appetizing name, cake cutting is actually a moniker for a complicated mathematical process studied by computer scientists that examines the fair division of resources.

How many computer scientists does it take to cut a cake, you ask? Quite a few, if each cake eater has specific tastes. Cake cutting, also known as fair division, is about figuring out how to divide a resource so that each recipient feels they've received a fair portion based on their needs and desires.

Consider the example of a cake garnished with icing on one side and strawberries on the other. The two people splitting the cake have unique interests one prefers icing, the other strawberries.

To solve the problem, they agree that one will cut the cake and the other will choose a piece.

If one makes an unfair cut, they risk ending up with a less desirable piece.

So there's an impetus to make a fair cut, with equal parts icing and cake. That way, each party would receive at least half of what they wanted.

It gets complicated when more cake-eaters are added. Let's say an icing lover and two strawberry fanatics crash the party. Now the cake will need to be divided into five pieces. What should they do?

Well, the computer scientist would ask each recipient to indicate where they would cut the cake to create two equal-valued parts. That information would be applied to an algorithm (a recursive, step-by- step problem-solving procedure) that churns out an optimal solution whereby each cake-eater receives what they deem to be their fair portion of the whole value of the cake.

The cake-cutting problem was first presented by Polish academics in the 1940s. Since then, mathematicians and computer scientists have attempted to one-up each other with more efficient algorithms.

At the U of T seminar, Jeff Edmonds, a computer scientist from York University, presented an algorithm he developed with Kirk Pruhs of the University of Pittsburgh. They showed that by identifying the recipient's desires in a randomized manner, they can solve a problem in fewer operations.

Of course, the science of cake cutting can be applied to much more complicated matters than dessert. Cake-cutting algorithms can be used to divide assets in a will, settle a divorce, or resolve international issues such as contested underwater mining territories.

But if you ever find yourself at computer scientist's birthday party, the key to getting your favourite part of the cake is easy. When they bust out the algorithms, you bust out a fork.

- Christopher Hutsul