Ο φοιτητής του προγράμματος Βασίλειος Σταμάτης θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Aναποτελεσματικότητα Μηχανισμών Μονομερούς Αντιστοίχησης
την Παρασκευή 20 Σεπτεμβρίου 2024 και ώρα 17:00, μέσω τηλεμετάδοσης (σύνδεσμος: https://centralntua.webex.com/centralntua/j.php?MTID=m3ce8306981a866546b0485adadf0285c).
Σύνοψη Διπλωματικής:
Αυτή η διπλωματική εργασία εξετάζει μηχανισμούς μονομερούς αντιστοίχισης με βάση τις διατακτικές προτιμήσεις παικτών, οι οποίοι κατανέμουν αδιαίρετους πόρους. Επικεντρωνόμαστε σε δύο σημαντικούς μηχανισμούς: τον Random Priority και τον Probabilistic Serial. Ο Random Priority είναι ασφαλής από χειραγώγηση από τους παίκτες (truthful), αλλά συχνά οδηγεί σε υποβέλτιστα δίκαια αποτελέσματα, ενώ ο Probabilistic Serial παράγει δίκαια αποτελέσματα, αλλά είναι ευάλωτος σε χειραγώγηση.
Εξετάζουμε αρκετές έννοιες, όπως την κοινωνική ευημερία, την αποδοτικότητα, την ασφάλεια στην χειραγώγηση και αναλύουμε την απόδοση αυτών των μηχανισμών. Μελετούμε το Approximation Ratio, το οποίο ποσοτικοποιεί πόσο κοντά βρίσκεται το αποτέλεσμα ενός μηχανισμού στην ιδανική λύση από την άποψη της κοινωνικής ευημερίας· το Τίμημα της Αναρχίας (Price of Anarchy), που μετρά πώς η στρατηγική συμπεριφορά των παικτών επηρεάζει την αποδοτικότητα του μηχανισμού· το Incentive Ratio, το οποίο εκφράζει το μέγιστο όφελος που μπορεί να κερδίσει ένας παίκτης με την αλλαγή των προτιμήσεων σε σύγκριση με την αληθινή του αναφορά.
Τέλος, παραθέτουμε πειραματικά αποτελέσματα και συζητούμε μια νέα μετρική, για να εκτιμηθεί πώς η στρατηγική συμπεριφορά των πρακτόρων επηρεάζει το κοινωνικό όφελος του μηχανισμού, σε σχέση με την έκβαση του, αν όλοι έλεγαν την αλήθεια.
Η Επιτροπή,
Δημήτριος Φωτάκης (Επιβλέπων),
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Ε.Μ.Π.
Άρης Φίλος-Ράτσικας,
School of Informatics, University of Edinburgh
Βαγγέλης Μαρκάκης,
Τμήμα Πληροφορικής, Ο.Π.Α