Cette thèse a deux parties. La première traite des jeux stratégiques non-atomiques, la seconde propose des applications de la théorie des jeux aux réseaux de télécommunications. Dans la première partie, les modèles de jeux non-atomiques proposés par Schmeidler (1973) et par Mas-Colell (1984) sont décrits et comparés. Nous montrons alors que ces jeux non-atomiques sont de bonnes approximations de jeux avec un nombre finis de joueurs et dans lesquels l'influence de chacun sur le paiement des autres joueurs est évanescente. Nous proposons ensuite une extension et des variations du modèle de Mas-Colell afin d'obtenir un cadre unificateur pour diverses applications des jeux non-atomiques, telles les jeux de routage, les jeux de foule et les jeux évolutionnaires. Ces trois types de jeu sont étudiés. Enfin nous étendons le concept de stratégie évolutionnairement stable au modèle de Schmeidler, ce qui donne un critère de sélection des équilibres. La deuxième partie traite de problèmes de routage dans les réseaux. Tout d'abord nous modélisons des situations où deux types de joueur partagent un réseau, des joueurs ayant une influence certaine sur la répartition des paquets dans le réseau et des joueurs n'en ayant pas. Puis, nous étudions la convergence de dynamiques de meilleures réponses dans des réseaux d'architecture simple. Finalement, nous modélisons le problème du routage mutipoint-à-multipoint.

Il existe de nombreuses méthodes d'optimisation du routage réseau en général. Dans cette thèse nous nous intéressons au développement d'algorithmes distribués permettant une stabilisation, au sens de Nash, des flux réseaux. Nous rappelons tout d'abord brièvement le contexte général d'Internet aujourd'hui et quelques notions de théorie des jeux. Nous présentons un jeu de tarification simple à deux joueurs, que la méthode des joueurs fictifs permet de faire converger. Puis nous présentons un jeu de routage plus complexe, à n joueurs, basé sur le modèle de Wardrop, ainsi qu'un algorithme de comportement distribué qui permet au système de converger vers un équilibre de Wardrop (équilibre social). Ces équilibres sont confondus avec les équilibres de Nash dans le cas limite où un joueur représente une partie infinitésimale du trafic. Nous présentons ensuite un raffinement de notre représentation initiale du problème, qui permet une diminution de sa complexité, en terme de dimension des espaces de stratégies et de temps de calcul. Nous montrons qu'il s'agit d'une bonne heuristique d'approximation de la première méthode trop coûteuse, sa qualité dépend d'un unique paramètre. Enfin, nous concluons par la présentation de résultats de simulation qui montrent que notre méthode distribuée est effectivement capable d'apprendre les meilleurs équilibres du système.

Le premier chapitre, en français, présente les principaux outils mathématiques utilisés dans le manuscrit, les résultats classiques sur la rationalité coalitionnelle pour les jeux coopératifs à utilité transférable et notamment sur le cœur et ses extensions, quelques résultats nouveaux sur le cœur k-additif et l’implémentation en équilibre de Nash fort de solutions de jeux coopératifs. Il y est synthétisé, sans démonstrations, les résultats des trois articles ainsi que quelques résultats nouveaux ou complémentaires. Les trois chapitres suivants, en anglais, correspondent aux trois articles. L’annexe A donnera en anglais les démonstrations des résultats nouveaux et non contenus dans les articles. / The first chapter, in french, presents the main mathematics tools used for this thesis, some classical results about coalitional rationality for cooperative TU-games, and among other things, about the core and its extensions. This chapter presents also some new or less known results about the k-additive core and strong Nash implementation of some cooperative games’ solutions. In addition, we summurize, without proofs, the main results which are contained in the three articles and some extra results that can be read in english in the appendix A. The three next chapters, in english, are the three articles. The Appendix A gives, in english, the proof of some extra results.

