Complexité des dynamiques de jeux

La th eorie de la complexit e permet de classi er les problemes en fonction de leur di cult 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 problemes, en optimisation et en economie, les d ecisions et les calculs sont e ectu es par des agents ind ependants qui suivent des objectifs di 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 problemes. Elle propose des concepts de stabilit e, le plus classique etant l equilibre de Nash.Une maniere 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 probleme, 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 a n 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), nding simple subcases, and nding an approximate solution.We extent fast convergence results to an approximate Nash equilibria in negative congestion games. However, we proved that nding 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).PARIS11-SCD-Bib. électronique (914719901) / SudocSudocFranceF