Modelado y resolución del problema de asignación de plazas de movilidad internacional: un enfoque basado en las preferencias ponderadas de los solicitantes

1 aSB Equation Chapter 1 Section 1 Trabajo Fin de Grado en Ingeniería de Organización Industrial Modelado y resolución del problema de asignación de plazas de movilidad internacional: un enfoque basado en las preferencias ponderadas de los solicitantes. Autor: Carmen Rodríguez González Tutor: Pedro Luís González Rodríguez Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Universidad de Sevilla Sevilla, 2025 Trabajo Fin de Grado en Ingeniería de Organización Industrial Modelado y resolución del problema de asignación de plazas de movilidad internacional: un enfoque basado en las preferencias ponderadas de los solicitantes. Autor: Carmen Rodríguez González Tutor: Pedro Luís González Rodríguez Catedrático de Universidad Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2025 Trabajo Fin de Grado: Modelado y resolución del problema de asignación de plazas de movilidad internacional: un enfoque basado en las preferencias ponderadas de los solicitantes. Autor: Carmen Rodríguez González Tutor: Pedro Luís González Rodríguez El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2025 El Secretario del Tribunal A Pedro Luis, por estar dispuesto a ayudarme a construir este proyecto desde cero, y creer en él durante todo el proceso. A papá y mamá, por dejarme siempre elegir el camino que quiero seguir, y hacer todo lo que esté en sus manos para ponérmelo fácil. A Ana y José Luís, por enseñarme, casi sin querer, lo más importante de la vida: a disfrutarla. A Suiza y a todo lo que 1 año en ese país me ha dado. A Irene y Mario por ser siempre casa. Y a todas las personas que, de una forma u otra, han estado ahí, haciéndome sentir afortunada. Gracias 1 Resumen Este proyecto propone un método alternativo a los existentes para resolver el problema de asignación de plazas de movilidad internacional. El modelo propuesto está orientado a mejorar la satisfacción general de los solicitantes con las asignaciones, sin renunciar al principio de meritocracia, que se respeta de forma estricta en todo el proceso. Para ello, se permite a los candidatos expresar sus preferencias de manera más flexible que en el sistema tradicional. La propuesta se basa en el algoritmo de aceptación diferida de Roth-Persanson, implementado como un modelo de optimización cuyo objetivo es maximizar el producto de las utilidades individuales, siguiendo el criterio de bienestar social de Nash. Para su validación, el modelo se ha implementado en lenguaje de programación Python y se alimenta con escenarios de diferentes características para comprobar su potencial y sus limitaciones. Además, los resultados se han comparado con los obtenidos mediante una simulación del sistema de asignación actual de la Universidad de Sevilla, para evaluar las mejoras generadas. 8 9 1 JUSTIFICACIÓN Y OBJETIVOS DEL PROYECTO 1.1. Introducción y justificación A finales de octubre de 2024, España sufrió un grave fenómeno meteorológico conocido como DANA, que afectó especialmente a varias localidades de Comunidad Valenciana y alrededores. Este desastre, como la mayoría de los eventos climáticos con un impacto significativo en la población, evidenció entre otras cosas, numerosas deficiencias en la gestión de recursos en situaciones de emergencia. Estas evidencias motivaron un interés inicial por estudiar la asignación justa de recursos en escenarios de crisis, ya que se observaba un amplio margen de mejora en el tratamiento y reparto de las donaciones. Si se lograba optimizar y automatizar este proceso de forma justa y transparente, podrían alcanzarse mejoras significativas en la gestión de futuras emergencias. A medida que avanzaba el análisis, fueron presentándose otros contextos donde también se reparten recursos limitados, y en los que los principios de transparencia y justicia siguen siendo esenciales, lo que llevó a ampliar el campo de interés, y de forma natural e inevitable, el foco del estudio. Aunque el enfoque inicial seguía siendo el más interesante y ambicioso, pronto se hizo evidente que los contextos de crisis presentan una complejidad intrínseca difícil de sortear: La justicia se vuelve más relativa que nunca ya que suele faltar de todo en todas partes. Además, aunque la valoración o utilidad de los recursos es muy subjetiva, las demandas de los afectados tienden a ser muy similares, lo que hace que el valor de los bienes resulte prácticamente incalculable. A esto se suma la necesidad de contar con la colaboración continua de personas afectadas, para conocer sus preferencias y evaluar sus necesidades, algo que muchas veces no es viable. Por último, la escasez de datos fiables con los que trabajar y la complejidad de generar datos simulados que representen bien este tipo de escenarios han sido factores determinantes en la decisión de reenfocar el proyecto. Continuarlo con esa orientación habría supuesto desarrollar una propuesta meramente teórica, demasiado sujeta a supuestos y con escasas posibilidades de aplicación en la vida real, alejándose de la motivación inicial. Tras este punto de inflexión, el proyecto se orienta a escenarios de gestión de recursos más estáticos y controlables, posando el foco finalmente sobre el proceso de asignación de plazas de movilidad a estudiantes. Este proceso, aunque puede variar ligeramente entre universidades, suele estar bastante estandarizado. Generalmente se basa en criterios de admisión predefinidos por las universidades de destino y méritos académicos del estudiante solicitante, dejando las preferencias personales del mismo en segundo plano. Esto se refleja además de en la escasa ponderación que se les da a estas preferencias dentro del proceso, en la forma tan rígida en la han de ser expresadas por los solicitantes: mediante una lista ordenada de destinos. El sistema no les permite indicar por ejemplo que hay un destino que les gusta mucho más que los otros, o que varios destinos ocupan el mismo nivel en su orden de preferencia. Al no representar de forma fiel y real las preferencias, la mayoría de los sistemas realizan una asignación ineficiente. El porcentaje de estudiantes que obtienen su primera o segunda opción no suele superar el 60% y cada año quedan destinos sin asignar y estudiantes sin plaza. Además, no se tiene en cuenta el hecho de que una segunda opción no tiene el mismo valor o no aporta el mismo grado de satisfacción a todos los alumnos. Con el objetivo de evaluar de forma objetiva los métodos actuales, se decidió consultar 10 directamente a los principales interesados y afectados en este contexto: los estudiantes. Se elaboró una encuesta a través de Google Forms que estuvo activa entre marzo y abril de 2025 y fue difundida entre estudiantes universitarios (principalmente de grado) mediante redes sociales y grupos de clase. Mediante una serie de preguntas de múltiples opciones se recogieron testimonios sobre las sensaciones de los estudiantes al enfrentarse al proceso de solicitud de plazas de movilidad internacional, y sobre su grado de satisfacción con el resultado de las asignaciones (se incluyen capturas del formulario en el anexo IV). Finalmente, la encuesta que llegó a más de 100 estudiantes reveló que: - Tan solo un 46.2% tiene claras sus preferencias a la hora de la solicitud. - La mayoría de los estudiantes aplican a todos los destinos que se le ofertan (independientemente de si tienen clara sus preferencias o no) - Hasta 3 candidatos confiesan incluso haber ordenado los destinos aleatoriamente. - Casi el 40% de los solicitantes alegan que les resulto complicado poner en orden los destinos ya que había algunos que estaban empatados en su listado real de preferencias. Tras la exposición de todos estos factores, refinar o repensar los métodos de asignación que dan solución a este problema, desarrollando una forma más apropiada de resolver las asignaciones podría traducirse en: - Una mayor satisfacción para los solicitantes con la solución de la asignación. - Una disminución en la tasa de rechazo de las oportunidades, posterior a la asignación. - Si la demanda es lo suficiente diversa podría conseguirse incluso mejorar la ocupación del total de plazas ofertadas 1.2. Objetivo general En el contexto de la asignación de plazas de movilidad internacional, las preferencias de cada solicitante han de ser correctamente comprendidas y tenidas en cuenta para que las oportunidades caigan en las manos que más las valoran, hecho qué es aún más importante cuando la demanda supera a la oferta. El objetivo de este proyecto consiste pues, en estudiar y modelar un método o procedimiento para resolver el problema de asignación de plazas de movilidad de forma justa y lo más satisfactoria posible. El desafío consiste en que dicho modelo permita gestionar las plazas de forma automática, respetando la meritocracia, pero maximizando la utilidad general o el valor percibido por todos los beneficiados. 1.3. Objetivos específicos Para ejecutar el objetivo general planteado, se establecerán una serie de hitos a alcanzar, a modo de guía en el proceso de desarrollo del proyecto. Estos se plantean a continuación como los objetivos específicos a completar: 1. Analizar la gestión actual de este problema de asignación, así como procedimientos y mecanismos utilizados en la asignación de diferentes recursos limitados en diversos escenarios. Identificar debilidades y fortalezas de los procedimientos estudiados y qué 11 criterios se aplican para acercar las soluciones a la justicia. 2. Realizar una revisión de los métodos de asignación existentes, discutiendo las principales ventajas e inconvenientes de dichos procedimientos, así como la aplicabilidad en el caso planteado. 3. Describir y modelar el problema, una vez estudiado el estado del arte, estableciendo las bases para abordar el mismo, definiendo las restricciones necesarias y la forma de valorar las preferencias de los candidatos. Este paso es clave para conseguir ofrecer un modelo que opere de manera justa y eficiente, y que sea percibido así por los solicitantes. 4. Implementar el modelo mediante el desarrollo de un prototipo funcional que pueda ser testeado a través de simulaciones de escenarios representativos y analizar el comportamiento del algoritmo y su respuesta ante distintas variantes. 5. Validar el modelo y la implementación de este mediante experimentaciones y pruebas piloto. 6. Extraer conclusiones a partir de los resultados obtenidos en la simulación sobre la viabilidad de la herramienta en un escenario real y su impacto en la optimización del bienestar o satisfacción de los beneficiados. 1.4. Estructura del documento El proyecto se desarrolla en cinco capítulos, seguidos de un apartado de referencias y cuatro anexos. En este primer capítulo se presenta la justificación del trabajo, exponiendo el objetivo general perseguido con el mismo y los objetivos específicos propuestos para alcanzarlo. El segundo capítulo recoge la revisión del estado del arte realizada, que contempla tanto el análisis del tratamiento actual de diferentes problemas de asignación como el estudio de métodos de asignación existentes, con el fin de explorar su potencial y sus limitaciones. En el tercer capítulo se describe y se modela el problema objeto de estudio, detallando los fundamentos del enfoque adoptado, así como el diseño y la formulación matemática del método de resolución propuesto. El cuarto capítulo recoge el proceso experimental, dividido en fases. De cada una de las fases de experimentación, se describen la intención, las herramientas y escenarios utilizados y los resultados obtenidos tras su ejecución. Por último, en el quinto capítulo se presentan las conclusiones generales del trabajo, evaluando críticamente el modelo desarrollado y sus limitaciones. En este apartado también se plantean posibles líneas de mejora cuya eficacia podría validarse en futuros estudios. Tras esta estructura de cinco capítulos, se añade al documento un apartado de referencias biográficas y cuatro anexos en los que se incluyen los códigos de programación del modelo en lenguaje Python y otro material complementario que facilita la comprensión del estudio. 12 2 ANÁLISIS DEL ESTADO DEL ARTE: MÉTODOS E INICIATIVAS EXISTENTES 2.1. Análisis del tratamiento de problemas de asignación. A continuación, se llevará a cabo un análisis del tratamiento actual del problema de asignación de plazas de movilidad internacional. Además, se explorará la forma de abordar otros problemas de asignación de recursos u oportunidades limitadas en diferentes contextos. El objetivo de esta investigación es identificar los puntos fuertes de las soluciones existentes que puedan aprovecharse en el desarrollo de este proyecto, descartando los factores que no se ajusten al escenario en estudio. En definitiva, se busca analizar las limitaciones y fortalezas de los procedimientos de asignación existentes y su forma de aplicar el criterio de justicia, para así construir una propuesta bien fundamentada. 2.1.1 Método de asignación actual de destinos de movilidad internacional Actualmente el método de asignación de plazas de movilidad internacional no es un proceso completamente estandarizado. Aunque existen leyes estatales y autonómicas que regulan la educación superior y la movilidad, así como la normativa específica del programa Erasmus+, cada universidad puede establecer requisitos adicionales y procedimientos propios para la gestión de la movilidad. Al ser las propias universidades las responsables de negociar y firmar acuerdos con instituciones extranjeras para conseguir plazas para su alumnado, se les otorga autonomía para regular como distribuir esas plazas entre los solicitantes Aun así, generalmente, el proceso de asignación suele basarse en criterios de admisión y preferencia muy similares, que incluyen los requisitos establecidos por las universidades de destino además de otras variables que permitan medir los méritos académicos del estudiante (European Comission, 2025). En este capítulo se analizarán las condiciones actuales de las dos universidades públicas que coexisten en Sevilla: La Universidad de Sevilla (US) y la Universidad Pablo de Olavide (UPO). Universidad de Sevilla La Convocatoria General de Movilidad Internacional de Estudiantes de la Universidad de Sevilla (Universidad de Sevilla, 2024), establece el siguiente proceso de asignación de plazas de movilidad. Para participar en la convocatoria, los estudiantes deben: - Estar matriculados en cualquiera de las titulaciones oficiales de Grado, Máster o Doctorado, - Si la movilidad es de un semestre, deberán tener al menos 78 créditos pendientes y si es de 13 duración superior, al menos 96 (requisito solo aplicable a alumnos de grado) - Si la movilidad pertenece al Programa Erasmus+, los candidatos deben ser ciudadanos de alguno de los países del Programa o acreditar estar en posesión de un permiso válido para residir en España. - No haber reconocido el equivalente a 120 créditos en programas de movilidad - No estar realizando estudios o estancias de movilidad entrante en la Universidad de Sevilla a través de otros programas - En caso de haber sido titular de una movilidad del curso anterior, y no querer realizarla, haber presentado la renuncia a la beca concedida antes de la fecha exigida. - Estar al corriente de pagos o devoluciones pendientes con la universidad de Sevilla. - No haber superado los 12 meses de movilidad internacional en el ciclo formativo en el que se esté solicitando (exceptuando caso de Grados de más de 240 créditos, que pueden disfrutar de estancias por un periodo total de 24 meses) Además de todos los requisitos generales previamente expuestos, cada plaza cuenta con un perfil específico que los estudiantes han de cumplir tanto en el momento de realizar la solicitud como durante el curso. Esto supone que cada solicitante tenga una oferta individualizada, en función de sus estudios y aptitudes académicas y lingüísticas. Con esa oferta, el estudiante ha de realizar la solicitud, ordenando según sus preferencias hasta 10 de los destinos a su disposición. Una vez realizadas las solicitudes, comienza la fase de baremación, en la que el solicitante entra con: - Su listado de preferencias - La nota media correspondiente a su expediente académico - Las competencias lingüísticas que tenga reconocidas (Estas aptitudes puede que ya hayan sido evaluadas previamente como requisitos específicos, pero ahora servirán como méritos ponderables durante el proceso de asignación) Con esos datos, se calcula la puntuación del solicitante para cada una de las plazas solicitadas aplicando la siguiente baremación: 4. Puntuación asociada al Expediente académico: Nota media ponderada + 0,003 puntos por cada crédito superado, hasta un máximo de 120 créditos. 5. Competencia lingüística como mérito: +0.5 puntos por cada nivel de idioma superior al exigido. Si no se exige idioma, se valora igualmente el idioma del país de destino 6. En el caso de empate se tendrán en cuenta los siguientes criterios: 1º Mayor número de créditos superados 2º Mayor nota media Con estas puntuaciones, los solicitantes adquieren un orden de prioridad en cada destino que hayan solicitado. Respetando ese orden de prioridad y teniendo en cuenta las preferencias del alumnado, se adjudican las plazas disponibles, generando los listados provisionales. Desde las publicaciones de estos listados provisionales, los solicitantes cuentan con un plazo para alegaciones y renuncias. Tras esta fase, comienza la fase de adjudicación, que cuenta con 3 adjudicaciones en las que se 14 actualizan las listas con titulares y suplentes. Tras cada adjudicación los titulares pueden reservar plaza, a esperas de ser aceptados en una mejor opción; aceptar plaza, con lo que renuncian al resto de plazas en las que hayan quedado de suplentes, o rechazar la convocatoria, lo que indica que renuncian a todas las plazas solicitadas en esta convocatoria. Estas acciones van provocando movimientos en las listas, cambiando los resultados hasta la adjudicación final. En cuento a cifras, aunque no se tengan datos concretos sobre el número total de solicitudes y plazas ofertadas, si se conoce que durante el curso 2023/2024, un total de 1931 estudiantes participaron en programas de movilidad internacional como estudiantes salientes. Esta cifra permite hacerse una idea aproximada del volumen de estudiantes implicados en este proceso y el número de oportunidades que ofrece la US. Universidad Pablo de Olavide La Universidad Pablo de Olavide que hasta el curso pasado seguía un modelo de asignación muy similar al de la Universidad de Sevilla (centrado en la nota media del expediente académico, el nivel de idiomas y otras condiciones específicas adicionales como la de deportista de alto nivel) ha introducido cambios significativos en su sistema de baremación para el curso 2025/2026. El nuevo sistema busca priorizar las preferencias de los solicitantes frente a su nota académica (Diario de Sevilla, 2025). Según datos aportados por el vicerrector primero de la UPO, Antonio Sánchez Medina, el nuevo modelo ha producido un aumento notable en el grado de satisfacción de los estudiantes: un 90% de los solicitantes ha obtenido plaza en alguna de sus 3 primeras opciones, un porcentaje que antes no llegaba ni al 70% (Diario UPO, 2025). Además, se evita en la medida de lo posible y si la variedad de la demanda lo permite, un fenómeno que hasta la fecha era muy común, y es que se quedaban estudiantes sin destino, habiendo plazas libres. Sin embargo, la implementación del nuevo sistema ha creado polémica ya que, aunque pueda suponer un aumento de la satisfacción general, unos 34 estudiantes (cifra que podría ascender a 140, dependiendo del medio de información) alegan que la asignación no ha sido justa con su situación. Estos estudiantes, que han amenazado incluso con llevar el caso a tribunales, afirman tener más méritos que otros estudiantes y aun así, no haber recibido las oportunidades que merecen. La convocatoria publicada no especificaba con claridad el cambio en la baremación, y eso junto con una demora de duración considerable en la publicación de las adjudicaciones, hace sospechar a los afectados de que se trate de un error informático a la hora de calcular las notas de los solicitantes. Sin embargo, la respuesta oficial de la Universidad sigue siendo que se ha implementado una reforma en el modelo de asignación para maximizar el beneficio del estudiantado (Diario de Sevilla, 2025) En cualquier caso, esta situación ha abierto un debate sobre si la justicia en este caso se traduce en mérito académico puro o mayor utilidad generada en los beneficiaros. Además, el conflicto resalta la importancia de transparencia total en las bases de las convocatorias, así como una comunicación clara y anticipada de cualquier cambio normativo, para prevenir desconfianza y conflictos legales. A diferencia de la US, la UPO sí que hace públicas las cifras de solicitantes y plazas. Para el curso 2025/2026, hubo 618 solicitantes para las más de mil plazas ofertadas por la entidad. 15 2.1.2 Modelos de asignación de recursos en otros contextos Existen numerosos contextos en los que la asignación de recursos de una forma justa y equitativa supone todo un desafío. A continuación, se analiza una variedad de escenarios de reparto de bienes u oportunidades limitadas. En cada uno de ellos se desarrollan estrategias alineadas con los objetivos y prioridades del contexto, que determinarán la forma de repartir los recursos limitados entre múltiples beneficiarios: Distrito Único Andaluz El Distrito Único Andaluz (DUA) es un sistema gestionado por la Junta de Andalucía que coordina el proceso de admisión a las universidades públicas andaluzas. Cada año el procedimiento se pone en marcha para asignar las plazas de todas las universidades públicas de la región a los estudiantes que han superado la selectividad (PAU), un ciclo formativo de grado superior o están en posesión de otros títulos o diplomas que estén establecidos como vías de acceso validas. Para participar en el proceso de preinscripción los solicitantes deberán acceder la web del Distrito Único Andaluz (Junta de Andalucía, 2025) y formular la solicitud, compuesta aquellas titulaciones y centros de Andalucía en los que desee cursar sus estudios con independencia de la Universidad o provincia en la que obtuvieron los requisitos de acceso. Las peticiones han de introducirse en el orden de preferencia del solicitante (hasta un máximo de 12 opciones), que será vinculante durante todo el proceso. Las plazas se asignan en función de la nota con la que acceda el solicitante al proceso, que dependerá de la vía de acceso que haya seguido. Dicha nota es variable en función de la titulación a la que se aplique, ya que cada universidad establece que materias específicas de la prueba de admisión son relevantes para cada titulación, ponderándolas con diferentes coeficientes. En cada fase de admisión los estudiantes son procesados exclusivamente por su nota de admisión al proceso y el sistema busca asignarles sus primeras opciones siempre y cuando sea posible respetando el criterio de meritocracia. Esto permite que una persona que ha solicitado una titulación en 5º lugar obtenga plaza antes que otra que lo ha solicitado en 1er lugar si este último tiene menor nota de acceso a dicha titulación. En definitiva, el Distrito Único Andaluz funciona gracias a un procedimiento regulado, transparente y basado en la meritocracia, en el que la nota de admisión es el criterio principal de prioridad. Adicionalmente, el sistema procura tener en cuenta el orden de preferencias de cada estudiante en la medida de lo posible. (Junta de Andalucía, 2025) Asignación de Becas Se consideran becas todas las transferencias destinadas a estudiantes o sus hogares, ya sea en forma de ayudas económicas directas, reducción de precios u otros beneficios aplicables a la formación del beneficiario. Estas ayudas requieren la solicitud previa del interesado (INE, 2025). El sistema de asignación de becas varía según el tipo de beca, la entidad responsable y el país en el que se gestiona. Aceptando la variabilidad de este proceso, a continuación, se 16 desglosarán el procedimiento de asignación, los criterios que pueden influir en la adjudicación y otros factores adicionales que pueden condicionar el acceso a estas ayudas. La evaluación del candidato y la posterior asignación de la beca pueden estar orientadas a dos vertientes principalmente, aunque suelen tener en cuenta criterios de ambos enfoques. 1. Reconocimiento de méritos y evaluación de aptitudes del candidato. 2. Evaluación de la necesidad del candidato: criterios económicos y sociales de su entorno familiar. En España, recientemente surgió un debate sobre la ponderación de estos criterios. En enero de 2025, la formación política de Sumar propuso que la asignación de estas ayudas se realizase exclusivamente en función del criterio de necesidad económica, eliminado el criterio de mérito académico. Este enfoque ha generado polémica ya que algunos sectores consideran que podrían desincentivar el esfuerzo académico mientras que otros argumentan que priorizar la renta, garantiza un mayor equilibrio de oportunidades (Curiel, 2025). En cualquier caso, el proceso será similar, comenzando con la definición de los criterios de aceptación de la solicitud. Una vez aceptadas las solicitudes, se lleva a cabo una evaluación detallada que asigna puntos al candidato según los criterios de preferencia o méritos previamente establecidos (Cadena SER, 2024). Ejemplos de criterios de aceptación: o Un límite de renta per cápita de la unidad familiar (u otro indicador objetivo de la situación económica y social del solicitante) o Mantener una nota mínima o Estar matriculado en un programa específico o No haber repetido curso o No haber recibido previamente otra beca del mismo tipo Ejemplos de criterios de preferencia: o Renta total de la unidad familiar o Rendimiento académico o Matricula en asignaturas especificas o Antecedentes curriculares y laborales o Competencias personales y habilidades blandas Es frecuente que los mismos criterios sean contemplados como criterios de admisión y/o criterios de preferencia, dependiendo de las bases de selección de beneficiarios de cada ayuda. Los criterios seleccionados por la entidad que concede las ayudas se evalúan según un baremo establecido por la misma, convirtiéndose en una puntuación final que determinará las oportunidades del solicitante (en el caso de que la beca sea de formación) o la cuantía a recibir por el mismo (en el caso de que la beca de carácter económico) (US, 2024). Cabe mencionar que, en algunos casos, se aplican coeficientes específicos para equilibrar 17 ciertas situaciones. Por ejemplo, en la Universidad de Sevilla, las notas de los estudiantes de Arquitectura e Ingeniería se multiplican por un coeficiente de 1.17 para equilibrar la dificultad de estas titulaciones. Además, las entidades han de especificar también la jerarquía de criterios de desempate, para evitar conflictos posteriores en estos casos (US, 2025). Iniciativa Spliddit Spliddit es una plataforma online diseñada para facilitar la división justa de bienes, gastos y recursos entre varias personas. Nació como un proyecto de investigación para acercar la teoría de juegos y la equidad matemática al público general y actualmente sigue operativa con el objetivo de promover decisiones justas y minimizar conflictos en la vida cotidiana. La plataforma ofrece herramientas especializadas para diferentes escenarios de reparto, siempre basadas en principios de equidad como la minimización de la envidia y la garantía de equidad proporcional. Además, ofrece explicaciones detalladas sobre cada asignación que respaldan la división propuesta, fomentando en todo momento la transparencia. Uno de los servicios que propone es la división de bienes, recomendada para situaciones como herencias, divorcios u otros contextos en los que haya bienes tangibles en reparto. En este proceso, los participantes asignan valores a cada objeto y el algoritmo generará una división basada en dichas valoraciones, que garantice la equidad, reduciendo la posibilidad de conflictos. El sistema garantiza una asignación libre de envidia hasta un bien, lo que significa que un participante no envidiará a otro si se elimina un solo bien del conjunto asignado a ese otro participante. En el caso de bienes divisibles, como dinero en efectivo o acciones, la envidia podría eliminarse reduciendo apenas una centésima parte (1%) del bien en disputa. El algoritmo usado no es público, pero la página web sí que detalla que este asume lo siguiente: el valor que un participante obtiene de un conjunto de bienes es la suma de los puntos que ha asignado previamente a cada bien individual dentro del conjunto. El problema de optimización se formula como un programa lineal entero mixto, siguiendo el principio de maximización del bienestar social de Nash y garantizando así una distribución equitativa y eficiente de los bienes entre los participantes (Procaccia, et al., 2025). Fondo internacional del desarrollo agrícola Para distribuir los fondos de los proyectos, el FIDA utiliza el Sistema de Asignación de Recursos basado en los Resultados (PBAS). Este sistema determina la cantidad de financiación que hay que asignar al país en cuestión mediante una fórmula que evalúa sus necesidades, resultados y vulnerabilidad, garantizando que los fondos se destinen a quienes más los requieren (FIDA, 2025). El sistema utilizado permite además que la asignación se realice con un enfoque ex ante, es decir, que el presupuesto quede comprometido con anticipación, basándose en información o estimaciones previas a la ejecución de los proyectos. Por ello, todos los PBAS dependen de evaluaciones realizadas por el personal operacional de las instituciones interesadas, y la objetividad y el buen juicio del personal son esenciales para su calidad. La objetividad de las evaluaciones depende de la claridad y transparencia del sistema de evaluación y las directrices comunes impartidas al personal interesado. Es esencial que 24 2.2. Análisis de métodos de asignación existentes A continuación, se analizarán diferentes métodos de asignación que, a priori, podrían ser aplicables o adaptables al contexto de la distribución de plazas de movilidad internacional. El objetivo es identificar mecanismos que permitan respetar el principio de prioridad por mérito académico e incorporar de forma significativa las preferencias de cada candidato, con el fin maximizar la satisfacción global de los beneficiados, sin desvirtuar el principio de meritocracia. Algoritmo de GaleShapley El algoritmo de GaleShapley, también conocido como algoritmo de aceptación deferida, es una solución clásica al problema de emparejamiento o matrimonio estable en teoría de emparejamientos. Este problema consiste en emparejar dos grupos de individuos de tamaños similares según sus preferencias garantizando estabilidad, es decir, que ningún dúo de individuos se prefieran mutuamente por encima de sus parejas asignadas y que ningún individuo prefiera estar soltero a estar con su pareja actual. El algoritmo suele ilustrarse mediante una metáfora basada en el emparejamiento entre hombres y mujeres, donde cada individuo tiene una lista ordenada de preferencias sobre los miembros del otro conjunto. El funcionamiento de estos emparejamientos es el siguiente: Cada individuo comienza sin emparejamiento. Los “hombres” clasifican a todas las “mujeres” según sus preferencias. Las “mujeres” evalúan las propuestas recibidas y se quedan con la que más les gusta como pareja actual. El proceso se repite, los “hombres” rechazados avanzan en su lista de preferencias y rehacen sus propuestas tras los rechazos y las mujeres evalúan las nuevas propuestas recibidas. Si les gusta una propuesta más que su pareja actual, podrán cambiarla. El proceso continúa iterativamente hasta que todos los hombres estén emparejados o hasta que todas las mujeres hayan rechazado las propuestas menos deseadas (Singh, 2024). En definitiva, el algoritmo de GaleShapley consiste en un proceso iterativo de propuestas y aceptaciones o rechazos provisionales, que depende de las preferencias ordinales de los agentes de ambos grupos, dando lugar finalmente (tras aun número finito de pasos) a una asignación estable. A continuación, se presenta un seudocódigo a modo de resumen del algoritmo previamente explicado. 25 Algoritmo de Roth-Peranson (Aceptación diferida) El algoritmo de asignación de Roth-Peranson es una adaptación avanzada del algoritmo de GaleShapley, que fue diseñada específicamente para abordar el problema de asignación de plazas de residencia médica en Estados Unidos (National Matching Program, 2025). Este método, también conocido por dar solución al problema de asignación estudiante-universidad, no es más que una aplicación del algoritmo de aceptación diferida, en el que los interesados proponen solicitud a los oferentes. A continuación, se analizará su funcionamiento: Existen dos conjuntos finitos y disjuntos, ya sean estudiantes y plazas en universidades, médicos y residencias o solicitantes y plazas de destino Erasmus (se continúa la explicación con el primer supuesto, estudiantes-universidades). Cada universidad tiene una capacidad que representa la cantidad de plazas que posee dicha universidad. Al igual que en el problema de emparejamiento estable, miembros de ambos conjuntos tienen preferencias sobre con quien emparejarse, quedarse sin plaza o dejar una vacante. Formalmente cada estudiante realiza una lista en un orden estricto sobre el conjunto de las universidades y cada universidad realiza una lista de prioridades sobre el conjunto de los estudiantes. Primero, los estudiantes solicitan plaza a la primera opción de su lista de preferencias. Cada universidad admite provisionalmente al máximo número de alumnos posible, de acuerdo a su propio orden de prioridad y a su capacidad. Si el número de solicitantes superan dicha capacidad, se rechaza a los sobrantes. Los estudiantes que son rechazados solicitan entrar en la siguiente de sus opciones y las universidades pueden reconsiderar la admisión provisional realizada en las etapas anteriores quedándose con sus mejores propuestas. El procedimiento termina cuando cada estudiante ha sido admitido en una universidad o ha sido rechazado por todas las universidades de su lista de preferencias (Muiño Rodríguez, 2016). Este algoritmo de aceptación diferida parece ser el utilizado en el escenario del Distrito Único Andaluz y en el de asignación de plazas de movilidad internacional en la US. Aunque no se mencione explícitamente, su lógica coincide con la descripción operativa de ambos sistemas, Entrada: - Preferencias de “hombres” y “mujeres” Mientras exista al menos un “hombre” libre que no haya propuesto a todas las “mujere s”: El “hombre” elige la “mujer” que más le gusta de las que aún no le ha propuesto Si la “mujer” está libre: Se emparejan Si la “mujer” ya tiene pareja, pero prefiere al nuevo “hombre”: Cambia de pareja Si la “mujer” prefiere a su pareja actual: Rechaza al nuevo hombre Salida: - Lista de emparejamientos estables entre “hombres” y “mujeres” 26 permitiendo una asignación basada en meritocracia (valoración diferenciada que cada plaza otorga a cada solicitante), contemplando a la vez las preferencias individuales de los estudiantes. Se muestra a continuación un seudocódigo que representa el algoritmo descrito anteriormente: El algoritmo de aceptación diferida, que hasta ahora se ha visto como “student-proposing” (los estudiantes inician el proceso proponiendo sus opciones preferidas), también podría plantearse como “school-proposing”. De este modo, las universidades iniciarían el proceso, cambiando la influencia de prioridades y preferencias (Cantillon et al., 2024). Algoritmo de Boston (Aceptación inmediata) El algoritmo de Boston también da una solución al problema de asignación de escuela a estudiantes, En su funcionamiento, cada estudiante intenta entrar inicialmente en su opción preferida y las escuelas aceptan a los candidatos mejor situados en su lista de prioridades hasta agotar sus plazas. Estas asignaciones son definitivas desde el primer paso. En las siguientes rondas de asignación, los estudiantes que no han sido admitidos repiten el proceso con sus siguientes opciones y las escuelas nuevamente aceptan a los mejores según sus prioridades. Este método es adecuado en contextos donde se da menos importancia a respetar el orden de prioridades de las universidades o se desea favorecer que los solicitantes obtengan sus primeras opciones, ya que, al realizar las asignaciones de forma inmediata ronda por ronda, no se permite una reconsideración de nuevas solicitudes a las entidades. La debilidad de este algoritmo se presenta en que, al no ser estratégicamente dominante, puede incentivar a los estudiantes a no revelar sus preferencias reales por miedo a quedarse sin plaza en el proceso de asignación, lo que puede desvirtuar un poco el objetivo del algoritmo que es aumentar la satisfacción general de los estudiantes con los destinos asignados (Cantillon et al., 2024). Entrada: - Lista de estudiantes con sus preferencias ordenadas - Lista de escuelas con sus prioridades y número de plazas 1. Cada estudiante aplica a su opción favorita (la primera en su lista). 2. Cada programa: - Revisa a todos los estudiantes que lo eligieron. - Se queda con los mejores según su prioridad, hasta llenar sus plazas. - Rechaza al resto. 3. Los estudiantes rechazados: - Aplican a la siguiente opción en su lista. 4. Repetir los pasos 2 y 3 hasta que: - Todos estén asignados, o - No queden más opciones por intentar. Salida: - Asignación final de cada estudiante a una escuela (o sin plaza si no fue acepta do en ningún programa de su lista) 27 Se adjunta un seudocódigo correspondiente al algoritmo previamente descrito: El algoritmo de Boston forma parte de una familia más amplia de algoritmos denominada mecanismos de prioridad por rango (rank-priority mechanisms). Estos mecanismos tienen en común que las decisiones de asignación se toman paso a paso, siguiendo un orden preestablecido de pares (preferencia, prioridad). Diferentes órdenes de estos pares generan distintas soluciones o asignaciones cuya eficacia y estabilidad dependen del propósito de la asignación además de otros factores (si los participantes actúan bajo información completa o incompleta y si son estratégicos o no). El caso particular del algoritmo de Boston consiste en priorizar sistemáticamente las preferencias de los estudiantes sobre las prioridades de las escuelas, siguiendo un orden lexicográfico, como ha podido comprobarse en la explicación anterior del algoritmo. En Jaramillo et al (2021) se analiza bajo qué condiciones y ordenamientos estos mecanismos pueden ofrecer ventajas. El mismo, revela que, bajo información incompleta, es decir, cuando los participantes no conocen completamente las preferencias de los demás, todos los mecanismos de prioridad por rango pueden producir emparejamientos inestables, por lo tanto, en el escenario habitual, ninguno presenta ventajas en términos de estabilidad. Sin embargo, si existen ordenamientos alternativos dentro de esta familia que pueden generar asignaciones con matices distintos y resultados orientados a fines específicos. Por ejemplo, un ordenamiento que dé más peso a las prioridades institucionales podría favorecer resultados más ajustados al mérito académico, mientras que otros que equilibren preferencia y prioridad podrían buscar una distribución más homogénea entre centros educativos o compensar desigualdades sociales o geográficas. Se toma conciencia tras esta revisión de la literatura, de la existencia de estas alternativas y de la flexibilidad de diseño en esta familia de métodos. Entrada: - Lista de estudiantes con sus preferencias ordenadas - Lista de escuelas con sus prioridades y número de plazas Inicialización: - Todos los estudiantes están sin asignar - Todas las escuelas tienen sus plazas disponibles Para cada ronda i = 1, 2, ..., hasta que no haya estudiantes sin asignar: 1. Cada estudiante sin asignar aplica a su opción número i (si le queda alguna) 2. Cada escuela: - Revisa a los estudiantes que la eligieron en esta ronda - Ordena a esos estudiantes según su prioridad - Asigna plazas disponibles a los mejores candidatos - Rechaza al resto Fin del bucle Salida: - Asignación final de cada estudiante a una escuela (o sin plaza si no fue aceptad o en ningún programa de su lista) 28 Algoritmo TTC de Gale (Top Trading Cycle) El algoritmo TTC de Gale consiste se usa para resolver el problema de asignación de bienes indivisibles a agentes, por etapas. En cada etapa se construye un grafo cuyos nodos son los pares agente-objeto que aún no han sido asignados en etapas anteriores y cada agente apunta a otro que posea su objeto favorito (puede ser él mismo). Se crean ciclos en el grafo de nodos, que se traducen en asignaciones, Una vez asignados los agentes con sus objetos preferidos, se sacan del grafo y entre los individuos no eliminados se vuelven a buscar ciclos (Muiño Rodríguez, 2016) Existen adaptaciones de este algoritmo para el contexto de asignación escolar, donde los bienes pasan a ser plazas escolares y los agentes son los estudiantes, representándose en nodos diferentes. Cada estudiante apunta a la mejor escuela según su orden de preferencia, si no hay ninguna escuela de su orden de preferencias disponible para el/ella, el estudiante apunta a una escuela ficticia y es eliminado del problema. Cada escuela a su vez señala al mejor estudiante disponible según su orden de prioridad (disponible significa que la haya apuntado). La escuela ficticia señala a todos los estudiantes. Dado que el número de estudiantes y de escuelas es finito, existe al menos un ciclo en cada etapa. Cada estudiante que forme parte de un ciclo queda emparejado con la escuela a la que apuntó, y ese estudiante y su plaza de la escuela son eliminadas del problema (Cantillon et al., 2024). A continuación, se presenta un seudocódigo que representa el algoritmo TTC adaptado al contexto de la asignación escolar: Entrada: - Estudiantes con sus preferencias ordenadas sobre las escuelas - Escuelas con prioridades sobre los estudiantes y número de plazas Inicialización: - Cada estudiante está sin asignar - Cada escuela tiene sus plazas disponibles - Cada plaza se trata como una "unidad individual" con su propia prioridad Mientras haya estudiantes sin asignar: 1. Cada estudiante apunta a su escuela favorita aún disponible (la primera en su lista que tenga plazas) 2. Cada plaza apunta al estudiante con mayor prioridad que la ha elegido 3. Se forman ciclos (del tipo estudiante → escuela → estudiante) 4. Para cada ciclo: - Asignar a cada estudiante la plaza que lo apunta - Eliminar a los estudiantes asignados del sistema - Eliminar las plazas asignadas del sistema - Eliminar esas escuelas de las listas de los demás estudiantes si ya no tienen pla zas Fin del bucle Salida: - Asignación final de estudiantes a escuelas 29 Aunque a primera vista el algoritmo TTC pueda parecer similar al algoritmo de Boston, existen diferencias fundamentales en su funcionamiento, y en algunos casos, en sus resultados. En cada fase del TTC cada universidad solo puede apuntar a un único estudiante (su preferido de entre los que la hayan apuntado) lo que implica que solo se asigna, como máximo, una plaza (de cada universidad) por fase. Esto permite que los estudiantes mantengan vivas sus opciones preferidas en fases posteriores, sin verse penalizados por no obtenerlas en la primera ronda. Además, el algoritmo TTC garantiza asignaciones eficientes en el sentido de Pareto, es decir, no existe otra asignación en la que alguien pueda mejorar sin perjudicar a otro. Gracias a estas propiedades, el TTC refleja de forma más fiel las prioridades reales de los solicitantes y respeta de forma más rigurosa las prioridades de las instituciones. De este modo, se evita incentivar a los solicitantes a manipular sus preferencias, al contrario que en el algoritmo de Boston. Algoritmo Húngaro (de Kuhn-Munkres) El algoritmo húngaro, también conocido como algoritmo de Kuhn-Munkres es un método diseñado para resolver problemas de asignación entre dos conjuntos del mismo tamaño, como por ejemplo 𝑛 tareas a 𝑛 agentes o recursos, minimizando el coste total. El algoritmo opera como si existiese un grafo bipartito ponderado, donde los nodos de un conjunto representan las tareas y los del otro los agentes. Cada arista tiene un peso que indica el coste de asignar una tarea a un agente. La solución se encuentra buscando de manera iterativa rutas de mejora en el grafo, que permitan intercambiar asignaciones reduciendo o manteniendo el coste, hasta alcanzar la una solución óptima. También puede tratarse construyendo una matriz de costes y transformándola iterativamente mediante operaciones de reducción de filas y columnas, con el fin de exponer ceros que representen posibles asignaciones optimas. En realidad, el problema que se trata no es más que un caso particular y muy restringido del problema clásico de programación de tareas (RM||Cmax), donde el número de tareas y recursos coincide (n=m) y no existen restricciones adicionales. Esta simplificación del problema permite que el algoritmo se ejecute en tiempo polinomial, dando soluciones computacionalmente eficientes. Aun así, existen versiones del método para manejar casos desequilibrados, donde el número de tareas y agentes es desigual y puede adaptarse para incluir restricciones de capacidad y precedencia, además de múltiples objetivos (FasterCapital, 2025). 30 El seudocódigo que se expone a continuación explica el funcionamiento del algoritmo húngaro mediante el enfoque matricial: Modelo de Programación Lineal Entera Mixta (MILP) aplicado al problema RM || Cmax La programación Lineal Entera Mixta es una técnica de optimización matemática utilizada entre otras cosas para resolver problemas de asignación, combinando variables enteras y variables continuas, sujetas a un conjunto de restricciones y a una función objetivo lineales. El problema RM || Cmax, es un problema de asignación de trabajos a máquinas con el objetivo de minimizar el makespan (Cmax) teniendo en cuenta que cada trabajo tiene un tiempo de ejecución diferente en cada máquina (Pinedo, 2016) Entrada: - Una matriz de costes C[n][n], donde C[i][j] es el coste de asignar el trabajador i al trabajo j 1. Restar el mínimo de cada fila: Para cada fila i: - Restar el valor mínimo de la fila i a todos los elementos de esa fila 2. Restar el mínimo de cada columna: Para cada columna j: - Restar el valor mínimo de la columna j a todos los elementos de esa columna 3. Cubrir todos los ceros de la matriz con el mínimo número de líneas horizontales o verticales 4. Si el número de líneas es igual a n: - Se ha encontrado una asignación óptima → ir al paso 6 Si no: - Encontrar el valor mínimo no cubierto (llámalo m) - Restar m de todos los elementos no cubiertos - Sumar m a los elementos cubiertos dos veces - Repetir desde el paso 3 5. Encontrar una asignación óptima: - Seleccionar un conjunto de ceros tal que no haya dos en la misma fila o columna - Esa es la asignación óptima Salida: - Asignación óptima con coste mínimo total 31 A continuación, se expone el modelo matemático de optimización: Algoritmo de bienestar social de Nash El algoritmo de bienestar social de Nash (Maximum Nash Welfare, MNW) es un enfoque usado en el marco de la teoría de juegos y la economía del bienestar, para asignar recursos entre múltiples agentes de forma que se maximice el producto de las utilidades individuales conseguidas con dicha asignación (Reddy Pittu, 2025). Matemáticamente el objetivo es el siguiente: max∏𝑢𝑖 𝑛 𝑖=1 Donde 𝑢𝑖 es la utilidad que el agente i obtiene con el bien o los bienes que se le han asignado. Esto permite lograr un equilibrio entre dos objetivos fundamentales - Equidad: evitar disparidad extrema entre individuos - Eficiencia: maximizar el bienestar total del grupo, sin desperdiciar recursos) En contextos de asignación de bienes indivisibles, lograr equidad y eficiencia simultáneamente es muy difícil, sin embargo, el enfoque de MNW ofrece buenas garantías en ambos sentidos, logrando equidad EF1 (libre de envidia hasta un bien) y eficiencia de Pareto, donde no es posible mejorar la utilidad de un individuo sin empeorar a otro. Conjuntos: - N: conjunto de trabajos o tareas. - M: conjunto de máquinas. Datos: - Pij: tiempo de procesamiento del trabajo j en la máquina i. Variables: - Xij ∈{0,1: variable binaria que indica si el trabajo j es asignado a la máquina i. - Cmax: variable continua que representa el makespan del sistema. Función objetivo: - Min Cmax Restricciones: 1. Cada trabajo debe ser asignado exactamente a una máquina: ∑𝑋𝑖𝑗 =1 𝑚 𝑖=1 ∀ j ∈ N 2. El tiempo total de cada máquina no puede exceder el makespan: ∑𝑃𝑖𝑗 ∙ 𝑋𝑖𝑗 ≤𝐶𝑚𝑎𝑥 𝑛 𝑗=1 ∀ i ∈ M 3. Restricción de dominio binario: 𝑋𝑖𝑗 ∈{𝟎,𝟏} ∀ i ∈ M ,j ∈𝐍 32 Estas garantías quedan respaldadas por una serie de axiomas que refuerzan la validez de la herramienta: - Simetría: Todos los individuos son tratados por igual, aunque esto puede alterarse, ya que existen variantes ponderadas de la función, que permiten asignar diferentes pesos a los agentes, reflejando así prioridades o necesidades de la población - Monotonía: Si las utilidades individuales aumentan, el bienestar social también lo hace - Independencia de alternativas irrelevantes: El resultado no cambia si se añaden o quitan opciones que nadie iba a elegir. - Independencia de escala: cambiar las unidades en las que se mide la utilidad no afecta al resultado final de la asignación Estas propiedades hacen que MNW sea una herramienta potente para resolver problemas de asignación en los que se busca un equilibrio significativo entre justicia (equidad) y eficiencia (Ramezani & Endriss, 2025) A continuación, se expone un seudocódigo explicativo para facilitar el entendimiento del proceso de asignación usando la función de bienestar social de Nash Este pseudocódigo es una simplificación del funcionamiento, que solo sería correcto si el número de bienes y agentes es pequeño. Para problemas reales, se usan técnicas más eficientes como programación entera mixta (MILP) o búsqueda heurística. Conclusiones acerca de la revisión de los métodos de asignación existentes La tabla que se muestra a continuación (Tabla 3), facilita la comparación de los algoritmos analizados, resaltando sus diferencias. Las observaciones clave expuestas en la misma suponen las conclusiones del análisis realizado en este apartado. Entrada: - conjunto de agentes - conjunto de bienes - Utilidad de cada bien para cada agente Para cada forma posible de repartir los bienes entre los agentes Calcular la utilidad total de cada agente Calcular el producto de todas las utilidades Si ese producto es mayor que el mejor hasta ahora: Guardar esta asignación como la mejor Guardar el nuevo producto como el mejor hasta ahora Salida: - Mejor asignación encontrada 33 Algoritmo Tipo de preferencias Tipo de solución Proceso de asignación Consideración de las prioridades de oferentes y solicitantes Observaciones clave Algoritmo de GaleShapley Ordinales, de ambos conjuntos Estable (puede dejar a alguien con una opción peor para evitar inestabilidad) Propuestas iterativas con aceptaciones provisionales o rechazos Las preferencias de las mujeres (oferentes) priman sobre las de los hombres (solicitantes) Óptimo para el lado que propone (estrategia dominante para ellos) Algoritmo de RothPeranson Ordinales, de ambos conjuntos Estable (adaptación del algoritmo de Gale-Shapley) Propuestas iterativas con aceptaciones provisionales o rechazos Las prioridades de las escuelas (oferentes) priman sobre las preferencias de los estudiantes Su lógica coincide con la descripción operativa del sistema de asignación de destinos Erasmus (US) y DUA Algoritmo de Boston Ordinales, de ambos conjuntos No necesariamente estable Asignaciones definitivas por ronda según preferencias y prioridades Se priorizan sistemáticamente las preferencias de los estudiantes sobre las prioridades de las escuelas No es estrategia dominante, no incentiva la honestidad, generando resultados manipulables. Algoritmo TTC de Gale (Top Trading Cycle) Ordinales, de ambos conjuntos Eficiencia de Pareto (puede asignar mejor opción a alguien, aunque cree una solución inestable) Asignación por ciclos Se respetan las prioridades de las escuelas por encima de las preferencias de los participantes Es estrategia dominante, aunque decir la verdad no garantiza estabilidad Algoritmo Húngaro (de KuhnMunkres) Cardinales (coste o puntuación) Optima (mínimo coste total) Reducción de matriz de costes o búsqueda de rutas de mejora Generalmente no considera preferencias, solo valores de coste/utilidades cuantificables Limitado a problemas con número igual de agentes y bienes (n x n) MILP aplicado al problema RM || Cmax Cardinales (costes) Óptima respecto a la función Cmax Resolución de un modelo MILP con restricciones y función objetivo Generalmente no considera preferencias, solo valores de coste cuantificables Aunque fue creado para la programación de tareas en máquinas, su estructura es flexible, permitiendo incorporar otras restricciones y objetivos. Algoritmo de bienestar social de Nash Cardinales (utilidades) Optima respecto a la función producto de utilidades Optimización global del producto de utilidades No prioriza explícitamente un lado; aunque puede ponderarse para reflejar prioridades Garantiza eficiencia de Pareto y equidad EF1; proporcionando soluciones equilibradas Tabla 3 Resumen del análisis de algoritmos de asignación 40 3.3.6 Destino Ficticio Dado que el modelo recorre de forma sistemática todas las combinaciones posibles entre candidatos y destinos, se hace necesario incorporar un destino ficticio denominado Dummy para evitar asignaciones indeseadas. Este destino servirá para “absorber” a los estudiantes que no han conseguido plaza en las opciones qué querían y evitar que sean asignados en un destino que no han solicitado u “ocupen” una plaza en uno para el que no sean aptos. Para implementarlo, se parte de la base de que las asignaciones indeseadas quedan marcadas en el modelo con una preferencia de cero por parte de los estudiantes (𝑆𝑖𝑗 =0). Por ello, se establece una preferencia ligeramente mayor que cero para este destino ficticio (𝑆𝑖,𝑑𝑒𝑠𝑡𝑖𝑛𝑜 𝑓𝑖𝑐𝑡𝑖𝑐𝑖𝑜 = 0.1 ∀ 𝑖 ∈ 𝐶), para situarlo por debajo de cualquier otro destino, pero garantizando que el algoritmo no tenga que forzar asignaciones no deseadas, manteniendo así la coherencia entre el escenario real y los resultados. La prioridad de ese destino ficticio para todos los estudiantes se fija con un valor constante e irrelevante, ya que el destino Dummy no discrimina entre solicitantes, y está configurado con una capacidad suficiente para albergar a todos ellos (𝐶𝑑𝑢𝑚𝑚𝑦 = | 𝐶 |). Es decir, ningún solicitante que no haya obtenido plaza en sus destinos solicitados se quedará sin plaza en el destino Dummy. En definitiva, Dummy se configura como una opción sin preferencias de ningún tipo, cuyo único propósito es evitar que el algoritmo fuerce asignaciones no deseadas sin renunciar a una estructura completa de bucles y restricciones en el modelo. 3.4. Diseño experimental Para llevar a cabo la experimentación, expuesta en el próximo apartado, el modelo previamente descrito ha sido implementado con lenguaje de programación Python, utilizando el solver Gurobi para la resolución del problema de optimización. El código completo se encuentra explicado en el Anexo I. Los datos de entrada, que incluyen las preferencias de los estudiantes, las prioridades de los destinos y las capacidades de cada plaza se introducen en un archivo Excel que se carga y se procesa directamente desde el propio código. Siguiendo la misma estructura para facilitar la extracción de los datos, se diseñan distintos archivos que representan escenarios de validación específicos, con el fin analizar el comportamiento del modelo frente a diferentes situaciones y evaluar su efectividad. En el anexo II queda ilustrado un ejemplo de dicha estructura. 41 4 EXPERIMENTACIÓN A continuación, se describe el proceso de experimentación del modelo, dividiendo esta parte del proyecto varias en fases consecutivas. De cada una de las 4 fases, se expondrá su propósito específico, así como los escenarios de validación usados y las conclusiones obtenidas tras su ejecución. Cabe aclarar que el modelo expuesto en el capítulo anterior (capitulo 3), está ya debidamente actualizado con todos los aprendizajes obtenidos durante cada fase de experimentación. La fase 1 se centra en verificar que el modelo está correctamente implementado y que cumple con las restricciones planteadas, especialmente la de estabilidad. Para ello se construyen escenarios reducidos y fácilmente interpretables. En la fase 2 se evalúa cómo el comportamiento del modelo ante escenarios con empates en las preferencias, poniendo a prueba el impacto de la función objetivo basada en el criterio de Nash en términos de mejora de utilidad y satisfacción. La fase 3 compara el modelo propuesto con el sistema actual de asignación utilizado por la Universidad de Sevilla, adaptando los escenarios utilizados previamente y simulando el mecanismo tradicional para contrastar resultados. Finalmente, la fase 4 analiza la escalabilidad del modelo frente a escenarios de gran volumen, con el objetivo de valorar su viabilidad en contextos reales. 4.1. Fase 1: verificación funcional del modelo. El objetivo de esta fase es validar que el modelo implementado en Python funcione correctamente, y comprobar que las restricciones, especialmente la que garantiza la estabilidad, quedan bien reflejadas y respetadas en la solución. Para ello se construye una especie de entorno simulado o “escenario realista reducido”, asignando nombres a los estudiantes y destinos para facilitar la interpretación de las soluciones y la detección de errores. Este entorno consta de 8 estudiantes o candidatos (Ana, Luis, Marta, Juan, Elena, Pedro, Sofía y Carlos) y 5 destinos (París, Berlín, Roma, Lisboa y Atenas). Con estos conjuntos se crearán diferentes escenarios variando algunos datos de preferencias, prioridades o capacidad. La reducida escala de estos escenarios permite que se puedan resolver a mano, facilitando el análisis del comportamiento del modelo en diferentes situaciones. - Escenario 1: En este primer escenario cada estudiante expresa sus preferencias sobre todos los destinos, ordenándolos de forma estricta (asigna puntuaciones del 5 al 1, siendo 5 el más preferido). Tampoco existen empates en las prioridades que otorgan los destinos a los candidatos. Además, cada destino oferta una plaza, es decir, tiene capacidad igual a uno. Esto permite verificar si el algoritmo de aceptación diferida está correctamente modelado y se consigue la estabilidad clásica de Gale-Shapley. 42 Las tablas 4 y 5 expuestas a continuación resumen los datos de entrada de este escenario. Prioridades Destino Capacidad Ana Luis Marta Juan Elena Pedro Sofía Carlos Paris 1 9 8 7 6 5 4 3 2 Berlín 1 2 9 3 1 4 6 5 7 Roma 1 8 7 9 1 4 2 6 5 Lisboa 1 4 5 9 3 7 1 6 2 Atenas 1 1 3 4 5 7 9 8 1 Tabla 4 Capacidades y preferencias escenario 1 Preferencias Paris Berlín Roma Lisboa Atenas Ana 1 4 2 5 3 Luis 4 1 2 3 5 Marta 5 1 3 2 4 Juan 3 1 2 5 4 Elena 2 1 4 3 5 Pedro 1 5 4 3 2 Sofía 2 3 4 5 1 Carlos 4 5 1 3 2 Tabla 5 Preferencias escenario 1 Para este escenario el modelo solo encuentra una solución factible, es decir, una asignación estable, que se señala en color naranja en las tablas 4 y 5. Al tratarse de un espacio de soluciones extremadamente reducido (a una combinación), el algoritmo no tiene margen para maximizar la función objetivo. Esto queda demostrado en las preferencias tan bajas que ofrecen las asignaciones conseguidas. Este resultado confirma que, en escenarios sin empates en las preferencias o prioridades, el modelo tiende a proporcionar una única asignación factible y estable. Aunque, en escenarios muy específicos, como resulta casualmente el escenario 2, pueden existir soluciones alternativas igualmente válidas. - Escenario 2: Con este escenario quiere comprobarse si la estabilidad conseguida hasta el momento con el modelo se mantiene en el caso de capacidades superiores a 1. Para ello se modifican las capacidades del primer escenario. Gracias a la ejecución del modelo con este escenario, se observó que la restricción R3 tenía que ser actualizada para tratar la asignación de agentes con capacidades superiores. 43 Prioridades Destino Capacidad Ana Luis Marta Juan Elena Pedro Sofía Carlos Paris 2 9 8 7 6 5 4 3 2 Berlín 1 2 9 3 1 4 6 5 7 Roma 1 8 7 9 1 4 2 6 5 Lisboa 1 4 5 9 3 7 1 6 2 Atenas 1 1 3 4 5 7 9 8 1 Tabla 6 capacidades y prioridades escenario 2 Preferencias Paris Berlín Roma Lisboa Atenas Ana 1 4 2 5 3 Luis 4 1 2 3 5 Marta 5 1 3 2 4 Juan 3 1 2 5 4 Elena 2 1 4 3 5 Pedro 1 5 4 3 2 Sofía 2 3 4 5 1 Carlos 4 5 1 3 2 Tabla 7 preferencias escenario 2 Este escenario reveló además una situación muy interesante: a pesar de no existir empates explícitos ni en las preferencias ni en las prioridades, el modelo encuentra dos soluciones estables distintas. produciéndose una de las situaciones excepcionales comentadas previamente. Esta particularidad se produce por la relación que se crea entre las preferencias de Ana y Marta y las prioridades que los destinos Roma y Paris asignan a cada una de ellas. Esto, junto a otras casualidades favorables permite que al intercambiar sus asignaciones entre estos dos destinos no se genere ningún par bloqueante. Por lo tanto, el escenario 2 aparte de cumplir el propósito para el que fue diseñado, casualmente permitió por primera vez comprobar la eficacia de la función objetivo, concluyendo con la solución 1 como la óptima para este escenario. - Escenario 3: Este tercer escenario, introduce valores de preferencia igual a 0 para ciertos destinos, reflejando situaciones donde algunos estudiantes no desean bajo ningún concepto ser asignados a ciertos destinos o simplemente no son aptos para ellos (además de en las preferencias, se reflejan simbólicamente en las prioridades). Este escenario hizo evidente la necesidad de añadir el destino ficticio Dummy como vía de escape para aquellos estudiantes que no puedan ser asignados a ninguna de sus opciones “válidas”. Una vez incorporado el destino Dummy a través del código, el mismo escenario sirvió para Solución 1 Solución 2 44 comprobar la eficacia de esta herramienta para evitar que el algoritmo fuerce asignaciones no válidas. En las tablas 8 y 9 se reflejan las asignaciones previas a la incorporación del destino Dummy sombreadas en naranja, y las asignaciones tras la modificación del modelo, escritas en naranja. Prioridades Destino Capacidad Ana Luis Marta Juan Elena Pedro Sofía Carlos Paris 2 9 8 7 6 5 4 3 2 Berlín 1 2 0 3 1 0 6 5 7 Roma 1 8 7 9 1 4 2 6 0 Lisboa 1 4 5 9 3 6 1 7 2 Atenas 1 1 3 4 5 7 0 8 1 Tabla 8 Capacidades y prioridades escenario 3 Preferencias Paris Berlín Roma Lisboa Atenas Ana 0 4 2 5 3 Luis 4 0 2 3 5 Marta 3 0 5 2 4 Juan 3 0 2 5 4 Elena 2 0 4 3 5 Pedro 0 5 4 3 2 Sofía 2 3 4 5 0 Carlos 4 5 0 3 2 Tabla 9 Preferencias escenario 3 Puede observarse como usando la herramienta del destino Dummy, se evita que el destino París sea asignado a Ana, que no lo quiere o no es apta para él, y se asigne directamente a alguien que, si lo pueda o quiera aprovechar, en este caso Juan. Solución con Dummy Solución sin Dummy 45 Tras esta fase de experimentación, se confirmó el correcto funcionamiento del modelo en escenarios simples, tras las modificaciones necesarias detectadas durante la propia validación. Hasta el momento, la mayoría de los escenarios testeados simulan contextos sin empates en las preferencias o prioridades, en los que el espacio de soluciones factibles suele reducirse a una única asignación estable. Por ello, en la siguiente fase se trabaja con escenarios que ofrezcan al modelo de optimización algún margen de actuación para así comprobar el potencial de la función objetivo para mejorar la satisfacción del alumnado. 4.2. Fase 2: Evaluación del comportamiento del modelo frente a empates y el impacto de la función objetivo para mejorar la utilidad. Una vez verificado el funcionamiento del modelo y comprobado que se respeta la estabilidad y no se generan pares bloqueantes, se generan escenarios con empates en las preferencias de los solicitantes para ahora sí, evaluar la mejora que supone incorporar una función objetivo como la que se ha diseñado. - Escenario 4: En este escenario, se sigue trabajando con el entorno creado para la primera fase, introduciendo las preferencias de los estudiantes con empates. En la tabla 10 puede observarse, por ejemplo, que Ana solo solicita plaza en París, a Luis no le importa a que destino ir y Marta prefiere Roma por encima de todos los demás, Juan y Elena tienen un orden de preferencias estricto, … Esto da lugar a múltiples soluciones factibles y estables, permitiendo analizar la diferencia entre obtener simplemente una asignación estable y aplicar la función objetivo que busca maximizar las utilidades individuales. Preferencias Paris Berlín Roma Lisboa Atenas Dummy Ana 10 0 0 0 0 0.1 Luis 10 10 10 10 10 0.1 Marta 1 1 10 1 1 0.1 Juan 8 9 10 7 6 0.1 Elena 9 10 8 7 6 0.1 Pedro 1 1 9 1 10 0.1 Sofía 10 7 8 0 0 0.1 Carlos 7 7 10 10 10 0.1 Tabla 10 preferencias escenario 4 46 A continuación, en la tabla 11 se exponen las 5 soluciones factibles que el modelo encuentra para este escenario. Puede observarse como la métrica que se usa para medir la satisfacción, que no es otra que el valor de la función de Nash varía entre 504 y 378. Esto demuestra que, gracias a implementar el algoritmo de aceptación diferida como un modelo de optimización, se pueden identificar fácilmente las asignaciones que generan una mayor utilidad para los estudiantes. En este caso se encuentran dos soluciones con la misma utilidad (señaladas en verde en la tabla 11), es decir, que generarán la misma satisfacción entre los estudiantes, por lo que, para escenarios con este tipo de resultados habría que definir el criterio de desempate que podría quedar relacionada con la satisfacción de los destinos, por ejemplo. - Escenario 5: Este escenario es similar al anterior, pero de mayor escala, con el fin de comparar si el impacto de la función objetivo se magnifica en proporción a la complejidad del escenario. Se consideran 10 destinos con diferentes capacidades y 30 estudiantes con sus respectivas preferencias y prioridades. Este escenario proporciona 13 asignaciones estables, obteniendo en la asignación optima un valor de utilidad total de 1.7283. A continuación, en la tabla 12 se recoge un resumen de las soluciones obtenidas. ASIGNACIONES Solución 1 Solución 2 Solución 3 Solución 4 Solución 5 Ana París París París París París Luís Lisboa Atenas París Atenas Lisboa Marta Atenas Lisboa Atenas París París Juan París París Lisboa Lisboa Atenas Elena Dummy Dummy Dummy Dummy Dummy Pedro Roma Roma Roma Roma Roma Sofía Dummy Dummy Dummy Dummy Dummy Carlos Berlín Berlín Berlín Berlín Berlín PRODUCTO NASH 504 504 441 441 378 Tabla 11 Soluciones factibles escenario 4 47 Productos de Nash Productos de Nash Solución 1 1.7283 (máx.) Solución 8 1.0370 Solución 2 1.5555 Solución 9 1.0370 Solución 3 1.5555 Solución 10 1.0370 Solución 4 1.2962 Solución 11 0.9333 Solución 5 1.1666 Solución 12 0.9333 Solución 6 1.1666 Solución 13 0.8889 (mín.) Solución 7 1.1522 Media 1.1913 Tabla 12 Soluciones factibles escenario 5 En este escenario se obtiene una única solución óptima, la solución 1, que con un valor de 1.7283 es la solución más eficiente desde el punto de vista del bienestar de los estudiantes. La solución 13 por su parte, alcanza el valor mínimo, procedente de una asignación significativamente menos satisfactoria para los candidatos. Tras esta fase de experimentación, se concluye que el uso de la función objetivo elegida, distingue la solución que mejora la satisfacción de los estudiantes asignados. Además, al observar el resto de las soluciones factibles, el valor medio y el mínimo, se concluye que es imprescindible en el modelo fusionar el método de asignación con un objetivo claro y relacionado con la satisfacción como es el Producto de las utilidades de Nash si se van a tratar escenarios con empates en preferencias o prioridades como se propone en este proyecto. 4.3. Fase 3: Comparativa con el modelo actual de asignación de la US. Con el objetivo de evaluar las mejoras que aporta el modelo propuesto frente a un sistema de asignación con las mismas características que el usado por la US actualmente (basado en algoritmos de aceptación diferida como el de Roth-Peranson, y con preferencias estrictas), se desarrolla una herramienta para facilitar la comparación. Se aprovecha la implementación del algoritmo de aceptación diferida que forma parte del modelo propuesto, pero desactivando la función objetivo, de tal modo que el algoritmo quede orientado únicamente a hallar soluciones factibles, es decir, estables. Este modelo, que trata de obtener las mismas soluciones que obtendría la US, requiere que tanto las preferencias de los estudiantes como las prioridades de los destinos estén expresadas en forma de rankings estrictos, sin empates. Para facilitar la comparación de ambos modelos, se adaptan los escenarios 4 y 5 usados previamente, mediante un mecanismo de desempate aleatorio implementado en Python. Esta herramienta transforma las preferencias reales originales en rankings estrictos simulando lo que ocurre cuando los estudiantes se ven forzados a ordenar sus preferencias de forma rígida, como sucede en la actualidad. El código que adapta los escenarios y los resuelve simulando el modelo de la US puede encontrase completo en el Anexo III. Con esta herramienta se generan 100 iteraciones de cada escenario original, variando aleatoriamente los desempates, lo que simula diferentes realidades posibles supuestamente 48 dependientes de las decisiones de los estudiantes. En cada iteración, se garantiza que los desempates no coincidan con los de iteraciones previas y que las asignaciones con utilidad nula (asignaciones no válidas) no sean desempatadas. Para cada iteración, se resuelve el problema y se calcula la utilidad real alcanzada (con las preferencias reales y originales de los escenarios antes de ser adaptados) A continuación, se presentan los resultados comparativos de los escenarios 4 y 5 resueltos con ambos métodos. ESCENARIO 4 Función de Nash Modelo propuesto Optimo 504 Simulación US Máximo 504 Mínimo 378 Media 423.99 N.º veces que se obtiene el óptimo 10/100 Tabla 13 Comparativa escenario 4 ESCENARIO 5 Función de Nash Modelo propuesto Optimo 1.7283 Simulación US Máximo 1.1522 Mínimo 0.0040 Media 0.4261 N.º veces que se obtiene el óptimo 0/100 Tabla 14 Comparativa escenario 5 Con esta fase de experimentación se concluye lo siguiente: Se parte de la base de que cada ejecución del código auxiliar generado para simular las asignaciones del sistema usado por la US puede proporcionar resultados diferentes debido a la aleatoriedad del método de desempate. Esto realmente refleja bastante bien lo que ocurre cuando se obliga a los estudiantes a ordenar sus preferencias reales de forma estricta. Al pedir a un estudiante que no tiene claras sus preferencias que rompa los empates, el resultado también tendría aleatoriedad en cierto modo. Por eso, para que un sistema como el que se usa actualmente en la US llegue a una asignación óptima en cuanto a satisfacción real, tendrían que darse una serie de coincidencias en las decisiones de todos los estudiantes a la hora de romper esos empates. Esta fase de experimentación demuestra que ese fenómeno es muy poco probable. En el escenario 4, al ser este de menor escala, sí que hay varias iteraciones con desempates aleatorios que logran una asignación óptima o bastante buena. Sin embargo, cuando aumenta la escala del escenario, como es el caso del escenario 5, ni siquiera 49 el valor de utilidad máxima obtenido por el modelo tradicional se acerca al óptimo del modelo propuesto. Esta fase demuestra pues que, si se permite a los estudiantes expresar sus preferencias de forma más flexible y real, el nivel de satisfacción generado con la asignación (medido con la función de Nash: producto de las utilidades de las asignaciones), incrementa considerablemente. Por lo tanto, el modelo propuesto no solo proporciona la estabilidad que asegura la US, sino mayor utilidad real para los estudiantes. 4.4. Fase 4: comprobación de escalabilidad En esta última fase de la experimentación, se testea el modelo frente a escenarios de mayor escala, para analizar su comportamiento. Se crean 5 escenarios de dimensiones crecientes: 100, 200, 300, 400 y 500 estudiantes con un número de plazas y destinos proporcionado. Estos escenarios cumplen las siguientes características generales con el fin de simular situaciones realistas: - Cada destino oferta entre 1 y 15 plazas - Las preferencias de los estudiantes se expresan con números enteros del 0 al 10. - Cada estudiante valora con una preferencia mayor que 0 a entre 1 y 20 destinos - Se permiten empates en las preferencias. - Las prioridades asignadas por los destinos son números reales entre 0 y 10. - Pueden existir empates en las prioridades La tabla 15 resume los cinco escenarios creados y sus principales parámetros: Número de estudiantes Número de destinos Número de plazas Escenario 6 100 50 80 Escenario 7 200 90 150 Escenario 8 300 130 270 Escenario 9 400 160 360 Escenario 10 500 50 400 Tabla 15 Resumen de los escenarios de grandes dimensiones A continuación, se muestran los resultados obtenidos tras la ejecución del modelo con los distintos escenarios planteados, incluyendo el tiempo de optimización requerido por el solver Gurobi, el valor máximo, mínimo y medio de la función objetivo (producto de Nash) considerando 30 soluciones halladas para compararlas con el óptimo hallado. 56 Singh, A., 2024. Built in. [En línea] Available at: https://builtin.com/articles/gale-shapleyalgorithm#:~:text=Shapley%20Algorithm%20Do%3F- ,The%20Gale%2DShapley%20algorithm%20is%20a%20deferred%20acceptance%20algorithm %20used,offers%20to%20match%20with%20another. [Último acceso: 19 mayo 2025]. Universidad de Sevilla, 2024. 1 CONVOCATORIA GENERAL DE MOVILIDAD INTERNACIONAL DE ESTUDIANTES DE LA UNIVERSIDAD DE SEVILLA. [En línea] Available at: chromeextension://efaidnbmnnnibpcajpcglclefindmkaj/https://www.us.es/sites/default/files/becas-yayudas/becasmovilidad/propias/Convocatoria%20General%20de%20Movilidad%20Internacional%202024_2 5.pdf [Último acceso: 18 Mayo 2025]. US, 2024. CONVOCATORIA EXTRAORDINARIA DE BECAS DE FORMACIÓN EN EL VICERRECTORADO DE ESTUDIANTES, Sevilla: Universidad de Sevilla. US, 2025. [En línea] Available at: https://www.master.us.es/experbiotec/Instrucciones_becas_2021_22.pdf [Último acceso: marzo 2025]. Viñas, J. B., 2011. Logística y tecnología en la acción humanitaria. En: Tecnologías para el desarrollo humano de las comunidades rurales aisladas. s.l.:Real Academia de Ingeniería, pp. 428-446. 57 ANEXO I Implementación del modelo en lenguaje de programación Python, utilizando el solver Gurobi para la resolución del problema de optimización: from openpyxl import load_workbook from gurobipy import Model, GRB, quicksum import math "---------------------FUNCIONES PARA EXTRAER DATOS EXCEL--------------------“ # Funcion para extraer datos de una hoja y crear una matriz def extract_matriz(sheet): matriz = [] for row in sheet.iter_rows(min_row=2, values_only=True): # Ignora la fila si todos los valores son None if all(cell is None for cell in row[1:]): continue matriz.append(row[1:]) return matriz # Función para extraer los conjuntos P y C (encabezados desde la columna B) def extract_conjuntos(sheet): return [cell.value for cell in sheet[1][1:] if cell.value is not None] # Función para extraer capacidad Cj en forma de diccionario def extract_data(sheet, columns): data = {} for row in sheet.iter_rows(min_row=2, values_only=True): key = row[0] values = [row[i] if i < len(row) else None for i in columns] data[key] = values if len(values) > 1 else values[0] return data "-------------------------MODELO DE OPTIMIZACIÓN----------------------------“ def asignar_estudiantes(candidatos, destinos, capacidades, S, R, P_i, R_j): # Crear el modelo modelo = Model("AsignacionEstudiantes") # Variables de decisión: #x_ij = 1 si el estudiante i es asignado al destino j x = modelo.addVars(candidatos, destinos, vtype=GRB.BINARY, name="x") #u=suma del logaritmo de las utilidades u = modelo.addVar(lb=-100,name="utilidad_total", vtype=GRB.CONTINUOUS) # Parámetro epsilon para evitar log(0) epsilon = 1e-3 # Función objetivo: maximizar la suma de log(S_ij + epsilon) * x_ij modelo.setObjective(u, GRB.MAXIMIZE) # Funciones para hallar otras soluciones factibles modelo.setParam(GRB.Param.PoolSearchMode, 2) # 2 = búsqueda intensiva de múltiples soluciones modelo.setParam(GRB.Param.PoolSolutions, 30) # Número máximo de soluciones que quieres guardar 58 # RESTRICCIONES # Añadir la restricción que define u modelo.addConstr( u == quicksum(math.log(S[(i, j)] + epsilon) * x[i, j] for i in candidatos for j in destinos), name="def_utilidad" ) # R1: cada estudiante puede ser asignado a lo sumo a un destino modelo.addConstrs( (quicksum(x[i, j] for j in destinos) <= 1 for i in candidatos), name="R1" ) # R2: ningún destino puede superar su capacidad modelo.addConstrs( (quicksum(x[i, j] for i in candidatos) <= capacidades[j] for j in destinos), name="R2" ) #R3: conseguir la estabilidad de Gale Shapley (teniendo en cuenta que capacidad puede ser>1) for i in candidatos: for j in destinos: modelo.addConstr( capacidad[j]*x[i, j]+ quicksum(x[i, k] for k in P_i[i][j])*capacidad[j] + quicksum(x[h, j] for h in R_j[j][i]) >= capacidad[j], name="R3" ) # Resolución modelo.optimize() if modelo.Status == GRB.INFEASIBLE: print("Modelo infactible. Generando IIS...") modelo.computeIIS() modelo.write("modelo_infactible.ilp") # Número de soluciones encontradas num_sols = modelo.SolCount print(f"Se encontraron {num_sols} soluciones factibles.") # Explorar las soluciones for k in range(num_sols): modelo.setParam(GRB.Param.SolutionNumber, k) print(f"\nSolución #{k + 1}") prod=1.0 for i in candidatos: for j in destinos: if x [i, j].Xn > 0.5: print(f"{i} \t→ {j:10s}\tu={S[i,j]:3f})") prod*=S[i,j] break print (f"\nProducto Nash={prod:4e}") productos_nash.append(prod) 59 # Extraer asignaciones óptimas if modelo.Status == GRB.OPTIMAL: print("\n=== ASIGNACIÓN óptima (Nash) ===") prod = 1.0 for i in candidatos: for j in destinos: if x[i, j].X > 0.5: print(f"{i} \t→ {j:10s}\tu={S[i,j]:.3f})") prod *= S[i,j] break print(f"\nProducto Nash = {prod:.4e}") else: print("Status:", modelo.Status) print(f"Tiempo de resolución (Gurobi): {modelo.Runtime:.4f} segundos") "--------------------------LECTURA DEL EXCEL--------------------------------“ # Cargar el archivo Excel excel = 'escenario3.xlsx' #introducir el nombre del archivo workbook = load_workbook(filename=excel) # Extraer las hojas relevantes destinos_sheet = workbook['Destinos'] prefcandidatos_sheet = workbook['PrefCandidatos'] priodestinos_sheet=workbook['PrefDestinos'] "---------------------------EXTRACCIÓN DE DATOS-----------------------------“ candidatos =extract_conjuntos(priodestinos_sheet) destinos =extract_conjuntos(prefcandidatos_sheet) preferencias =extract_matriz(prefcandidatos_sheet) prioridades =extract_matriz(priodestinos_sheet) capacidad= extract_data(destinos_sheet, [1]) productos_nash=[] #en productos_nash se almacenan los resultados de la f.o de cada solución "-------------------------TRATAMIENTO DE DATOS------------------------------“ # (construir los conjuntos S, R, Pi(j) y Rj(i)) # Construir S S = {} for i, estudiante in enumerate (candidatos): for j, destino in enumerate (destinos): S[(estudiante, destino)] = preferencias[i][j] # Construir R R={} for j, destino in enumerate (destinos): for i, estudiante in enumerate (candidatos): R[(destino, estudiante)]= prioridades [j][i] #Añadir destino ficticio 60 sin_destino = "Dummy" destinos.append(sin_destino) for i in candidatos: S[(i, sin_destino)] = 0.1 R[(sin_destino, i)] = 1 capacidad[sin_destino] = len(candidatos) # Construir P_i(j) P_i = {i: {} for i in candidatos} #será la lista de destinos que i prefiera por encima de j for i in candidatos: preferencias_i = {j: S[(i, j)] for j in destinos} for j in destinos: P_i[i][j] = [k for k in destinos if preferencias_i[k] >= preferencias_i[j] ] # Construir R_j(i) R_j = {j: {} for j in destinos} #será la lista de candidaos que j prefiera por encima de i for j in destinos: prioridades_j = {i: R[(j, i)] for i in candidatos} for i in candidatos: R_j[j][i] = [h for h in candidatos if prioridades_j[h] >= prioridades_j[i]] "-----------------------------SOLUCIÓN--------------------------------------“ resultado= asignar_estudiantes (candidatos,destinos,capacidad,S,R,P_i,R_j) #Mostrar resumen de productos Nash print("\n=== Resumen de productos de Nash ===") for i, p in enumerate(productos_nash, 1): print(f"Solución {i}: {p:.4e}") print(f"\nMáximo: {max(productos_nash):.4e}") print(f"Mínimo: {min(productos_nash):.4e}") print(f"Media: {sum(productos_nash)/len(productos_nash):.4e}") 61 ANEXO II Los archivos Exel de datos cuentan con 3 hojas, una para las capacidades de los destinos (Destinos) otra para las preferencias de los estudiantes (PrefCandidatos) y la tercera para las prioridades de los destinos (PrefDestinos). A continuación, se muestra un ejemplo: ➢ Hoja 1: destinos ➢ Hoja 2: PrefCandidatos ➢ Hoja 3: PrefDestinos 62 63 ANEXO III Código de Python que simula el desempate aleatorio de los escenarios y los resuelve mediante un algoritmo de aceptación diferida como el de Roth-Peranson, simulando el método de asignación de la US from openpyxl import load_workbook from gurobipy import Model, GRB, quicksum import random '------------------------MODELO DE OPTIMIZACIÓN-----------------------------' def asignar_estudiantes(candidatos, destinos, capacidades, S, R, P_i, R_j): # Crear el modelo modelo = Model("AsignacionEstudiantes") # Variables de decisión: #x_ij = 1 si el estudiante i es asignado al destino j x = modelo.addVars(candidatos, destinos, vtype=GRB.BINARY, name="x") # RESTRICCIONES # R1: cada estudiante puede ser asignado a lo sumo a un destino modelo.addConstrs( (quicksum(x[i, j] for j in destinos) <= 1 for i in candidatos), name="R1" ) # R2: ningún destino puede superar su capacidad modelo.addConstrs( (quicksum(x[i, j] for i in candidatos) <= capacidades[j] for j in destinos), name="R2" ) #R3: conseguir la estabilidad de Gale Shapley (teniendo en cuenta que capacidad puede ser>1) for i in candidatos: for j in destinos: modelo.addConstr( capacidad[j]*x[i, j]+ quicksum(x[i, k] for k in P_i[i][j])*capacidad[j] + quicksum(x[h, j] for h in R_j[j][i]) >= capacidad[j], name="R3" ) # Resolución modelo.optimize() # Extraer asignaciones óptimas asignaciones = {} if modelo.status == GRB.OPTIMAL: for i in candidatos: for j in destinos: if x[i, j].x > 0.5: asignaciones[i] = j print(f"{i} \t→ {j:10s}\tu={S[i,j]:.3f})") break return asignaciones 64 "---------------------FUNCIONES PARA EXTRAER DATOS EXCEL--------------------“ # Funcion para extraer datos de una hoja y crear una matriz def extract_matriz(sheet): matriz = [] for row in sheet.iter_rows(min_row=2, values_only=True): # Ignora la fila si todos los valores son None if all(cell is None for cell in row[1:]): continue matriz.append(row[1:]) return matriz # Función para extraer los conjuntos P y C (encabezados desde la columna B) def extract_conjuntos(sheet): return [cell.value for cell in sheet[1][1:] if cell.value is not None] # Función para extraer capacidad Cj en forma de diccionario def extract_data(sheet, columns): data = {} for row in sheet.iter_rows(min_row=2, values_only=True): key = row[0] values = [row[i] if i < len(row) else None for i in columns] data[key] = values if len(values) > 1 else values[0] return data "--------------------------LECTURA DEL EXCEL--------------------------------" # Cargar el archivo Excel excel = 'escenario1.xlsx' workbook = load_workbook(filename=excel) # Extraer las hojas relevantes destinos_sheet = workbook['Destinos'] prefcandidatos_sheet = workbook['PrefCandidatos'] priodestinos_sheet=workbook['PrefDestinos'] "---------------------------EXTRACCIÓN DE DATOS-----------------------------" candidatos =extract_conjuntos(priodestinos_sheet) destinos =extract_conjuntos(prefcandidatos_sheet) preferencias =extract_matriz(prefcandidatos_sheet) prioridades =extract_matriz(priodestinos_sheet) capacidad= extract_data(destinos_sheet, [1]) # Añadir destino ficticio sin_destino = "Dummy" destinos.append(sin_destino) # Añadir preferencia 0.1 para el dummy a cada candidato (añadir columna a cada fila) for i in range(len(preferencias)): preferencias[i] = list(preferencias[i]) # Asegurarse de que es modificable preferencias[i].append(0.1) # Dummy es el menos preferido 65 # Añadir prioridad 1.0 del dummy a cada candidato (añadir columna a cada fila) fila_dummy = [1 for _ in candidatos] prioridades.append(fila_dummy) # Añadir capacidad del dummy capacidad[sin_destino] = len(candidatos) "-------------------------TRATAMIENTO DE DATOS------------------------------" #Esta parte del código genera ordenaciones aleatorias que los estudiantes #podrían introducir en el caso de la US evitando repeticiones REPETICIONES = 100 MAX_INTENTOS_FALLIDOS = 100 productos_nash = [] ordenaciones_vistas = set() ejecuciones_realizadas = 0 intentos_fallidos = 0 while ejecuciones_realizadas < REPETICIONES and intentos_fallidos < MAX_INTENTOS_FALLIDOS: print(f"\n---- EJECUCIÓN #{ejecuciones_realizadas+1} ----") dic_pref_actual = {} ordenacion_total = [] # Generar ordenaciones aleatorias por estudiante for i, candidato in enumerate(candidatos): # Agrupar destinos por puntuación grupos = {} for destino, punt in zip(destinos, preferencias[i]): grupos.setdefault(punt, []).append(destino) # Mezclar destinos en empates de punt > 0 for punt, grupo in grupos.items(): if punt > 0 and len(grupo) > 1: random.shuffle(grupo) # Construir lista ordenada por puntaje descendente destinos_ordenados = [ d for punt in sorted(grupos.keys(), reverse=True) for d in grupos[punt] ] dic_pref_actual[candidato] = destinos_ordenados ordenacion_total.append(tuple(destinos_ordenados)) # Revisión de duplicados ordenacion_total = tuple(ordenacion_total) if ordenacion_total in ordenaciones_vistas: print("Ordenación repetida. Se descarta.") intentos_fallidos += 1 continue ordenaciones_vistas.add(ordenacion_total) intentos_fallidos = 0 ejecuciones_realizadas += 1 # Convertir ordenaciones a matriz de ranking numérico matriz = [] for i, candidato in enumerate(candidatos): pref_i = preferencias[i] destin_i = dic_pref_actual[candidato]