Σε αυτή τη διπλωματική εργασία μεταπτυχιακού μελετάμε ένα παίγνιο 2 επιπέδων όπου, σε ένα δίκτυο με n ακμές από μια πηγή s σε ένα στόχο t, μια μονάδα ροής θέλει να μετακινηθεί από το s στο t χρησιμοποιώντας την ακμή με το χαμηλότερο κόστος, ενώ οι διαχειριστές των ακμών ανταγωνίζονται για κέρδος βάζοντας δίοδια στις ακμές και δημιουργώντας έτσι ένα παίγνιο συμφόρησης με διόδια. Εξετάζουμε μόνο αφινικές καθυστερήσεις για τις ακμές. Επιπλέον, ο κάθε χρήστης δικτύου αντιδρά στα διόδια με ετερογενές τρόπο, δηλ. ο κάθε παίκτης p στη ροή του δικτύου έχει διαφορετική τιμή ευαισθησίας χρόνου-χρήματος, η οποία περιγράφεται από μια συνάρτηση κατανομής α(p). Πρώτα παρουσιάζουμε κάποιους βασικούς ορισμούς και ιδιότητες των ομοιογενών παιγνίων κέρδους, τα οποία είναι κυρίως βασισμένα σε προηγούμενες δουλειές, και με αυτά ως βάση, τα επεκτείνουμε για να περιγράψουμε παίγνια κέρδους με ετερογενείς χρήστες. Εισαγάγουμε έναν νέο όρο, τη συνάρτηση διαχωρισμού ευαισθησίας, ορισμένη για οποιεσδήποτε 2 ακμές του δικτύου ως η τιμή ευαισθησίας χρόνουχρήματος για την οποία, δωσμένων σετ διοδίων t, τα κόστη των 2 ακμών είναι ίσα. Με τη βοήθειά της θα περιγράψουμε μερικές ιδιότητες γύρω από την εγωιστική συμπεριφορά των ετερογενών χρηστών για διαφορετικά διόδια, καθώς και θα αποδείξουμε την ύπαρξη άνω φράγματος για τις τιμές ευαισθησίας που αφορούν το παίγνιο. Στη συνέχεια, φτάνοντας στο κύριο σώμα αυτής της έρευνας, εξετάζουμε την ύπαρξη ισορροπίας Nash στο παίγνιο κέρδους μεταξύ των διαχειριστών των ακμών για διαφορετικές περιπτώσεις ετερογενών χρηστών. Δείχνουμε ότι δεν υπάρχει ισορροπία Nash όταν υπάρχουν πολλοί χρήστες με 0 ευαισθησία, δηλ. παίκτες που δεν επηρρεάζονται από τα διόδια, κάτι το οποίο μας αναγκάζει στο εξής να υποθέσουμε ότι α(p) > 0. Στη συνέχεια, εξετάζουμε περιπτώσεις όπου η συνάρτηση κατανομής είναι σταθερή και άρα η συμπεριφορά των χρηστών παραμένει ομογενής (κάνοντάς τα ψευδο-ετερογενή παίγνια), μέσω των οποίων μετά θα περιγράψουμε πώς συμπεριφέρονται η ροή, τα διόδια και τα σημεία ισορροπίας όταν αυτή η σταθερή τιμή μεταβάλλεται. Χρησιμοποιώντας όλα τα παραπάνω, μελετάμε βηματικές συναρτήσεις κατανομής, όπου, περιορίζοντας το μοντέλο μας σε στιγμιότυπα 2 ακμών, αποδεικνύουμε μια ισχυρή απαίτηση για την τιμή ενός πιθανού σημείου ισορροπίας Nash στο παίγνιο κέρδους μεταξύ των διαχειριστών των ακμών, συνδέοντάς το με το σημείο ισορροπίας σε ένα ισοδύναμο ψευδο-ετερογενές παίγνιο. Εντέλει, παρουσιάζουμε και αναλύουμε έναν αλγόριθμο για τον υπολογισμό αυτού του σημείου ισορροπίας, αν υπάρχει, σε χρόνο γραμμικό σε σχέση με τον πληθάριθμο της βηματικής συνάρτησης, και κλείνουμε με μια συζήτηση για πιθανές μελλοντικές εργασίες.
(EL)
In this masters thesis we study a 2-level game where, on an n-link network from a source s to a target t, a unit of flow wants to move from s to t using the link with the lowest cost, while the link operators compete for profit by assigning tolls to links and thus creating a toll congestion game. We examine only affine latencies for the links. In addition, each flow user responds to tolls in a heterogeneous way, i.e. each player p in the flow has a different time-money sensitivity value, which is described by a distribution function α(p). We first present some definitions and properties of pricing homogeneous games, heavily based on previous work, and using them as base, we extend them to describe pricing games with heterogeneous users. We introduce a new term, the sensitivity split function, defined for any 2 links of the network as the time-money sensitivity value for which, given a set of tolls t, the link costs are equal. With its help we describe some properties around the selfish behaviour of heterogeneous users for different tolls, as well as prove the existence of bounds for the sensitivity values that are relevant to the game. Then, arriving at the main body of this study, we investigate the existence of a Nash Equilibrium in the profit game between the link operators for different cases of heterogeneous users. We show there is no Nash Equilibrium when there are many users with 0 sensitivity, i.e. players not affected by tolls, forcing us to assume onward α(p) > 0. We then investigate cases of fixed distribution functions, where the user behaviour remains homogeneous (making them pseudo-heterogeneous games), through which we then describe how flow, tolls and equilibria behave as that fixed value changes. Using all the above, we study step distribution functions, where, by limiting our scope to 2 links, we prove a strong requirement for the value of a potential Nash Equilibrium in the profit game between the link operators, connecting it to the equilibrium of an equivalent pseudo-heterogeneous game. We finally present and analyse an algorithm that calculates that equilibrium, if it exists, in time linear with regard to the step function's cardinality, and we finish with some discussion about potential future work.
(EN)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
