Técnicas evolutivas para división justa de tortas discretas

Abstract

Abordamos en este trabajo el corte de tortas discretas (discrete cake-cutting) con el objetivo de obtener una asignación libre de envidia (envy-free) con el número mínimo de cortes. No se conoce un algoritmo polinomial para este problema. Con el fin de obtener información sobre qué funciones del conjunto de cortes y de las valoraciones de los jugadores pueden conducir a una asignación libre de envidia de manera experimentalmente más rápida, implementamos algoritmos genéticos usando mutación y cruce para las posiciones de los cortes y las asignaciones de porciones a cada agente. Reportamos los resultados de esta implementación sobre instancias generadas aleatoriamente.

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.