Παίγνια συμφόρησης: στοχαστικές επεκτάσεις και τεχνικές μείωσης του τιμήματος της αναρχίας

Abstract

The subject of this thesis is the theoretical analysis and generalization of congestion games models and it aims to provide a study on methods for reducing the Price of Anarchy and a study related to stochastic extensions of congestion games and in which extend the Price of Anarchy may be affected within them. First, the literature that relates mostly to the problems studied is presented and rightafter an extensive presentation of the results of the thesis follows. The problem of finding or approximating the best subnetwork in bottleneck routing games is studied. Although the corresponding problem in additive costs congestion games is almost fully understood, for the problem studied here, the existing results hold for more general games and in fact are much weaker than the ones presented here. For the simplest version of this problem, via a complex reduction, an NP hardness results for finding or approximating the best subnetwork of the underlying network is proved: it is NP hard to approximate the best subnetwork by a factor less than O(n^0.121) (where n is the number of nodes of the network). In the positive side it is proven that in some subclasses of these games the paradox does not appear at all and also it is given an approximation algorithm for some cases where the NP hardness reductions cannot apply. Results that have to do with Braess paradox in additive costs congestion games are presented. Prior to the work presented here, it has been proved that if the underlying network of a congestion game is a random Erdos-Renyi graph then with high probability it suffers from Braess Paradox. Here, it is proven that the problem of finding the best subnetwork in such random networks can be essentially reduced to the problem of finding the best subnetwork of a network belonging to the simplest class of graphs that may suffer from the paradox. Using a very recent result from the theory of probabilities, it is given a polynomial approximation algorithm for finding best subnetworks in such networks. Then, the expansion properties of Erdos-Renyi graphs are used and an approximately good subnetwork for the initial network is drawn.By slightly changing direction, the basic properties of congestion games with uncertain delays and risk averse users are studied. The classic formulation of congestion games ignores uncertainty in delays that arises in many real life situations. Modelling the cause of uncertainty in delays, two orthogonal models are introduced, one with stochastic players, where each players participates in the game with a given probability and thus the actual delay on the edges that players choose gets uncertain, and another with stochastic edges where each edge, with a given probability, may ‘‘fail’’ and provide greater delay to the players using it. For the arising classes of games, the existence of pure Nash equilibrium and potentials and the behaviour of the price of anarchy is studied. Uniting the above directions, a new way for improving the price of anarchy in congestion games with uncertain delays and risk averse users is given. More specifically, it is shown that if one can insert uncertainty in the edges of the network in a way that the expected cost of those edges remains the same, then, because of the risk aversion of the players, these edges become less attractive for the players. Thus, the price of anarchy may improve as more players may turn to edges that the optimal solution would choose for them. The arising algorithmic problem relates to congestion games with restricted tolls and results can also be drawn from there. In this thesis Karush-Kuhn-Tucker conditions are closely followed and there are given results that give a better and ‘‘less cheap’’ use of extra uncertainty and provide better insight of the improvement in the price of anarchy.

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