Game theory and dynamic mechanisms on graphs
Authors: Λαγός Αθανάσιος-Ραφαήλ 
Published: January 2023

Σε αυτή τη διατριβή, μελετώνται εφαρμογές μεθόδων της θεωρίας παιγνίων και του αυτομάτου ελέγχου σε προβλήματα που ανακύπτουν σε αποκεντρωμένα διασυνδεδεμένα συστήματα. Συγκεκριμένα, εξετάζονται τρεις εφαρμογές. Η πρώτη εφαρμογή αφορά στην διάδοση απόψεων και τη χειραγώγηση σε κοινωνικά δίκτυα. Η δεύτερη σχετίζεται με την αυθόρμητη ανταπόκριση ενός πληθυσμού στο ξέσπασμα μιας επιδημίας μέσω της εφαρμογής κοινωνικής αποστασιοποίησης. Στην τρίτη εφαρμογή εισάγεται ένα πρωτόκολλο στοχαστικής συνεννόησης (consensus) για τον συντονισμό πρακτόρων με δυναμική υψηλής τάξης σε πεπερασμένο χρόνο. Σε αυτές τις τρεις εφαρμογές, η δομή του συστήματος είναι διασυνδεδεμένη, οι πράκτορες διαθέτουν κάποιο είδος νοημοσύνης και ενεργούν με αποκεντρωμένο τρόπο. Έτσι, είτε προκύπτουν καταστάσεις παιγνίου και μελετώνται τα σημεία ισορροπίας είτε απαιτούνται αποκεντρωμένα πρωτόκολλα ελέγχου για την επίτευξη κάποιου συλλογικού στόχου.Στην πρώτη εφαρμογή, μια διαδικασία κοινωνικής επιλογής μοντελοποιείται ως παίγνιο Nash μεταξύ των πρακτόρων. Οι παίκτες επικοινωνούν μεταξύ τους μέσω ενός δικτύου επικοινωνίας, π.χ., ενός κοινωνικού δικτύου, μοντελοποιημένου από ένα μη κατευθυνόμενο γράφο και οι απόψεις τους έχουν δυναμικές που μοντελοποιούν το φαινόμενο της σύγκλισης λόγω συμμόρφωσης προς τις απόψεις των γειτόνων. Τα κριτήρια των παικτών για αυτό το παίγνιο εκφράζουν την διελκυστίνδα της επιλογής μεταξύ αυτοσυνεπών και χειραγωγητικών συμπεριφορών. Οι βέλτιστες αποκρίσεις τους καταλήγουν σε έναν δυναμικό κανόνα για τις ενέργειές τους. Μελετάται η ευστάθεια αυτών των δυναμικών. Στην περίπτωση της αστάθειας, η οποία προκύπτει όταν οι παίκτες είναι εξαιρετικά χειραγωγητικοί, η σταθεροποίηση αυτής της δυναμικής μέσω του σχεδιασμού της τοπολογίας του δικτύου διατυπώνεται ως ένα πρόβλημα ακέραιου προγραμματισμού. Οι περιορισμοί έχουν τη μορφή Διγραμμικής Ανισότητας Πινάκων (BMI), η οποία είναι γνωστό ότι οδηγεί σε ένα μη κυρτό σύνολο εφικτών λύσεων, στη γενική περίπτωση. Για την αντιμετώπιση αυτού του προβλήματος προτείνεται ένας γενετικός αλγόριθμος, ο οποίος χρησιμοποιεί λογισμικό επίλυσης Γραμμικών Ανισοτήτων Πίνακων (LMI) κατά τη διαδικασία επιλογής της επόμενης γενιάς.Η δεύτερη εφαρμογή ασχολείται με την επιλογή ενός πληθυσμού να εφαρμόσει κοινωνική αποστασιοποίηση, η οποία διατυπώνεται ως παίγνιο Nash, όπου οι παίκτες καθορίζουν τις κοινωνικές τους αλληλεπιδράσεις. Οι διασυνδέσεις μεταξύ των παικτών μοντελοποιούνται από ένα γράφο που περιγράφει το δίκτυο των κοινωνικών τους επαφών. Η πληροφορία που είναι διαθέσιμη στους παίκτες έχει κρίσιμο ρόλο στο παίγνιο αυτό. Εξετάζονται δύο σενάρια διαθέσιμης πληροφορίας, η περίπτωση που οι παίκτες γνωρίζουν ακριβώς την κατάσταση της υγείας των γειτόνων τους και η περίπτωση που διαθέτουν μόνο στατιστική πληροφορία για την συνολική διάδοση της επιδημίας. Οι παίκτες θεωρούνται μυωπικοί και έτσι μελετώνται οι ισορροπίες Nash των στατικών παιγνίων που προκύπτουν για κάθε ημέρα. Οι ισορροπίες Nash χαρακτηρίζονται και εισάγονται αλγόριθμοι για τον υπολογισμό τους. Επιπλέον, μέσω προσομοιώσεων εξετάζονται οι επιπτώσεις της δομής του δικτύου, της μεταδοτικότητα του ιού, του αριθμού των ευάλωτων παικτών, των δυνατοτήτων του συστήματος υγειονομικής περίθαλψης και της ποιότητας των πληροφοριών (fake news).Στην τρίτη εφαρμογή εισάγεται και αναλύεται ένα νέο στοχαστικό πρωτόκολλο συνενόησης, που βασίζεται στη στοχαστική μίξη της ελάχιστης και της μέγιστης τιμής των γειτόνων κάθε πράκτορα. Η στοχαστική μίξη και η χαμηλή υπολογιστική προσπάθεια καθιστούν αυτό το πρωτόκολλο κατάλληλο για ασφαλή συναίνεση σε κυβερνοφυσικά (cyberphysical) συστήματα, που αποτελούνται από αυτόνομους πράκτορες με περιορισμένους πόρους. Αποδεικνύεται ότι το πρωτόκολλο συγκλίνει σχεδόν σίγουρα σε πεπερασμένο χρόνο. Επιπλέον, εξετάζεται η εφαρμογή του πρωτοκόλλου στοχαστικής συνενόησης σε συνδυασμό με έναν νόμο ελέγχου πεπερασμένου χρόνου σε ένα κατανεμημένο σύστημα πρακτόρων με δυναμική υψηλής τάξης και αποδεικνύεται ότι οι καταστάσεις των πρακτόρων συγκλίνουν σε πεπερασμένο χρόνο. Τέλος, παρουσιάζονται προσομοιώσεις που δείχνουν την αποτελεσματικότητα αυτού του αποκεντρωμένου σχήματος ελέγχου πεπερασμένου χρόνου σε πράκτορες με δυναμικές διπλού ολοκληρωτή.