Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/113B541A-9D26-4C5E-BBDD-6E28F09EB58E | - |
| Αναγνωριστικό | https://doi.org/10.26233/heallink.tuc.67719 | - |
| Γλώσσα | en | - |
| Μέγεθος | 95 pages | en |
| Τίτλος | Overlapping coalition formation under uncertainty | en |
| Τίτλος | Υπό αβεβαιότητα σχηματισμός επικαλυπτόμενων συνασπισμών | el |
| Δημιουργός | Mamakos Michail | en |
| Δημιουργός | Μαμακος Μιχαηλ | el |
| Συντελεστής [Επιβλέπων Καθηγητής] | Chalkiadakis Georgios | en |
| Συντελεστής [Επιβλέπων Καθηγητής] | Χαλκιαδακης Γεωργιος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Lagoudakis Michael | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Λαγουδακης Μιχαηλ | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Samoladas Vasilis | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Σαμολαδας Βασιλης | el |
| Εκδότης | Πολυτεχνείο Κρήτης | el |
| Εκδότης | Technical University of Crete | en |
| Ακαδημαϊκή Μονάδα | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Ακαδημαϊκή Μονάδα | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Περίληψη | 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”). | en |
| Περίληψη | Στα συνεργατικά παίγνια συχνά γίνεται η υπόθεση ότι οι πράκτορες έχουν πλήρη γνώση της χρησιμότητας που αποφέρει ο σχηματισμός των συνασπισμών, και ότι ο καθένας μπορεί να συμμετέχει μόνο σε ένα συνασπισμό. Στην παρούσα μεταπτυχιακή εργασία, αφαιρούμε αυτούς τους περιορισμούς, οι οποίοι συχνά δε συνάδουν με τα πραγματικά περιβάλλοντα. Ως εκ τούτου, μελετάμε διάφορες πηγές αβεβαιότητας με τις οποίες έρχονται αντιμέτωποι οι πράκτορες σε συνεργατικά περιβάλλοντα, ενώ τους επιτρέπουμε να συμμετέχουν σε πολλούς συνασπισμούς ταυτόχρονα. Αρχικά εστιάζουμε στα προβλήματα που αντιμετωπίζουν οι πράκτορες σχετικά με την αβεβαιότητα που προέρχεται από τη συνεισφορά των εν δυνάμει συνεργατών τους. Για την αντιμετώπιση αυτού του προβλήματος αναπτύσσουμε τρεις μεθόδους οι οποίες βασίζονται στον υπολογισμό φραγμάτων πιθανοτήτων για την εκτίμηση της ικανότητας ομάδων πρακτόρων να πραγματοποιήσουν μία εργασία. Η πρώτη μέθοδος βασίζεται σε μία βελτίωση της ανισότητας Paley-Zygmund, ενώ η δεύτερη και η τρίτη βασίζονται στη διμερή ανισότητα του Chebyshev και την ανισότητα του Hoeffding, αντίστοιχα. Οι μέθοδοί μας επιτρέπουν στους πράκτορες να απαιτούν επίπεδα εμπιστοσύνης της επιλογής τους σχετικά με τη συνεισφορά πόρων των συνασπισμών. Οι πράκτορές μας διατηρούν Μπαεσιανές πεποιθήσεις, που ανανεώνονται μετά από κάθε σχηματισμό συνασπισμών. Έπειτα, μελετάμε καταστάσεις στις οποίες οι πράκτορες έχουν αβεβαιότητα σχετικά με την υποκείμενη συνεργατική δομή, βάση της οποίας καθορίζονται τα κέρδη των (πιθανώς επικαλυπτόμενων) συνασπισμών. Έτσι, αρχικά προτείνουμε ένα καινοφανές σχήμα συνοπτικής αναπαράστασης, το οποίο ονομάζουμε "Relational Rules", και το οποίο επεκτείνει την εξαιρετικά γνωστή αναπαραστάση "MC-nets" σε συνεργατικά παίγνια με επικαλυπτόμενους συνασπισμούς. Στη συνέχεια παρουσιάζουμε μία νέα μέθοδο λήψης αποφάσεων για αποκεντροποιήμενο σχηματισμό επικαλυπτόμενων συνασπισμών, η οποία χρησιμοποιεί, για πρώτη φορά στη βιβλιογραφία της δημιουργίας συνασπισμών, μια επιτυχημένη προσέγγιση μή επιβλεπόμενης μηχανικής μάθησης "Probabilistic Topic Modeling" ("Πιθανοτικής Θεματικής Μοντελοποίησης"). Τα πειράματά μας δεικνύουν ότι οι πράκτορες, ερμηνεύοντας τους συνασπισμούς ως έγγραφα, μπορούν αποτελεσματικά να μάθουν επικερδή πρότυπα συνεργασίας (ή "topics") με αποδοτικό τρόπο. | el |
| Τύπος | Μεταπτυχιακή Διατριβή | el |
| Τύπος | Master Thesis | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2017-04-04 | - |
| Ημερομηνία Δημοσίευσης | 2017 | - |
| Θεματική Κατηγορία | Multi-agent Systems | en |
| Θεματική Κατηγορία | Coalition formation | en |
| Βιβλιογραφική Αναφορά | Michail Mamakos, "Overlapping coalition formation under uncertainty", Master Thesis, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2017 | en |
| Βιβλιογραφική Αναφορά | Μιχαήλ Μαμάκος, "Υπό αβεβαιότητα σχηματισμός επικαλυπτόμενων συνασπισμών", Μεταπτυχιακή Διατριβή, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2017 | el |
Copyright © DIAS 2013
