Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/D53C57E6-8DB1-40FD-9BBA-CAAB852FFC40 | - |
| Αναγνωριστικό | https://doi.org/10.26233/heallink.tuc.83197 | - |
| Γλώσσα | en | - |
| Μέγεθος | 90 pages | en |
| Τίτλος | Collaboration pattern detection in hedonic cooperative games with externalities | en |
| Τίτλος | Ανίχνευση μοτίβων συνεργειών σε ηδονικά συνεργατικά παίγνια με εξωτερικές επιδράσεις | el |
| Δημιουργός | Troullinos Dimitrios | en |
| Δημιουργός | Τρουλλινος Δημητριος | el |
| Συντελεστής [Επιβλέπων Καθηγητής] | Chalkiadakis Georgios | en |
| Συντελεστής [Επιβλέπων Καθηγητής] | Χαλκιαδακης Γεωργιος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Lagoudakis Michail | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Λαγουδακης Μιχαηλ | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Samoladas Vasilis | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Σαμολαδας Βασιλης | el |
| Εκδότης | Πολυτεχνείο Κρήτης | el |
| Εκδότης | Technical University of Crete | en |
| Ακαδημαϊκή Μονάδα | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Ακαδημαϊκή Μονάδα | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Περίληψη | 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 |
| Περίληψη | Τα συνεργατικά παίγνια μοντελοποιούν την δημιουργία συνασπισμών από ορθολογικούς πράκτορες, οι οποίοι ενώνουν τις δυνάμεις τους για να απολαύσουν κάποιας μορφής ωφέλεια, η οποία θα ήταν αδύνατον να αποκομιστεί με ατομική δράση. Τα ηδονικά παίγνια, από την άλλη, είναι μια κατηγορία συνεργατικών παιγνίων που μοντελοποιεί πράκτορες με ηδονικές προτιμήσεις, δηλαδή πράκτορες που έχουν προτιμήσεις σχετικά με την ταυτότητα των υπόλοιπων στο συνασπισμό τους. Ουσιαστικά λοιπόν, οι απολαβές ενός πράκτορα σε τέτοια περιβάλλοντα αντικατοπτρίζουν την ικανοποίηση που αποκομίζει από τον σχηματισμένο συνασπισμό του. Τώρα, τα συνεργατικά παίγνια με εξωτερικές επιδράσεις ή σε μορφή συνάρτησης διαμέρισης θεωρούν ότι οι απολαβές επηρεάζονται από τη διαμέριση του χώρου των πρακτόρων, δηλαδή το ποιό είναι το σύνολο των ήδη σχηματισμένων συνασπισμών. Μέχρι σήμερα, δεν υπάρχουν εργασίες που να έχουν εξετάσει ηδονικά παίγνια με εξωτερικές επιδράσεις. Την ίδια στιγμή, η αβεβαιότητα σε περιβάλλοντα μπορεί να παρατηρηθεί σε πολλά ρεαλιστικά περιβάλλοντα συνεργατικών παιγνίων, και ως εκ τούτου η συνεργασία μεταξύ πρακτόρων υπό αβεβαιότητα είναι ένα θέμα που έχει μελετηθεί ευρέως. Υπό το πρίσμα αυτό, στην παρούσα Διπλωματική Εργασία αρχικά επεκτείνουμε τον τυπικό ορισμό δύο πολύ γνωστών κλάσεων ηδονικών παιγνίων, συγκεκριμένα των additively separable hedonic games και των boolean hedonic games, σε μορφή συνάρτησης διαμέρισης. Κατόπιν, συνδυάζουμε τις προαναφερθείσες ιδέες και εστιάζουμε σε πράκτορες σε ηδονικά παιχνίδια με εξωτερικές επιδράσεις που δεν έχουν επίγνωση των ίδιων προτιμήσεων. Δεικνύουμε πώς να αποσπάσουμε αυτές τις κρυφές προτιμήσεις, χρησιμοποιώντας καθιερωμένες μεθόδους επιβλεπόμενης εκμάθησης—και συγκεκριμένα γραμμική παλινδρόμηση, γραμμική παλινδρόμηση με συναρτήσεις βάσης, και προωθητικά νευρωνικά δίκτυα—αφού τις προσαρμόσουμε στο τρέχον πρόβλημα. Επιπλέον, αξιοποιούμε μια μετρική ειδικά σχεδιασμένη για την αξιολόγηση της απόδοσης μεθόδων μηχανικής μάθησης που προσπαθούν να εκμαιεύσουν τις υποβόσκουσες ηδονικές προτιμήσεις σχετικά με διαμερίσεις. Στη συνέχεια, εξοπλίζουμε τους πράκτορες με την ικανότητα να δημιουργούν νέες εν δυνάμει ικανοποιητικές για αυτούς διαμερίσεις με χρήση μίξης Γκαουσιανών μοντέλων, με στόχο την πρόταση διαμερίσεων σε διαπραγματεύσεις πολλαπλών πρακτόρων. Τέλος, προτείνουμε δύο καινοφανή πρωτόκολλα σχηματισμού συνασπισμών, που εμπλέκουν πολλαπλούς πράκτορες με κρυφές και συγκρουόμενες προτιμήσεις, και τα οποία επιχειρούν να μεγιστοποιήσουν την κοινωνική ευημερία, χωρίς την παρουσία μιας κεντρικής οντότητας. | el |
| Τύπος | Διπλωματική Εργασία | el |
| Τύπος | Diploma Work | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2019-09-17 | - |
| Ημερομηνία Δημοσίευσης | 2019 | - |
| Θεματική Κατηγορία | Machine learning | en |
| Θεματική Κατηγορία | Unsupervised learning | en |
| Θεματική Κατηγορία | Supervised learning | en |
| Θεματική Κατηγορία | Hedonic games in partition function form | en |
| Θεματική Κατηγορία | Hedonic games | en |
| Θεματική Κατηγορία | Cooperative games | en |
| Βιβλιογραφική Αναφορά | 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 |
| Βιβλιογραφική Αναφορά | Δημήτριος Τρουλλινός, "Ανίχνευση μοτίβων συνεργειών σε ηδονικά συνεργατικά παίγνια με εξωτερικές επιδράσεις", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2019 | el |
Copyright © DIAS 2013
