Matchings stabili: struttura ed estensioni

L'obiettivo di questa tesi è l'analisi di due problemi riguardanti i matchings stabili: il problema del matrimonio stabile e quello dei coinquilini stabili. Viene inizialmente analizzato il problema del matrimonio stabile, risolto nel 1962 da Gale e Shapley, e che ha ancora oggi varie applicazioni e utilizzi. Si considerano due gruppi (uomini e donne, o studenti e università) in cui ogni elemento ordina i membri dell'altro gruppo in ordine di preferenza; lo scopo è mettere in coppia i membri di un gruppo con quelli dell'altro in modo stabile, ovvero trovare un matching in cui non esistano due persone che si preferiscano a vicenda rispetto al loro partner nel matching. Gale e Shapley dimostrarono che tale ''matrimonio stabile'' esiste sempre e può essere trovato tramite un semplice algoritmo, nato appunto per assegnare gli studenti alle università. Viene dimostrato che, applicando l'algoritmo, si determina una soluzione stabile per tale problema, che coincide con il matching ottimo per gli uomini. Viene in seguito dimostrato che l'insieme dei matching stabili, una volta introdotta un'opportuna relazione di dominanza, costituisce un reticolo distributivo, avente come elementi minimo e massimo, rispettivamente, il matching ottimo per gli uomini e quello per le donne. Si passa poi ad analizzare, tramite l'algoritmo di Irving, il problema dei coinquilini stabili, che può essere visto come una generalizzazione del problema precedente, in cui gli elementi sono raggruppati in un solo insieme; anche in tal caso l'obiettivo è trovare un matching stabile. Tale problema, a differenza del problema del matrimonio stabile, non sempre ammette una soluzione stabile, e, inoltre, l'insieme dei matching stabili costituisce un semireticolo, introdotta un'opportuna relazione.