Back to search

National and Kapodistrian University of Athens

Pricing Games in Heterogeneous Parallel Networks

Abstract

dc:description

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

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Παππάς Θωμάς
  • Pappas Thomas

Subjects

dc:subject × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:3463709

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Παππάς Θωμάς; Pappas Thomas. Pricing Games in Heterogeneous Parallel Networks. 2025. https://pergamos.lib.uoa.gr/uoa/dl/object/3463709