Prendre de bonnes décisions dans des environnements multiagents est une tâche difficile dans la mesure où la présence de plusieurs décideurs implique des conflits d'intérêts, un manque de coordination, et une multiplicité de décisions possibles. Si de plus, les décideurs interagissent successivement à travers le temps, ils doivent non seulement décider ce qu'il faut faire actuellement, mais aussi comment leurs décisions actuelles peuvent affecter le comportement des autres dans le futur. La théorie des jeux est un outil mathématique qui vise à modéliser ce type d'interactions via des jeux stratégiques à plusieurs joueurs. Des lors, les problèmes de décision multiagent sont souvent étudiés en utilisant la théorie des jeux. Dans ce contexte, et si on se restreint aux jeux dynamiques, les problèmes de décision multiagent complexes peuvent être approchés de façon algorithmique. La contribution de cette thèse est triple. Premièrement, elle contribue à un cadre algorithmique pour la planification distribuée dans les jeux dynamiques non-coopératifs. La multiplicité des plans possibles est à l'origine de graves complications pour toute approche de planification. Nous proposons une nouvelle approche basée sur la notion d'apprentissage dans les jeux répétés. Une telle approche permet de surmonter lesdites complications par le biais de la communication entre les joueurs. Nous proposons ensuite un algorithme d'apprentissage pour les jeux répétés en ``self-play''. Notre algorithme permet aux joueurs de converger, dans les jeux répétés initialement inconnus, vers un comportement conjoint optimal dans un certain sens bien défini, et ce, sans aucune communication entre les joueurs. Finalement, nous proposons une famille d'algorithmes de résolution approximative des jeux dynamiques et d'extraction des stratégies des joueurs. Dans ce contexte, nous proposons tout d'abord une méthode pour calculer un sous-ensemble non vide des équilibres approximatifs parfaits en sous-jeu dans les jeux répétés. Nous montrons ensuite comment nous pouvons étendre cette méthode pour approximer tous les équilibres parfaits en sous-jeu dans les jeux répétés, et aussi résoudre des jeux dynamiques plus complexes. / Making good decisions in multiagent environments is a hard problem in the sense that the presence of several decision makers implies conflicts of interests, a lack of coordination, and a multiplicity of possible decisions. If, then, the same decision makers interact continuously through time, they have to decide not only what to do in the present, but also how their present decisions may affect the behavior of the others in the future. Game theory is a mathematical tool that aims to model such interactions as strategic games of multiple players. Therefore, multiagent decision problems are often studied using game theory. In this context, and being restricted to dynamic games, complex multiagent decision problems can be algorithmically approached. The contribution of this thesis is three-fold. First, this thesis contributes an algorithmic framework for distributed planning in non-cooperative dynamic games. The multiplicity of possible plans is a matter of serious complications for any planning approach. We propose a novel approach based on the concept of learning in repeated games. Our approach permits overcoming the aforementioned complications by means of communication between players. We then propose a learning algorithm for repeated game self-play. Our algorithm allows players to converge, in an initially unknown repeated game, to a joint behavior optimal in a certain, well-defined sense, without communication between players. Finally, we propose a family of algorithms for approximately solving dynamic games, and for extracting equilibrium strategy profiles. In this context, we first propose a method to compute a nonempty subset of approximate subgame-perfect equilibria in repeated games. We then demonstrate how to extend this method for approximating all subgame-perfect equilibria in repeated games, and also for solving more complex dynamic games.

Depuis longtemps, le processus de contagion financière suscite l'intérêt des économistes et des autorités réglementaires. Diamond et Dybvig (1983) rationalisent les paniques bancaires dans le sens où elles émergent comme une réponse rationnelle à un problème de coordination des agents. La difficulté avec ce type de modèle est de savoir pourquoi les agents prêtent aux banques s'ils anticipent qu'elles vont faire faillites. Depuis un certain temps, les économistes attachent beaucoup d'importance à l'évolution du comportement des agents. Dans ce mémoire, je montre que les deux équilibres en stratégies pures de la deuxième étape du modèle de Diamond et Dybvig sont évolutionnairement stables et que l'équilibre symétrique en stratégies mixtes ne l'est pas. Dans ce contexte, les faillites bancaires s'interprètent comme l'appartition d'un trop grand nombre d'expérimentateurs à la fois.

Nous nous intéressons dans cette thèse à des problèmes d'optimisation liés au domaine des réseaux. Ces problèmes sont d'une part des problèmes d'optimisation ``classiques'' dans lesquels nous cherchons à pallier la NP-difficulté d'un problème en proposant des algorithmes approchés, le plus souvent avec garantie de performance. D'autre part, nous avons considéré des problèmes dans lesquels les utisateurs du réseau sont indépendants et individualistes. Chaque utilisateur souhaite alors optimiser sa propre fonction objectif, qui peut être très différente de la fonction objectif globale que, en tant que concepteurs d'un protocole, nous souhaitons optimiser. Nous nous plaçons alors dans le cadre de la théorie des jeux algorithmique et cherchons à optimiser cette fonction objectif globale en prenant en compte des contraintes supplémentaires dues au fait que les utilisateurs se comportent de façon individualiste. Les problémes que nous avons considérés sont des problémes d'ordonnancement et de routage.

