Μελέτη δρομολογήσεων και συμφόρησης σε δίκτυα με βάση τη Θεωρία Παιγνίων

• Κύριος συγγραφέας: Παναγοπούλου, Παναγιώτα
• Άλλοι συγγραφείς: Σπυράκης, Παύλος
• Έκδοση: 2007
• Θέματα: Θεωρία παιγνίων; Παίγνια συμφόρησης; Παίγνια δυναμικού; Game theory; Congestion games; Potential games; Price of anarchy; 519.82

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