La th´eorie de la complexit´e permet de classifier les probl`emes en fonction de leur difficult´e. Le cadre classique dans lequel elle s’applique est celui d’un algorithme centralis´e qui dispose de toutes les informations. Avec l’essor des r´eseaux et des architectures d´ecentralis´ees, l’algo- rithmique distribu´ee a ´et´e ´etudi´ee. Dans un grand nombre de probl`emes, en optimisation et en ´economie, les d´ecisions et les calculs sont effectu´es par des agents ind´ependants qui suivent des objectifs diff´erents dont la r´ealisation d´epend des d´ecisions des autres agents. La th´eorie des jeux est un cadre naturel pour analyser les solutions de tels probl`emes. Elle propose des concepts de stabilit´e, le plus classique ´etant l’´equilibre de Nash.Une mani`ere naturelle de calculer de telles solutions est de “ faire r´eagir “ les agents ; si un agent voit quelles sont les d´ecisions des autres joueurs ou plus g´en´eralement un “ ´etat du jeu “, il peut d´ecider de changer sa d´ecision pour atteindre son objectif faisant ainsi ´evoluer l’´etat du jeu. On dit que ces algorithmes sont des “ dynamiques “.On sait que certaines dynamiques convergent vers un concept de solution. On s’int´eresse `a la vitesse de convergence des dynamiques. Certains concepts de solutions sont mˆeme complets pour certaines classes de complexit´e ce qui rend peu vraisemblable l’existence de dynamiques simples qui convergent rapidement vers ces solutions. On a utilis´e alors trois approches pour obtenir une convergence rapide : am´eliorer la dynamique (en utilisant par exemple des bits al´eatoires), restreindre la structure du probl`eme, et rechercher une solution approch´ee.Sur les jeux de congestion, on a ´etendu les r´esultats de convergence rapide vers un ´equilibre de Nash approch´e aux jeux n´egatifs. Cependant, on a montr´e que sur les jeux sans contrainte de signe, calculer un ´equilibre de Nash approch´e est PLS-complet. Sur les jeux d ’appariement, on a ´etudi´e la vitesse de dynamiques concurrentes lorsque les joueurs ont une information partielle param´etr´ee par un r´eseau social. En particulier, on a am´elior´e des dynamiques naturelles afin qu’elles atteignent un ´equilibre enO(log(n)) tours (avec n le nombre de joueurs). / Complexity theory allows to classify problems by their algorithmic hardness. The classical framework in which it applies is the one of a centralized algorithm that knows every informa- tion. With the development of networks and decentralized architectures, distributed dynamics was studied. In many problems, in optimization or economy, actions and computations are made by independant agents that don’t share the same objective whose realization depends on the actions of other agents. Game theory is a natural framework to study solutions of this kind of problem. It provides solution concepts such as the Nash equilibrium.A natural way to compute these solutions is to make the agents “react” ; if an agent sees the actions of the other player, or more generally the state of the game, he can decide to change his decision to reach his objective and updates the state of the game. We call �dynamics� this kind of algorithms.We know some dynamics converges to a stable solution. We are interested by the speed of convergence of these dynamics. Some solution concepts are even complete for some complexity classes which make unrealistic the existence of fast converging dynamics. We used three ways to obtain a fast convergence : improving dynamics (using random bits), finding simple subcases, and finding an approximate solution.We extent fast convergence results to an approximate Nash equilibria in negative congestion games. However, we proved that finding an approximate Nash equilibrium in a congestion games without sign restriction is PLS-complete. On matching game, we studied the speed of concurrent dynamics when players have partial information that depends on a social network. Especially, we improved natural dynamics for them to reach an equilibrium inO(log(n)) rounds (with n is the number of players).

