Μελέτη του παγκόσμιου ιστού με χρήση θεωρίας οικονομικών και παιγνίων

Abstract

The worldwide web is created, supported, used, and run by a multitude of selfish, optimizing economic agents with various and dynamically varying degrees of competition and interest alignment.In this dissertation we propose models that capture the grid of interests in the worldwide web, using concepts and techniques that come from the fields of Economics and Game Theory.The first proposed model is economic and consists of three types of interacting players: (a) Document authors, that provide content in the worldwide web. (b) Users that seek useful information in the worldwide web, and (c) a Search Engine whose purpose is to help users find interesting documents. The worldwide web is created by the interaction of the above mentioned players, each one of them is interested in maximizing utility by interacting with other players. A basic element of this model is the utility U(i,d) that correlates user i with the document d. Some interesting questions we examine are: What is the efficiency or price of anarchy of the search algorithm, in other words, which fraction of the maximum possible utility can be realized by a search engine? What are the characteristics of the ultimate worldwide web state that results from this process? We find experimentally that total utility is increased when users' utilities are clustered. Also, the degree of the documents follows a power law distribution in this case. Finally, we pose a number of interesting questions about the competition and quality of search engines, search algorithms, incentives of the webpages and search engine spamming. The second model is game-theoretic. Worldwide web is modelled as a graph, in which each node provides information. The action space of each node consists of choosing a set of outgoing links along with click probabilities on these links. A node's utility is the product of the traffic through this node, perhaps captured by its PageRank in the Markov chain created by the strategy profile, times the quality of the node, a surrogate for the website's monetization potential. The latter depends on the intrinsic quality of the node's content, as modified by the chosen outgoing links and probabilities. We only require that the quality be a concave function of the node's strategy (meaning the distribution over outgoing links). We suggest a natural example of a quality function. We prove that the resulting game always has a pure Nash equilibrium. Experiments suggest that these equilibria are not hard to compute, have characteristics consistent with what we know about the worldwide web, and seem to have very favorable price of anarchy. Quantifying rigorously the price of anarchy of these equilibria, as well as the complexity of finding them, are important open problems.Finally, we examine experimentally two more models that are extensions with utility functions of known network creation models.

