Sesión Matemática DiscretaComparación de Algoritmos de asignación de bienes indivisibles.
Agustín Alvarez
Universidad Nacional de General Sarmiento, Instituto de Ciencias, Los Polvorines, Provincia de Buenos Aires, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Cómo repartir un conjunto de bienes indivisibles (artículos, no plata) entre un grupo de personas no es un problema sencillo. Las personas podrían ser un grupo de hermanas que heredan un conjunto de bienes, o un matrimonio que se divorcia, o países en conflicto por un conjunto de recursos. Pensando en las hermanas que heredan, cada hermana valora los bienes según su propia subjetividad y se desea tener un método que reparta los bienes de manera que todas queden satisfechas con el reparto. Hay definidas distintas medidas de justicia y funciones de bienestar para medir cuán buenos son los repartos de este tipo y lo deseable suele ser proponer algoritmos de reparto que se desempeñen bien respecto a estas medidas o cuantificadores. Proponemos un método de asignación y lo comparamos a través de simulaciones con otros algoritmos conocidos. A su vez, para casos de pocos agentes y pocos artículos también comparamos con métodos exhaustivos que logran, de existir, repartos proporcionales o repartos sin envidia, observando en qué proporción de casos no se logran estos repartos justos con el algoritmo propuesto y los conocidos. También comparamos con métodos exhaustivos que maximizan medidas de bienestar como el Bienestar de Nash o el igualitario, observando la pérdida con los otros algoritmos en este sentido. El objetivo de realizar esta comparación es elegir un método de asignación que sea computable tanto en casos de pocos herederos y pocos agentes como cuando estas cantidades son moderadas o grandes y que su comportamiento sea bueno o aceptable en los casos en que se puede comparar con algoritmos exhaustivos. Programar dicho método dentro de una aplicación Shiny para brindar una herramienta de reparto de bienes indivisibles para posibles usuarios interesados.
Es un problema bastante similar al de repartir bienes, el de repartir un conjunto de tareas entre trabajadores, donde cada uno valora las tareas según su percepción. También se estudia este problema y se propone un método de reparto de tareas.
Finalmente se crea una aplicación Shiny para que los usuarios interesados puedan utilizar libremente esta herramienta en cualquiera de los tipos de reparto.
Algunos trabajos importantes del área se incluyen en las referencias.
Referencias
[1] Amanatidis, G., Aziz, H., Birmpas, G., Filos-Ratsikas, A., Li, B., Moulin, H., . . . & Wu, X. (2023). Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322, 103965.
[2] Lipton, R. J., Markakis, E., Mossel, E., & Saberi, A. (2004). On approximately fair allo- cations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (pp. 125-131).
[3] Plaut, B., & Roughgarden, T. (2020). Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2), 1039-1068.
[4] Akrami, H., Alon, N., Chaudhury, B. R., Garg, J., Mehlhorn, K., & Mehta, R. (2022). EFX allocations: Simplifications and improvements. arXiv preprint arXiv:2205.07638.