Emparellamentos Estables: Algoritmo de Gale-Shapley

Abstract

A primeira parte deste traballo centrarase en introducir e desenvolver as propiedades matemáticas do algoritmo de Gale-Shapley. Este algoritmo pretende dar solución ao problema de atopar emparellamentos estables entre dous conxuntos diferenciados, nos que cada elemento dun conxunto ten unha orde de preferencias sobre o outro conxunto. Este algoritmo, a pesar do seu carácter abstracto e teórico, introducirase a través dun caso particular, no que os emparellamentos son individuais, e que soe estudarse no contexto dos matrimonios entre individuos. A partir de aí, revisarase o caso xeral e compararanse as distintas propiedades que presentan. Para verificar o seu correcto funcionamento, este traballo tamén inclúe un estudo numérico, realizado a partir da implementación do código do algoritmo de Gale-Shapley. Por outra banda, tamén se incluíu unha das aplicacións de Gale-Shapley mais recentes, as subastas de anuncios en Internet. Despois dunha breve introdución á teoría de subastas, describirase o algoritmo dun mecanismo xeral de subastas e as súas propiedades. De novo, tamén se implementou este algoritmo en código e incluíuse un estudo numérico do mesmo.

The first part of this work will focus on introducing and developing the mathematical properties of the Gale-Shapley algorithm. This algorithm aims to provide a solution to the problem of finding stable matches between two distinct sets, where each element of one set has a preference order over the elements of the other set. This algorithm, despite its abstract and theoretical nature, will be introduced through a particular case, in which the matches are one-to-one, and which is usually studied in the context of marriages between people. From there, the general case will be reviewed and the different properties they present will be compared. In order to verify its correct functioning, this work also includes a numerical study, with an implementation in code of the Gale-Shapley algorithm. On the other hand, one of the most recent Gale-Shapley applications, Internet ad auctions, was also included. After a brief introduction to auction theory, the algorithm of a general auction mechanism and its properties will be described. Again, this algorithm was also implemented in code and a numerical study of the algorithm was performed and included