Στην παρούσα διπλωματικής εργασία εφαρμόζουμε τις αρχές της Θεωρίας Παιγνίων, και συγκεκριμένα τις έννοιες των Ισορροπιών Nash και των Παι­γνίου Συμφόρησης, ώστε να αναλύσουμε την επίδραση που έχει στην καθο­λική απόδοση ενός δικτύου και γενικότερα ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Αρχικά ασχολούμαστε με το πρόβλημα της εγωιστικής δρομολόγησης φορ­τίων από μια κοινή πηγή προς έναν κοινό προορισμό σε ένα δίκτυο επικοι­νωνίας. Σε ένα τέτοιο περιβάλλον οι χρήστες επιλέγουν εγωιστικά τις στρα­τηγικές τους, οι οποίες στην περίπτωση μας αντιστοιχούν σε μονοπάτια από την πηγή προς τον προορισμό Όταν οι χρήστες δρομολογούν τα φορτία τους σύμφωνα με τις στρατηγικές που επιλέγουν, έρχονται αντιμέτωποι με μια κα­θυστέρηση που προκαλείται από τα φορτία όλων των χρηστών καθώς διαμοι­ράζονται τις ακμές. Κάθε χρήστης στοχεύει στην ελαχιστοποίηση του εγωι­στικού τον κόστους, που αντιστοιχεί σε αυτήν ακριβώς την καθυστέρηση, γεγονός που συνήθως έρχεται σε αντίθεση με το στόχο της βελτιστοποίησης της καθολικής απόδοσης του δικτύου. Η θεωρία των ισορροπιών Nash μας παρέχει μία σημαντική αρχή επίλυ­σης για τέτοιου είδους καταστάσεις: μια ισορροπία Nash, είναι μια κατάσταση του συστήματος τέτοια ώστε δεν υπάρχει κάποιος χρήστης που να μπορεί να μειώσει το εγωιστικό του κόστος αλλάζοντας μονομερώς τη στρατηγική του. Σε ένα τέτοιο δίκτυο λοιπόν περιμένουμε οι χρήστες να καταλήξουν σε μια ισορροπία Nash. Ωστόσο, ο υπολογισμός μιας τέτοιας ισορροπίας παραμέ­νει ένα πρόβλημα του οποίου η πολυπλοκότητα είναι, στη γενική περίπτωση, άγνωστη. Στα πλαίσια αυτής της διπλωματικής εργασίας δείχνουμε πειραματικά ότι ο υπολογισμός μιας αγνής ισορροπίας Nash σε ένα περιβάλλον εγωιστικής δρομολόγησης, όπου η καθυστέρηση σε κάθε ακμή ισούται με το φορτίο της. μπορεί να γίνει σε πολυωνυμικό χρόνο για μια μεγάλη ποικιλία δικτύων και κατανομών των φορτίων των χρηστών. Επιπλέον, προτείνουμε μια αρχική ανάθεση χρηστών σε μονοπάτια η οποία, όπως δείχνουν οι προσομοιώσεις μας, οδηγεί σε μια αξιοσημείωτη μείωση του συνολικού αριθμού των βημάτων που απαιτούνται ώστε να καταλήξουμε σε μια αγνή ισορροπία Nash. Επίσης αποδεικνύουμε την ύπαρξη αγνών ισορροπιών Nash και για την περίπτωση που η καθυστέρηση σε κάθε ακμή είναι εκθετική συνάρτηση του φορτίου της. Στη συνέχεια προτείνουμε και αναλύουμε ένα νέο μηχανισμό κόστους που θέτει τιμές για την ανταγωνιστική χρησιμοποίηση πόρων από ένα σύνολο χρη­στών. Το βασικό πλεονέκτημα αυτού του μηχανισμού είναι ότι οι πόροι θέ­τουν τα κόστη με έναν ισοδύναμο, δίκαιο τρόπο, και το πλέον σημαντικό είναι ότι κανένας πόρος δεν επωφελείται εις βάρος των χρηστών. Αυτός ο δίκαιος μηχανισμός κόστους επαγάγει ένα μη συνεργατικό παί­γνιο μεταξύ των χρηστών, για το οποίο αναλύουμε τις ισορροπίες Nash. Απο­δεικνύουμε ότι δεν υπάρχουν αγνές ισορροπίες Nash, εκτός από την περί­πτωση όπου όλα τα φορτία είναι ίσα, ενώ δείχνουμε ότι υπάρχει πάντα μία πλήρως μικτή ισορροπία Nash. Επίσης αναλύουμε για το παίγνιο αυτό το Κόστος της Αναρχίας, που εκφράζει την απόκλιση της απόδοσης του συ­στήματος στη χειρότερη ισορροπία Nash από τη βέλτιστη απόδοση. Αποδει­κνύουμε ότι το Κόστος της Αναρχίας στη χειρότερη περίπτωση είναι γραμ­μικό ως προς το πλήθος των χρηστών και ότι το φράγμα αυτό είναι αυστηρό. Ωστόσο προτείνουμε δύο τρόπους για να μετριάσουμε τη δυσάρεστη αυτή διαπίστωση. Καταρχήν, μελετάμε την περίπτωση όπου τα φορτία των χρηστών επιλέ­γονται από μία πολύ ευρεία οικογένεια φραγμένων κατανομών πιθανότητας. Ορίζουμε το Διαχεόμενο Κόστος της Αναρχίας το οποίο λαμβάνει υπόψη την κατανομή πιθανότητας των φορτίων και αποδεικνύουμε ότι Διαχεόμενο Κόστος της Αναρχίας φράσσεται εκ των άνω από μία μικρή σταθερά. Επιπλέον, προτείνουμε έναν υβριδικό μηχανισμό κόστους, ο οποίος επιτυγχάνει ένα ση­μαντικά μικρότερο Κόστος της Αναρχίας, ενώ το κέρδος κάθε πόρου παρα­μένει αμελητέο. / -

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第25443号 / 情博第881号 / 新制||情||148(附属図書館) / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 湊 真一, 教授 大木 英司, 教授 山本 章博 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Nous considérons des jeux de congestion sur des graphes. Dans les jeux non-atomiques, nous considérons un ensemble de joueurs infinitésimaux. Chaque joueur veut aller d'un sommet à un autre en choisissant une route de coût minimal. Le coût de chaque route dépend du nombre de joueur la choisissant. Dans les jeux atomiques divisibles, nous considérons un ensemble de joueurs ayant chacun une demande à transférer d'un sommet à un autre, en la subdivisant éventuellement sur plusieurs routes. Dans ces jeux, un équilibre de Nash est atteint lorsque chaque joueur a choisi une stratégie de coût minimal. L'existence d'un équilibre de Nash est assurée sous de faibles hypothèses. Les principaux sujets sont l'unicité, le calcul, l'efficacité et la sensibilité de l'équilibre de Nash. De nombreux résultats sont connus dans le cas où les joueurs sont tous impactés de la même façon par la congestion. Le but de cette thèse est de généraliser ces résultats au cas où les joueurs ont des fonctions de coût différentes. Nous obtenons des résultats sur l'unicité de l'équilibre dans les jeux non-atomiques. Nous donnons deux algorithmes capables de calculer un équilibre dans les jeux non-atomiques lorsque les fonctions de coût sont affines. Nous obtenons une borne sur le prix de l'anarchie pour certains jeux atomiques divisibles et prouvons qu'il n'est pas borné en général, même lorsque les fonctions sont affines. Enfin, nous prouvons des résultats sur la sensibilité de l'équilibre par rapport à la demande dans les jeux atomiques divisibles / We consider congestion games on graphs. In nonatomic games, we are given a set of infinitesimal players. Each player wants to go from one vertex to another by taking a route of minimal cost, the cost of a route depending on the number of players using it. In atomic splittable games, we are given a set of players with a non-negligible demand. Each player wants to ship his demand from one vertex to another by dividing it among different routes. In these games, we reach a Nash equilibrium when every player has chosen a minimal-cost strategy. The existence of a Nash equilibrium is ensured under mild conditions. The main issues are the uniqueness, the computation, the efficiency and the sensitivity of the Nash equilibrium. Many results are known in the specific case where all players are impacted in the same way by the congestion. The goal of this thesis is to generalize these results in the case where we allow player-specific cost functions. We obtain results on uniqueness of the equilibrium in nonatomic games. We give two algorithms able to compute a Nash equilibrium in nonatomic games when the cost functions are affine. We find a bound on the price of anarchy for some atomic splittable games, and prove that it is unbounded in general, even when the cost functions are affine. Finally we find results on the sensitivity of the equilibrium to the demand in atomic splittable games

Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη καταστάσεων ανταγωνισμού μεταξύ χρηστών, για τη χρησιμοποίηση ενός συνόλου κοινόχρηστων πόρων. Για την μοντελοποίηση και ανάλυση των καταστάσεων αυτών χρησιμοποιούμε ως εργαλεία, έννοιες από την θεωρία παιγνίων, όπως ισορροπίες 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.