Algoritmos Gale-Shapley e Irving para o problema do casamento estável com custo igualitário

Abstract

The paper proposes a comparative analysis between two stable matching algorithms: the GaleShapley Algorithm and the Irving Algorithm. The context is grounded in graph theory, where bipartite graphs are essential in representing relationships between sets of entities. The Stable Marriage Problem is a mathematical representation of pairing allocation between men and women with preferences, finding applications in economics, computing, and game theory. The Gale-Shapley Algorithm, introduced in 1962, establishes stable marriages without incentives for participant-initiated changes. However, subsequent studies suggest that this algorithm might disproportionately favor one gender, leading to the need for a more equitable criterion. The Irving Algorithm, from 1987, aims to maximize the average "satisfaction"of all involved individuals. The objective of the study is to implement and compare these algorithms, conducting a comprehensive bibliographic review of both to understand their logic and functionality. Furthermore, it aims to develop algorithm implementations and compare them based on solution quality metrics and execution time. The analysis focuses on comprehending how these algorithms behave concerning different sets of preferences and conditions, exploring metrics such as equalitarian solutions.