Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/D53C57E6-8DB1-40FD-9BBA-CAAB852FFC40 | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.83197 | - |
| Language | en | - |
| Extent | 90 pages | en |
| Title | Collaboration pattern detection in hedonic cooperative games with externalities | en |
| Title | Ανίχνευση μοτίβων συνεργειών σε ηδονικά συνεργατικά παίγνια με εξωτερικές επιδράσεις | el |
| Creator | Troullinos Dimitrios | en |
| Creator | Τρουλλινος Δημητριος | el |
| Contributor [Thesis Supervisor] | Chalkiadakis Georgios | en |
| Contributor [Thesis Supervisor] | Χαλκιαδακης Γεωργιος | el |
| Contributor [Committee Member] | Lagoudakis Michail | 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 | Cooperative games model the formation of coalitions of rational agents that come together to gain some form of utility which they would have otherwise been unable to collect by acting alone. Hedonic games, then, constitute the class of cooperative games that models agents with hedonic preferences, that is, agents who have preferences over their very coalitional membership, i.e. the identities of others in their coalition. Thus, an agent’s utility in such settings mirrors the satisfaction yielded from its assembled coalition. Now, cooperative games with externalities, or in partition function form, consider that agent utility is influenced by the partition of the agents space, i.e., the set of all disjoint coalitions currently in place. Existing studies, however, have not so far addressed hedonic games with externalities. At the same time, uncertainty is prevalent in most realistic cooperative game environments, and hence intra-agent collaboration under uncertainty is a topic widely studied. However, uncertainty in hedonic game settings has received only limited attention in the literature to date. Against this background, in this diploma thesis we first extend the formal definition of two well-known classes of hedonic games, namely additively separable hedonic games and boolean hedonic games, to partition function form. Then, we combine the aforementioned paradigms, and focus on agents in hedonic games with externalities who are unaware of their own preferences over partitions. We demonstrate how to extract these hidden preferences by employing well-established supervised learning methods—namely linear regression, linear regression with basis functions, and feed forward neural networks—and adapting them to the problem at hand. In the process, we make use of an evaluation metric specifically designed to evaluate the prediction accuracy of machine learning methods used to infer the underlying hedonic preferences over partitions. In addition, we show how an agent can use Gaussian mixture models to generate sets of potentially satisfactory partitions to propose in multi-agent negotiations. Finally, we put forward two novel coalition formation protocols that engage agents with hidden and conflicting preferences; and which are designed with the aim of maximizing social welfare, without the presence of a centralized entity or the ability to share information among agents. | en |
| Content Summary | Τα συνεργατικά παίγνια μοντελοποιούν την δημιουργία συνασπισμών από ορθολογικούς πράκτορες, οι οποίοι ενώνουν τις δυνάμεις τους για να απολαύσουν κάποιας μορφής ωφέλεια, η οποία θα ήταν αδύνατον να αποκομιστεί με ατομική δράση. Τα ηδονικά παίγνια, από την άλλη, είναι μια κατηγορία συνεργατικών παιγνίων που μοντελοποιεί πράκτορες με ηδονικές προτιμήσεις, δηλαδή πράκτορες που έχουν προτιμήσεις σχετικά με την ταυτότητα των υπόλοιπων στο συνασπισμό τους. Ουσιαστικά λοιπόν, οι απολαβές ενός πράκτορα σε τέτοια περιβάλλοντα αντικατοπτρίζουν την ικανοποίηση που αποκομίζει από τον σχηματισμένο συνασπισμό του. Τώρα, τα συνεργατικά παίγνια με εξωτερικές επιδράσεις ή σε μορφή συνάρτησης διαμέρισης θεωρούν ότι οι απολαβές επηρεάζονται από τη διαμέριση του χώρου των πρακτόρων, δηλαδή το ποιό είναι το σύνολο των ήδη σχηματισμένων συνασπισμών. Μέχρι σήμερα, δεν υπάρχουν εργασίες που να έχουν εξετάσει ηδονικά παίγνια με εξωτερικές επιδράσεις. Την ίδια στιγμή, η αβεβαιότητα σε περιβάλλοντα μπορεί να παρατηρηθεί σε πολλά ρεαλιστικά περιβάλλοντα συνεργατικών παιγνίων, και ως εκ τούτου η συνεργασία μεταξύ πρακτόρων υπό αβεβαιότητα είναι ένα θέμα που έχει μελετηθεί ευρέως. Υπό το πρίσμα αυτό, στην παρούσα Διπλωματική Εργασία αρχικά επεκτείνουμε τον τυπικό ορισμό δύο πολύ γνωστών κλάσεων ηδονικών παιγνίων, συγκεκριμένα των additively separable hedonic games και των boolean hedonic games, σε μορφή συνάρτησης διαμέρισης. Κατόπιν, συνδυάζουμε τις προαναφερθείσες ιδέες και εστιάζουμε σε πράκτορες σε ηδονικά παιχνίδια με εξωτερικές επιδράσεις που δεν έχουν επίγνωση των ίδιων προτιμήσεων. Δεικνύουμε πώς να αποσπάσουμε αυτές τις κρυφές προτιμήσεις, χρησιμοποιώντας καθιερωμένες μεθόδους επιβλεπόμενης εκμάθησης—και συγκεκριμένα γραμμική παλινδρόμηση, γραμμική παλινδρόμηση με συναρτήσεις βάσης, και προωθητικά νευρωνικά δίκτυα—αφού τις προσαρμόσουμε στο τρέχον πρόβλημα. Επιπλέον, αξιοποιούμε μια μετρική ειδικά σχεδιασμένη για την αξιολόγηση της απόδοσης μεθόδων μηχανικής μάθησης που προσπαθούν να εκμαιεύσουν τις υποβόσκουσες ηδονικές προτιμήσεις σχετικά με διαμερίσεις. Στη συνέχεια, εξοπλίζουμε τους πράκτορες με την ικανότητα να δημιουργούν νέες εν δυνάμει ικανοποιητικές για αυτούς διαμερίσεις με χρήση μίξης Γκαουσιανών μοντέλων, με στόχο την πρόταση διαμερίσεων σε διαπραγματεύσεις πολλαπλών πρακτόρων. Τέλος, προτείνουμε δύο καινοφανή πρωτόκολλα σχηματισμού συνασπισμών, που εμπλέκουν πολλαπλούς πράκτορες με κρυφές και συγκρουόμενες προτιμήσεις, και τα οποία επιχειρούν να μεγιστοποιήσουν την κοινωνική ευημερία, χωρίς την παρουσία μιας κεντρικής οντότητας. | el |
| Type of Item | Διπλωματική Εργασία | el |
| Type of Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2019-09-17 | - |
| Date of Publication | 2019 | - |
| Subject | Machine learning | en |
| Subject | Unsupervised learning | en |
| Subject | Supervised learning | en |
| Subject | Hedonic games in partition function form | en |
| Subject | Hedonic games | en |
| Subject | Cooperative games | en |
| Bibliographic Citation | Dimitrios Troullinos, "Collaboration pattern detection in hedonic cooperative games with externalities", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2019 | en |
| Bibliographic Citation | Δημήτριος Τρουλλινός, "Ανίχνευση μοτίβων συνεργειών σε ηδονικά συνεργατικά παίγνια με εξωτερικές επιδράσεις", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2019 | el |
Copyright © DIAS 2013