Dans cette thèse nous nous interrogeons sur les conséquences d'une approche volontariste de décentralisation de la gestion de périmètres irrigués en Tunisie sur le comportement coopératif des agriculteurs. Nous examinons l'effet de l'adhésion volontaire comme mécanisme incitatif dans la provision d'un bien collectif. Pour cela, nous comparons la provision d'un bien public avec seuil de fourniture à celle d'un bien club. Notre expérimentation a été conduite en laboratoire et sur le terrain. L'expérience montre que la présence d'adhésion volontaire augmente la contribution du groupe, le succès de provision et le bien être. Elle augmente aussi le nombre de contributeurs dans le groupe. Une explication possible de nos résultats peut être la réduction de l'incertitude stratégique. Notre expérience révèle également que lorsque la dimension risque dans le jeu est neutralisé, l'adhésion volontaire n'améliore plus la contribution du groupe. L'adhésion volontaire fait alors seulement baisser la variance. L'étude de la validité externe des résultats obtenus en laboratoire montre qu'il n'existe pas de différences importantes en fonction de l'origine des sujets. Le comportement coopératif des étudiants tunisiens est similaire au comportement des sujets d'origine montpelliéraine. Seule, la variance de contribution du groupe baisse. Cependant, l'expérience de terrain avec les agriculteurs montre que l'adhésion volontaire n'améliore pas le comportement coopératif autant que dans le laboratoire. Le succès de provision et le bien être s'améliorent seulement dans un group d'agriculteurs sur trois. L'expérience de terrain montre néanmoins que l'adhésion volontaire augmente le nombre des contributeurs et révèle un niveau de coopération élevé qui se maintient dans le temps.

On trouve dans la littérature de nombreux exemples de jeux où les stratégies souhaitées sont soumises à des contraintes ''transversales'' portant sur des ensembles de parties, reliées entre elles par quelque relation sémantique. L'exemple le plus fameux est celui des stratégies dans les jeux à information imparfaite, et les jeux où la condition de gain a un aspect épistémique en sont d'autres. Cependant, aucune étude approfondie n'a à notre connaissance été menée sur ce type de contraintes dans leur généralité. C'est ce que nous nous proposons de commencer dans cette thèse. Nous définissons donc une notion générale de stratégies uniformes. Les propriétés d'uniformité des stratégies sont exprimées dans un langage logique qui étend CTL∗ avec deux quantificateurs originaux. Ces quantificateurs sont très proches des opérateurs de connaissance classiques en logique épistémique, et font intervenir des ensembles de parties reliées entre elles par des relations binaires. Nous montrons comment cette notion de stratégies uniformes capture les exemples connus de la littérature, puis nous étudions en profondeur le problème de la synthèse de stratégies uniformes, en considérant que les relations binaires entre les parties sont reconnaissables par des automates finis (relations rationnelles). Nous établissons plusieurs résultats de décidabilité et de complexité, reposant largement sur des techniques d'automates : nous introduisons notamment comme outils les automates d'arbres bondissants et les automates d'ensembles d'informations. Par ailleurs, nos résultats permettent d'améliorer des résultats existants et d'en établir de nouveaux, dans les domaines du model-checking des logiques temporelles et épistémiques, ainsi que de la planification épistémique.

La Côte d’Ivoire, pays d’Afrique de l’Ouest prospère et stable depuis le début de l’indépendance de 1960, bascule dans une longue et douloureuse guerre, le 24 décembre 1999, à la suite d’une mutinerie de soldats. S’en suit alors un intense ballet diplomatique visant à rétablir la paix et la Côte d’Ivoire assiste alors à plusieurs tentatives de médiation internationale. Cette recherche vise à comprendre la notion de succès en médiation en proposant de modéliser le conflit ivoirien à partir d’un modèle de la théorie des jeux, celui du dilemme du prisonnier. / Often cited as a model of peace and stability, Ivory Coast, a West African economic powerhouse, was embroiled in a civil war in September 2002 that disrupted the institutional order. During this time, the country was divided into the Southern and Northern zones. The former, a coastal area, is referred to as the "Governmental Zone". The Northern is the area that was captured in September 2002, by a few thousand army mutineers. Between the two North and South divide lies the buffer zone called the Zone de confiance, which served as a military buffer zone between the North and the South. How did the division occur? How did the several mediation work? Could we ensure that the signing of a peace agreement guaranteed a mediation success?

