Σχεδιασμός Μηχανισμών, Κοινωνική Επιλογή και Υπολογισμός Ισορροπιών σε Περιορισμένα Πεδία (Mechanism Design, Social Choice and Equilibrium Computation in Restricted Domains)

Abstract

Η παρούσα διδακτορική διατριβή μελετάει αποδοτικά αλγοριθμικά πλαίσια για περιβάλλοντα στα οποία η πληροφορία δεν είναι άμεσα διαθέσιμη. Πιο συγκεκριμένα μελετάει περιορισμούς στην πρόσβαση στην πληροφορία από τρεις διαφορετικές γωνίες: (1) Η πληροφορία είναι προσωπική (και ιδιωτική) σε στρατηγικούς παίκτες και χρειάζεται να αποκαλυφθεί στον αλγόριθμο μέσα από κατάλληλα σχεδιασμένα κίνητρα: Αυτή η περιοχή συνήθως αναφέρεται ως «αλγοριθμικός σχεδιασμός μηχανισμών». Η έρευνα στα πλαίσια της διατριβής επικεντρώνεται στην αντιμετώπιση ισχυρών αρνητικών αποτελεσμάτων περιορίζοντας την ανάλυση σε «φυσιολογικά» υποσύνολα στιγμιότυπων του προβλήματος, μια πρακτική από την περιοχή της ανάλυσης πέραν της χειρότερης περίπτωσης στη θεωρία αλγορίθμων. Συγκεκριμένα, αναλύεται η προσεγγισιμότητα του προβλήματος χωροθέτησης εγκαταστάσεων από φιλαλήθεις μηχανισμούς. (2) Η επικοινωνία είναι ακριβή: Μελετώντας αυτόν τον περιορισμό σε περιβάλλοντα με στρατηγικούς παίκτες αποδεικνύεται ότι απλοί μηχανισμοί για κλασσικά προβλήματα μπορούν να υλοποιηθούν με ασυμπτωτικά βέλτιστη πολυπλοκότητα επικοινωνίας (ανάμεσα στον μηχανισμό και τους παίκτες). (3) Η πληροφορία που χρησιμοποιείται από τον μηχανισμό είναι περιορισμένη: η διατριβή εστιάζει στην παραμόρφωση στο πρόβλημα της ψηφοφορίας, που είναι η έννοια που ποσοτικοποιεί την επίπτωση της πρόσβασης σε περιορισμένη πληροφορία στην κοινωνική ωφέλεια του αποτελέσματος ενός αλγορίθμου (σε όρους προσέγγισης της βέλτιστης λύσης). Εδώ μελετώνται και οι επιπτώσεις διάφορων μορφών περιορισμένης πληροφορίας στην μετρική παραμόρφωση αλλά και η παραμόρφωση ενός πολύ διαδεδομένου μηχανισμού, του STV, σε σχέση με την διαστασιμότητα του σχετικού μετρικού χώρου. Επιπλέον, στα πλαίσια της διατριβής διερευνάται η κλασική πτυχή της αλγοριθμικής θεωρίας παιγνίων που αφορά την πολυπλοκότητα υπολογισμού αμιγών ισορροπιών. Μελετάται το πρόβλημα αυτό στο πλαίσιο των βεβαρυμένων παιγνίων συμφόρησης με γραμμικές συναρτήσεις καθυστέρησης, και παρουσιάζεται ένας αποδοτικός αλγόριθμος για τον υπολογισμό προσεγγιστικών ισορροπιών σε μια ενδιαφέρουσα κλάση των Max-Cut παιγνίων.