Φυσικές και Αποδοτικές Δυναμικές σε Παίγνια Διαμόρφωσης ́Αποψης μέσω τεχνικών Κυρτής Βελτιστοποίησης

Abstract

H παρούσα διδακτορική διατριβή μελετά παίγνια, δυναμικά συστήματα και υπολογιστικά προβλήματα που σχετίζονται με τη διαμόρφωση άποψης. Η εργασία αυτή κινείται σε τρείς βασικούς άξονες. Ο πρώτος άξονας αφορά στη μελέτη των ιδιοτήτων σύγκλισης αλγόριθμων επιλογής στρατηγικών σε παίγνια διαμόρφωσης άποψης που εξελίσσονται στο χρόνο. Εξετάζονται εκτενώς οι ιδιότητες σύγκλισης σε ισορροπία Nash όταν η ανανέωση των απόψεων (στρατηγικών) γίνεται βάσει αλγορίθμων best response και no-regret ακόμα και σε περιπτώσεις που οι παίκτες έχουν μερική γνώση των απόψεων (στρατηγικών) των άλλων παικτών. Ο δεύτερος άξονας αφορά στην επέκταση των άνω φραγμάτων για το Τίμημα της Αναρχίας σε παίγνια διαμόρφωσης άποψης όταν οι απόψεις κάποιων παικτών μπορεί να δουν απωθητικά για τις απόψεις άλλων παικτών. Αποδεικνύεται ότι το Τίμημα της Αναρχίας φράσσεται από μία καθολική σταθερά που δεν εξαρτάται από τον αριθμό των παικτών. Στον τρίτο άξονα της εργασίας, εξετάζεται μία δυναμική εκδοχή του προβλήματος k-median στην οποία οι θέσεις των πελατών βρίσκονται στην ευθεία και εξελίσσονται στον χρόνο. Για το πρόβλημα αυτό παρουσιάζεται ένας αλγόριθμος πολυωνυμικού χρόνου ο οποίος στηρίζεται στην επίλυση ενός κατάλληλου γραμμικού προγράμματ