Αλγόριθμοι για Δίκαια και Σταθερά Ταιριάσματα

Abstract

Το πρόβλημα του σταθερού γάμου (ή σταθερού ταιριάσματος) ζητά την εύρεση ενός τέλειου διμερούς ταιριάσματος σε μία αγορά δύο πλευρών (π.χ. αιτούντες εργασία και εργοδότες), όπου κάθε ενδιαφερόμενος κατατάσσει πλήρως τα μέλη της άλλης πλευράς βάσει των προτιμήσεών του. Το ταίριασμα αυτό θα πρέπει να χαρακτηρίζεται από σταθερότητα, υπό την έννοια ότι κανένα ζευγάρι παικτών δε θα εγκατέλειπαν αμφότεροι τα ταίρια τους επειδή προτιμούν να είναι μαζί. Οι Gale και Shapley που διατύπωσαν το πρόβλημα, έδωσαν έναν αλγόριθμο ο οποίος βρίσκει πάντα μία τέτοια σταθερή λύση σε πολυωνυμικό χρόνο. Όμως, ο αλγόριθμος αυτός {\em μεροληπτεί} υπέρ της μίας πλευράς, δίνοντάς της τα καλύτερα δυνατά ζευγάρια όσον αφορά τις προτιμήσεις, ενώ στην άλλη δίνει τα χειρότερα δυνατά. Είναι λοιπόν εύλογο να αναζητήσουμε άλλες λύσεις, οι οποίες θα είναι υπό κάποια έννοια πιο δίκαιες. Παρ' όλα αυτά, η βελτιστοποίηση μετρικών που αντικατοπτρίζουν τη δικαιοσύνη σε αυτό το πρόβλημα είναι NP-hard.

Σε αυτή τη διπλωματική εργασία, θα κάνουμε μία εκτενή μελέτη όλων των αλγορίθμων που έχουν προταθεί στη βιβλιογραφία και ευελπιστούν να δώσουν δίκαια και σταθερά ταιριάσματα. Προσαρμόζοντας και συνδυάζοντας τους με νέους, θα σχεδιάσουμε αλγορίθμους που ξεπερνούν τους υπάρχοντες σε απόδοση, κλιμακωσιμότητα και δικαιοσύνη. Στη συνέχεια, θα ακολουθήσει μία διεξοδική πειραματική αξιολόγηση πάνω σε διάφορες κατανομές προτιμήσεων, στην οποία θα αντιπαραβάλλουμε όλους τους διαφορετικούς αλγορίθμους και μηχανισμούς, εντοπίζοντας τις υπερέχουσες στρατηγικές.