Planifier les actions d’un agent dans un environnement dynamique et incertain, a été largement étudié et le cadre des processus décisionnels de Markov offre les outils permettant de modéliser et de résoudre de tels problèmes. Le domaine de la théorie des jeux, a permis l’étude des interactions stratégiques entre plusieurs agents pour un jeu donné. Le cadre des jeux stochastiques, est considéré comme une généralisation du domaine des processus décisionnels de Markov et du champ de la théorie des jeux et permet de modéliser des systèmes ayant plusieurs agents et plusieurs états. Cependant, planifier dans unsystème multi-agents est considéré comme difficile, car la politique d’actions de l’agent dépend non seulement de ses choix mais aussi des politiques des autres agents. Le travail que nous présentons dans cette thèse porte sur la prise de décision distribuée dans les systèmes multi-agents. Les travaux existants dans le domaine, permettent la résolution théorique des jeux stochastiques mais imposent de fortes restrictions et font abstraction de certains problèmes cruciaux du modèle. Nous proposons un algorithme de planification décentralisée pour le modèle des jeux stochastiques, d’une part basé sur l’algorithme Value-Iteration et d’autre part basé sur la notion d’équilibre issue de la résolution des jeux matriciels. Afin d’améliorer le processus de résolution et de traiter des problèmes de taille importante, nous recherchons à faciliter la prise de décision et à limiter les possibilités d’actions à chaque étape d’interaction. L’algorithme que nous avonsproposé, a été validé sur un exemple d’interaction incluant plusieurs agents et différentes expérimentations ont été menées afin d’évaluer la qualité de la solution obtenue. / Planning agent’s actions in a dynamic and uncertain environment has been extensively studied. The framework of Markov decision process provides tools to model and solve such problems. The field of game theory has allowed the study of strategic interactions between multiple agents for a given game. The framework of stochastic games is considered as a generalization of the fields of Markov decision process and game theory. It allows to model systems with multiple agents and multiple states. However, planning in a multi-agent system is considered difficult : agent’s decisions depend not only on its actions but also on actions of the other agents. The work presented in this thesis focuses on decision making in distributed multi-agent systems. Existing works in this field allow the theoretical resolution of stochastic games but place severe restrictions and ignore some crucial problems of the model. We propose a decentralized planning algorithm for the model of stochastic games. Our proposal is based on the Value-Iteration algorithm and on the concept of Nash equilibrium. To improve the resolution process and to deal with large problems, we sought to ease decision making and limit the set of joint actions at each stage. The proposed algorithm was validated on a coordination problem including several agents and various experiments were conducted to assess the quality of the resulting solution.

Cette thèse se focalise sur les jeux de potentiel et une généralisation d'un jeu d'ordonnancement dans un graphe que nous avons appelé jeu de placement.Dans ce jeu, le coût d'un joueur est impacté par son voisinage.Nous pouvons illustrer cela avec un exemple : le placement de joueurs dans un train, pour lesquels la présence de voisins directs influe sur le bien-être.Les résultats de cette thèse se divisent en deux parties.Tout d'abord, nous étudions ces jeux en considérant l'existence et les propriétés de structure des équilibres.Nous nous posons la question fondamentale de savoir s'il existe des équilibres de Nash dans le jeu de placement.Si tel est le cas, nous tachons de déterminer si ces équilibres sont facilement calculables.Dans le cas où il n'existe pas d'équilibre nous prouvons la NP-complétude du problème.Dans un second temps nous nous intéressons à la notion de calcul distribué d'équilibre de Nash dans des jeux de placement.En particulier nous considérons un jeu basé sur le problème de Max-Cut, qui a été plus étudié en théorie des graphes.Cela nous a permis d'étendre nos travaux à une application aux réseaux mobiles pour la gestion d'interférences dans les réseaux sans fils.Nous avons pu, pour les différents jeux, mettre en place des algorithmes distribués de calcul d'équilibres et étudier leur convergence.Parallèlement, nous avons étendu les travaux de Max-Cut à un problème de sélection d'offre de qualité de service parmi divers fournisseurs d'accès.Nous comparons les performances d'algorithmes de calcul distribué d'équilibres et de minimisation de regret. / This thesis focuses on potential games and a generalized load balancing game in a graph we called placement game.In this game, the cost of a player is affected by its neighbors.We can illustrate this with an example: the placement of players on a train, where the presence of direct neighbors affects their well-being.The results of this thesis are divided into two parts.First, we study these games considering the existence and structural properties of equilibria.We ask ourselves the fundamental question of whether there are Nash equilibria in the placement game.If this is the case we aim to determine if they are easily calculable, if there is no such equilibria we prove the NP-completeness of the problem.Secondly we focus on the concept of distributed algorithms to compute Nash equilibria in placement games.In particular we consider a game based on the Max-Cut problem, which has been more frequently studied.This allowed us to expand our work to a mobile network application for managing interference in wireless networks.We were able, for those different games, to implement distributed algorithms to compute equilibria and study their convergence.Meanwhile, we have expanded the Max-Cut works with a selection of QoS offers problem from various network providers.We compare the performance of distributed algorithms and regret minimization.

