Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη καταστάσεων ανταγωνισμού μεταξύ χρηστών, για τη χρησιμοποίηση ενός συνόλου κοινόχρηστων πόρων. Για την μοντελοποίηση και ανάλυση των καταστάσεων αυτών χρησιμοποιούμε ως εργαλεία, έννοιες από την θεωρία παιγνίων, όπως ισορροπίες Nash, παίγνια συμφόρησης και μηχανισμοί συντονισμού. Ο κάθε κοινόχρηστος πόρος χρεώνει κάποιο κόστος στους χρήστες που τον χρησιμοποιούν. Θεωρούμε ότι οι χρήστες των κοινόχρηστων πόρων είναι εγωιστικοί, δηλαδή μοναδική τους επιδίωξη είναι η μεγιστοποίηση της προσωπικής τους ωφέλειας. Μια ισορροπία Nash είναι μια κατάσταση όπου κανένας χρήστης δεν μπορεί να αυξήσει το εγωιστικό του όφελος αν αλλάξει μονομερώς την στρατηγική του.
Πιο συγκεκριμένα ασχολούμαστε με το KP-μοντέλο γνωστό και ως μοντέλο παράλληλων ακμών και ιδιαίτερα με μεθόδους σύγκλισης σε αγνές ισορροπίες Nash, όπου δηλαδή οι στρατηγικές (ακμές) των χρηστών είναι ντετερμινιστικές. Γενικά, ένα παίγνιο (σύστημα) δεν έχει πάντα μια αγνή ισορροπία Nash. Ωστόσο, εμείς θα μελετήσουμε περιπτώσεις που εγγυημένα έχουν τουλάχιστον μια αγνή ισορροπία Nash. Ονομάζουμε πολιτική χρέωσης των ακμών τον τρόπο με τον οποίο υπολογίζεται το κόστος του κάθε χρήστη όταν χρησιμοποιεί μια ακμή.
Μια μέθοδος σύγκλισης σε μια αγνή ισορροπία Nash, είναι να επιτραπεί στους χρήστες να αλλάζουν εγωιστικά τις στρατηγικές τους μέχρι να καταλήξουν σε μια αγνή ισορροπία Nash. Ενδιαφερόμαστε για την ταχύτητα σύγκλισης σε μια αγνή ισορροπία Nash, δηλαδή το πλήθος των εγωιστικών αλλαγών στρατηγικών μέχρι να καταλήξουμε σε ισορροπία. Αρχικά, χρησιμοποιείται η πολιτική χρέωσης συνολικού φορτίου (Makespan), όπου κάθε ακμή χρεώνει το συνολικό της φορτίο σε κάθε χρήστη που την χρησιμοποιεί. Στην πιο απλή περίπτωση, η όλη διαδικασία χωρίζεται σε βήματα. Σε κάθε βήμα επιλέγεται, από το σύνολο των χρηστών που έχουν όφελος να αλλάξουν στρατηγική, ένας χρήστης ο οποίος αλλάζει στρατηγική. Η επιλογή γίνεται με βάση κάποιον αλγόριθμο προτεραιότητας. Για το μοντέλο αυτό, που ονομάζεται ESS-μοντέλο, η ταχύτητα σύγκλισης είναι στη χειρότερη περίπτωση εκθετική στο πλήθος των χρηστών. Παρουσιάζουμε την επίδραση των αλγορίθμων προτεραιότητας στην ταχύτητα σύγκλισης καθώς και αποτελέσματα για τρεις διαφορετικές κατηγορίες ακμών. Μια άλλη προσέγγιση, με εφαρμογή στα κατανεμημένα συστήματα, είναι η παράλληλη αλλαγή στρατηγικών από τους χρήστες (rerouting), όπου περισσότεροι από έναν χρήστες μπορούν να αλλάξουν ταυτόχρονα τη στρατηγική τους. Το μοντέλο αυτό υπερτερεί του ESS στην ταχύτητα σύγκλισης καθώς και στο πλήθος των πραγματικών καταστάσεων που μοντελοποιεί. Στη γενικότερη περίπτωση, όπου οι χρήστες επιτρέπεται να συνάπτουν συνασπισμούς (coalitions) μεταξύ τους, χρησιμοποιούμε έννοιες από τη συνεργατική θεωρία παιγνίων. Οπότε έχουμε να αντιμετωπίσουμε ομάδες χρηστών που αλλάζουν εγωιστικά τις ομαδικές στρατηγικές τους. Παρουσιάζουμε ένα ψευδοπολυωνυμικό φράγμα στην ταχύτητα σύγκλισης για μια ειδική περίπτωση όπου οι ακμές είναι πανομοιότυπες και επιτρέπονται συνασπισμοί πλήθους το πολύ δύο χρηστών.
Ένας άλλος τρόπος σύγκλισης σε μια αγνή ισορροπία Nash είναι η κατασκευή ενός αλγορίθμου που αναθέτει στρατηγικές στους χρήστες, όχι απαραίτητα με βάση τα εγωιστικά κριτήρια του καθενός, χωρίς να αυξάνει το κοινωνικό κόστος. Με τον όρο κοινωνικό κόστος αναφερόμαστε σε μια συνολική μετρική της απόδοσης του συστήματος σε συνάρτηση με τις στρατηγικές των χρηστών του συστήματος. Ο αλγόριθμος Nashify που παρουσιάζουμε, συγκλίνει σε μια αγνή ισορροπία Nash σε πολυωνυμικό πλήθος βημάτων, χωρίς να αυξάνει το κοινωνικό κόστος.
Στη συνέχεια, εισάγουμε την έννοια των μηχανισμών συντονισμού. Οι μηχανισμοί συντονισμού είναι ένα σύνολο πολιτικών χρέωσης για τις ακμές, που έχουν ως στόχο την παροχή κινήτρων στους εγωιστικούς χρήστες έτσι ώστε οι εγωιστικές αλλαγές των στρατηγικών τους να συγκλίνουν σε αγνές ισορροπίες Nash με μειωμένο κοινωνικό κόστος. Στην παρούσα εργασία, μελετάμε την επίδραση των μηχανισμών συντονισμού στην ταχύτητα σύγκλισης των εγωιστικών χρηστών σε μια ισορροπία Nash. Εξετάζουμε εκτός από την πολιτική χρέωσης συνολικού φορτίου (makespan) και κάποιες διαφορετικές πολιτικές χρέωσης (SJF, LJF, FIFO) και μελετάμε την επίδραση των αλγορίθμων προτεραιότητας στην ταχύτητα σύγκλισης τους. Παρουσιάζουμε και αποδεικνύουμε φράγματα στην ταχύτητα σύγκλισης για τις SJF και LJF πολιτικές που χρεώνουν τους χρήστες με βάση το μέγεθος των βαρών τους. Τέλος αποδεικνύουμε για την πολιτική χρέωσης FIFO, ένα γραμμικό άνω φράγμα στην ταχύτητα σύγκλισης για την ειδική περίπτωση των πανομοιότυπων ακμών και ένα ψευδοπολυωνυμικό άνω φράγμα για την γενική περίπτωση των ακμών.
Τελικά, αξιολογούμε πειραματικά την επίδραση των αλγορίθμων προτεραιότητας στις πολιτικές χρέωσης στο ESS μοντέλo με πανομοιότυπες ακμές. Ουσιαστικά, συγκρίνουμε τις πολιτικές χρέωσης συνολικού φορτίου, SJF, LJF και FIFO καθώς και το συνεργατικό με το μη συνεργατικό μοντέλο σχετικά με τη ταχύτητα σύγκλισης τους. Παρατηρούμε ότι για την συνολικού φορτίου, SJF, LJF και FIFO πολιτική χρέωσης τα πειραματικά αποτελέσματα επαληθεύουν τα θεωρητικά φράγματα. Δηλαδή η FIFO πολιτική παρουσιάζει ταχύτερη σύγκλιση από τις υπόλοιπες πολιτικές ανεξάρτητα του αλγόριθμου προτεραιότητας. Για την περίπτωση των συνασπισμών με πολιτική χρέωσης συνολικού φορτίου, παρατηρούμε ότι η ταχύτητα σύγκλισης είναι πολυωνυμική στο πλήθος των χρηστών ακόμα και στην χειρότερη επιλογή συνασπισμών. Το αποτέλεσμα αυτό υποδεικνύει ότι το ψευδοπολυωνυμικό θεωρητικό άνω φράγμα μπορεί να βελτιωθεί. / General goal of the current diploma thesis is the study of competitive
situations among users of a set of global resources. In order to analyze
and model these situations we use as tools, game theoretic elements, such
as Nash equilibrium, congestion games and coordination mechanisms. Every
global resource debit a cost value to its users. We assume that the users
are selfish, that is their sole objective is the maximization of their personal
benefit. An Nash equilibrium is a situation in which no user can increase his
personal benefit by changing only his or her own strategy unilaterally.
More specific, we are interested in the KP-model or parallel links model
and we study convergence methods to pure Nash equilibrium, in which all the
strategies a user can select are deterministic. Generally, a game has not
always a pure Nash equilibrium. Although we are going to study cases in
which there is always at least one Nash equilibrium. We define as cost policy
of an edge the function which computes the cost of each user of this edge.
A method of convergence in a pure Nash equilibrium is, starting from an
initial configuration, to allow all users to selfishly change their strategies (one
after the other) until they reach a pure Nash equilibrium. We are interested
in the convergence time to pure Nash equilibrium, that is the number of these
selfish moves. Firstly, we study the makespan cost policy, in which each
edge debits its total load to everyone that use it. In the most simple case,
the whole procedure is divided into several steps. At each step, the priority
algorithm choose one user from the set of users that benefit by changing their
current strategy. For this model, named ESS-model, the convergence time is
at the worst case exponential to the number of users. We present the effect of
several priority algorithms to the convergence time and results for the major
different cases of edges (identical, related, unrelated). Another approach, with
applications to distributed systems, is the concurrent change of strategies
(rerouting) in which more than one users can change simultaneously their
strategies. This model is more powerful than ESS because of its real life
applications. Another model we study is that of coalitions, in which the users
can contract alliances. This model comes from cooperative game theory. In
this case we have to deal with groups of users changing selfishly their group
strategies. We present a pseudo-polynomial bound to the convergence time
in the identical machines model with coalitions of at most 2 users.
Another model of convergence, a little different than the others stated
above, is the construction of an algorithm that delegates strategies to the
users unselfishly without increasing the social cost. Informally, social cost is
a total metric of the system performance depending on the users strategies.
This model is named nashification and the algorithm nashify that provides
converge to a pure Nash equilibrium in polynomial number of steps without
increasing the social cost.
As far as the coordination mechanisms are concerned, they are a set of
cost policies for the edges, that provides motives to the selfish users in order
to converge to a pure Nash equilibrium with decreased social cost. In this
thesis, we study the effect of coordination mechanisms in the convergence
time. We examine, except from makespan, the sjf, ljf and fifo cost policies.
Sjf and ljf policies debit the users concerning their weights.
The thesis results are divided in two categories. On the one hand, we
prove upper and lower bounds of convergence time for sjf, ljf and fifo policies.
Especially for fifo we prove in identical machines case a tight linear bound
which is independent from the priority algorithm and a pseudo-polynomial
bound in unrelated machines case. On the other hand, we implement all
the above mentioned models and analyze them experimentally. In our experiments there are 3 parameters: the priority algorithm, the cost policy,
and the number of coalitions. In all cases the experimental results follows
the theoretical with one exception which is the most interesting among the
experiments. In the case of coalitions with at most 2 users the theoretical
upper bound is pseudo-polynomial to the number of users but the experimental results shows that the convergence time is polynomial. These results
force us to conjecture that there is a polynomial upper bound.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/4600 |
| Date | 09 September 2011 |
| Creators | Φυσικόπουλος, Βησσαρίων |
| Contributors | Σπυράκης, Παύλος, Κοντογιάννης, Σπυρίδων, Fisikopoulos, Vissarion, Σπυράκης, Παύλος, Κοντογιάννης, Σπυρίδων |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
Page generated in 0.0028 seconds