Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/80FDEE47-F556-4D32-A48A-0BDE9DAB63EC | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.87677 | - |
| Language | en | - |
| Extent | 79 pages | en |
| Title | Extending the MC-nets representation scheme to cooperative game settings with uncertainty or overlaps | en |
| Title | Επέκταση της Mc-nets αναπαράστασης συνεργατικών παιγνίων σε περιβάλλοντα με αβεβαιότητα ή επικαλύψεις | el |
| Creator | Streviniotis Errikos | 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 game theory studies how self rational agents interact with each other in order to form coalitions and achieve a common goal by collaborating, while maximising their own profits. Representing the collaborations efficiently is key for supporting coalition formation decisions and achieving tractable computation in cooperative game settings. Moreover, research in cooperative games often assumes that there is no uncertainty in the settings of the game, or that agents cannot participate in many coalitions simultaneously. In this thesis, we focus on a well-known coalitional representation scheme, the MC-nets representation, and extend it to settings where we remove the aforementioned unrealistic assumptions, namely having complete information and no-overlaps. We begin by extending the Relational Rules representation, a scheme that itself extends MC-nets to cooperative games with overlapping coalitions, so that it now includes both positive and negative literals. Our proposed representation reduces to the classic MC nets representation for non-overlapping environments. We then introduce a novel succinct representation scheme for cooperative games under uncertainty, the ε-MC nets. The proposed representation is discussed first in the context of transferable utility games, and exploits estimates over marginal contributions to form compact rules representing collaboration patterns with potentially uncertain value. In more detail, given a set of MC-nets rules that use prior beliefs over values instead of the actual ones, we provide a polynomial algorithm for reaching the proposed succinct representation. We provide theoretical results regarding the information loss (regarding the perceived value of the agent collaboration patterns) after the compression of the original representation of the set. We show that the loss from compressing the set is bounded by a value directly proportional to ε, which represents an error regarding the believed value of an original rule which we are willing to accept in order to compress the representation. We then extend our algorithm to exploit equivalence classes of agents. This allows us to obtain an even more compact representation, and to derive new, previously unheld beliefs over the value of unobserved agent collaboration patterns. Moreover, we show that our approach extends naturally to non-transferable utility games. We conduct a systematic experimental evaluation of our algorithm’s variants, studying its behaviour in various realistic settings, and provide results on the compression achieved in each evaluated setting. Our experimental results confirm the effectiveness of our approach. | el |
| Content Summary | Η συνεργατική θεωρία παιγνίων μελετά πως ορθολογικοί πράκτορες αλληλεπιδρούν μεταξύ τους προκειμένου να δημιουργήσουν συνασπισμούς ώστε συνεργαζόμενοι να πετύχουν κάποιο κοινό στόχο, ενώ παράλληλα μεγιστοποιούν τις ατομικές τους απολαβές. Η αποδοτική αναπαράσταση των συνεργασιών στα πλαίσια ενός συνασπισμού, είναι σημαντική για την υποστήριξη λήψης αποφάσεων σχετικά με τη δημιουργία των συνασπισμών, και γενικότερα για την επίτευξη υπολογισμών σε συνεργατικά παίγνια. Επιπλέον, στην σχετική με συνεργατικά παίγνια έρευνα, χρησιμοποιούνται συχνά οι παραδοχές ότι δεν υπάρχει αβεβαιότητα στις ρυθμίσεις του παιχνιδιού ή/και ότι οι πράκτορες δεν μπορούν να συμμετέχουν σε πολλούς συνασπισμούς ταυτόχρονα. Στην παρούσα διπλωματική εργασία, επικεντρωνόμαστε σε ένα από τα πλέον γνωστά σχήματα αναπαράστασης συνεργατικών παιγνίων, την αναπαράσταση MC-nets, και το επεκτείνουμε ώστε να αφαιρέσουμε τις προαναφερθείσες μη-ρεαλιστικές παραδοχές (δηλαδή, αυτή της πλήρους πληροφόρησης και της μη ύπαρξης επικαλύψεων). Η πρώτη μας συνεισφορά συνίσταται στην επέκταση της αναπαράστασης Relational Rules, ενός πρόσφατα διατυπωμένου σχήματος αναπαράστασης που επέκτεινε εν μέρει τα MC-nets σε συνεργατικά παίγνια με επικαλυπτόμενους συνασπισμούς χρησιμοποιώντας λογικές προτάσεις με θετικά μόνο λεκτικά. Η προτεινόμενη στην παρούσα διπλωματική επέκταση, κατορθώνει να επεκτείνει πλήρως τα MC-nets, χρησιμοποιώντας για την αναπαράσταση συνεργασιών λογικές προτάσεις που μπορεί να περιλαμβάνουν τόσο θετικά όσο και αρνητικά λεκτικά. H προτεινόμενη αναπαράσταση, αντιστοιχεί επακριβώς στην κλασική MC-nets αναπαράσταση σε περιβάλλοντα με μη επικαλυπτόμενους συνασπισμούς. Στη συνέχεια, προτείνουμε ένα νέο, περιεκτικό σχήμα αναπαράστασης για συνεργατικά παίγνια με αβεβαιότητα, το οποίο καλούμε ε-MC nets. Η προτεινόμενη αναπαράσταση ορίζεται αρχικά στο πλαίσιο των παιγνίων με μεταβιβάσιμη αξία (transferable utility), και εκμεταλλεύεται εκτιμήσεις περιθωρίων συνεισφορών πρακτόρων για να σχηματίσει συμπαγείς κανόνες αναπαριστώντας μοτίβα συνεργασίας με ενδεχομένως αβέβαιη αξία. Πιο συγκεκριμένα, δεδομένου ενός σετ από MC-nets κανόνες που χρησιμοποιούν πρότερες εκτιμήσεις αξίας συνεργασιών, παρέχουμε έναν πολυωνυμικό αλγόριθμο που επιτυγχάνει την προτεινόμενη συμπαγή αναπαράσταση. Επιπροσθέτως, παρέχουμε θεωρητικά αποτελέσματα σχετικά με την απώλεια πληροφορίας (όσον αφορά τις εκλαμβανόμενες αξίες των μοτίβων συνεργασίας πρακτόρων) μετά τη συμπίεση της αρχικής αναπαράστασης για το σετ κανόνων, δείχνοντας ότι φράσσεται από μια τιμή ευθέως ανάλογη με το αποδεκτό περιθώριο απόστασης από την αξία ενός αρχικού MC-net κανόνα. Κατόπιν, επεκτείνουμε τον αλγόριθμό μας ώστε να εκμεταλλεύεται την ύπαρξη κλάσεων ισοδυναμιών των πρακτόρων. Αυτό μας επιτρέπει να αποκτήσουμε μια ακόμα πιο συμπαγή αναπαράσταση, καθώς και να παράγουμε νέες, προηγουμένως ανύπαρκτες πεποιθήσεις για τις αξίες μη-παρατηρήσιμων μοτίβων συνεργασίας πρακτόρων. Επιπλέον, δεικνύουμε ότι η προσέγγιση μας μπορεί να επεκταθεί και σε συνεργατικά παίγνια με μη μεταβιβάσιμη αξία (non-transferable utility games). Τέλος, διεξάγουμε μια συστηματική πειραματική αξιολόγηση των παραλλαγών του αλγορίθμου μας, μελετώντας τη συμπεριφορά τους μέσω προσομοιώσεων σε ποικίλα ρεαλιστικά περιβάλλοντα, και παρέχουμε αποτελέσματα σχετικά με την συμπίεση που επιτυγχάνεται σε κάθε περίπτωση. Τα πειραματικά μας αποτελέσματα επιβεβαιώνουν την αποτελεσματικότητα της προσέγγισής μας. | el |
| Type of Item | Διπλωματική Εργασία | el |
| Type of Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2020-12-11 | - |
| Date of Publication | 2020 | - |
| Subject | Cooperative games | en |
| Subject | MC-nets | en |
| Subject | Representation schemes | en |
| Subject | Uncertainty and overlaps | en |
| Bibliographic Citation | Errikos Streviniotis, "Extending the MC-nets representation scheme to cooperative game settings with uncertainty or overlaps", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2020 | en |
| Bibliographic Citation | Ερρίκος Στρεβινιώτης, "Επέκταση της Mc-nets αναπαράστασης συνεργατικών παιγνίων σε περιβάλλοντα με αβεβαιότητα ή επικαλύψεις", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2020 | el |
Copyright © DIAS 2013