Les communications pair-à-pair en temps réel ainsi que les applications de transmissions multi-média peuvent améliorer leurs performances en utilisant des services d'estimation de topologie au niveau d'application. Les systèmes aux coordonnées virtuelles représentent un tel service. A l'aide d'un tel système les noeuds d'un réseau pair-à-pair prédisent les latences entre différents noeuds sans nécessiter des mesures étendues. Malheureusement, prédire les latences correctement requis que les noeuds soient honnêtes et coopératifs. La recherche récente propose des techniques pour atténuer des attaques basiques (inflation, déflation, oscillation) où les attaquants conduisent un type d'attaque seulement. Dans ce travail, nous définissons et utilisons un modèle basé sur la théorie des jeux pour identifier la meilleure solution pour défendre le système en supposant que les attaquants utilisent l'attaque la plus pire. Ce modèle nous aide à démontrer l'impact et l'efficacité des attaques et défenses en utilisant un système de coordonnées virtuelles répondu. De même, nous explorons des techniques de l'apprentissage automatique supervisé pour détecter des attaques plus lentes et subtiles, comme l'attaque à l'inflation-lente et l'attaque de dégroupage de réseau qui sont capable de contourner des techniques de défenses existantes. Nous évaluons nos techniques sur le système Vivaldi contre des stratégies d'attaques plus complexes sur des simulations ainsi que des déploiements Internet / Peer-to-peer real-time communication and media streaming applications optimize their performance by using application-level topology estimation services such as virtual coordinate systems. Virtual coordinate systems allow nodes in a peer-to-peer network to accurately predict latency between arbitrary nodes without the need of performing extensive measurements. However, systems that leverage virtual coordinates as supporting building blocks, are prone to attacks conducted by compromised nodes that aim at disrupting, eavesdropping, or mangling with the underlying communications. Recent research proposed techniques to mitigate basic attacks (inflation, deflation, oscillation) considering a single attack strategy model where attackers perform only one type of attack. In this work, we define and use a game theory framework in order to identify the best attack and defense strategies assuming that the attacker is aware of the defense mechanisms. Our approach leverages concepts derived from the Nash equilibrium to model more powerful adversaries. We apply the game theory framework to demonstrate the impact and efficiency of these attack and defense strategies using a well-known virtual coordinate system and real-life Internet data sets. Thereafter, we explore supervised machine learning techniques to mitigate more subtle yet highly effective attacks (frog-boiling, network-partition) that are able to bypass existing defenses. We evaluate our techniques on the Vivaldi system against a more complex attack strategy model, where attackers perform sequences of all known attacks against virtual coordinate systems, using both simulations and Internet deployments

L’onde acoustique est utilisée par de nombreux systèmes et organismes marins pour communiquer, naviguer ou inférer de l’information sur l’environnement. Le développement des activités humaines liées au monde de la mer induit une augmentation du nombre de sources acoustiques en activité simultanée dans l’océan. L’environnement acoustique sous-marin (ASM) est donc partagé par de nombreuses sources hétérogènes (sonars, modems, mammifères marins, ...) entrant involontairement en compétition pour l’utilisation d’une ressource offerte par le canal de transmission. L’objectif de ce travail de thèse est de proposer des solutions permettant aux systèmes de communications ASM d’adapter leurs paramètres de transmission de manière intelligente, autonome et décentralisée selon l’environnement acoustique dans lequel ils évoluent. A plusieurs égards, les problématiques de ce sujet de thèse sont proches de celles ayant motivé le développement des recherches sur la radio cognitive. Cependant, les spécificités du milieu acoustique, les sources d’interférencesde diverses natures, et l’absence de standards de communications posent de nouvelles difficultés. / Underwater acoustic waves are used by many systems and biologic organisms to communicate, navigate or infer information about the environment. Future developments of human maritime activities imply an increase of the number of active acoustic sources in the oceans. The underwater environment is therefore shared by many heterogeneous sources (sonars, modems, marine mammals, ...) competing involuntarily for using the physical resources offered by the communication channel.The goal of this thesis is to provide solutions allowing autonomous and decentralized adaptation of the transmission strategies of underwater acoustic communication systems, according to the environment. To some extent, this work deals with topics that are closely related to what has motivated the first researches on cognitive radio systems. However, the specific properties of the underwater environment, the heterogeneity of interfering acoustic sources, and the absence of communication standards rise new difficulties.

