Παιχνίδια τιμολόγησης σε ετερογενή παράλληλα δίκτυα

Σε αυτή τη διπλωματική εργασία μεταπτυχιακού μελετάμε ένα παίγνιο 2 επιπέδων όπου, σε ένα δίκτυο με n ακμές από μια πηγή s σε ένα στόχο t, μια μονάδα ροής θέλει να μετακινηθεί από το s στο t χρησιμοποιώντας την ακμή με το χαμηλότερο κόστος, ενώ οι διαχειριστές των ακμών ανταγωνίζονται για κέρδος βάζοντας δίοδια στις ακμές και δημιουργώντας έτσι ένα παίγνιο συμφόρησης με διόδια. Εξετάζουμε μόνο αφινικές καθυστερήσεις για τις ακμές. Επιπλέον, ο κάθε χρήστης δικτύου αντιδρά στα διόδια με ετερογενές τρόπο, δηλ. ο κάθε παίκτης p στη ροή του δικτύου έχει διαφορετική τιμή ευαισθησίας χρόνου ­χρήματος, η οποία περιγράφεται από μια συνάρτηση κατανομής α(p). Πρώτα παρουσιάζουμε κάποιους βασικούς ορισμούς και ιδιότητες των ομοιογενών παιγνίων κέρδους, τα οποία είναι κυρίως βασισμένα σε προηγούμενες δουλειές, και με αυτά ως βάση, τα επεκτείνουμε για να περιγράψουμε παίγνια κέρδους με ετερογενείς χρήστες. Εισαγάγουμε έναν νέο όρο, τη συνάρτηση διαχωρισμού ευαισθησίας αs(t), ορισμένη για οποιεσδήποτε 2 ακμές του δικτύου ως η τιμή ευαισθησίας χρόνου­χρήματος για την οποία, δωσμένων σετ διοδίων t, τα κόστη των 2 ακμών είναι ίσα. Με τη βοήθεια της αs θα περιγράψουμε μερικές ιδιότητες γύρω από την εγωιστική συμπεριφορά των ετερογενών χρηστών για διαφορετικά διόδια, καθώς και θα αποδείξουμε την ύπαρξη άνω φράγματος για τις τιμές ευαισθησίας που αφορούν το παίγνιο. Στη συνέχεια, φτάνοντας στο κύριο σώμα αυτής της έρευνας, εξετάζουμε την ύπαρξη ισορροπίας Nash στο παίγνιο κέρδους μεταξύ των διαχειριστών των ακμών για διαφορετικές περιπτώσεις ετερογενών χρηστών. Δείχνουμε ότι δεν υπάρχει ισορροπία Nash όταν υπάρχουν πολλοί χρήστες με 0 ευαισθησία, δηλ. παίκτες που δεν επηρρεάζονται από τα διόδια, κάτι το οποίο μας αναγκάζει στο εξής να υποθέσουμε ότι α(p) > 0. Στη συνέχεια, εξετάζουμε περιπτώσεις όπου η συνάρτηση κατανομής είναι σταθερή και άρα η συμπεριφορά των χρηστών παραμένει ομογενής (κάνοντάς τα ψευδο­ετερογενή παίγνια), μέσω των οποίων μετά θα περιγράψουμε πώς συμπεριφέρονται η ροή, τα διόδια και τα σημεία ισορροπίας όταν αυτή η σταθερή τιμή μεταβάλλεται. Χρησιμοποιώντας όλα τα παραπάνω, μελετάμε βηματικές συναρτήσεις κατανομής, όπου, περιορίζοντας το μοντέλο μας σε στιγμιότυπα 2 ακμών, αποδεικνύουμε μια ισχυρή απαίτηση για την τιμή ενός πιθανού σημείου ισορροπίας Nash στο παίγνιο κέρδους μεταξύ των διαχειριστών των ακμών, συνδέοντάς το με το σημείο ισορροπίας σε ένα ισοδύναμο ψευδο­ετερογενές παίγνιο. Εντέλει, παρουσιάζουμε και αναλύουμε έναν αλγόριθμο για τον υπολογισμό αυτού του σημείου ισορροπίας, αν υπάρχει, σε χρόνο γραμμικό σε σχέση με τον πληθάριθμο της βηματικής συνάρτησης, και κλείνουμε με μια συζήτηση για πιθανές μελλοντικές εργασίες.