Μελέτη παιγνίων δημιουργίας δικτύου

• Κύριος συγγραφέας: Τσοκανά, Σοφία
• Άλλοι συγγραφείς: Κακλαμάνης, Χρήστος
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2016
• Θέματα: Παίγνια; Ισορροπία; Δίκτυα επικοινωνιών; Φράγμα; Εγωιστές χρήστες; Δρομολόγηση; Τίμημα αναρχίας; Απόδοση; Games; Equilibrium; Communication networks; Bounds; Selfish players; Routing; Anarchy price; Nash; 004.65

Ένα από τα πλέον σημαντικά θέματα στην επιστήμη των υπολογιστών είναι η σχεδίαση δικτύων επικοινωνιών και κατανεμημένων συστημάτων μεγάλης απόδοσης. ΄Ενα τέτοιο δίκτυο μεγάλης εμβέλειας είναι το Διαδίκτυο, του οποίου η ραγδαία ανάπτυξη τα τελευταία χρόνια ωθεί τους ερευνητές σε συνεχείς μελέτες με σκοπό την μεγιστοποίηση της απόδοσής του, ή εναλλακτικά την ελαχιστοποίηση του κόστους επικοινωνίας των χρηστών. Η ιδιαιτερότητα του Διαδικτύου έγκειται στο ότι δεν υπάρχει κάποια κεντρική αρχή που να ελέγχει τις κινήσεις των χρηστών. Αντιθέτως, κάθε χρήστης κινείται με μοναδικό κίνητρο την μεγιστοποίησvη του προσωπικού του οφέλους και δεν υπάρχει κεντρικός συντονισμός. Στην παρούσα διπλωματική εργασία, στο πλαίσιο του Μεταπτυχιακού Διπλώματος Ειδί- κευσης Επιστήμη και Τεχνολογία Υπολογιστών, ασχολούμαστε με προβλήματα απόδοσης δικτύων επικοινωνίας στην περίπτωση που οι χρήστες είναι εγωιστές. Πιο συγκεκριμένα, εξετάζουμε το πρόβλημα από παιγνιοθεωρητική σκοπιά, μελετώντας μία ειδική κατηγορία παιγνίων, τα Παίγνια Δημιουργίας Δικτύου. Τα Παίγνια Δημιουργίας Δικτύου είναι παίγνια στα οποία μοντελοποιείται ο τρόπος με τον οποίο ένα δίκτυο εξελίσσεται από τις επιλογές των χρηστών, καθορίζοντας την τελική του μορφή. Οι χρήστες έχουν ένα σύνολο στρατηγικών το οποίο αποτελείται από ενέργειες, οι οποίες στοχεύουν στο να μειώσουν την αντικειμενική συνάρτηση κόστους, όπως αυτή ορίζεται σε κάθε μοντέλο. Οι παράγοντες που επηρεάζουν τη δομή του δικτύου και ο τρόπος με τον οποίο αυτοί οι μηχανισμοί λειτουργούν ορίζονται διαφορετικά στο κάθε μοντέλο. Στην εργασία, εξετάζουμε την ύπαρξη ισορροπίας στο τελικό δίκτυο. Με άλλα λόγια, εστιάζουμε στην ύπαρξη σταθερού δικτύου, όπου κανείς παίκτης δεν έχει κίνητρο να αλλάξει τις επιλογές του για να βελτιώσει την κατάστασή του. Σε πρώτη φάση, αντικείμενο της διπλωματικής εργασίας είναι η βιβλιογραφική μελέτη αυτού του ερευνητικού πεδίου, καθώς και η παρουσίαση συγκεκριμένων μοντέλων και απο- τελεσμάτων από την πολύ πρόσφατη βιβλιογραφία. Στη συνέχεια, εμβαθύνουμε στα μοντέλα με τα οποία ασχολούμασvτε και μεταξύ άλλων μελετάμε την τιμή του κόστους της αναρχίας. Το κόστος της αναρχίας ή αλλιώς τίμημα της αναρχίας, ορίστηκε ως η ποσότητα για τη μέτρηση της απόρροιας της έλλειψης συντονισμού. Πρόκειται για τον λόγο του κοινωνικού κόστους της χειρότερης ισορροπίας του παιγνίου προς το κοινωνικό κόστος της βέλτιστης λύσης. Η ανάλυση εστιάζει στην απόδειξη νέων φραγμάτων για το κόστος της αναρχίας σε συγκεκριμένα μοντέλα παιγνίων δημιουργίας δικτύου.