Cake cutting; What's up with that?; [ONT Edition]
Toronto Star. Toronto, Ont.: Feb 12, 2006. pg. D.16
Full Text (449   words)
(Copyright (c) 2006 Toronto Star, All Rights Reserved. )

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