A review of some fair allocation algorithms for indivisible items

Abstract

Este trabajo revisa algunos algoritmos justos y eficientes en el problema de asignación de elementos indivisibles en la instancia aditiva general y la instancia aditiva g-binary en los casos de bienes, tareas y mezclas de bienes y tareas. En primer lugar, se estudia el estado del arte para comprender los conceptos básicos, avances y limitaciones del problema. Luego, se examinan las nociones de justicia y eficiencia, así como algunas versiones más débiles. Después, en la instancia aditiva general, se analiza el comportamiento de los algoritmos Round Robin, Double Round Robin, MUW solution y MNW solution con el fin de identificar las propiedades que se cumplen en los casos de bienes, tareas y mezclas de bienes y tareas. Posteriormente, se analiza el comportamiento de los algoritmos en la instancia aditiva g-binary con el fin de identificar si los algoritmos alcanzan alguna propiedad adicional. Finalmente, se obtiene una clasificación de las propiedades que cumplen los algoritmos Round Robin, Double Round Robin, MUW solution y MNW solution en los casos de bienes, tareas y mezclas de bienes y tareas. Además, se demuestra que el algoritmo MNW solution en instancias aditivas g-binary maximiza tanto el bienestar social de Nash como el utilitario.