Estudio del problema del matrimonio estable : presentación del algoritmo de Gale-Shapley, análisis de variantes e introducción de la variante preferencia por características

Abstract

La presente tesis busca enunciar el Problema del Matrimonio Estable, mostrar su solución con sus respectivas demostraciones y ejemplos. Luego, mostrar tres variantes de este problema: Conjuntos Desiguales, Preferencias Incompletas, Preferencias por Características. Para cada una se desarrolla la teoría correspondiente y necesaria. Además, se muestran conceptos previos para tener a la mano las herramientas requeridas para tener contexto del problema, sus variantes, los algoritmos y las pruebas que aseguran su solución. Este problema nace al tener el caso donde existan dos conjuntos del mismo tamaño cuyo deseo es emparejarse con el otro conjunto, es decir, para cada elemento encontrar una pareja del otro conjunto. Lo que agrega el enunciado es que cada elemento cuenta con una lista de preferencias. Con base en esta lista entra el concepto de emparejamiento inestable. Este busca emular qué pasaría si dos elementos que no están emparejados se prefieren mutuamente antes que a sus parejas. Si esto sucede se dice que el emparejamiento es inestable. La solución muestra que bajo ciertas condiciones siempre se puede encontrar un emparejamiento no inestable, o emparejamiento estable, además, también se muestra para las respectivas variantes.

This thesis aims to present the Stable Marriage Problem, to show its solution together with the corresponding proofs and examples, and then to introduce three variants of this problem: Unequal Sets, Incomplete Preferences, and Preference by Characteristics. For each variant, the necessary and corresponding theory is developed.

In addition, the thesis presents the preliminary concepts required to provide the tools and context needed to understand the problem, its variants, the algorithms involved, and the proofs that guarantee their solutions.

The Stable Marriage Problem arises from a situation in which two sets of equal size wish to be matched to one another—that is, each element seeks to be paired with an element from the other set. The key addition to the problem statement is that each element has a preference list. Based on these lists, the notion of an unstable matching emerges: this refers to the scenario where two elements who are not paired to each other mutually prefer one another over their assigned partners. If such a situation occurs, the matching is said to be unstable.

The solution demonstrates that, under certain conditions, it is always possible to find a matching that is not unstable, known as a stable matching. The thesis also shows that this result holds for the respective variants presented.