Υπολογισμός και Σύγκλιση σε Σημεία Ισορροπίας σε Συνεξελικτικά Παίγνια Διαμόρφωσης Άποψης

Abstract

Τα παίγνια διαμόρφωσης άποψης μοντελοποιούν την διαδικασία με την οποία οι άνθρωποι ανταλλάσσουν και διαμορφώνουν απόψεις. Αναλυτικότερα, περιγράφουν τα κοινωνικά σύνολα χρησιμοποιώντας δίκτυα, όπου οι κόμβοι είναι οι άνθρωποι και οι ακμές οι σχέσεις μεταξύ τους και υποθέτουν ότι οι άνθρωποι εκφράζουν ως άποψη ένα σταθμισμένο μέσο όρο των απόψεων των ατόμων με τα οποία έρχονται σε επαφή. Τα συνεξελικτικά παίγνια διαμόρφωσης άποψης συμπεριλαμβάνουν το γεγονός ότι οι σχέσεις μεταξύ των ανθρώπων διαμορφώνονται ταυτόχρονα με τις απόψεις τους.

Σε αυτή τη διπλωματική εργασία ασχολούμαστε με τον υπολογισμό σημείων ισορροπίας σε συνεξελικτικά παίγνια διαμόρφωσης άποψης. Πιο συγκεκριμένα, τα παίγνια που μελετάμε αποτελούν γενίκευση του μοντέλου Friedkin Johnsen στην οποία τα βάρη μεταξύ των παικτών είναι συνάρτηση των απόψεων που εκφράζουν και έχουν πάντα σημείο ισορροπίας γιατί είναι concave n-person games. Ως προς τη σύγκλιση μελετάμε δύο φυσικές δυναμικές, το best response και το follow the leader. Αρχικά, δείχνουμε ότι κάποια στιγμιότυπα τέτοιων παιγνίων μπορεί να έχουν πολλά σημεία ισορροπίας και σε τέτοιες περιπτώσεις το best response δεν συγκλίνει καθολικά. Επίσης, αποδεικνύουμε ότι για συναρτήσεις βαρών που δεν είναι διαφορίσιμες μπορεί το best response να μη συγκλίνει και τοπικά. Στη συνέχεια, χρησιμοποιώντας μία συνάρτηση δυναμικού, δείχνουμε ότι στα concave n-person games των οποίων οι συναρτήσεις κέρδους είναι diagonally strictly concave υπάρχει αλγόριθμος που συγκλίνει στο μοναδικό σημείο ισορροπίας. Στην περίπτωση των συνεξελικτικών παιγνίων διαμόρφωσης άποψης παρατηρούμε ότι αυτός ο αλγόριθμος είναι ισοδύναμος με το follow the leader, το οποίο επίσης δείχνουμε ότι εξασφαλίζει no-regret στους παίκτες που το ακολουθούν.