Παίγνια συμφόρησης
Authors: Λιανέας Αθανάσιος 
Published: September 2021

Το αντικείμενο της διατριβής είναι η θεωρητική ανάλυση και γενίκευση μοντέλων παιγνίων συμφόρησης, με στόχο την μελέτη μεθόδων μείωσης του Τιμήματος της Αναρχίας και τη μελέτη στοχαστικών επεκτάσεων των παιγνίων συμφόρησης με παράλληλη έρευνα του κατά πόσο μπορούν αυτές να επηρεάσουν, είτε θετικά είτε αρνητικά, το Τίμημα της Αναρχίας. Αρχικά, παρουσιάζονται βασικά στοιχεία της βιβλιογραφίας που έχουν άμεση σχέση με τα προβλήματα που μελετήθηκαν και στην συνέχεια ακολουθεί μια εκτεταμένη παρουσίαση των αποτελεσμάτων της εργασίας. Παρουσιάζονται αποτελέσματα που αφορούν το παράδοξο του Braess σε παίγνια συμφόρησης όπου το κόστος κάθε παίκτη ισούται με το κόστος της πιο ακριβής ακμής (ακμή συμφόρησης) που χρησιμοποιεί και το κόστος του δικτύου ισούται με το κόστος της πιο ακριβής ακμής που χρησιμοποιείται. Μελετάται το πρόβλημα εύρεσης έστω και προσεγγιστικά καλύτερου υποδικτύου σε τέτοιου είδους παίγνια. Παρότι το αντίστοιχο πρόβλημα σε παίγνια με προσθετικά κόστη είχε κατηγοριοποιηθεί από πλευράς χρονικής πολυπλοκότητας για το εν λόγω πρόβλημα υπήρχαν κάποια αποτελέσματα μόνο για γενικεύσεις του και μάλιστα αρκετά πιο ασθενή από αυτά που παρουσιάζονται στην διατριβή. Για την πιο απλή εκδοχή του προβλήματος, μέσω μιας σύνθετης αναγωγής, αποδεικνύονται αποτελέσματα δυσκολίας στην προσέγγιση του καλύτερου υποδικτύου: είναι ΝΡ-δύσκολο το πρόβλημα εύρεσης έστω και Ο(n^0.121) προσεγγιστικά καλού υποδικτύου (όπου n ο αριθμός κόμβων δικτύου). Παράλληλα καταδεικνύονται δύο υποκατηγορίες τέτοιων παιγνίων που δεν πάσχουν καθόλου από το παράδοξο ενώ δίνεται ένας προσεγγιστικός αλγόριθμος για την περιπτώσεις δικτύων όπου η αναγωγή της απόδειξης της ΝΡ-δυσκολίας δεν μπορεί να εφαρμοστεί.Παρουσιάζονται, επίσης, αποτελέσματα που έχουν να κάνουν με το παράδοξο του Braess σε παίγνια συμφόρησης με προσθετικά κόστη. Για τέτοιου είδους παίγνια επάνω σε Erdos-Renyi τυχαίους γράφους (ως υποκείμενα δίκτυα) έχει αποδειχτεί ότι με μεγάλη πιθανότητα εμφανίζεται το παράδοξο του Braess. Στην εργασία αυτή, το πρόβλημα εύρεσης καλύτερου υποδικτύου σε τέτοιου είδους παίγνια, διαισθητικά ανάγεται σε πρόβλημα εύρεσης καλύτερου υποδικτύου σε παίγνια όπου το υποκείμενο δίκτυο ανήκει στην πιο απλή οικογένεια υποδικτύων που θα μπορούσαν να πάσχουν από το παράδοξο, με την δυσκολία εύρεσης καλύτερου υποδικτύου σε τέτοια δίκτυα να παραμένει άγνωστη. Χρησιμοποιώντας ένα πολύ πρόσφατο αποτέλεσμα από τη θεωρία πιθανοτήτων, δίνεται ένας πολυωνυμικός αλγόριθμος προσέγγισης του καλύτερου υποδικτύου σε τέτοια δίκτυα και ακολούθως, χρησιμοποιώντας τις επεκτατικές ιδιότητες των Erdos-Renyi γράφων, άγεται ένα προσεγγιστικά καλό υποδίκτυο του αρχικού δικτύου.Σε λίγο διαφορετική κατεύθυνση, μελετώνται τα βασικά χαρακτηριστικά παιγνίων συμφόρησης με αβεβαιότητα στις ακμές και παίκτες ευαίσθητους στο ρίσκο. Η κλασική μοντελοποίηση των παιγνίων συμφόρησης αγνοεί την αβεβαιότητα στις ακμές που ενυπάρχει σε αρκετές περιπτώσεις της καθημερινότητας. Μοντελοποιώντας την αιτία της αβεβαιότητας στα κόστη των ακμών, στην εργασία, ορίζονται δύο "ορθογώνια" μοντέλα, ένα με στοχαστικούς παίκτες, όπου οι παίκτες συμμετέχουν ή όχι στο παίγνιο με δεδομένη πιθανότητα και άρα η πραγματική συμφόρηση για τις ακμές που επιλέγουν αποκτά τυχαιότητα, και ένα με στοχαστικές ακμές, όπου οι ακμές δύνανται με κάποια πιθανότητα να έχουν "μη-κανονική" συμπεριφορά και να προσδίδουν μεγαλύτερη καθυστέρηση κατά την χρήση τους. Σε αυτά τα παίγνια γίνεται μελέτη ως προς την ύπαρξη σημείων ισορροπίας και συναρτήσεων δυναμικού ενώ μελετάται και η συμπεριφορά του τιμήματος της αναρχίας.Ενοποιώντας τις δύο κατευθύνσεις, στην εργασία δίδεται ένας νέος τρόπος βελτίωσης του τιμήματος της αναρχίας σε παίγνια με αβεβαιότητα στις ακμές και παίκτες ευαίσθητους στο ρίσκο. Πιο συγκεκριμένα, δείχνεται ότι αν είναι δυνατή η προσθήκη επιπλέον αβεβαιότητας σε επιλεγμένες ακμές με τρόπον ώστε να μην αλλάζει το αναμενόμενο κόστος τους, τότε, λόγω της ευαισθησίας των παικτών στο ρίσκο, αυτές οι ακμές γίνονται λιγότερο προτιμητέες από τους παίκτες και συνεπώς το τίμημα της αναρχίας δύναται να βελτιωθεί λόγω της στροφής των παικτών προς ακμές που η βέλτιστη λύση θα επέλεγε για αυτούς. Το πρόβλημα που ορίζεται προς αυτή την κατεύθυνση μοιάζει με την περιορισμένη χρήση διοδίων σε δίκτυα και αποτελέσματα μπορούν να προκύψουν από εκεί. Στην εργασία δίνονται αποτελέσματα που προσπαθώντας να ακολουθήσουν τις Karush Kuhn Tucker συνθήκες βελτιστότητας δίνουν μια "οικονομικότερη" και καλύτερη διαχείριση της αβεβαιότητας και παρέχουν καλύτερη διαίσθηση για την προκύπτουσα βελτίωση του τιμήματος της αναρχίας.