Estudio del problema del matrimonio estable en un entorno multiagente

Abstract

El presente trabajo pretende determinar si un algoritmo de emparejamiento estable, como el de Gale-Shapley, puede ser sustituido por un sistema supervisado de clasificación de forma que encuentre también parejas estables de una forma más eficiente. Para ello, se ha desarrollado un software basado en un sistema multi agente implementado con JADE. El sistema genera, en forma de agentes, el mismo número de elementos de dos grupos diferentes. Cada agente nace con una serie de características, se comunica con todos los agentes del grupo contrario y los ordena, según sus propias preferencias, en una lista de parejas favoritas. Envía esta lista a otro agente, un emparejador, que utiliza el algoritmo de Gale-Shapley para formar parejas estables y las guarda en archivos CSV. Un tercer tipo de agente, un clasificador supervisado de las bibliotecas Weka (Logistic), es entrenado con esos datos y es evaluado para comprobar su grado de acierto.Se ha encontrado que el clasificador es capaz de encontrar algunas parejas estables pero lo hace en un grado muy escaso y con una precisión también demasiado pequeña. No se justifica, por tanto el uso de un clasificador para sustituir el algoritmo de Gale-Shapley.

El present treball pretén determinar si un algoritme d'emparellament estable, com el de Gale-Shapley, pot ser substituït per un sistema supervisat de classificació de manera que trobi també parelles estables d'una forma més eficient. Per a això, s'ha desenvolupat un programari basat en un sistema multi agent implementat amb JADE. El sistema genera, en forma d'agents, el mateix nombre d'elements de dos grups diferents. Cada agent neix amb una sèrie de característiques, es comunica amb tots els agents del grup contrari i els ordena, segons les seves pròpies preferències, en una llista de parelles favorites. Envia aquesta llista a un altre agent, l'emparellador, que utilitza l'algoritme de Gale-Shapley per formar parelles estables i les guarda en arxius CSV. Un tercer tipus d'agent, el classificador supervisat de les biblioteques Weka (Logistic), és entrenat amb aquestes dades i és avaluat per comprovar el seu grau d'encert. S'ha trobat que el classificador és capaç de trobar algunes parelles estables però ho fa en un grau molt escàs i amb una precisió també massa petita. No es justifica, per tant l'ús d'un classificador per substituir l'algoritme de Gale-Shapley.

The present work tries to find out if a stable pairing algorithm, such as the Gale-Shapley , can be replaced by a supervised classification system so that it also finds stable pairs in a more efficient way. To achieve this, we have developed a software based on a multi agent system implemented with JADE. The system generates, as agents, the same number of elements from two different groups. Each agent is created with a series of characteristics, communicates with all the agents from the opposite group and orders them, according to their own preferences, in a list of favorite couples. Later, it sends this list to another agent, a matchmaker, which uses the Gale-Shapley algorithm to form stable pairs and saves them in CSV files. A third type of agent, a supervised classifier from the Weka libraries, Logistic, is trained with this data and is evaluated to check its degree of success. We have seen this classifier is able to find some stable pairs but just a few ones, and with a very small precision too. It is not justified, therefore, the use of a classifier to replace the Gale-Shapley algorithm.