Συντάχθηκε 08-12-2020 09:19
Ενημερώθηκε:
08-12-2020 16:14
Τόπος: Η παρουσίαση θα γίνει με τηλεδιάσκεψη
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 10/12/2020 09:00
Λήξη: 10/12/2020 10:00
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΕΡΡΙΚΟΣ ΣΤΡΕΒΙΝΙΩΤΗΣ
θέμα
Επέκταση της Mc-nets Αναπαράστασης Συνεργατικών Παιγνίων σε Περιβάλλοντα με Αβεβαιότητα ή Επικαλύψεις
Extending the MC-nets representation scheme to cooperative game settings with uncertainty or overlaps
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Γεώργιος Χαλκιαδάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Μιχαήλ Λαγουδάκης
Αναπληρωτής Καθηγητής Βασίλειος Σαμολαδάς
Περίληψη
Η συνεργατική θεωρία παιγνίων μελετά πως ορθολογικοί πράκτορες αλληλεπιδρούν μεταξύ τους προκειμένου να δημιουργήσουν συνασπισμούς ώστε συνεργαζόμενοι να πετύχουν κάποιο κοινό στόχο, ενώ παράλληλα μεγιστοποιούν τις ατομικές τους απολαβές. Η αποδοτική αναπαράσταση των συνεργασιών στα πλαίσια ενός συνασπισμού, είναι σημαντική για την υποστήριξη λήψης αποφάσεων σχετικά με τη δημιουργία των συνασπισμών, και γενικότερα για την επίτευξη υπολογισμών σε συνεργατικά παίγνια. Επιπλέον, στην σχετική με συνεργατικά παίγνια έρευνα, χρησιμοποιούνται συχνά οι παραδοχές ότι δεν υπάρχει αβεβαιότητα στις ρυθμίσεις του παιχνιδιού ή/και ότι οι πράκτορες δεν μπορούν να συμμετέχουν σε πολλούς συνασπισμούς ταυτόχρονα.
Στην παρούσα διπλωματική εργασία, επικεντρωνόμαστε σε ένα από τα πλέον γνωστά σχήματα αναπαράστασης συνεργατικών παιγνίων, την αναπαράσταση MC-nets, και το επεκτείνουμε ώστε να αφαιρέσουμε τις προαναφερθείσες μη-ρεαλιστικές παραδοχές (δηλαδή, αυτή της πλήρους πληροφόρησης και της μη ύπαρξης επικαλύψεων).
Η πρώτη μας συνεισφορά συνίσταται στην επέκταση της αναπαράστασης Relational Rules, ενός πρόσφατα διατυπωμένου σχήματος αναπαράστασης που επέκτεινε εν μέρει τα MC-nets σε συνεργατικά παίγνια με επικαλυπτόμενους συνασπισμούς χρησιμοποιώντας λογικές προτάσεις με θετικά μόνο λεκτικά. Η προτεινόμενη στην παρούσα διπλωματική επέκταση, κατορθώνει να επεκτείνει πλήρως τα MC-nets, χρησιμοποιώντας για την αναπαράσταση συνεργασιών λογικές προτάσεις που μπορεί να περιλαμβάνουν τόσο θετικά όσο και αρνητικά λεκτικά. H προτεινόμενη αναπαράσταση, αντιστοιχεί επακριβώς στην κλασική MC-nets αναπαράσταση σε περιβάλλοντα με μη επικαλυπτόμενους συνασπισμούς.
Στη συνέχεια, προτείνουμε ένα νέο, περιεκτικό σχήμα αναπαράστασης για συνεργατικά παίγνια με αβεβαιότητα, το οποίο καλούμε ε-MC nets. Η προτεινόμενη αναπαράσταση ορίζεται αρχικά στο πλαίσιο των παιγνίων με μεταβιβάσιμη αξία (transferable utility), και εκμεταλλεύεται εκτιμήσεις περιθωρίων συνεισφορών πρακτόρων για να σχηματίσει συμπαγείς κανόνες αναπαριστώντας μοτίβα συνεργασίας με ενδεχομένως αβέβαιη αξία.
Πιο συγκεκριμένα, δεδομένου ενός σετ από MC-nets κανόνες που χρησιμοποιούν πρότερες εκτιμήσεις αξίας συνεργασιών, παρέχουμε έναν πολυωνυμικό αλγόριθμο που επιτυγχάνει την προτεινόμενη συμπαγή αναπαράσταση. Επιπροσθέτως, παρέχουμε θεωρητικά αποτελέσματα σχετικά με την απώλεια πληροφορίας (όσον αφορά τις εκλαμβανόμενες αξίες των μοτίβων συνεργασίας πρακτόρων) μετά τη συμπίεση της αρχικής αναπαράστασης για το σετ κανόνων, δείχνοντας ότι φράσσεται από μια τιμή ευθέως ανάλογη με το αποδεκτό περιθώριο απόστασης από την αξία ενός αρχικού MC-net κανόνα.
Κατόπιν, επεκτείνουμε τον αλγόριθμό μας ώστε να εκμεταλλεύεται την ύπαρξη κλάσεων ισοδυναμιών των πρακτόρων. Αυτό μας επιτρέπει να αποκτήσουμε μια ακόμα πιο συμπαγή αναπαράσταση, καθώς και να παράγουμε νέες, προηγουμένως ανύπαρκτες πεποιθήσεις για τις αξίες μη-παρατηρήσιμων μοτίβων συνεργασίας πρακτόρων. Επιπλέον, δεικνύουμε ότι η προσέγγιση μας μπορεί να επεκταθεί και σε συνεργατικά παίγνια με μη μεταβιβάσιμη αξία (non-transferable utility games).
Τέλος, διεξάγουμε μια συστηματική πειραματική αξιολόγηση των παραλλαγών του αλγορίθμου μας, μελετώντας τη συμπεριφορά τους μέσω προσομοιώσεων σε ποικίλα ρεαλιστικά περιβάλλοντα, και παρέχουμε αποτελέσματα σχετικά με την συμπίεση που επιτυγχάνεται σε κάθε περίπτωση. Τα πειραματικά μας αποτελέσματα επιβεβαιώνουν την αποτελεσματικότητα της προσέγγισής μας.
Meeting ID: 863 7735 1353
Password: 011074
