Σχεδιασμός Προσεγγιστικών Μηχανισμών χωρίς Χρηματικά Ανταλλάγματα

Το IEEE NTUA Student Branch διοργανώνει ομιλία με θέμα “Σχεδιασμός Προσεγγιστικών Μηχανισμών χωρίς Χρηματικά Ανταλλάγματα” με ομιλητή τον κ.Δημήτρη Φωτάκη, την Τρίτη 28-5-2013, στις 2μ.μ., στο Αμφιθέατρο Πολυμέσων, κάτω από την Κεντρική Βιβλιοθήκη.

 

Θα ξεκινήσουμε με μια σύντομη εισαγωγή στους βασικούς στόχους και σε κάποιες βασικές έννοιες της Αλγοριθμικής Θεωρίας Παιγνίων. Στη συνέχεια, θα εστιάσουμε στο σχεδιασμό προσεγγιστικών μηχανισμών χωρίς χρηματικά ανταλλάγματα για προβλήματα κοινωνικής επιλογής. Το αρνητικό αποτέλεσμα των Gibbard-Satterthwaite αποκλείει την ύπαρξη μη τετριμμένων μηχανισμών που είναι φιλαλήθεις (strategyproof) για την γενική περίπτωση του προβλήματος κοινωνικής επιλογής. Έτσι η τρέχουσα ερευνητική προσπάθεια αφορά σε μηχανισμούς που είναι φιλαλήθεις για συγκεκριμένους χώρους προτιμήσεων και ταυτόχρονα εγγυώνται μια ικανοποιητική προσέγγιση της κοινωνικά βέλτιστης επιλογής. Σε αυτό το πλαίσιο, θα διερευνήσουμε τον καλύτερο λόγο προσέγγισης που μπορεί να επιτευχθεί από ντετερμινιστικούς και πιθανοτικούς φιλαλήθεις μηχανισμούς για το Παίγνιο Επιλογής k Θέσεων (k-Facility Location Game) σε έναν μετρικό χώρο. Θα δούμε ότι οι ντετερμινιστικοί μηχανισμοί δεν αποτελούν αποδεκτή λύση για την επιλογή k >= 3 θέσεων, και θα παρουσιάσουμε κάποιους απλούς και αποδοτικούς πιθανοτικούς μηχανισμούς που είναι φιλαλήθεις για κάθε τιμή του k.

UPDATE!

Παρακάτω μπορείτε να βρείτε την παρουσίαση της ομιλίας όπως πραγματοποιήθηκε από τον κ. Φωτάκη

Presentation 28-5-13