Συντάχθηκε 13-09-2019 09:26
Ενημερώθηκε:
13-09-2019 09:28
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Δημητρίου Τρουλλινού
με θέμα
Ανίχνευση Μοτίβων Συνεργειών σε Ηδονικά Συνεργατικά Παίγνια με Εξωτερικές Επιδράσεις
Collaboration Pattern Detection in Hedonic Cooperative Games with Externalities
Τρίτη 17 Σεπτεμβρίου 2019, 10:30 π.μ.
Αίθουσα 2042, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Γεώργιος Χαλκιαδάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Μιχαήλ Γ. Λαγουδάκης
Αναπληρωτής Καθηγητής Βασίλειος Σαμολαδάς
Περίληψη
Τα συνεργατικά παίγνια μοντελοποιούν την δημιουργία συνασπισμών από ορθολογικούς πράκτορες, οι οποίοι ενώνουν τις δυνάμεις τους για να απολαύσουν κάποιας μορφής ωφέλεια, η οποία θα ήταν αδύνατον να αποκομιστεί με ατομική δράση. Τα ηδονικά παίγνια, από την άλλη, είναι μια κατηγορία συνεργατικών παιγνίων που μοντελοποιεί πράκτορες με ηδονικές προτιμήσεις, δηλαδή πράκτορες που έχουν προτιμήσεις σχετικά με την ταυτότητα των υπόλοιπων στο συνασπισμό τους. Ουσιαστικά λοιπόν, οι απολαβές ενός πράκτορα σε τέτοια περιβάλλοντα αντικατοπτρίζουν την ικανοποίηση που αποκομίζει από τον σχηματισμένο συνασπισμό του. Τώρα, τα συνεργατικά παίγνια με εξωτερικές επιδράσεις ή σε μορφή συνάρτησης διαμέρισης θεωρούν ότι οι απολαβές επηρεάζονται από τη διαμέριση του χώρου των πρακτόρων, δηλαδή το ποιό είναι το σύνολο των ήδη σχηματισμένων συνασπισμών. Μέχρι σήμερα, δεν υπάρχουν εργασίες που να έχουν εξετάσει ηδονικά παίγνια με εξωτερικές επιδράσεις.
Την ίδια στιγμή, η αβεβαιότητα σε περιβάλλοντα μπορεί να παρατηρηθεί σε πολλά ρεαλιστικά περιβάλλοντα συνεργατικών παιγνίων, και ως εκ τούτου η συνεργασία μεταξύ πρακτόρων υπό αβεβαιότητα είναι ένα θέμα που έχει μελετηθεί ευρέως.
Υπό το πρίσμα αυτό, στην παρούσα Διπλωματική Εργασία αρχικά επεκτείνουμε τον τυπικό ορισμό δύο πολύ γνωστών κλάσεων ηδονικών παιγνίων, συγκεκριμένα των additively separable hedonic games και των boolean hedonic games, σε μορφή συνάρτησης διαμέρισης. Κατόπιν, συνδυάζουμε τις προαναφερθείσες ιδέες και εστιάζουμε σε πράκτορες σε ηδονικά παιχνίδια με εξωτερικές επιδράσεις που δεν έχουν επίγνωση των ίδιων προτιμήσεων. Δεικνύουμε πώς να αποσπάσουμε αυτές τις κρυφές προτιμήσεις, χρησιμοποιώντας καθιερωμένες μεθόδους επιβλεπόμενης εκμάθησης—και συγκεκριμένα γραμμική παλινδρόμηση, γραμμική παλινδρόμηση με συναρτήσεις βάσης, και προωθητικά νευρωνικά δίκτυα—αφού τις προσαρμόσουμε στο τρέχον πρόβλημα. Επιπλέον, αξιοποιούμε μια μετρική ειδικά σχεδιασμένη για την αξιολόγηση της απόδοσης μεθόδων μηχανικής μάθησης που προσπαθούν να εκμαιεύσουν τις υποβόσκουσες ηδονικές προτιμήσεις σχετικά με διαμερίσεις. Στη συνέχεια, εξοπλίζουμε τους πράκτορες με την ικανότητα να δημιουργούν νέες εν δυνάμει ικανοποιητικές για αυτούς διαμερίσεις με χρήση μίξης Γκαουσιανών μοντέλων, με στόχο την πρόταση διαμερίσεων σε διαπραγματεύσεις πολλαπλών πρακτόρων. Τέλος, προτείνουμε δύο καινοφανή πρωτόκολλα σχηματισμού συνασπισμών, που εμπλέκουν πολλαπλούς πράκτορες με κρυφές και συγκρουόμενες προτιμήσεις, και τα οποία επιχειρούν να μεγιστοποιήσουν την κοινωνική ευημερία, χωρίς την παρουσία μιας κεντρικής οντότητας.
Abstract
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.
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 2042, Πολυτεχνειούπολη
Έναρξη: 17/09/2019 10:30
Λήξη: 17/09/2019 11:30
