Sesión Matemática Discreta y Teoría de JuegosAlgoritmos para la asignación justa de tareas indivisibles entre agentes asimétricos.
Andrea Carolina Antunez
Universidad Nacional de General Sarmiento , Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
En este trabajo, abordamos el problema de la asignación justa de un conjunto de \(m\) tareas (ítems no deseados) indivisibles \(M=\{c_1,\ldots , c_m\}\) entre un conjunto de \(n\) agentes asimétricos \(N=\{1,\ldots , n\}\). Cada agente \(i\in N\) posee una función de costo aditiva \(d_i: M \to \mathbb{R}_{\geq 0}\), donde \(d_i(c)\) cuantifica el costo que le representa al agente \(i\) realizar la tarea \(c\), y un peso asignado \(w_i > 0\) que modela su cuota relativa de responsabilidad sobre el conjunto de tareas \(M\). Estos datos definen una instancia \(I=(M,N,d,w)\) donde un reparto se representa por una \(n\)-partición \(A = (A_1, \dots, A_n)\) del conjunto \(M\).
Este marco permite modelizar el problema de obtener un reparto justo de tareas entre agentes con distintos niveles de responsabilidad mediante algoritmos que garanticen algún criterio de justicia y de tal forma que el reparto sea bien aceptado por quienes realizan estas tareas. Los mecanismos de reparto derivados de los utilizados para bienes (ítems deseados), como los presentados en [1], no suelen garantizar medidas de justicia equivalentes al aplicarse al reparto de tareas [2].
Presentamos y analizamos algoritmos en este contexto. Por un lado, estudiamos algoritmos de selección secuencial para el reparto de tareas entre agentes asimétricos. Por otro, generalizamos algoritmos de asignación entre agentes simétricos al caso de reparto ponderado [3,4]. A partir de medidas de justicia adaptadas al reparto con agentes asimétricos, tales como ser libre envidia salvo una tarea y la proporcionalidad ponderada, el objetivo final de este trabajo es la comparación del desempeño de estos algoritmos entre distintas estrategias de reparto.
Trabajo en conjunto con: Agustín Álvarez (Universidad Nacional de General Sarmiento).
Referencias
[1] Amanatidis, G., Aziz, H., Birmpas, G., Filos-Ratsikas, A., Li, B., Moulin, H., and Wu, X. (2023). Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322, 103965.
[2] Aziz, H., Chan, H., and Li, B. (2019). Weighted maxmin fair share allocation of indivisible chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp. 46--52.
[3] Guo, H., Li, W., and Deng, B. (2023). A survey on fair allocation of chores. Mathematics, 11(16), 3616.
[4] Wu, X., Zhang, C., and Zhou, S. (2023). Weighted EF1 allocations for indivisible chores. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), p. 1155.