Sesión Matemática DiscretaComparación de Algoritmos de asignaciones pesadas de bienes indivisibles.
Solange del Cielo Pitronaci
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.
El reparto de bienes indivisibles entre un grupo de personas es un problema que ha despertado mucho interés en las últimas dos décadas, ver por ejemplo la revisión de la historia del arte presentada en [1]. El problema se aborda en la mayoría de los trabajos con el supuesto que todas las agentes tienen la misma prioridad ante los bienes a repartir. Sin embargo, más recientemente ha ganado también atención el problema más realista (y que generaliza al anterior) en el que las agentes pueden tener distintas prioridades para recibir los bienes (prioridades pesadas), lo que ocurriría entre accionistas de una empresa que se disuelve, cuando tienen distintos porcentajes, o en una herencia en la que están involucradas personas con distinto parentesco a la persona fallecida, etc., ver por ejemplo [2] y [3]. En este caso, los repartos se denominan asignaciones pesadas. Cada agente entre las que se reparten los bienes tiene su propia subjetividad y se desea tener un método que reparta los bienes de manera que todas queden satisfechas con la asignación de acuerdo a la prioridad que les corresponde. Hay definidas distintas medidas de justicia y funciones de bienestar para medir cuán buenas son las asignaciones de este tipo (ver [3]) y lo deseable suele ser proponer algoritmos de asignación 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. Para el algoritmo que generaliza a Round Robin al caso de prioridades pesadas presentado en [3] proponemos modificaciones. Generalizamos algoritmos de asignación entre agentes de igual prioridad presentados en [4] y [5] al caso de prioridades pesadas. A su vez, para casos de pocos agentes y pocos artículos también comparamos con métodos exhaustivos que logran, de existir, asignaciones pesadas proporcionales o asignaciones pesadas libres de envidia (ver definiciones en [3]), observando en qué proporción de casos no se logran estas asignaciones justas con los algoritmos que analizamos. También comparamos con métodos exhaustivos que maximizan medidas de bienestar como el Bienestar de Nash para prioridades pesadas (ver [3]) o el igualitario en los casos de prioridades pesadas, observando la pérdida con los algoritmos analizados en este sentido. El objetivo de realizar esta comparación es elegir los métodos más destacadados por separado para los casos en los que es posible una búsqueda exhaustiva entre todas las posibles asignaciones y los que no y programar una aplicación para que usuarios/as interesados/as puedan disponer libremente de estos algoritmos de asignación.
Trabajo en conjunto con: Agustín Alvarez (Universidad Nacional de General Sarmiento, Instituto de Ciencias).
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, 103965.
[2] Suksompong, W. (2025). Weighted fair division of indivisible items: A review. Information Processing Letters, 187, 106519.
[3] Chakraborty, M., Igarashi, A., Suksompong, W., \& Zick, Y. (2021). Weighted envy-freeness in indivisible item allocation. ACM Transactions on Economics and Computation (TEAC), 9(3), 1-39.
[4] Plaut, B., & Roughgarden, T. (2020). Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2), 1039-1068.
[5] Goldberg, P. W., Høgh, K., & Hollender, A. (2025). The frontier of intractability for EFX with two agents. Theoretical Computer Science, 115367.