Overlapping coalition formation under uncertainty

Mamakos Michail

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

Search

Browse

My Space

Overlapping coalition formation under uncertainty

Mamakos Michail

Available Files

Services

Export

Share

Statistics

Metadata & Content in a METS Package:

Metadata in Format: