Το πρόβλημα του σταθερού γάμου

Abstract

Στην παρούσα έρευνα παρουσιάζεται το πρόβλημα σταθερού γάμου (stable marriage problem) το οποίο διερευνά την εύρεση της κατάλληλης αντιστοίχισης μεταξύ ανδρών και γυναικών, λαμβάνοντας όμως υπόψη την λίστα προτιμήσεων που κάθε άτομο εκφράζει στα μέλη του αντίθετου φύλου. Η αντιστοίχιση αυτή γίνεται με κριτήριο την σταθερότητα της λύσης, δηλαδή για κάποιο ήδη αντιστοιχημένο ζευγάρι να μην υπάρχει το κίνητρο να φύγει από την υπάρχουσα επιλογή του. Συγχρόνως παρουσιάζονται πληροφορίες σχετικά με τον τερματισμό και την σταθερότητα της λύσης. Παράλληλα επισημαίνεται η μοναδικότητα της λύσης μαζί με την έλλειψη δικαιοσύνης της λύσης για τα μέλη εκείνου του συνόλου που δεν προτείνουν αλλά βρίσκονται στην θέση της αποδοχής των προτάσεων των μελών του άλλου συνόλου. Επιπρόσθετα, αναφέρονται σε θεωρητικό επίπεδο αλλά και μέσω παραδειγμάτων διάφορες παραλλαγές του αλγορίθμου των Gale & Shapley όπως οι μη πλήρεις λίστες προτίμησης, οι λίστες προτίμησης με ισότητες, ο συνδυασμός προβλημάτων με μη πλήρεις λίστες προτίμησης και λίστες ισότητας, το πρόβλημα αντιστοίχισης νοσοκομείων και ειδικευόμενων νοσοκομείων και το πρόβλημα αντιστοίχισης φοιτητών σε δωμάτια των δύο ατόμων.