O Παγκόσμιος ιστός δημιουργήθηκε, υποστηρίζεται και χρησιμοποιείται από ένα σύνολο από εγωιστικές οικονομικές οντότητες, κάθε μια εκ των οποίων προσπαθεί να βελτιστοποιήσει διάφορους παράγοντες, και οι οποίες έχουν ποικίλους βαθμούς ανταγωνισμού και συνεργασίας μεταξύ τους.Στη διατριβή προτείνουμε μοντέλα απεικόνισης του πλέγματος των συμφερόντων στον παγκόσμιο ιστό, στα οποία χρησιμοποιούμε έννοιες, τεχνικές της Θεωρίας Οικονομικών και Παιγνίων. Το πρώτο προτεινόμενο μοντέλο είναι οικονομικό και αποτελείται από τρεις τύπους παικτών: (α) Συγγραφείς των εγγράφων (Document Authors), που διαθέτουν περιεχόμενο στον Παγκόσμιο Ιστό. (β) Χρήστες (Users) που αναζητούν χρήσιμη πληροφορία στον Παγκόσμιο Ιστό και (γ) Μια μηχανή αναζήτησης (Search Engine),η οποία σκοπό έχει να βοηθά το χρήστη να ανακαλύψει τα έγγραφα που τον ενδιαφέρουν. Κατά το μοντέλο αυτό, ο παγκόσμιος ιστός δημιουργείται από την αλληλεπίδραση των προαναφερθέντων παικτών, κάθε ένας εκ των οποίων ενδιαφέρεται να αποκομίσει το μέγιστο δυνατό όφελος από την αλληλεπίδραση με τους άλλους παίκτες. Βασικό στοιχείο του μοντέλου αποτελεί η ωφελιμότητα U(i,d) η οποία συσχετίζει το χρήστη i με το έγγραφο d. Τα ενδιαφέροντα ερωτήματα που εξετάζουμε είναι: Ποιο είναι το τίμημα της αναρχίας της διαδικασίας εξέλιξης του μοντέλου, δηλαδή ποιο τμήμα της συνολικής ωφελιμότητας είναι δυνατόν να πάρουν οι χρήστες από τον αλγόριθμο αναζήτησης? Ποια είναι η τελική μορφή του παγκόσμιου ιστού, σύμφωνα με το μοντέλο αυτό? Από την πειραματική μελέτη της συμπεριφοράς του μοντέλου συμπεραίνουμε ότι η συνολική ωφελιμότητα αυξάνεται όταν οι ωφελιμότητες των χρηστών είναι πιο συγκεντρωμένες (clustered). Επίσης, η κατανομή βαθμών των εγγράφων είναι προφανέστερα κατανομή νόμου δύναμης (power law) στην περίπτωση αυτή. Τέλος, θέτουμε πολλά ενδιαφέροντα ερωτήματα σχετικά με ανταγωνισμό και ποιότητα μηχανών αναζήτησης, αλγορίθμους αναζήτησης και κίνητρα ιστοσελίδων και παραποίηση αποτελεσμάτων μηχανών αναζήτησης (search engine spam).Το δεύτερο μοντέλο είναι παιγνιοθεωρητικό. Ο παγκόσμιος ιστός μοντελοποιείται ως γράφημα, στο οποίο οι κόμβοι παρέχουν πληροφορίες. Ο χώρος στρατηγικών κάθε κόμβου είναι η επιλογή ενός συνόλου εξερχομένων υπερσυνδέσμων, καθώς και η επιλογή των πιθανοτήτων να ακολουθηθεί καθένας από αυτούς. Η ωφελιμότητα που έχει ο κόμβος από τις επιλογές του είναι το γινόμενο δύο όρων: (α) Της κίνησης μέσω του κόμβου (η οποία θα μπορούσε να εκφραστεί από την τιμή PageRank στην αλυσίδα Markov που δημιουργήθηκε από τις ενέργειες του κόμβου) και (β) Της ποιότητας του συγκεκριμένου κόμβου, η οποία εκφράζει την ωφελιμότητα ανά επίσκεψη, όπως για παράδειγμα τη δημιουργία φήμης, ή δυνατότητας κέρδους. Η ποιότητα ενός κόμβου εξαρτάται από το εγγενές περιεχόμενό του, καθώς και από τις τροποποιήσεις στο περιεχόμενο, τις οποίες επιφέρουν οι επιλογές των υπερσυνδέσμων. Ο μοναδικός περιορισμός που θέτουμε στην ποιότητα είναι να είναι κοίλη συνάρτηση της στρατηγικής του κόμβου (της κατανομής δηλαδή πιθανοτήτων στους εξερχόμενους υπερσυνδέσμους). Προτείνουμε ένα φυσικό παράδειγμα μιας τέτοιας συνάρτησης ποιότητας. Αποδεικνύουμε ότι το παιχνίδι που προκύπτει έχει πάντα αμιγή ισορροπία κατά Nash. Τα πειράματα υποδεικνύουν ότι τα σημεία ισορροπίας αυτά υπολογίζονται εύκολα, αποφεύγονται τα αμφίδρομα σημεία ισορροπίας που παρουσιάζονται σε αντίστοιχα μοντέλα της βιβλιογραφίας και έχουν ευνοϊκό τίμημα της αναρχίας. Το προκύπτον ως ισορροπία του παιχνιδιού, γράφημα έχει σε γενικές γραμμές τα χαρακτηριστικά του παγκόσμιου ιστού. Ενδιαφέροντα ανοικτά προβλήματα είναι ο ακριβής χαρακτηρισμός της πολυπλοκότητας εύρεσης των σημείων ισορροπίας και του τιμήματος της αναρχίας.Τέλος, εξετάζουμε πειραματικά δυο ακόμα μοντέλα, τα οποία είναι επεκτάσεις με συναρτήσεις ωφελιμότητας γνωστών μοντέλων δημιουργίας γραφημάτων.