Le cloud computing est l’accomplissement du rêve de nombreux informaticiens désireux de transformer et d’utiliser leurs logiciels comme de simples services, rendant ces derniers plus attractifs et séduisants pour les utilisateurs. Dans le cadre de cette thèse, les technologies du cloud computing sont présentées, ainsi que les principaux défis que ce dernier va rencontrer dans un futur proche, notamment pour la gestion et l’analyse des données. A partir de la théorie moderne d'ordonnancements des tâches, nous avons proposé une gestion hiérarchique d’ordonnancements des tâches qui satisfait aux différentes demandes des cloud services. D’un point de vue théorique, nous avons principalement répondu à trois questions cruciales de recherche. Premièrement, nous avons résolu le problème de l'allocation des ressources au niveau de l’utilisateur. Nous avons en particulier proposé des algorithmes basés sur la théorie des jeux. Avec une méthode Bayésienne d’apprentissage, l'allocation des ressources atteint l'équilibre de Nash parmi les utilisateurs en compétition malgré une connaissance insuffisante des comportements de ces derniers. Deuxièmement, nous avons abordé le problème d'ordonnancements des tâches au niveau du système. Nous avons trouvé un nouveau seuil pour l'utilisation d’ordonnancements des tâches en ligne, considérant le dispositif séquentiel de MapReduce. Ce seuil donne de meilleurs résultats que les méthodes existantes dans l’industrie. Troisièmement, nous avons défini un critère de comparaison pour les tests d’ordonnancements de tâches en ligne. Nous avons proposé un concept de fiabilité d'essai pour évaluer la probabilité qu'un ensemble de tâches aléatoires passe un essai donné. Plus la probabilité est grande, plus la fiabilité est élevée. Un test présentant une grande fiabilité garantit une bonne utilisation du système. D’un point de vue pratique, nous avons développé un simulateur basé sur le concept de MapReduce. Ce simulateur offre un environnement directement utilisable par les chercheurs familiers avec SimMapReduce, leur permettant de s’affranchir des aspects informatiques d’implémentations et leur permettant notamment de se concentrer sur les aspects algorithmiques d’un point de vue théorique. / Cloud computing, the long-held dream of computing as a utility, has the potential to transform a large part of the IT industry, making software even more attractive as a service and shaping the way in which hardware is designed and purchased. In this thesis, we reviewed the new cloud computing technologies, and indicated the main challenges for their development in future, among which resource management problem stands out and attracts our attention. Combining the current scheduling theories, we proposed cloud scheduling hierarchy to deal with different requirements of cloud services. From the theoretical aspects, we have accomplished three main research issues. Firstly, we solved the resource allocation problem in the user-level of cloud scheduling. We proposed game theoretical algorithms for user bidding and auctioneer pricing. With Bayesian learning prediction, resource allocation can reach Nash equilibrium among non-cooperative users even though common knowledge is insufficient. Secondly, we addressed the task scheduling problem in the system-level of cloud scheduling. We proved a new utilization bound for on-line schedulability test, considering the sequential feature of MapReduce. We deduced the relationship between cluster utilization bound and the ratio of Map to Reduce. This new schedulable bound with segmentation uplifts classic bound which is most used in industry. Thirdly, we settled the comparison problem among on-line schedulability tests in cloud computing. We proposed a concept of test reliability to evaluate the probability that a random task set could pass a given schedulability test. The larger the probability is, the more reliable the test is. From the aspect of system, a test with high reliability can guarantee high system utilization. From the practical aspects, we have developed a simulator to model MapReduce framework. This simulator offers a simulated environment directly used by MapReduce theoretical researchers. The users of SimMapReduce only concentrate on specific research issues without getting concerned about finer implementation details for diverse service models, so that they can accelerate study progress of new cloud technologies.

Depuis une dizaine d'années, l'étude des réseaux est une branche très active de la recherche en économie. Il est désormais largement admis que ceux-ci jouent un rôle central dans la transmission décentralisée des informations entre les individus. Les informations communiquées par ces derniers concernent aussi bien les opportunités d'emplois que l'état du marché dans lequel une équipe de travailleurs évolue. Cette thèse propose une nouvelle approche du lien entre la manière dont les agents transmettent stratégiquement leurs informations privées et la structure du réseau dont ils font partie. La théorie des jeux non coopérative a été appliquée à l'étude des réseaux sociaux et économiques dans les deux branches suivantes: d'une part, les Jeux en Réseaux considèrent que les joueurs sont les membres d'un réseau donné et analysent la manière dont les comportements stratégiques et les résultats économiques sont influencés par l'architecture de ce réseau ; d'autre part, les Jeux de Formation de Réseaux modélisent la construction stratégique des connections entre les individus. Ce travail apporte une contribution µa ces deux domaines de recherche. Dans la première partie de ma thèse, que forme le Chapitre 1 intitulé Centralisation des Informations dans les Réseaux, les joueurs appartiennent à un réseau qui affectent leur manière de transmettre leurs informations. Dans la seconde partie, constituée des Chapitres 2 et 3 et intitulée Réseaux de Communication Stratégique, la structure des liens entre les agents découle de leur communication stratégique.