Εφαρμοσμένη επιχειρησιακή έρευνα στην πληροφορική: παιγνιοθεωρητικά υποδείγματα για δίκτυα χρηστών του διαδικτύου

Abstract

This thesis analyzes the behavior and the interaction of individuals or member communities of internet user networks, by developing quantitative economic models. Game Theoretic analysis is used as a tool to solve these models and predict users' behavior in equilibrium. The first part models the interaction between spam senders and e-mail users as a two-player adversary game, where anti-spam filters are intervened. The resulting game is solved by applying a prototypal diagrammatic method that allows the determination of all Nash equilibria in 2xM nonzero sum games. This method is presented in detail and then used to prove for the 2xM case the Nash existence theorem, the Minimax theorem and the lesser known fact that the total number of Nash equilibria is odd. The derived equilibria of the spam game predict the strategies that the two opponent communities will eventually adopt. Moreover, the results are employed to optimally tune the anti-spam filters, so that users' expected utility is maximized. The basic spam game is extended to include the possibility of employing Human Interactive Proofs (HIPs), in conjunction with anti-spam filters. The analysis shows that making relatively cheap HIPs widely available to the community of e-mail users, reduces the volume of spam on the internet and increases the benefit that legitimate users obtain from the e-mail. Finally, a signalling game, that models the interaction between (legitimate or spam) e-mail senders and users, is introduced. The mechanism of Attention Bonds is employed. A unique perfect Bayesian equilibrium, which guarantees legitimate communication, is established only when the bonds are relatively expensive and the percentage of spam messages is relatively high. In the second part of this thesis a new model of the interaction of rational peers in large Peer-to-Peer (P2P) networks is developed. At the heart of the model is altruism, an intrinsic parameter reflecting peers' inherent willingness to contribute. Two different approaches for modelling altruistic behaviour are introduced. With either approach, Game Theoretic analysis is used to calculate Nash equilibria and predict peers' behavior in terms of individual contribution. Two cases of P2P networks are considered: (i) of peers that have homogeneous altruism levels or (ii) of peers that have heterogeneous altruism levels, but with known probability distributions. The analysis shows that, under the effects of altruism, a substantial fraction of peers will contribute when altruism levels are within certain intervals, even though no incentive mechanism is used. The model is enhanced with a simple but powerful incentive scheme to limit free-riding and increase contribution to the network. The particular incentive scheme is shown to achieve its goal on networks with altruistic peers, although the benefit that the strongly altruistic peers receive is decreased.

Η διατριβή παρουσιάζει και αναλύει πρωτότυπα ποσοτικά υποδείγματα με στόχο τη μελέτη της διαδραστικής σχέσης μεταξύ ομάδων ή μεμονωμένων μελών σε δίκτυα χρηστών του διαδικτύου. Ως εργαλείο επίλυσης των υποδειγμάτων και πρόβλεψης της συμπεριφοράς των χρηστών χρησιμοποιείται η Θεωρία Παιγνίων. Στο πρώτο μέρος της διατριβής παρουσιάζεται ένα παιγνιοθεωρητικό υπόδειγμα που περιγράφει τη διαδραστική σχέση μεταξύ των χρηστών ηλεκτρονικής αλληλογραφίας και των αποστολέων ανεπιθύμητων μηνυμάτων (spam e-mail), όταν παρεμβάλλονται φίλτρα ανεπιθύμητης αλληλογραφίας. Το παίγνιο που προκύπτει επιλύεται με μία πρωτότυπη διαγραμματική μέθοδο για τον προσδιορισμό σημείων ισορροπίας κατά Nash σε 2xM παίγνια μη μηδενικού αθροίσματος. Η προτεινόμενη μέθοδος εφαρμόζεται για να αποδειχθούν θεμελιώδη θεωρήματα της Θεωρίας Παιγνίων για 2xΜ παίγνια με διαγραμματικό τρόπο. Με βάση τα σημεία ισορροπίας του παιγνίου ηλεκτρονικής αλληλογραφίας, εκτιμάται το ποσοστό των ανεπιθύμητων μηνυμάτων σε ισορροπία και προτείνεται η βέλτιστη, από πλευράς χρηστών, ρύθμιση των φίλτρων. Στη συνέχεια το βασικό υπόδειγμα επεκτείνεται με την ανάλυση ενός μηχανισμού αποφυγής της ανεπιθύμητης αλληλογραφίας μέσω αποδείξεων ανθρώπινης αλληλεπίδρασης (human interactive proofs). Τέλος, παρουσιάζεται και επιλύεται ένα παίγνιο σημάνσεων μεταξύ των αποστολέων και των παραληπτών της ηλεκτρονικής αλληλογραφίας, εφαρμόζοντας ένα μηχανισμό ομολόγων προσοχής (attention bonds). Το δεύτερο μέρος της διατριβής αναπτύσσει ένα ολοκληρωμένο υπόδειγμα για τη συμπεριφορά ορθολογικών οντοτήτων σε ένα δίκτυο ομότιμων οντοτήτων (peer-to-peer network), στο οποίο διαμοιράζεται κάποιος πόρος. Κεντρική έννοια της ανάλυσης είναι ο αλτρουισμός των οντοτήτων, ένα ενδογενές κίνητρο που διαμορφώνει τη συνεισφορά αυτών. Προσδιορίζονται σημεία ισορροπίας, τα οποία παρέχουν μία πρόβλεψη για το επίπεδο της συνεισφοράς των οντοτήτων στο δίκτυο ως συνάρτηση της κατανομής του αλτρουισμού. Εξετάζοντας δύο διαφορετικές θεωρήσεις για τον αλτρουισμό, αποδεικνύεται ότι οι οντότητες ενδέχεται να συνεισφέρουν στο δίκτυο ακόμη και χωρίς να απαιτούνται εξωγενή κίνητρα. Το υπόδειγμα επεκτείνεται με την υιοθέτηση ενός απλού αλλά δίκαιου μηχανισμού κινήτρων, ως αποτέλεσμα του οποίου η συνολική συνεισφορά στο δίκτυο αυξάνεται.