Les défis auxquels sont confrontés les différents secteurs de l’économie, répondent à l'évolution et à la spécialisation des consommateurs et des producteurs, dont les besoins sont de plus en plus complexes. À cet égard, au cours des 5 dernières années, les marchés de l'électricité ont subi un processus évolutif qui vise à répondre aux besoins de tous les intervenants dans des scénarios de développement durable.Aussi les agents impliqués dans les marchés de l'électricité, exposés à des risques opérationnels, juridiques, éthiques, financiers, entre autres, doivent‐ils se spécialiser pour s'approprier notamment de nouvelles technologies. Cette recherche porte principalement sur l'étude du risque financier tout à s'attachant à prendre en compte les nombreuses spécificités des marchés de l'électricité dans le but d'assurer le bon fonctionnement du marché et de ses participants.Dans les développements antérieurs, certains modèles se sont concentrés sur les phénomènes de pannes de courant électrique, d'instabilité du réseau, de variations de puissance, de réseaux intelligents, entre autres. D'autres études ont abordé la question de la prédiction de variables comme le prix et la stratégie d'entreprise, dans le but d'accroître les profits des participants. Ce projet de thèse propose un modèle financier complexe, qui se traduit par le calcul d'un équilibre de marché à partir des conditions initiales et des contraintes de risque. En utilisant la théorie des jeux, nous expliquons l'instabilité de l’équilibre. Nous montrons, en dépit de la complexité, qu'il est possible de trouver un scénario optimal en termes de rentabilité pour le système et les agents.Ce travail est structuré de la façon suivante. Dans le premier chapitre, une revue des études antérieures est présentée afin d’établir le contexte de la recherche. Le chapitre 2 décrit le marché de l'électricité colombienne avec ses particularités. Dans le chapitre 3, les indicateurs de risque (KRI) sont définis. Ils constitueront une partie fondamentale du modèle complet présenté dans le chapitre 4. Enfin, le chapitre 5, d'une part, présente les résultats obtenus et, d'autre part, discute de différentes voies d'approfondissement. / The challenges faced by different sectors of the economy, respond to the evolution and specialization of consumers and producers, where the needs are becoming more complex. In this sense, during the last 5 years the electricity markets have undergone an evolutionary pro- cess that aims to meet the needs of all stakeholders in the midst of sustainability scenarios.Thus, the agents involved in the electricity market, present a num- ber of exhibitions of operational nature, legal, ethical, financial, among others, which require a specialization allowing the entry of new tech- nologies. This research project focuses on the study of financial risk, which despite being so specific, consider many elements with the aim of ensuring the functioning of the market and its participants.In previous studies, some models have concentrated on the in- vestigation of blackouts phenomena, the stability of the network, the dynamic power system, and Smart grids, among others. Mean- while other investigations have addressed the problem of forecasting different variables like the spot price and corporate strategy, with the aim of increasing the profitability of the participants. Now, this project presents the proposal of a complex financial model, which results in calculating a market equilibrium considering initial condi- tions and risk constraints. Using game theory it demonstrates equi- librium instability and that through complexity it is possible to find an optimal scenario in terms of profitability for the system and the agents.In chapter 1 it carried out a review of previous studies in order to justify the investigation, then Chapter 2 includes a description of the Colombian electricity market, with different specifications. In chap- ter 3 the KRI are defined, and they will be integrated in Chapter 4 as a fundamental part of the comprehensive model. Finally, Chapter 5 includes the results of the study ending with some possible further studies and additional considerations.

Une chaîne logistique est composée d'entreprises fabriquant et distribuant des produits aux consommateurs. En modélisant chacune de ses entreprises comme un agent intelligent, nous étudions l'effet "coup de fouet" (Bullwhip effect) qui s'y propage. Cet effet est une amplification de la variabilité de la demande lorsque l'on s'éloigne du client final. On peut aussi voir ce phénomène comme un cas particulier de fluctuations des flux dans un système distribué. Ces fluctuations réduisent l'efficacité de la chaîne logistique, principalement du fait de l'élévation des niveaux d'inventaire et de la réduction de l'agilité. On estime que ce phénomène coûterait de 40 à 60 millions USD pour une papetière de 300 kilotonnes.<br /> <br />L'effet coup de fouet étant provoqué par un manque de coordination entre les agents, nous proposons deux principes qui doivent inspirer tout mécanisme de coordination, à savoir : (i) commander ce que l'on nous commande élimine l'effet coup de fouet mais ne gère pas les inventaires, et (ii) les entreprises ne devraient réagir qu'une seule fois à chaque changement dans la consommation du marché. Afin de valider ces deux principes, nous simulons une chaîne logistique forestière appelée le Jeu du Bois Québécois. Ce jeu permet d'enseigner ce qu'est l'effet coup de fouet. Chaque joueur-entreprise y est modélisé par un agent intelligent appliquant une stratégie donnée pour passer ses commandes. À cet effet, nous avons conçu deux stratégies suivant nos deux principes.<br /><br />Dans un premier temps, nous comparons expérimentalement l'efficacité de ces deux stratégies avec cinq autres stratégies. Nous supposons ici que la chaîne logistique est homogène, c'est-à-dire que toutes ses entreprises utilisent la même stratégie de commande. Nous vérifions ainsi que nos deux mécanismes de coordination, implémentés sous la forme de stratégies, sont efficaces pour la chaîne logistique dans son ensemble.<br /><br />Dans un second temps, nous cessons de supposer la chaîne homogène pour faire davantage de simulations nous permettant de construire un jeu. En analysant ce jeu avec la Théorie de Jeux, nous vérifions que les entreprises n'ont pas intérêt d'arrêter unilatéralement d'utiliser nos deux mécanismes de coordination (équilibre de Nash).

