| Περίληψη: | Στην παρούσα διπλωματικής εργασία εφαρμόζουμε τις αρχές της Θεωρίας Παιγνίων, και συγκεκριμένα τις έννοιες των Ισορροπιών Nash και των Παιγνίου Συμφόρησης, ώστε να αναλύσουμε την επίδραση που έχει στην καθολική απόδοση ενός δικτύου και γενικότερα ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του.
Αρχικά ασχολούμαστε με το πρόβλημα της εγωιστικής δρομολόγησης φορτίων από μια κοινή πηγή προς έναν κοινό προορισμό σε ένα δίκτυο επικοινωνίας. Σε ένα τέτοιο περιβάλλον οι χρήστες επιλέγουν εγωιστικά τις στρατηγικές τους, οι οποίες στην περίπτωση μας αντιστοιχούν σε μονοπάτια από την πηγή προς τον προορισμό Όταν οι χρήστες δρομολογούν τα φορτία τους σύμφωνα με τις στρατηγικές που επιλέγουν, έρχονται αντιμέτωποι με μια καθυστέρηση που προκαλείται από τα φορτία όλων των χρηστών καθώς διαμοιράζονται τις ακμές. Κάθε χρήστης στοχεύει στην ελαχιστοποίηση του εγωιστικού τον κόστους, που αντιστοιχεί σε αυτήν ακριβώς την καθυστέρηση, γεγονός που συνήθως έρχεται σε αντίθεση με το στόχο της βελτιστοποίησης της καθολικής απόδοσης του δικτύου.
Η θεωρία των ισορροπιών Nash μας παρέχει μία σημαντική αρχή επίλυσης για τέτοιου είδους καταστάσεις: μια ισορροπία Nash, είναι μια κατάσταση του συστήματος τέτοια ώστε δεν υπάρχει κάποιος χρήστης που να μπορεί να μειώσει το εγωιστικό του κόστος αλλάζοντας μονομερώς τη στρατηγική του. Σε ένα τέτοιο δίκτυο λοιπόν περιμένουμε οι χρήστες να καταλήξουν σε μια ισορροπία Nash. Ωστόσο, ο υπολογισμός μιας τέτοιας ισορροπίας παραμένει ένα πρόβλημα του οποίου η πολυπλοκότητα είναι, στη γενική περίπτωση, άγνωστη.
Στα πλαίσια αυτής της διπλωματικής εργασίας δείχνουμε πειραματικά ότι ο υπολογισμός μιας αγνής ισορροπίας Nash σε ένα περιβάλλον εγωιστικής δρομολόγησης, όπου η καθυστέρηση σε κάθε ακμή ισούται με το φορτίο της. μπορεί να γίνει σε πολυωνυμικό χρόνο για μια μεγάλη ποικιλία δικτύων και κατανομών των φορτίων των χρηστών. Επιπλέον, προτείνουμε μια αρχική ανάθεση χρηστών σε μονοπάτια η οποία, όπως δείχνουν οι προσομοιώσεις μας, οδηγεί σε μια αξιοσημείωτη μείωση του συνολικού αριθμού των βημάτων που απαιτούνται ώστε να καταλήξουμε σε μια αγνή ισορροπία Nash. Επίσης αποδεικνύουμε την ύπαρξη αγνών ισορροπιών Nash και για την περίπτωση που η καθυστέρηση σε κάθε ακμή είναι εκθετική συνάρτηση του φορτίου της.
Στη συνέχεια προτείνουμε και αναλύουμε ένα νέο μηχανισμό κόστους που θέτει τιμές για την ανταγωνιστική χρησιμοποίηση πόρων από ένα σύνολο χρηστών. Το βασικό πλεονέκτημα αυτού του μηχανισμού είναι ότι οι πόροι θέτουν τα κόστη με έναν ισοδύναμο, δίκαιο τρόπο, και το πλέον σημαντικό είναι ότι κανένας πόρος δεν επωφελείται εις βάρος των χρηστών.
Αυτός ο δίκαιος μηχανισμός κόστους επαγάγει ένα μη συνεργατικό παίγνιο μεταξύ των χρηστών, για το οποίο αναλύουμε τις ισορροπίες Nash. Αποδεικνύουμε ότι δεν υπάρχουν αγνές ισορροπίες Nash, εκτός από την περίπτωση όπου όλα τα φορτία είναι ίσα, ενώ δείχνουμε ότι υπάρχει πάντα μία πλήρως μικτή ισορροπία Nash. Επίσης αναλύουμε για το παίγνιο αυτό το Κόστος της Αναρχίας, που εκφράζει την απόκλιση της απόδοσης του συστήματος στη χειρότερη ισορροπία Nash από τη βέλτιστη απόδοση. Αποδεικνύουμε ότι το Κόστος της Αναρχίας στη χειρότερη περίπτωση είναι γραμμικό ως προς το πλήθος των χρηστών και ότι το φράγμα αυτό είναι αυστηρό. Ωστόσο προτείνουμε δύο τρόπους για να μετριάσουμε τη δυσάρεστη αυτή διαπίστωση.
Καταρχήν, μελετάμε την περίπτωση όπου τα φορτία των χρηστών επιλέγονται από μία πολύ ευρεία οικογένεια φραγμένων κατανομών πιθανότητας. Ορίζουμε το Διαχεόμενο Κόστος της Αναρχίας το οποίο λαμβάνει υπόψη την κατανομή πιθανότητας των φορτίων και αποδεικνύουμε ότι Διαχεόμενο Κόστος της Αναρχίας φράσσεται εκ των άνω από μία μικρή σταθερά. Επιπλέον, προτείνουμε έναν υβριδικό μηχανισμό κόστους, ο οποίος επιτυγχάνει ένα σημαντικά μικρότερο Κόστος της Αναρχίας, ενώ το κέρδος κάθε πόρου παραμένει αμελητέο.
|
|---|
