Cette thèse est consacrée à une étude d'un point de vue général de jeux d'accessibilité dans des systèmes munis de compteurs. Dans ce type de jeux, l'objectif de l'un des deux joueurs est d'atteindre une configuration particulière, qui est composée d'un sommet de l'arène où le jeu se déroule et d'un n-uplet de valeurs pour les compteurs. Ces valeurs de compteurs sont mises à jour, généralement par des additions de vecteurs, lorsqu’un arc est emprunté. Le problème de décision associé à un jeu d’accessibilité est de savoir si le joueur en question a une stratégie gagnante depuis une configuration donnée. Lorsque ce problème est décidable, on s’intéresse à la possibilité de décrire l’ensemble de ces configurations dites gagnantes. Au cours de l’étude, des caractéristiques des jeux d’accessibilités avec des compteurs sont mises en parallèle, en cherchant des similarités, ou au contraire des différences, au niveau de la décidabilité et de la complexité du problème de décision, quand l’une de ces caractéristiques est modifiée. On retiendra en tant que caractéristique majeure le comportement quand un compteur devrait devenir négatif. Nous nous focalisons principalement sur trois sémantiques. Nous considérons également d’autres caractéristiques selon lesquelles il était possible de comparer décidabilité et complexité. Nous nous penchons sur un modèle intitulé « robot games », sur lequel nous obtenons des résultats majeurs : un algorithme de complexité asymptotiquement optimale en dimension un et une preuve d’indécidabilité en dimension trois. / This thesis is devoted to a general study of a reachability games on systems with counters. In this kind of games, the objective of one of two players is to reach a particular configuration, which is a pair composed of a vertex of the game arena and a tuple of values for the counters. The values of the counters are updated, usually by vector additions, when a edge is taken. The decision problem associated with a reachability game is whether a player has a winning strategy for the game from a given configuration, in other words whether the configuration is winning. When the problem of determining the winner from a given configuration is decidable, we wonder whether it is even possible to describe the set of winning configurations. In our study, we look at various features of counter reachability games, finding similarities or, on the contrary, differences with regard to decidability or complexity of the decision problem, when one of the features is modified. The main feature that we consider is what happens when a counter should become negative. We focus primarily on three semantics. We also consider other features that allow to compare decidability and complexity. We introduce a model, called “robot games”, on which we obtain our main results: an algorithm with an optimal complexity for dimension one, and undecidability for dimension three.

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.

La négociation est un processus pour atteindre un accord concernant un certain sujet entre deux ou plusieurs agents. Dans la négociation basée sur la théorie des jeux, la négociation est vue comme un jeu. Un jeu est appliqué à chaque situation dans laquelle les participants interagissent pour trouver une solution. La négociation basée sur l’argumentation est faite par un échange d’arguments entre les agents négociateurs. Il y a beaucoup de travaux en négociation par la théorie des jeux qui traitent de tous les aspects de la négociation. D’autre part, les recherches en négociation par argumentation se sont principalement focalisées sur les protocoles pour réguler la négociation et les mécanismes de décisions pour générer et ordonner les offres; Cependant l’étude des aspectsstratégiques qui définissent le comportement de l’agent durant la négociation ont été largement négligés. Cela reste vrai pour la contrainte du temps.Cette thèse essaie de combler ces lacunes en travaillant en trois directions. Premièrement, un cadre pour la négociation par argumentation est proposé et qui est basé sur quelques concepts étudiés en négociation par la théorie des jeux. Ce cadre permet de classer les offres suivant les arguments qui les supportent et de négocier en utilisant une adaptation du très connu Alternating Offers Protocol proposé en théorie des jeux. Pour ce protocole une stratégie générique qui peut être utilisée avec n’importe quelle relation de préférence entre les offres et avec n’importe quelle forme de concession a été définie. Deuxièmement, cette thèse propose quelques tactiques pour la négociation par argumentation avec une contrainte de temps. Les tactiques sont basées sur l’information que l’agent possède sur son adversaire. Cette information est collectionnée durant le processus de négociation ou est obtenue en connaissant le rôle de son opposant. En dernier lieu, une évaluation expérimentale montre que les tactiques et les concessions influencent la longueur de la négociation et l’issue de la négociation, sous les hypothèses de contrainte de temps et de la connaissance de certaines informations sur l’agent adversaire. / Negotiation is the process to reach an agreement concerning matters between two or several agents. In game theoretic negotiation, the latter is seen as a game. A game is applied to every situation in which the participants interact to find a solution. Argumentation-based negotiation is done by exchanging arguments between the participating agents. There is a lot of work in game-theoretic negotiation that deals with all the aspects of negotiation. On the other hand, research in argumentation-based negotiation has focused mainly on the protocols to regulate the negotiation and reasoning mechanisms to generate and order offers; however the study of strategic issues that define the behavior of an agent during the negotiation has been largely neglected. The same holds for the time constraint.This thesis tries to fill this gap by working in three directions. Firstly, a framework for argumentation-based negotiation is proposed which is based on some concepts studied in game-theoretic negotiation. The framework permits to set in order the different offers following the supporting arguments and to negotiate by using an adaptation of the well known Alternating Offers Protocol propounded in game theory. For this protocol a generic strategy which can be used with any form of preference relationship over the set of offers and with any form of concession is given. Secondly, this thesis proposes some tactics for time constrained argumentation-based negotiation. The tactics are based on the information that an agent possesses about his opponent agent. This information is gathered during the negotiation dialogue or is obtained by knowing the role of the opponent agent. Finally, an experimental evaluation is presented that shows how tactics and concessions may influence the negotiation length and outcome, under the assumptions of time constraints and the availability of information on the opponent.

