RT Generic
T1 Emparellamentos Estables: Algoritmo de Gale-Shapley
A1 García Andrade, Uxío
AB 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 deatopar emparellamentos estables entre dous conxuntos diferenciados, nos que cada elemento dunconxunto ten unha orde de preferencias sobre o outro conxunto. Este algoritmo, a pesar do seucará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. Apartir de aí, revisarase o caso xeral e compararanse as distintas propiedades que presentan. Paraverificar o seu correcto funcionamento, este traballo tamén inclúe un estudo numérico, realizadoa 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, assubastas 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 seimplementou este algoritmo en código e incluíuse un estudo numérico do mesmo.
AB 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 offinding stable matches between two distinct sets, where each element of one set has a preferenceorder over the elements of the other set. This algorithm, despite its abstract and theoreticalnature, will be introduced through a particular case, in which the matches are one-to-one, andwhich is usually studied in the context of marriages between people. From there, the general casewill be reviewed and the different properties they present will be compared. In order to verify itscorrect functioning, this work also includes a numerical study, with an implementation in codeof 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 auctionmechanism and its properties will be described. Again, this algorithm was also implemented incode and a numerical study of the algorithm was performed and included
YR 2022
FD 2022-07
LK http://hdl.handle.net/10347/30164
UL http://hdl.handle.net/10347/30164
LA glg
NO Traballo Fin de Grao en Matemáticas. Curso 2021-2022
DS Minerva
RD 27 abr 2026