Optimización y análisis de complejidad de repartos de bienes bajo distintas condiciones de bienestar social

Abstract

El área de la asignación de recursos abarca una gran variedad de problemas, los cuales se encuentran presentes en muchos campos tales como la informática, economía e incluso la política. Existen muchas clasificaciones para este tipo de problemas, pero en esta tesis nos centraremos en la Asignación de Recursos Multi-Agente, donde el objetivo es asignar una cantidad de recursos entre algunos agentes de acuerdo con un objetivo dado. Desgraciadamente, se sabe que la dificultad computacional de realizar dicho tipo de repartos es alta (NP-dureza) incluso bajo las formas más sencillas de dicho reparto. Además, existe otra dificultad que radica en que un agente puede verse trivialmente beneficiado si miente sobre el interés que tiene por los recursos disponibles. Por ejemplo, en un bienestar social igualitario donde el objetivo es maximizar el beneficio del agente menos beneficiado, un agente podría aparentar que no le interesan los recursos, de manera que el reparto priorizará su bienestar sobre el de los demás agentes...

The area of resource allocation covers a wide variety of problems, which are present in many fields such as computer science, economics and even political science. There are many classifications for this type of problems, but in this theis we will focus on Multi-Agent Resource Allocation, where the objetive is to allocate an amount of resources among some agents according to a given goal.Unfortunately, the computational difficulty of performing such allocations is known to be high (NP-hard) even under the simplest forms of such allocation. Another difficulty is that an agent can be trivially benefited if he lies about his interest in the available resources. For example, in an egalitarian social welfare where the objective is to maximise the benefit of the least benefited agent, an agent could pretend that he is not interested in the resources, so that the distribution will prioritise his welfare over that of the other agents...