A review of some fair allocation algorithms for indivisible items

dc.contributor.advisorCamacho, Franklin José
dc.contributor.advisorFonseca Delgado, Rigoberto Salomón
dc.contributor.authorChipantasig Chipantashi, Jefferson Javier
dc.date.accessioned2025-06-26T22:30:45Z
dc.date.available2025-06-26T22:30:45Z
dc.date.issued2025-06
dc.descriptionThis work reviews some fair and efficient algorithms in the allocation problem of indivisible items in the general additive and g-binary additive instances for the cases of goods, chores, and mixtures of goods and chores. Firstly, the state of the art is studied to comprehend the fundamental concepts, advancements, and limitations of the problem. Subsequently, notions of fairness and efficiency, as well as some weaker versions, are examined. Then, in the general additive instance, the behavior of the Round Robin, Double Round Robin, MUW solution, and MNW solution algorithms is analyzed to identify the properties that hold in the cases of goods, chores, and combinations of both. After this, the algorithms' behavior in the g-binary additive instance is scrutinized to identify if the algorithms achieve any additional properties. Finally, a classification of the properties fulfilled by the Round Robin, Double Round Robin, MUW solution, and MNW solution algorithms is obtained in the cases of goods, chores, and mixtures of goods and chores. Moreover, it is demonstrated that the MNW solution algorithm in g-binary additive instances maximizes both Nash and utilitarian social welfare.es
dc.description.abstractEste 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.es
dc.description.degreeIngeniero/a en Tecnologías de la Informaciónes
dc.identifier.urihttp://repositorio.yachaytech.edu.ec/handle/123456789/971
dc.language.isoenges
dc.pagination.pages107 hojases
dc.publisherUniversidad de Investigación de Tecnología Experimental Yachayes
dc.rightsopenAccesses
dc.subjectAlgoritmoses
dc.subjectElementos indivisibleses
dc.subjectBienestar sociales
dc.subjectAlgorithmses
dc.subjectIndivisible itemses
dc.subjectSocial welfarees
dc.titleA review of some fair allocation algorithms for indivisible itemses
dc.typebachelorThesises

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
ECMC0177.pdf
Size:
935.43 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
13.47 KB
Format:
Item-specific license agreed upon to submission
Description: