Μελέτη παιγνίων δημιουργίας δικτύου
Ένα από τα πλέον σημαντικά θέματα στην επιστήμη των υπολογιστών είναι η σχεδίαση δικτύων επικοινωνιών και κατανεμημένων συστημάτων μεγάλης απόδοσης. ΄Ενα τέτοιο δίκτυο μεγάλης εμβέλειας είναι το Διαδίκτυο, του οποίου η ραγδαία ανάπτυξη τα τελευταία χρόνια ωθεί τους ερευνητές σε συνεχείς μελέτες μ...
Κύριος συγγραφέας: | |
---|---|
Άλλοι συγγραφείς: | |
Μορφή: | 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 |