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).

La théorie de la complexité permet de classifier les problèmes en fonction de leur difficulté. Le cadre classique dans lequel elle s'applique est celui d'un algorithme centralisé qui dispose de toutes les informations. Avec l'essor des réseaux et des architectures décentralisées, l'algorithmique distribuée a été etudiee. Dans un grand nombre de problèmes, en optimisation et en économie, les décisions et les calculs sont effectu'es par des agents indépendants qui suivent des objectifs diff'erents dont la réalisation dépend des décisions des autres agents. La théorie des jeux est un cadre naturel pour analyser les solutions de tels problèmes. Elle propose des concepts de stabilité, le plus classique étant l'équilibre de Nash.Une manière naturelle de calculer de telles solutions est de " faire réagir " les agents ; si un agent voit quelles sont les décisions des autres joueurs ou plus généralement un " état du jeu ", il peut décider de changer sa décision pour atteindre son objectif faisant ainsi 'évoluer 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éresse 'a la vitesse de convergence des dynamiques. Certains concepts de solutions sont même complets pour certaines classes de complexité ce qui rend peu vraisemblable l'existence de dynamiques simples qui convergent rapidement vers ces solutions. On a utilisé alors trois approches pour obtenir une convergence rapide : améliorer la dynamique (en utilisant par exemple des bits aléatoires), restreindre la structure du problème, et rechercher une solution approchée.Sur les jeux de congestion, on a étendu les résultats de convergence rapide vers un équilibre de Nash approche aux jeux négatifs. Cependant, on a montré que sur les jeux sans contrainte de signe, calculer un équilibre de Nash approche est PLS-complet. Sur les jeux d'appariement, on a étudie la vitesse de dynamiques concurrentes lorsque les joueurs ont une information partielle paramétrée par un reseau social. En particulier, on a améliore des dynamiques naturelles afin qu'elles atteignent un équilibre enO(log(n)) tours (avec n le nombre de joueurs).