Evolutionary techniques for fair divisions of discrete cakes

Abstract

In this work, we address the problem of discrete cake-cutting with the goal of obtaining an envy-free allocation using the minimum number of cuts. No polynomial-time algorithm is known for this problem. To gain insight into which functions of the set of cuts and the players’ valuations may lead to an envy-free allocation more efficiently in practice, we implemented genetic algorithms using mutation and crossover on both the cut positions and the assignment of portions to each agent. We report the results of this implementation on randomly generated instances.