Ημερολόγιο Εκδηλώσεων

Περιγραφή:
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών Πρόγραμμα Μεταπτυχιακών Σπουδών ΠΑΡΟΥΣΙΑΣΗ ΜΕΤΑΠΤΥΧΙΑΚΗΣ ΕΡΓΑΣΙΑΣ ΜΙΧΑΗΛ ΜΑΜΑΚΟΥ με θέμα Overlapping Coalition Formation under Uncertainty Υπό Αβεβαιότητα Σχηματισμός Επικαλυπτόμενων Συνασπισμών Εξεταστική Επιτροπή Αναπληρωτής Καθηγητής Γεώργιος Χαλκιαδάκης (επιβλέπων) Αναπληρωτής Καθηγητής Μιχαήλ Λαγουδάκης Επίκουρος Καθηγητής Βασίλης Σαμολαδάς Abstract [προαιρετικά] Research in cooperative games often assumes that agents have complete information regarding the coalitional values, and that they can belong to one coalition only. In this thesis, we remove these unrealistic restrictions, and study various aspects of uncertainty facing agents in coalition formation environments, while allowing them to belong to multiple coalitions simultaneously. We begin by focusing on agent uncertainty regarding the resource contributions of potential partners. To tackle this, we provide three novel methods that obtain probability bounds for assessing the success of teams towards coalitional task completion. Our first method is based on an improvement of the Paley-Zygmund inequality, while the second and the third are devised based on the two-sided Chebyshev’s inequality and the Hoeffding’s inequality, respectively. Our methods allow agents to demand certain confidence levels regarding the resource contribution of coalitions; and agent beliefs are updated in a Bayesian manner, following formation decisions. We then proceed to study situations where agent uncertainty is over the underlying collaboration structure, which determines the values of the (possibly overlapping) coalitions. In this context, we first propose a novel concise representation scheme, termed ”Relational Rules“, which extends the celebrated MC-nets representation to cooperative games with overlapping coalitions. We then present a novel decision-making method for decentralized overlapping coalition formation, which employs, for the first time in the coalition formation literature, “Probabilistic Topic Modeling” (a highly successful unsupervised learning approach). We demonstrate experimentally that by interpreting formed coalitions as documents, agents using our approach are able to effectively and efficiently learn profitable collaboration patterns (or “topics”). Περίληψη Στα συνεργατικά παίγνια συχνά γίνεται η υπόθεση ότι οι πράκτορες έχουν πλήρη γνώση της χρησιμότητας που αποφέρει ο σχηματισμός των συνασπισμών, και ότι ο καθένας μπορεί να συμμετέχει μόνο σε ένα συνασπισμό. Στην παρούσα μεταπτυχιακή εργασία, αφαιρούμε αυτούς τους περιορισμούς, οι οποίοι συχνά δε συνάδουν με τα πραγματικά περιβάλλοντα. Ως εκ τούτου, μελετάμε διάφορες πηγές αβεβαιότητας με τις οποίες έρχονται αντιμέτωποι οι πράκτορες σε συνεργατικά περιβάλλοντα, ενώ τους επιτρέπουμε να συμμετέχουν σε πολλούς συνασπισμούς ταυτόχρονα. Αρχικά εστιάζουμε στα προβλήματα που αντιμετωπίζουν οι πράκτορες σχετικά με την αβεβαιότητα που προέρχεται από τη συνεισφορά των εν δυνάμει συνεργατών τους. Για την αντιμετώπιση αυτού του προβλήματος αναπτύσσουμε τρεις μεθόδους οι οποίες βασίζονται στον υπολογισμό φραγμάτων πιθανοτήτων για την εκτίμηση της ικανότητας ομάδων πρακτόρων να πραγματοποιήσουν μία εργασία. Η πρώτη μέθοδος βασίζεται σε μία βελτίωση της ανισότητας Paley-Zygmund, ενώ η δεύτερη και η τρίτη βασίζονται στη διμερή ανισότητα του Chebyshev και την ανισότητα του Hoeffding, αντίστοιχα. Οι μέθοδοί μας επιτρέπουν στους πράκτορες να απαιτούν επίπεδα εμπιστοσύνης της επιλογής τους σχετικά με τη συνεισφορά πόρων των συνασπισμών. Οι πράκτορές μας διατηρούν Μπαεσιανές πεποιθήσεις, που ανανεώνονται μετά από κάθε σχηματισμό συνασπισμών. Έπειτα, μελετάμε καταστάσεις στις οποίες οι πράκτορες έχουν αβεβαιότητα σχετικά με την υποκείμενη συνεργατική δομή, βάση της οποίας καθορίζονται τα κέρδη των (πιθανώς επικαλυπτόμενων) συνασπισμών. Έτσι, αρχικά προτείνουμε ένα καινοφανές σχήμα συνοπτικής αναπαράστασης, το οποίο ονομάζουμε "Relational Rules", και το οποίο επεκτείνει την εξαιρετικά γνωστή αναπαραστάση "MC-nets" σε συνεργατικά παίγνια με επικαλυπτόμενους συνασπισμούς. Στη συνέχεια παρουσιάζουμε μία νέα μέθοδο λήψης αποφάσεων για αποκεντροποιήμενο σχηματισμό επικαλυπτόμενων συνασπισμών, η οποία χρησιμοποιεί, για πρώτη φορά στη βιβλιογραφία της δημιουργίας συνασπισμών, μια επιτυχημένη προσέγγιση μή επιβλεπόμενης μηχανικής μάθησης "Probabilistic Topic Modeling" ("Πιθανοτικής Θεματικής Μοντελοποίησης"). Τα πειράματά μας δεικνύουν ότι οι πράκτορες, ερμηνεύοντας τους συνασπισμούς ως έγγραφα, μπορούν αποτελεσματικά να μάθουν επικερδή πρότυπα συνεργασίας (ή "topics") με αποδοτικό τρόπο.