Sesión Matemática Discreta y Teoría de JuegosComparación de algoritmos de asignación de tareas indivisibles
Agustín Alvarez
Universidad Nacional de General Sarmiento, Instituto de Ciencias., Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Estudiamos el problema de repartir un conjunto \(M=\{c_1,\ldots,c_m\}\) de \(m\) tareas indivisibles entre un grupo \(N=\{1,\ldots,n\}\) de \(n\) agentes. Consideramos que los agentes tienen valuación aditiva. Esto significa que saber cuánto le pesa cada tarea a un agente sirve para saber el peso de cualquier grupo de tareas mediante la suma.
La propuesta del trabajo consiste en comparar algoritmos conocidos de reparto y algunos nuevos que proponemos mediante una simulación.
Métodos analizados: El método greedy para reparto de bienes indivisibles presentado en [1] se extiende para tareas indivisibles y consiste en que los agentes eligen de manera secuencial y cada agente elige la tarea que le resulta menos pesada cuando le toca elegir. El orden cómo eligen puede venir dado por ronda (tipo Round Robin) o que siempre le toca elegir al que menos carga siente que se le ha asignado hasta el momento. Proponemos un método secuencial en el cuál el turno le toca a la persona que más carga siente que tiene asignada hasta el momento, y en vez de elegir qué tarea realizar, elige qué tarea no va a realizar. Sobre esta idea desarrollamos algunas variantes dependiendo a quién se le asigna esa tarea que el agente eligió para no hacer él: una variante más “determinística” en la que la tarea se le asigna a quien siente menos carga hasta el momento y otra aleatoria donde se sortea a quien se le asigna. Ponderamos la virtud de los algoritmos con aleatoriedad ya que al repetirlos en reiteradas oportunidades se obtienen distintas asignaciones y uno se puede quedar con la “mejor” en cierto sentido que elijamos. Esto permite potenciar este tipo de algoritmos secuenciales, de rápido cómputo. Otro algoritmo analizado es el propuesto en [2] que adapta el método de eliminación de ciclos de envidia propuesto en [3] al caso de tareas para que siga siendo libre de envidia salvo un bien. También aquí proponemos una variante al método: la tarea que se entrega en cada paso, que se entrega a alguien que no envidia a nadie, se elige al azar entre las tareas restantes. Esto permite potenciar el método como antes. También proponemos un método en el que se comienza con un reparto de todas las tareas al azar y luego se va intentando realizar traspaso de tareas entre los agentes en cierto orden de acuerdo a la carga que sienten. Se intenta que los agentes le den tareas a otros que les resulten más livianas. Las simulaciones se realizan en escenarios en los que es posible revisar de manera exhaustiva todos los posibles repartos para comparar los algoritmos propuestos con algoritmos “óptimos” y también en escenarios donde no es posible una revisión exhaustiva. En general lo que comparamos es la proporción de repartos proporcionales y libres de enfidia que logra cada algoritmo en cada escenario de simulación. Para ver definiciones sobre estas medidas de justicia, ver [4].
Trabajo en conjunto con: Andrés Blas Pujadas (Universidad Nacional de General Sarmiento).
Referencias
[1] Paul W. Goldberg, Kasper Hogh, and Alexandros Hollender. The frontier of intractability for EFX with two agents. Theoretical Computer Science, 1052:115367, 2025.
[2] Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On approximate envy-freeness for indivisible chores and mixed resources. Leibniz International Proceedings in Informatics (LIPIcs), 207:1:1–1:23, 2021.
[3] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 125–131, 2004.
[4] Hao Guo, Weidong Li, and Bin Deng. A survey on fair allocation of chores. Mathematics, 11(16):3616, 2023.