ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Μεταπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΜΕΤΑΠΤΥΧΙΑΚΗΣ ΕΡΓΑΣΙΑΣ
Αθηνάς Γεωργαρά
με θέμα
Ηδονικά Παίγνια στον Πραγματικό Κόσμο: Μηχανική Μάθηση και Θεωρητικές Επεκτάσεις
Hedonic Games in the Real World: Machine Learning and Theoretical Extensions
Πέμπτη 1 Αυγούστου 2019, 10 π.μ.
Αίθουσα 145.Π42, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Γεώργιος Χαλκιαδάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Μιχαήλ Γ. Λαγουδάκης
Καθηγητής Ευριπίδης Πετράκης
Περίληψη: Παρά την ικανότητά της να μοντελοποιεί μαθηματικά σε ένα αφαιρετικό επίπεδο πραγματικά προβλήματα, η συνεργατική θεωρία παιγνίων συχνά υιοθετεί υποθέσεις που τελικά δεν ευσταθούν σε πραγματικά περιβάλλοντα. Με βάση τα παραπάνω, σε αυτήν την μεταπτυχιακή εργασία εστιάζουμε στα Ηδονικά Παίγνια--μια κλάση συνεργατικών παιγνίων στην οποία οι παίκτες σχηματίζουν συνασπισμούς με βάση προσωπικές προτιμήσεις που σχετίζονται με τους πιθανούς συμπαίκτες τους--και αναιρούμε κάποιες συνήθεις υποθέσεις, με στόχο να παρέχουμε ένα μοντέλο που περιγράφει ακριβέστερα τον πραγματικό κόσμο. Η εργασία μας προσέγγισε και επέκτεινε τα Ηδονικά Πάιγνια τόσο από θεωρητική όσο και από πρακτική σκοπιά, και κατέληξε σε ποικίλλες επιστημονικές συνεισφορές.
Κατ' αρχάς, μια επικρατούσα υπόθεση στην βιβλιογραφία είναι ότι οι πράκτορες ενδιαφέρονται αποκλειστικά και μόνο για την σύνθεση του δικού τους συνασπισμού. Στην παρούσα εργασία, αφαιρούμε αυτόν την υπόθεση με το να επιτρέπουμε στους πράκτορες να αναπτύσσουν προτιμήσεις όχι μόνον σχετικά με συνασπισμούς, αλλά και σχετικά με δομές συνασπισμών--δηλαδή, διαμερίσεις του χώρου των πρακτόρων. Συγκεκριμένα, εισάγουμε έναν τυπικό ορισμό για τα ηδονικά παίγνια σε μορφή συνάρτησης διαμέρισης (PFF-HGs), και επεκτείνουμε γνωστές κλάσεις ηδονικών παιγνίων σε αυτή την μορφή.
Μια άλλη υπόθεση που γίνεται συνήθως στα ηδονικά παίγνια, είναι αυτή της πλήρους πληροφόρησης. Ωστόσο, στον πραγματικό κόσμο αυτό δεν ισχύει σχεδόν ποτέ. Για να αντιμετωπίσουμε το θέμα, εξετάζουμε το πρόβλημα της αβεβαιότητας όσον αφορά κρυμμένες σχέσεις προτιμήσεων σε ηδονικά παίγνια. Συγκεκριμένα, υποθέτουμε ότι οι πράκτορες αλληλεπιδρούν σε ένα άγνωστο περιβάλλον ηδονικού παιγνίου, παρατηρούν ένα μικρό αριθμό από στιγμιότυπα, και προσπαθούν να μάθουν τις μή εμφανείς πτυχές του παιχνιδιού. Για το σκοπό αυτό, εφαρμόζουμε διάφορα μοντέλα επιβλεπόμενης και μή (μηχανικής) μάθησης, για να εξάγουμε προσεγγιστικά τις κρυφές σχέσεις προτιμήσεων και να ανιχνεύσουμε επιθυμητά μοτίβα συνεργασιών. Πιο συγκεκριμένα, παρέχουμε μια ενδελεχή αξιολόγηση με την χρήση γραμμικής παλινδρόμησης, παλινδρόμησης με συναρτήσεις βάσης, προωθητικών νευρωνικών δικτύων αλλά και του αλγορίθμου πιθανοτικής θεματικής μοντελοποίησης Latent Dirichlet Allocation (LDA), για την προσεγγιστική μάθηση των αγνώστων προτιμήσεων σε διάφορες κλάσεις ηδονικών παιγνίων.
Τέλος, προτείνουμε και εισάγουμε την μελέτη μιας νέας κλάσης συνεργατικών παιγνίων, των Ηδονικών Παιγνίων Χρησιμότητας (HUGs), τα οποία λαμβάνουν υπ' όψιν τόσο ``ηδονικές΄΄ προτιμήσεις (σχετικές με τη σύνθεση της ομάδας), όσο και προτιμήσεις σχετιζόμενες με χρησιμότητα. Δίνουμε τον επίσημο ορισμό των HUGs, και επεκτείνουμε υπάρχουσες λύσεις ευστάθειας σε αυτά τα παίγνια. Εν συνεχεία, εισάγουμε μια καινούρια λύση ευστάθειας, την οποία καλούμε Μεμονωμένα Ορθολογικό - Μεμονωμένα Ευσταθές (IRIS) σημείο ισορροπίας, που σχεδιάστηκε ειδικά για τα παίγνια HUGs, και η οποία χαρακτηρίζει ευσταθείς δομές συνασπισμών σε αυτά τα παίγνια. Επιπροσθέτως, προτείνουμε ένα φυσικό μοντέλο ``τριχοτόμησης'' του χώρου των ηδονικών προτιμήσεων, μελετάμε συγκεκριμένες ιδιότητες των HUGs σε αυτό το μοντέλο, και το εκμεταλλευόμαστε ώστε να χαρακτηρίσουμε την εφικτότητα σχηματισμού συνασπισμών στα HUGs, και να υπολογίσουμε ένα πιθανοτικό άνω όριο για το ``κλάδεμα'' του χώρου συνασπισμών. Ως εκ τούτου, το κλάδεμα μπορεί να χρησιμοποιηθεί για να μειώσουμε το υπολογιστικό φορτίο για τον υπολογισμό κοινώς αποδεκτών από τους παίκτες (τεχνικά, ``ευσταθών στον πυρήνα kernel'') πληρωμών σε IRIS δομές συνασπισμών.
Abstract: Successful as it may be in mathematically modelling many real-life problems, cooperative game theory regularly adopts assumptions that cannot possibly stand in most specific everyday scenarios. Given this, in our work in this thesis we focus on Hedonic Games---a class of cooperative games in which players form coalitions based on their individual preferences regarding their potential partners---and tackle certain such assumptions in order to provide a model that fits better the real world. To this end, we make several contributions to Hedonic Games, approaching them from both a theoretical and practical point of view and extending them in various ways.
To begin, a prevalent assumption in the literature is that agents are interested solely on the composition of their own coalition. In our work we lift this assumption by allowing agents to develop preferences not only on coalitions, but also on coalition structures---i.e., partitions of the agents' space. Specifically, we motivate and put forward the formal definition of hedonic games in partition function form (PFF-HGs), and extend well-studied hedonic games' classes to this setting.
Another usual assumption in the hedonic games literature is that of complete information. However, in the real world this is almost never the case. To tackle this, we examine the problem of uncertainty regarding hidden preference relations in hedonic games. Specifically, we assume that agents interact within an unknown hedonic game setting, observe a small number of game instances, and attempt to learn the hidden aspects of the game. Then, we employ several learning models, both supervised and unsupervised, to approximately extract the latent preference relations and detect desirable collaboration patterns. In particular, we provide a thorough evaluation of the use of linear regression, regression with basis functions, feed forward neural networks, and the online Latent Dirichlet Allocation (LDA) algorithm for approximately learning the unknown preferences across several classes of hedonic games.
Last but not least, we initiate the study of a novel class of cooperative games, the Hedonic Utility Games (HUGs), that takes into consideration both hedonic and utility-related preferences. We formally define HUGs, and show how to extend and apply existing stability solution concepts to them. Then, we put forward a novel solution concept, Individually Rational - Individually Stable (IRIS), which characterizes the stability of coalition structures in HUGs and was developed specifically for such settings. In addition, we propose a natural, “trichotomous” hedonic preferences model; study certain HUGs properties in that model; and exploit it to characterize the feasibility of HUGs coalitions, and to obtain a probability bound for pruning the coalitional space. Pruning can thus be exploited to reduce the computational load of deriving globally acceptable (``kernel-stable'') payoff configurations for IRIS partitions.
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 145Π-42
Έναρξη: 01/08/2019 10:00
Λήξη: 01/08/2019 11:00
