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

• Autores: Jonathan Carrero Aranda
• Directores de la Tesis: Ismael Rodríguez Laguna (dir. tes.) , Fernando Rubio Díez (dir. tes.)
• Lectura: En la Universidad Complutense de Madrid ( España ) en 2024
• Idioma: español
• Tribunal Calificador de la Tesis: Pablo Manuel Rabanal Basalo (presid.) , Natalia López Barquilla (secret.) , Juan Jesús Roldán Gómez (voc.) , María del Carmen Ruiz Delgado (voc.) , Alfonso Ortega de la Puente (voc.)
• Enlaces
  • Tesis en acceso abierto en: Docta Complutense
• Resumen

  • 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 los esfuerzos se centran 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 añadida 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.

    En esta tesis se estudia este tipo de situaciones, tanto desde un punto de vista teórico como experimental. En concreto, se desarrollan algoritmos genéticos de aproximación capaces de encontrar repartos subóptimos en tiempos razonables, y se introducen reglas adicionales que dificultan mentir. Además, se lleva a cabo un análisis formal de la complejidad computacional asociada a estas mentiras, ya sea en la búsqueda de soluciones óptimas o también aproximadas.

    Una parte de esta tesis consiste en extender este tipo de problemas con el objetivo de abarcar escenarios más realistas. De esta manera, se plantean algunos cambios en la naturaleza de los recursos, como por ejemplo el estudio de recursos complementarios (un pincel y un bote de pintura). Adicionalmente, se trasladan los conocimientos adquiridos a un problema de negociación entre partidos políticos. En este sentido, cuando en un país existe una organización democrática en la que no hay mayoría absoluta, los partidos políticos se ven obligados a pactar entre ellos para aprobar el mayor número posible de leyes en función de sus propios intereses. Surge entonces un nuevo escenario en el que los partidos políticos intentan utilizar algunas estrategias predefinidas para conseguir que se aprueben (o no) leyes de forma que puedan aumentar su satisfacción con el veredicto final.

    Por último, hacemos uso de la tecnología blockchain y aprovechamos las características inherentes de la misma para solucionar algunos de los problemas más importantes que surgen cuando llevamos a cabo repartos de recursos haciendo uso de los métodos tradicionales. En concreto, se desarrollan contratos inteligentes y aplicaciones descentralizadas que son capaces de mejorar la transparencia, inmutabilidad y trazabilidad en los repartos, así como generar instancias dinámicas de este tipo de problemas con las que los investigadores pueden testear sus algoritmos de una manera segura, justa y equitativa.