Η πτυχιακή αυτή πραγματεύεται θέματα της Αλγοριθμικής Θεωρίας Παιγνίων.
Εστιάζουμε
σε δικτυακά παίγνια συμφόρησης, όπου οι παίκτες διαλέγουν μονοπάτια στο δίκτυο
σκε-
φτόμενοι, εγωιστικά, μόνο την ελαχιστοποίηση του δικού τους κόστους. Η επιλογή
τους
έχει άμεσο αντίκτυπο στους υπόλοιπους παίκτες, καθώς η καθυστέρηση κάθε ακμής
του
δικτύου είναι μη-φθήνουσα συνάρτηση του αριθμού των παικτών που την
χρησιμοποιούν.
Το ντετερμινιστικό μοντέλο των παίγνιων συμφόρησης έχει μελετηθεί εξαντλητικά
και είναι
πλήρως κατανοητό από την επιστημονική κοινότητα.
Παρ’όλα αυτά, είναι αφύσικο να υποθέσουμε πως οι παίκτες έχουν ακριβή γνώση της
(ντερμινιστικής) καθυστέρησης σε κάθε ακμή, καθώς στην καθημερινή ζωή μια τέτοια
πρόβλεψη είναι αδύνατη. Έτσι, προέκυψε μια καινούργια ερευνητική κατεύθυνση,
αυτή
των στοχαστικών παίγνιων συμφόρησης με παίκτες που “αποστρέφονται το ρίσκο”
(risk-
averse). Έχουν προταθεί διάφορες επεκτάσεις για να μοντελοποιήσουν την
στοχαστική
φύση των πραγματικών δικτύων. Παρουσιάζουμε μια ποικιλία από αυτές, σε καθεμία
από
τις οποίες οι παίκτες αντιλαμβάνονται την αβεβαιότητα με διαφορετικό τρόπο.
Μελετάμε
την ύπαρξη ισορροπίας και τον υπολογισμό της καθώς επίσης και το Τίμημα της
Αναρχίας,
μια σημαντική έννοια που παρέχει εγγυήσεις για την καλή λειτουργία του δικτύου.
Τέλος, αναρωτιόμαστε αν η αβεβαίοτητα μπορεί σε κάποιες περιπτώσεις να συμβάλλει
στη βελτίωση αυτής της λειτουργίας. Σε αυτή την κατεύθυνση προτείνουμε ένα νεό
μο-
ντέλο στο οποίο εισάγουμε σκόπιμα θόρυβο (μέχρι ενός ορίου) σε κάποιες ακμές
ώστε
κάποιοι παίκτες, για να αποφύγουν τον κίνδυνο να μην τις χρησιμοποιήσουν και η
συνο-
λική απόδοση του δικτύου να βελτιωθεί λόγω μείωσης της συμφόρησης. Αποδεικνύουμε
την ύπαρξη ισορροπίας σε δίκτυα παράλληλων ακμών για ομογενείς και ετερογενείς
παί-
κτες, και σε σειριακά-παράλληλα δίκτυα (series-parallel networks) για ομογενείς
παίκτες.
Επιπλέον μετράμε την βελτίωση του Τιμήματος της Αναρχίας λόγω της αβεβαιότητας.
Κα-
τόπιν, εξετάζουμε μια γενίκευση του μοντέλου μας, στην οποία επιτρέπουμε ένα
συνολικό
όριο στο θόρυβο που θα εισαχθεί στο δίκτυο αντί για ένα όριο για κάθε ακμή.
Αποδεικνύ-
ουμε ότι τα δύο αυτά μοντέλα είναι ασυμπτωτικά όμοια, με την έννοια ότι δεν
μπορούμε
να πετύχουμε καλύτερα αποτελέσματα με το δεύτερο μοντέλο, στη χειρότερη
περίπτωση,
από όταν μοιράζουμε το θόρυβο ομοιόμορφα στις ακμές του δικτύου.
(EL)
This Bachelor thesis lies in the area of Algorithmic Game Theory. We focus on
Network
Congestion Games where selfish players choose their path in the network aiming
at minimizing
their perceived delay. Their choice has direct effect on the rest of the
players, since the
delay of every edge in the network is a non-decreasing function of the amount
of agents
using it. The deterministic model of congestion games has been extensively
studied and
is considered well-understood.
However, it seems unnatural to assume that players have precise knowledge of
the (deterministic)
edge latencies, since in real life situations, players cannot accurately
predict the actual
edge delays. Thus, a new research direction arised, that of stochastic
congestion games
with risk-averse players. Many different models trying to capture the
stochastic nature of
real life networks have been proposed. We present a variety of models, where
players
aim to minimize different objectives. We study the equilibrium existence and
computation,
and measure the Price of Anarchy (PoA), an important notion that provides
performance
guarantees for the function of the network.
Finally, we ask the question whether uncertainty can, in some cases, be used as
a means
to improve the performance of the network. In this direction we propose a new
model in
which we intensively introduce noise up to an allowed limit in some of the
edges so that the
risk-averse players will avoid using them and the overall performance will be
improved. We
provide theorems that guarantee equilibrium existence in parallel-arc and
series-parallel
networks for homogeneous players and in parallel-arc networks for heterogeneous
players
and we measure the potential improvement in the PoA due to the uncertainty.
Then we
study a generalization of our model where we have an overal limit in the noise
we can
place in the network instead of a limit for every arc. We prove that these two
models are
asumptotically identical, meaning we cannot improve the PoA more, in the worst
case,
than when we separate the noise uniformly among the edges.
(EN)
/aggregator-openarchives/portal/institutions/uoa