Ce travail porte sur l'étude des systèmes différentiels et algébriques du type Riccati issus de la théorie des jeux différentiels linéaires quadratiques. Ces systèmes dérivent de l'équilibre de Nash et de la commande optimale sous une contrainte différentielle stochastique. Ils sont le principal obstacle à franchir afin d'obtenir les stratégies optimales des joueurs. Dans le cas des systèmes différentiels, nous avons construit une méthode analytique pour le recherche d'une paire de solutions. Cette méthode s'appuie sur des changements de base de la matrice décrivant l'équilibre de Nash. Dans le cas des systèmes algébriques, nous avons proposé des itérations du type Lyapunov et des itérations du type Riccati. Des propriétés des solutions itératives ainsi que des conditions suffisantes de convergence de ces itérations sont également établies. Les résultats numériques obtenus avec ces deux types d'itérations sont présentées et comparés. Ces résultats démontrent une plus grande performance des itérations du type Riccati relativement aux itérations du type Lyapunov.

Planifier les actions d'un agent dans un environnement dynamique et incertain, a été largement étudié et le cadre des processus décisionnels de Markov offre les outils permettant de modéliser et de résoudre de tels problèmes. Le domaine de la théorie des jeux, a permis l'étude des interactions stratégiques entre plusieurs agents pour un jeu donné. Le cadre des jeux stochastiques, est considéré comme une généralisation du domaine des processus décisionnels de Markov et du champ de la théorie des jeux et permet de modéliser des systèmes ayant plusieurs agents et plusieurs états. Cependant, planifier dans unsystème multi-agents est considéré comme difficile, car la politique d'actions de l'agent dépend non seulement de ses choix mais aussi des politiques des autres agents. Le travail que nous présentons dans cette thèse porte sur la prise de décision distribuée dans les systèmes multi-agents. Les travaux existants dans le domaine, permettent la résolution théorique des jeux stochastiques mais imposent de fortes restrictions et font abstraction de certains problèmes cruciaux du modèle. Nous proposons un algorithme de planification décentralisée pour le modèle des jeux stochastiques, d'une part basé sur l'algorithme Value-Iteration et d'autre part basé sur la notion d'équilibre issue de la résolution des jeux matriciels. Afin d'améliorer le processus de résolution et de traiter des problèmes de taille importante, nous recherchons à faciliter la prise de décision et à limiter les possibilités d'actions à chaque étape d'interaction. L'algorithme que nous avonsproposé, a été validé sur un exemple d'interaction incluant plusieurs agents et différentes expérimentations ont été menées afin d'évaluer la qualité de la solution obtenue.

Dans le domaine d'optimisation de forme de structures, la réduction des coûts et l'amélioration des produits sont des défis permanents à relever. Pour ce faire, le procédé de mise en forme doit être optimisé. Optimiser le procédé revient alors à résoudre un problème d'optimisation. Généralement ce problème est un problème d'optimisation multicritère très coûteux en terme de temps de calcul, où on cherche à minimiser plusieurs fonctions coût en présence d'un certain nombre de contraintes. Pour résoudre ce type de problème, on a développé un algorithme robuste, efficace et fiable. Cet algorithme, consiste à coupler un algorithme de capture de front de Pareto (NBI ou NNCM) avec un métamodèle (RBF), c'est-à-dire des approximations des résultats des simulations coûteuses. D'après l'ensemble des résultats obtenus par cette approche, il est intéressant de souligner que la capture de front de Pareto génère un ensemble des solutions non dominées. Pour savoir lesquelles choisir, le cas échéant, il est nécessaire de faire appel à des algorithmes de sélection, comme par exemple Nash et Kalai-Smorodinsky. Ces deux approches, issues de la théorie des jeux, ont été utilisées pour notre travail. L'ensemble des algorithmes sont validés sur deux cas industriels proposés par notre partenaire industriel. Le premier concerne un modèle 2D du fond de la canette (elasto-plasticité) et le second est un modèle 3D de la traverse (élasticité linéaire). Les résultats obtenus confirment l'efficacité de nos algorithmes développés.