Φιλαλήθεις Μηχανισμοί Ανταλλαγής Νεφρών

Abstract

Η μεταμόσχευση ενός υγιούς νεφρού είναι η καλύτερη γνωστή αντιμετώπιση σοβαρής ασθένιας νεφρών. Εφόσον οι άνθρωποι έχουν δύο νεφρά και μπορούν να επιβιώσουν με ένα, πολλοί ασθενείς έχουν κάποιο συγγενή ή φίλο που είναι διατεθιμένος να δωρίσει το νεφρό του. Παρόλα αυτά, δεν είναι όλοι δότες συμβατοί με τους ασθενείς. Αυτό μας δίνει την ευκαιρία ανταλλαγής νεφρών. Δύο ή περισσότερα ζεύγη ασθενή-δότη ανταλλάζουν νεφρά έτσι ώστε κάθε ασθενής να λάβει νεφρό από δότη άλλου ζεύγους. Στη διπλωματική αυτή χρησιμοποιούμε αυτή τη λύση στα πλαίσια του Αλγοριθμικού Σχεδιασμού Μηχανισμών για να μεγιστοποιήσουμε τον συνολικό αριθμό μεταμοσχεύσεων που μπορούν να γίνουν σε ένα σύστημα με πολλούς ασθενείς, εξάγοντας όμως πρώτα τις αληθινές πληροφορίες από τους συμμετέχοντες του συστήματος που πιθανόν να έχουν κίνητρο να δηλώσουν ψευδώς τα ιδιωτικά τους δεδομένα. Θα παρουσιαστούν διάφοροι αλγόριθμοι (μηχανισμοί) που εξαιτίας του σχεδιασμού τους θα δίνουν κίνητρα στους συμμετέχοντες να μας δίνουν τις αληθινές τους πληροφορίες πετυγχαίνοντας παράλληλα μια λύση όσο το δυνατόν πιο κοντά στη βέλτιστη. Πιο συγκεκριμένα θα εξεταστούν υπό αυτό το πρίσμα τα προβλήματα του Ταιριάσματος και του Καλύμματος Κύκλων.