Decision-making of autonomous agents in networks with adversaries

Abstract

In modern networks, agents are characterized by enhanced capabilities of independent decision making, resulting in improved network efficiency in terms of throughput maximization, energy consumption and scalability, but new challenges emerge. Agents may have disparate, or even conflicting interests and hence, “misbehavior” issues can arise. The term “misbehavior” refers to the case when agents act in a way that is misaligned with the one prescribed by network protocols. As a result, altruistic cooperation can notbe taken for granted. For this reason, mechanisms that can enforce agents’ compliance with a desired behavior that is beneficial for the network, have been proposed in literature. Such mechanisms aretrust/reputation models, which aim at incentivizing agents to act in a cooperative way for their own benefits. This thesis aims at investigating the interactions of autonomous network agents when they have individual interests, as well as the impact of cooperation stimulation mechanisms on their decision-making process. More specifically, we investigate when agents, with myopic selfish or malicious motives, opt to share information with each other undersome cooperation enforcing mechanism such as trust/reputation models or punishment strategies. We start by investigating the information sharing in the most basic network functionality, namely packet-forwarding. In this study the impact of trust and action monitoring mechanisms on the agents’ decision-making process is analyzed and conditions are derived which if satisfied, ensure agents are incentivized to opt to follow a strategy that is beneficial for the network. Then, we move on to study information sharing in a higher level, by considering a specific information diffusion model and study the problem of distributed parameter estimation in an adversarial setting, where malicious agents exist in the network having the option to disseminate intentionally falsified information. Novel algorithms that are robust to malicious information dissemination are developed to drive agents’ parameter estimation and decision-making processes. Finally, we make an abstraction and study the problem of information sharing in a more general setting, without assuming a specific information sharing model. We utilize the notion of conditional mutual information to quantify the value of shared information. Appropriate punishment strategies are devised that can provably sustain information sharing at equilibrium. To achieve the research goals of this thesis, methods from Stochastic Control Theory, Game Theory, Signal Processing and Learning algorithms are utilized.

Στα σύγχρονα δίκτυα, οι κόμβοι χαρακτηρίζονται από ανεπτυγμένες ικανότητες ανεξάρτητης λήψης αποφάσεων, με αποτέλεσμα την αύξηση της δικτυακής επίδοσης σε τομείς όπως η διεκπεραιωτική ικανότητα, η κατανάλωση ισχύος και η επεκτασιμότητα, αλλά από την άλλη νέα θέματα ασφαλείας αναδύονται. Οι κόμβοι μπορεί να έχουν διαφορετικά, ή ακόμη και αντικρουόμενα συμφέροντα και ως εκ τούτου, μπορεί να προκύψουν θέματα «κακής συμπεριφοράς». Ο όρος αυτός αναφέρεται στην περίπτωση που οι κόμβοι συμπεριφέρονται με τρόπο διαφορετικό από αυτόν που προβλέπουν τα δικτυακά πρωτόκολλα. Επομένως,η «αλτρουιστική» συνεργασία μεταξύ των κόμβων δεν μπορεί να θεωρηθεί δεδομένη σε δίκτυα που αποτελούνται από αυτόνομους «ευφυείς» κόμβους (agents).Για αυτόν τον λόγο, μηχανισμοί που μπορούν να οδηγήσουν τους κόμβους σε μία ωφέλιμη για το δίκτυο συμπεριφορά, έχουν προταθεί στην βιβλιογραφία. Τέτοιοι μηχανισμοί είναι τα λεγόμενα μοντέλα εμπιστοσύνης, τα οποία στόχο έχουν την παροχή κινήτρων στους κόμβους προκειμένου να συμπεριφερθούν συνεργατικά για το δικό τους όφελος. Η διατριβή αυτή έχει ως σκοπό την μελέτη των αλληλεπιδράσεων αυτόνομων δικτυακών κόμβων όταν αυτοί χαρακτηρίζονται από διαφορετικά ατομικά συμφέροντα, καθώς και της επίδρασης των μοντέλων εμπιστοσύνης στην συμπεριφορά τους. Πιο συγκεκριμένα,μελετάμε πότε οι κόμβοι, με «εγωιστικά» ή «κακόβουλη» συμπεριφορά, επιλέγουν να μοιραστούν μεταξύ τους πληροφορία κάτω από κάποιο μηχανισμό επιβολής συνεργασίας όπως τα μοντέλα εμπιστοσύνης ή οι τιμωρητικές στρατηγικές. Ξεκινάμε διερευνώντας τον διαμοιρασμό πληροφορίας στο πλαίσιο της πιο βασικής λειτουργίας ενός δικτύου, της προώθησης πακέτου. Σε αυτή τη μελέτη αναλύεται η επίδραση των μηχανισμών εμπιστοσύνης και παρατήρησης των δράσεων των κόμβων και εξάγονται συνθήκες που αν ικανοποιούνται, οι κόμβοι συμμορφώνονται με μία ωφέλιμη για το δίκτυο συμπεριφορά. Στη συνέχεια, προχωράμε στην μελέτη του διαμοιρασμού πληροφορίας σε ψηλότερο επίπεδο, θεωρώντας ένα συγκεκριμένο μοντέλο μετάδοσης διάδοσης της πληροφορίας και μελετάμε το πρόβλημα του διαμοιρασμού της κατανεμημένης εκτίμησης παραμέτρων σε ένα εχθρικό περιβάλλον, όπου υπάρχουν κακόβουλοι κόμβοι που έχουν την δυνατότητα να διαχέουν ηθελημένα ψευδή πληροφορία. Αναπτύχθηκαν καινοτόμοι αλγόριθμοι οι οποίοι είναι εύρωστοι στην διάχυση ψευδούς πληροφορίας για να οδηγήσουν τους κόμβους σε αποδοτική εκτίμηση παραμέτρων και λήψη αποφάσεων. Τέλος, κάνουμε μία αφαίρεση και μελετάμε το πρόβλημα διαμοιρασμού πληροφορίας σε ένα πιο γενικό πλαίσιο, χωρίς να υποθέτουμε κάποιο μοντέλο διαμοιρασμού της πληροφορίας. Χρησιμοποιούμε την έννοια της δεσμευμένης αμοιβαίας πληροφορίας για να ποσοτικοποιήσουμε την αξία της πληροφορίας που μοιράζεται. Κατασκευάστηκαν κατάλληλες τιμωρητικές στρατηγικές οι οποίες μπορούν αποδεδειγμένα να διατηρήσουν την ανταλλαγή πληροφορίας. Για να επιτευχθούν οι ερευνητικοί στόχοι αυτής της διατριβής, χρησιμοποιούνται μέθοδοι από την Θεωρία Στοχαστικού Ελέγχου, την Θεωρία Παιγνίων, την Επεξεργασία Σήματος και Αλγόριθμοι Εκμάθησης.