The cake-cutting problem is a fair division problem that is based on a scenario in which any number of people wants to divide up a cake with different toppings and be treated fairly. The cake (or any other resource) needs to be divided among people who have different preferences over different parts of the cake – some people prefer bananas in a cake, some prefer the chocolate toppings. The point is, the division should be subjectively fair, meaning each individual should receive a piece that they believe is a fair share.
This type of problem has ‘haunted’ mathematicians for a long time. The reason is that this is a really good metaphor to think about fairness in general – from dividing up pizza to divorce settlements.
In the ‘60s, an algorithm that can fairly divide up a cake between three players was developed, but for more than three players, people had to rely on a 1995 algorithm which could run for a virtually unlimited number of steps to come up with an answer.
But now, a more efficient envy-free cake-cutting algorithm has been developed. This algorithm can solve the issue of cake division in a finite number of steps – anywhere between three and 203 cuts of the cake. Obviously, the new algorithm shows a drastically reduced running time is possible while keeping the division fair.
In the future, the researchers plan to make the new algorithm even faster and simpler.
While this advancement is certainly the most exciting from a theoretical point of view, it’s also good news for the real-world situations as it has the potential to make any division problem solvable.
Reference:
Digital Trends (http://www.digitaltrends.com/computing/cake-cutting-algorithm/)
Wikipedia (https://en.wikipedia.org/wiki/Fair_cake-cutting)
The Wonderful World of Algorithms 