Ανάπτυξη Αλγορίθμου Εύρεσης Ισορροπίας Nash σε πολυπρακτορικό σύστημα με χρήση δειγμάτων από γείτονες

Abstract

Η θεωρία παιγνίων βρίσκει όλο και μεγαλύτερη εφαρμογή σε πολυπρακτορικά συστήματα, στα οποία το σύνολο δράσεων (στρατηγική) κάθε πράκτορα διαμορφώνει την επιμέρους συνάρτηση κόστους του, άρα και το κατά πόσο είναι επωφελής ή επιζήμια η κατάσταση στην οποία αυτός βρίσκεται μέσα στο σύστημα. Στο πλαίσιο αυτό κρίνεται ιδαίτερα σημαντική η αναζήτηση ισορροπίας Nash, δηλαδή η επίτευξη μιας συμβιβαστικής συνθήκης κατά την οποία κανένας πράκτορας δεν έχει όφελος να διαφοροποιηθεί μονομερώς. Αντικείμενο μελέτης της παρούσας διπλωματικής εργασίας είναι η αναζήτηση ισορροπίας Nash σε στατικά παίγνια με διαχωρίσιμους συζευγμένους περιορισμούς για τα σύνολα δράσεων των πρακτόρων. Ειδικότερα, εξετάζονται πολυπρακτορικά συστήματα με συνεχώς διαφορίσιμες, αυστηρά κυρτές και ακτινικά μη φραγμένες συναρτήσεις κόστους και γραμμικές συναρτήσεις περιορισμών. Θεωρούμε τον γράφο γειτνίασης που σχηματίζουν οι πράκτο- ρες και αναπτύσσουμε αλγόριθμο εύρεσης Ισορροπίας Nash με ανταλλαγή δειγμάτων μεταξύ γειτνιαζόντων πρακτόρων. Για την απόδειξη της σύγκλισης τέτοιου τύπου συστημάτων σε ισορροπία Nash επιστρατεύεται η ανάλυση Lyapunov, προσαρμοσμένη σε εξισώσεις κατάστασης που συνδυάζουν τον συνεχή χρόνο με δείγματα. Τέλος, η λειτουργία του προτεινόμενου αλγορίθμου επιβεβαιώνεται μέσω αριθμητικής προσομοίωσης για ένα σύστημα πέντε πρακτόρων και συγκρίνεται με τη διακριτοποιημένη λειτουργία του αντίστοιχου αλγορίθμου συνεχούς χρόνου.