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

Ένα από τα πλέον σημαντικά θέματα στην επιστήμη των υπολογιστών είναι η σχεδίαση δικτύων επικοινωνιών και κατανεμημένων συστημάτων μεγάλης απόδοσης. ΄Ενα τέτοιο δίκτυο μεγάλης εμβέλειας είναι το Διαδίκτυο, του οποίου η ραγδαία ανάπτυξη τα τελευταία χρόνια ωθεί τους ερευνητές σε συνεχείς μελέτες μ...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριος συγγραφέας: Τσοκανά, Σοφία
Άλλοι συγγραφείς: Κακλαμάνης, Χρήστος
Μορφή: Thesis
Γλώσσα:Greek
Έκδοση: 2016
Θέματα:
Διαθέσιμο Online:http://hdl.handle.net/10889/9154
id nemertes-10889-9154
record_format dspace
spelling nemertes-10889-91542022-09-05T05:00:13Z Μελέτη παιγνίων δημιουργίας δικτύου Τσοκανά, Σοφία Κακλαμάνης, Χρήστος Κακλαμάνης, Χρήστος Νικολετσέας, Σωτήρης Καραγιάννης, Ιωάννης Tsokana, Sofia Παίγνια Ισορροπία Δίκτυα επικοινωνιών Φράγμα Εγωιστές χρήστες Δρομολόγηση Τίμημα αναρχίας Απόδοση Games Equilibrium Communication networks Bounds Selfish players Routing Anarchy price Nash 004.65 Ένα από τα πλέον σημαντικά θέματα στην επιστήμη των υπολογιστών είναι η σχεδίαση δικτύων επικοινωνιών και κατανεμημένων συστημάτων μεγάλης απόδοσης. ΄Ενα τέτοιο δίκτυο μεγάλης εμβέλειας είναι το Διαδίκτυο, του οποίου η ραγδαία ανάπτυξη τα τελευταία χρόνια ωθεί τους ερευνητές σε συνεχείς μελέτες με σκοπό την μεγιστοποίηση της απόδοσής του, ή εναλλακτικά την ελαχιστοποίηση του κόστους επικοινωνίας των χρηστών. Η ιδιαιτερότητα του Διαδικτύου έγκειται στο ότι δεν υπάρχει κάποια κεντρική αρχή που να ελέγχει τις κινήσεις των χρηστών. Αντιθέτως, κάθε χρήστης κινείται με μοναδικό κίνητρο την μεγιστοποίησvη του προσωπικού του οφέλους και δεν υπάρχει κεντρικός συντονισμός. Στην παρούσα διπλωματική εργασία, στο πλαίσιο του Μεταπτυχιακού Διπλώματος Ειδί- κευσης Επιστήμη και Τεχνολογία Υπολογιστών, ασχολούμαστε με προβλήματα απόδοσης δικτύων επικοινωνίας στην περίπτωση που οι χρήστες είναι εγωιστές. Πιο συγκεκριμένα, εξετάζουμε το πρόβλημα από παιγνιοθεωρητική σκοπιά, μελετώντας μία ειδική κατηγορία παιγνίων, τα Παίγνια Δημιουργίας Δικτύου. Τα Παίγνια Δημιουργίας Δικτύου είναι παίγνια στα οποία μοντελοποιείται ο τρόπος με τον οποίο ένα δίκτυο εξελίσσεται από τις επιλογές των χρηστών, καθορίζοντας την τελική του μορφή. Οι χρήστες έχουν ένα σύνολο στρατηγικών το οποίο αποτελείται από ενέργειες, οι οποίες στοχεύουν στο να μειώσουν την αντικειμενική συνάρτηση κόστους, όπως αυτή ορίζεται σε κάθε μοντέλο. Οι παράγοντες που επηρεάζουν τη δομή του δικτύου και ο τρόπος με τον οποίο αυτοί οι μηχανισμοί λειτουργούν ορίζονται διαφορετικά στο κάθε μοντέλο. Στην εργασία, εξετάζουμε την ύπαρξη ισορροπίας στο τελικό δίκτυο. Με άλλα λόγια, εστιάζουμε στην ύπαρξη σταθερού δικτύου, όπου κανείς παίκτης δεν έχει κίνητρο να αλλάξει τις επιλογές του για να βελτιώσει την κατάστασή του. Σε πρώτη φάση, αντικείμενο της διπλωματικής εργασίας είναι η βιβλιογραφική μελέτη αυτού του ερευνητικού πεδίου, καθώς και η παρουσίαση συγκεκριμένων μοντέλων και απο- τελεσμάτων από την πολύ πρόσφατη βιβλιογραφία. Στη συνέχεια, εμβαθύνουμε στα μοντέλα με τα οποία ασχολούμασvτε και μεταξύ άλλων μελετάμε την τιμή του κόστους της αναρχίας. Το κόστος της αναρχίας ή αλλιώς τίμημα της αναρχίας, ορίστηκε ως η ποσότητα για τη μέτρηση της απόρροιας της έλλειψης συντονισμού. Πρόκειται για τον λόγο του κοινωνικού κόστους της χειρότερης ισορροπίας του παιγνίου προς το κοινωνικό κόστος της βέλτιστης λύσης. Η ανάλυση εστιάζει στην απόδειξη νέων φραγμάτων για το κόστος της αναρχίας σε συγκεκριμένα μοντέλα παιγνίων δημιουργίας δικτύου. In this Master thesis we study the yield problems in communication networks in which players act selfishly, i.e. they try to maximize their own utility function (minimize their cost function). Νetwork formation games model the way a network is modified to its final form as users (players) act from their strategic profile. Each player has a set of strategies from which they choose in order to minimize a certain cost function, differently applied in each model. We study the existence of equilibria in such games. In other words we study the circumstances under which, a network is said to be stable, i.e. no player has an incentive to alter their strategy. Firstly, we present and explain the recent studies in this field. Secondly, we go deeper in specific models presented and we study the price of anarchy. The analysis focuses in proving new bounds on the price of anarchy in certain models in the field of network formation games. 2016-02-01T13:01:50Z 2016-02-01T13:01:50Z 2014-11-11 Thesis http://hdl.handle.net/10889/9154 gr 0 application/pdf
institution UPatras
collection Nemertes
language Greek
topic Παίγνια
Ισορροπία
Δίκτυα επικοινωνιών
Φράγμα
Εγωιστές χρήστες
Δρομολόγηση
Τίμημα αναρχίας
Απόδοση
Games
Equilibrium
Communication networks
Bounds
Selfish players
Routing
Anarchy price
Nash
004.65
spellingShingle Παίγνια
Ισορροπία
Δίκτυα επικοινωνιών
Φράγμα
Εγωιστές χρήστες
Δρομολόγηση
Τίμημα αναρχίας
Απόδοση
Games
Equilibrium
Communication networks
Bounds
Selfish players
Routing
Anarchy price
Nash
004.65
Τσοκανά, Σοφία
Μελέτη παιγνίων δημιουργίας δικτύου
description Ένα από τα πλέον σημαντικά θέματα στην επιστήμη των υπολογιστών είναι η σχεδίαση δικτύων επικοινωνιών και κατανεμημένων συστημάτων μεγάλης απόδοσης. ΄Ενα τέτοιο δίκτυο μεγάλης εμβέλειας είναι το Διαδίκτυο, του οποίου η ραγδαία ανάπτυξη τα τελευταία χρόνια ωθεί τους ερευνητές σε συνεχείς μελέτες με σκοπό την μεγιστοποίηση της απόδοσής του, ή εναλλακτικά την ελαχιστοποίηση του κόστους επικοινωνίας των χρηστών. Η ιδιαιτερότητα του Διαδικτύου έγκειται στο ότι δεν υπάρχει κάποια κεντρική αρχή που να ελέγχει τις κινήσεις των χρηστών. Αντιθέτως, κάθε χρήστης κινείται με μοναδικό κίνητρο την μεγιστοποίησvη του προσωπικού του οφέλους και δεν υπάρχει κεντρικός συντονισμός. Στην παρούσα διπλωματική εργασία, στο πλαίσιο του Μεταπτυχιακού Διπλώματος Ειδί- κευσης Επιστήμη και Τεχνολογία Υπολογιστών, ασχολούμαστε με προβλήματα απόδοσης δικτύων επικοινωνίας στην περίπτωση που οι χρήστες είναι εγωιστές. Πιο συγκεκριμένα, εξετάζουμε το πρόβλημα από παιγνιοθεωρητική σκοπιά, μελετώντας μία ειδική κατηγορία παιγνίων, τα Παίγνια Δημιουργίας Δικτύου. Τα Παίγνια Δημιουργίας Δικτύου είναι παίγνια στα οποία μοντελοποιείται ο τρόπος με τον οποίο ένα δίκτυο εξελίσσεται από τις επιλογές των χρηστών, καθορίζοντας την τελική του μορφή. Οι χρήστες έχουν ένα σύνολο στρατηγικών το οποίο αποτελείται από ενέργειες, οι οποίες στοχεύουν στο να μειώσουν την αντικειμενική συνάρτηση κόστους, όπως αυτή ορίζεται σε κάθε μοντέλο. Οι παράγοντες που επηρεάζουν τη δομή του δικτύου και ο τρόπος με τον οποίο αυτοί οι μηχανισμοί λειτουργούν ορίζονται διαφορετικά στο κάθε μοντέλο. Στην εργασία, εξετάζουμε την ύπαρξη ισορροπίας στο τελικό δίκτυο. Με άλλα λόγια, εστιάζουμε στην ύπαρξη σταθερού δικτύου, όπου κανείς παίκτης δεν έχει κίνητρο να αλλάξει τις επιλογές του για να βελτιώσει την κατάστασή του. Σε πρώτη φάση, αντικείμενο της διπλωματικής εργασίας είναι η βιβλιογραφική μελέτη αυτού του ερευνητικού πεδίου, καθώς και η παρουσίαση συγκεκριμένων μοντέλων και απο- τελεσμάτων από την πολύ πρόσφατη βιβλιογραφία. Στη συνέχεια, εμβαθύνουμε στα μοντέλα με τα οποία ασχολούμασvτε και μεταξύ άλλων μελετάμε την τιμή του κόστους της αναρχίας. Το κόστος της αναρχίας ή αλλιώς τίμημα της αναρχίας, ορίστηκε ως η ποσότητα για τη μέτρηση της απόρροιας της έλλειψης συντονισμού. Πρόκειται για τον λόγο του κοινωνικού κόστους της χειρότερης ισορροπίας του παιγνίου προς το κοινωνικό κόστος της βέλτιστης λύσης. Η ανάλυση εστιάζει στην απόδειξη νέων φραγμάτων για το κόστος της αναρχίας σε συγκεκριμένα μοντέλα παιγνίων δημιουργίας δικτύου.
author2 Κακλαμάνης, Χρήστος
author_facet Κακλαμάνης, Χρήστος
Τσοκανά, Σοφία
format Thesis
author Τσοκανά, Σοφία
author_sort Τσοκανά, Σοφία
title Μελέτη παιγνίων δημιουργίας δικτύου
title_short Μελέτη παιγνίων δημιουργίας δικτύου
title_full Μελέτη παιγνίων δημιουργίας δικτύου
title_fullStr Μελέτη παιγνίων δημιουργίας δικτύου
title_full_unstemmed Μελέτη παιγνίων δημιουργίας δικτύου
title_sort μελέτη παιγνίων δημιουργίας δικτύου
publishDate 2016
url http://hdl.handle.net/10889/9154
work_keys_str_mv AT tsokanasophia meletēpaigniōndēmiourgiasdiktyou
_version_ 1771297136806199296