Study on the effect of misinformation in multi-agent systems

Abstract

Industrial processes and research activities quite often involve interactions between selfinterested participants. Game theory is a standard tool to analyze and study these interactions, but usually comes along with the assumption that the participants (i.e. agents, players) have a common and correct (albeit not always complete) knowledge with regards to the abstract formulation of the interaction. However, in many real-world situations, it could be the case that (some of) the agents are misinformed with regards to the game that they play, essentially having an incorrect understanding of the setting, without being aware of it. This would invalidate the common knowledge assumption. To study this phenomenon in this dissertation we establish a new framework. We initiate our study by presenting a new game-theoretic framework, called misinformation games, that provides the formal machinery necessary to study this phenomenon, and present some basic results regarding its properties. Interestingly, the new concept provides new equilibrium concepts, related to the Nash equilibrium. Thereupon, we introduce a new metric, called Price of Misinformation, in order to quantify the influence of misinformation in the efficiency of the interaction. Furthermore, we apply our framework in a variety of well-known classes of games. Afterwards, we expand the misinformation game model, by developing a discrete-time iterative procedure, where in each time step each agent chooses an action according to the (possibly erroneous) game specification that she possesses. Then, the actual payoffs that correspond to the agglomeration of the agents’ choices are publicly announced, thus allowing agents to update their information. Consequently, agents may re-evaluate their behaviour in the next time step. We call this process Adaptation Procedure, and we provide various results regarding its properties. Further, we present a complete analysis of the behaviour of the agents as their game specifications are updated, and show that this leads to new equilibrium concepts. Thereafter, we enrich the Adaptation Procedure by incorporating the epistemic view that each agent has regarding the interaction. Towards this direction, we formally define the epistemic perspective of Adaptation Procedure in misinformation games. Namely, we construct a process, called Epistemic Adaptive Evolution, where agents revise both their information and their epistemic knowledge according to the game they play. This also provides new equilibrium concepts. With this at hand, we complete our framework, through which we can study the phenomenon of agent interaction with incorrect information. Evidently, in several cases in our model, it is necessary to compute several equilibrium concepts. For that, we introduce a novel online learning algorithm. Specifically, we propose a novel variant of the multiplicative weights update method using best-response strategies, that guarantees last-iterate convergence for zero-sum games with a unique Nash equilibrium. Next, we consider the case of misinformation games where the misinformation is due to random noise that additively distorts the payoff matrices of the agents (e.g., due to communication errors). We call this setting noisy games. We analyze the general properties of two-players noisy games and we derive theoretical formulas which determine the probability that the noise will significantly affect the strategic behaviour of the agents, based on the noise intensity and pattern. Following the analysis and study of interaction from the perspective of the participants, we approach the problem from the perspective of the game’s designer. In particular, we introduce a novel approach for Coordination mechanisms in games, based on the idea of misinforming agents about the game formulation, in order to steer them towards a behaviour that leads to an improved outcome in terms of social welfare. We propose a mechanism that provides the agents with the right incentives to adopt a socially optimal behaviour by misinforming them.

