On présente les fondements de la théorie algorithmique des jeux et des mécanismes. Les équilibres de Nash pour les jeux à somme nulle et les jeux matriciels, l'équilibre Arrow-Debreu.
On décrira les résultats classiques de complexité et d'approximation et des exemples de jeux et de mécanismes en Informatique.

Nous considérerons des modèles où un grand nombre de paquets (dans le cadre du trafic routier, ceux-ci correspondent à des véhicules), modélisé par un continuum, doivent aller d'un point du réseau à un autre. Pour ce faire les paquets peuvent etre délivrés via différents chemins (routes) possibles. Tout chemin présente un cout dépendant de sa fréquentation ou plus généralement de la répartition des paquets au travers des différents chemins. Les décisions de routage, c'est-à-dire le choix des routes pour les paquets, peuvent se faire de trois manières différentes : la décision centralisée, la décision groupée ou la décision individuelle. Le premier type de décision correspond à un problème de minimisation, les deux autres à des problèmes de jeux. Nous étudierons ces deux derniers types : la décision groupée conduit à un jeu à N personnes dont un concept de solution est l'équilibre de Nash et la décision individuelle à un jeu avec un continuum de joueurs dont un concept de solution est l'équilibre de Wardrop.

Notre objectif est de survoler dans le temps imparti par l'intermédiaire de quelques exemples, inspirés de problèmes de routage ou d'allocation de taches, certains résultats qui peuvent etre établis sur leurs équilibres de Nash, en particulier sur l'existence d'équilibres purs.
On cherchera à discuter en parallèle les liens connus entre équilibres de Nash et minimums locaux et globaux de certaines fonctions sur l'état global du système.

Nous nous intéressons au routage interdomaine d'un point de vue économique. Nous présentons un modèle de cout basé sur la théorie des jeux.
Les systèmes autonomes appartenant à divers opérateurs agissent comme des agents stratégiques en compétition pour offrir et tarifer leurs services de transit les uns aux autres. En effet, chaque opérateur fixe un prix pour chacun de ses voisins pour chaque unité de trafic en transit.
Les routes effectivement prises par le trafic sont ensuite calculées par BGP selon un critère de cout minimum. Le but de chaque opérateur est de choisir ses prix afin de minimiser ses couts.
Nous nous intéressons à des stratégies particulières de mise à jour des prix que les opérateurs peuvent utiliser localement afin de minimiser leurs couts.
Nous étudions les propriétés de stabilisation liées à de telles stratégies grace à différents scénarios simulés.

On s'intéresse à deux problèmes issus de la recherche opérationnelle. Dans les deux cas, on recherche une solution stable dans le sens où elle ne sera pas remise en cause par les agents. De plus, la solution recherchée doit optimiser une fonction objectif globale.
Le premier problème consiste à ordonnancer n taches (agents) sur deux machines. D'un point de vue global nous cherchons à minimiser le temps de terminaison de la dernière tache. Du point de vue d'une tache, seule la date à laquelle son exécution se termine est déterminante. Dans ce cadre, une solution stable est un équilibre de Nash, pouvant etre mauvais pour la fonction objectif. Cependant, en relachant la notion d'équilibre de Nash, nous montrons qu'il est possible d'améliorer la fonction objectif globale.
Le second problème concerne la partage équitable du cout d'un service apporté à un ensemble de clients (agents) dans un réseau. Dans ce cadre, une solution est dite stable si elle appartient au coeur du jeux coopératif sous-jacent. Cependant plusieurs solutions stables peuvent exister, et du point de vue d'un agent, engendrer des couts différents. Nous introduisons une mesure d'équité qui capture le mécontentement de chaque agent et nous proposons deux méthodes de partage de cout qui minimisent le pire mécontentement et le mécontentement moyen.