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

Abstract

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

Σε αυτή την εργασία, μελετάμε ένα παιγνιοθεωρητικό μοντέλο διαμόρφωσης άποψης, που ονομάζεται συνεξελικτικά παίγνια διαμόρφωσης άποψης, το οποίο σημαίνει ότι αυτό το μοντέλο προσπαθεί να περιλάβει το ότι οι σχέσεις εξελίσσονται μαζί με τις απόψεις. Αυτά τα παίγνια ανήκουν στην κλάση των κοίλων παιγνίων, συνεπώς έχουν πάντα ισορροπίες Nash. Ο στόχος μας είναι να τις υπολογίσουμε αποδοτικά. Η προσέγγισή μας είναι να χρησιμοποιήσουμε ένα πρόσφατο αποτέλεσμα των Μερτικόπουλου και Zhou, στην τομή της θεωρίας παιγνίων και της κυρτής βελτιστοποίησης, το οποίο, αδρά, εγγυάται γρήγορη σύγκλιση ενός mirror descent αλγορίθμου (Dual Averaging) σε ισορροπία, σε κοίλα παίγνια όπου ισχύει η συνθήκη diagonal strict concavity του Rosen. Συνεπώς, κατά βάση η δική μας εργασία ήταν να αναζητήσουμε ενδιαφέρουσες υποκατηγορίες συνεξελικτικών παιγνίων διαμόρφωσης άποψης στις οποίες να ισχύει αυτή η συνθήκη. Η εργασία μας χωρίζεται σε δύο τμήματα.

Αρχικά, κάποια θεωρητικά αποτελέσματα, όπου δείχνουμε ότι περιορισμένα στιγμιότυπα των παιγνίων αυτών είναι diagonally strictly concave (συγκεκριμένα, όταν η αυτοπεποίθηση / αδράνεια των παικτών είναι επαρκώς μεγάλη).

Κατόπιν, λόγω της αυξημένης δυσκολίας στο να εκμαιεύσουμε περαιτέρω θεωρητικά αποτελέσματα, μελετάμε το μοντέλο μέσω προσομοιώσεων. Τρέχοντας τον αλγόριθμο Dual Averaging σε αρκετά στιγμιότυπα συνεξελικτικών παιγνίων διαμόρφωσης άποψης, βλέπουμε ότι έχει πολύ καλή επίδοση, φτάνοντας σε ισορροπία μετά από σχετικά λίγους γύρους. Επίσης, βρίσκουμε κάποια αριθμητικά αντιπαραδείγματα του diagonal strict concavity, αλλά πολύ λίγα. Το οποίο θα μπορούσε να δικαιολογεί το γιατί συναντάμε θεωρητικές δυσκολίες, παρόλο που ο αλγόριθμος δείχνει να αποδίδει πολύ καλά σε τυπικές περιπτώσεις.