Συχνά οι βιομηχανικές διεργασίες και οι ερευνητικές δραστηριότητες περιλαμβάνουν αλληλεπιδράσεις μεταξύ συμμετεχόντων (ήτοι πράκτορες, παίχτες). Η Θεωρία Παιγνίων αποτελεί, συχνά, το εργαλείο με το όποιο μελετάμε τέτοιου είδους αλληλεπιδράσεις· συνήθως περιλαμβάνοντας την υπόθεση ότι οι πράκτορες έχουν κοινή και σωστή (χωρίς να είναι πάντοτε πλήρης) πληροφορία σχετικά με την δραστηριότητα στην οποία συμμετέχουν. Ωστόσο, στον πραγματικό κόσμο οι πράκτορες συχνά ενεργούν έχοντας λανθασμένη πληροφόρηση σχετικά με την αλληλεπίδραση και τις συνθήκες της, χωρίς να το γνωρίζουν· ακυρώνοντας κατ΄αυτόν τον τρόπο την υπόθεση της κοινής και σωστής πληροφόρησης. Για να μελετήσουμε αυτό το φαινόμενο, στην παρούσα διατριβή θεμελιώνουμε μια καινούργια δομή. Αρχικά, εισάγουμε στην δομή μας μια καινούργια κλάση παιγνίων, την οποία ονομάζουμε παίγνια εσφαλμένης πληροφορίας, η οποία μας παρέχει όλα τα αναγκαία θεωρητικά εργαλεία ώστε να μελετήσουμε το φαινόμενο της αλληλεπίδρασης υπό εσφαλμένη πληροφορία. Αξιοσημείωτο είναι ότι αυτή η κλάση παιγνίων παρέχει καινούργια σημεία ισορροπίας, τα οποία βασίζονται στα σημεία ισορροπίας Nash. Παράλληλα, παρουσιάζουμε βασικές ιδιότητες της δομής αυτής και την εφαρμόζουμε σε διάφορες κλασσικές κλάσεις παιγνίων. Ταυτοχρόνως, ορίζουμε μια νέα μετρική η οποία ποσοτικοποιεί την επίδραση της εσφαλμένης πληροφορία στην απόδοση της αλληλεπίδρασης. Εν συνεχεία, επεκτείνουμε το μοντέλο των παιγνίων εσφαλμένης πληροφορίας, αναπτύσσοντας μια επαναληπτική διαδικασία διακριτού χρόνου, όπου σε κάθε χρονικό βήμα κάθε πράκτορας διαλέγει μια ενέργεια σύμφωνα με τις (πιθανώς εσφαλμένες) προδιαγραφές της αλληλεπίδρασης που κατέχει. Κατόπιν, ανακοινώνονται δημόσια οι πραγματικές ανταμοιβές που λαμβάνουν οι πράκτορες, σύμφωνα με τον συνδυασμό των επιλογών που έχουν κάνει· ενημερώνοντας κατ’ αυτόν τον τρόπο την πληροφορία που κατέχουν. Ονομάζουμε αυτή την διαδικασία Διαδικασία Προσαρμογής και παρουσιάζουμε θεωρητικά αποτελέσματα σχετικά με τις ιδιότητες της. Περαιτέρω, αναλύουμε την συμπεριφοράς των πρακτόρων καθώς η πληροφορία που κατέχουν ενημερώνεται, και αποδεικνύουμε ότι αυτή οδηγεί σε καινούργια σημεία ισορροπίας. ΄Επειτα, διευρύνουμε την Διαδικασία Προσαρμογής ενσωματώνοντας την γνωσιολογική θεώρηση που έχει ο κάθε πράκτορας σχετικά με την αλληλεπίδραση στην οποία συμμετέχει. Προς αυτή την κατεύθυνση, ορίζουμε τυπικά την γνωσιολογική θεώρηση της Διαδικασίας Προσαρμογής στα παίγνια εσφαλμένης πληροφορίας. Συγκεκριμένα, κατασκευάζουμε μια διαδικασία, την οποία ονομάζουμε Γνωσιολογική Προσαρμοστική Εξέλιξη, κατά την οποία οι πράκτορες αναθεωρούν τόσο την πληροφορία που κατέχουν όσο και την γνωσιολογική πληροφορία σχετικά με την αλληλεπίδραση στην οποία συμμετέχουν. ΄Οπως και στα προηγούμενα σκέλη του μοντέλου μας, αναδύονται καινούργια σημεία ισορροπίας. Με αυτό το μέρος της μελέτης, ολοκληρώνουμε την δομή μέσω της οποίας μπορούμε να μελετήσουμε το φαινόμενο της αλληλεπιδράσης πρακτόρων με εσφαλμένη πληροφορία. Γίνεται άμεσα αντιληπτό ότι είναι σημαντικός ο υπολογισμός σημείων ισορροπίας (π.χ. Nash) σε διάφορα σημεία του μοντέλου μας. Για τον λόγο αυτό, αναπτύσσουμε έναν καινούργιο on-line αλγόριθμο μάθησης. Πιο συγκεκριμένα, προτείνουμε μια παραλλαγή της multiplicative weights update μεθόδου, χρησιμοποιώντας best-response στρατηγικές, η οποία εγγυάται κατά σημείο σύγκλιση για παίγνια μηδενικού αθροίσματος με μοναδικό σημείο ισορροπίας Nash. Ως συνέχεια της μελέτης του φαινομένου της επίδρασης της εσφαλμένης πληροφορίας σε αλληλεπιδράσεις πολλών πρακτόρων, αναλύουμε την επιρροή της δομής της εσφαλμένης πληροφορίας στην αλληλεπίδραση. Συγκεκριμένα, εισάγουμε μια νεα οικογένεια παιγνίων εσφαλμένης πληροφορίας, την οποία ονομάζουμε παίγνια θορύβου, όπου η εσφαλμένη πληροφορία εξαρτάται από τυχαίο θόρυβο, ο οποίος προστίθεται στις τιμές των ανταμοιβών. Κατόπιν, αναλύουμε τις γενικές ιδιότητες των παιγνίων θορύβου δύο παιχτών και εξάγουμε θεωρητικά αποτελέσματα ως προς την επίδραση του θορύβου στην στρατηγική συμπεριφορά των πρακτόρων. Τέλος, η μελέτη ολοκληρώνεται με την ανάλυση της αλληλεπίδρασης από την σκοπιά του σχεδιαστή της. Πιο συγκεκριμένα, παρουσιάζουμε μια νεα προσέγγιση στην περιοχή των Coordination mechanisms, βασιζόμενοι στην ιδέα ότι παρέχοντας εσφαλμένη πληροφορία στους πράκτορες, σχετικά με τις προδιαγραφές της αλληλεπίδρασης, μπορούμε να τους κατευθύνουμε σε συμπεριφορές που βελτιώνουν την απόδοση της αλληλεπίδρασης, με όρους συλλογικής πρόνοιας. Προτείνουμε έναν μηχανισμό που παρέχει στους πράκτορες τα κατάλληλα κίνητρα ώστε να υιοθετήσουν μια συλλογικά καλύτερη συμπεριφορά.