Les protéines et acides ribonucléiques sont les principaux acteurs de nombreux processus cellulaires.Comprendre leurs fonctions, structures et interactions est un challenge important.Les méthodes expérimentales fournissent des informations sur la structure et la dynamique des molécules.Cependant les méthodes expérimentales sont limitées par le nombre de molécules qu'elles peuvent observer et les moyens qu'elles requièrent.Les méthodes de prédiction permettent d'obtenir des informations structurelles de façon quasi-automatique.Pour s'assurer de leur fiabilité, elles sont testées sur des données expérimentales.Nous présentons une procédure basée sur la cinétique inverse pour trouver une transition entre deux conformations d'un ARN tout en conservant sa structure secondaire.Nous obtenons des résultats comparables à l'état de l'art, ce qui montre que notre sélection des degrés de liberté est pertinente.De plus, nous utilisons des données partielles, ce qui permet d'utiliser différents types de résultats expérimentaux.Nous abordons aussi le problème du repliement protéique par une approche de théorie des jeux.Nous représentons une protéine par un jeu où les joueurs sont les acides aminés et les stratégies, les angles dièdres.La prédiction de structure peut alors être vue comme la recherche d'un équilibre dans un jeu multi-joueur où les fonctions d'utilité correspondent à la qualité du repliement.Nous montrons que l'algorithme de non-regret, appelé Hedge, garantit l'élimination des stratégies dominées et la convergence locale vers un équilibre de Nash.Puis, en limitant notre analyse aux jeux de potentiel, nous montrons qu'une classe plus large d'algorithmes, les algorithmes de régularisation, convergent vers un équilibre de Nash presque surement. / Proteins and Ribonucleic Acids are the workhorses of many cellular processes.Understanding their functions, structures and interactions is an important challenge.Experimental methods provide actual information on structure and dynamics of molecules.However they have limitations : they cannot be applied to all molecules, and they need a lot of resources.Prediction methods are almost automatic ways of obtaining structural information.They are tested on experimental data to attest their reliability.We present, here, approaches tackling different problems.We develop a kinematics-based procedure to morph a RNA molecule between conformations while preserving its secondary structure.We obtain results comparable to state of the art methods showing that our selection of degrees of freedom is efficient.Furthermore we only use sparse information allowing for various kinds of experimental inputs.We also look at the protein structure prediction problem from a game theory angle.We represent the protein dynamics as a game, in which players are amino acids and strategies are dihedrals angles.The structure prediction can thus be seen as finding equilibrium in a multi-players game where all players have utility functions corresponding to the quality of the protein structure.We showed that a well-known no-regret algorithm, called Hedge, guarantees dominated strategies to vanish and a local convergence toward Nash equilibria.Furthermore restricting our analysis to potential games we showed that dual-averaging regularized learning algorithms converge toward a Nash equilibrium almost surely.

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.

De nos jours la protection des réseaux logistiques représente un vrai défi. Dans la littérature, plusieurs travaux ont examiné ce problème et ont proposé des modèles pour la défense stratégique des réseaux logistiques. Habituellement, chaque réseau protège individuellement ses installations en utilisant ses propres moyens. Or, la protection collaborative de ces réseaux est susceptible d'engendrer une amélioration de l'utilité des stratégies de défense utilisées et une réduction des coûts de cette protection. Nous considérons, dans ce mémoire, un ensemble des réseaux logistiques qui ont accepté de collaborer pour améliorer leurs méthodes de protection. Tout d'abord, nous avons commencé par définir et appliquer un modèle de protection stratégique basé sur la théorie des jeux non coopératifs sur un ensemble de réseaux logistiques, afin de déterminer les stratégies de défenses qui seront adoptées individuellement par chaque réseau. Ce modèle a été ensuite étendu et modifié dans le cas où plusieurs réseaux logistiques décidèrent de collaborer pour améliorer l'utilité de leurs stratégies de défense. Ce modèle permet également, l'évaluation de l'utilité de cette coalition et la réduction des coûts générés grâce à la collaboration. Pour que cette collaboration soit durable et bénéfique pour tous les réseaux, nous devons allouer les coûts engendrés par cette coalition à tous les participants de façon équitable. Pour cela, nous appliquons plusieurs méthodes de partage des coûts issues de la théorie des jeux collaboratifs. Enfin, ces modèles seront appliqués pour le cas de deux réseaux logistiques.

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?