Search

We study two-player zero-sum turn-based games on graphs, a framework of choice in theoretical computer science. Such games model the possibly infinite interaction between a computer system (often called reactive) and its environment. The system, seen as a player, wants to guarantee a specification (translated to a game objective) based on the interaction; its environment is seen as an antagonistic opponent. The aim is to automatically synthesize a controller for the system that guarantees the specification no matter what happens in the environment, that is, a winning strategy in the derived game.A crucial question in this synthesis quest is the complexity of strategies: when winning strategies exist for a game objective, how simple can they be, and how complex must they be? A standard measure of strategy complexity is the amount of memory needed to implement winning strategies for a given game objective. In other words, how much information should be remembered about the past to make optimal decisions about the future? Proving the existence of bounds on memory requirements has historically had a significant impact. Such bounds were, for instance, used to show the decidability of monadic second-order theories, and they are at the core of state-of-the-art synthesis algorithms. Particularly relevant are the finite-memory-determined objectives (for which winning strategies can be implemented with finite memory), as they allow for implementable controllers. In this thesis, we seek to further the understanding of finite-memory determinacy. We divide our contributions into two axes.First, we introduce arena-independent finite-memory determinacy, describing the objectives for which a single automatic memory structure suffices to implement winning strategies in all games. We characterize this property through language-theoretic and algebraic properties of objectives in multiple contexts (games played on finite or infinite graphs). We show in particular that understanding the memory requirements in one-player game graphs (i.e., the simpler situation of games where the same player controls all the actions) usually leads to bounds on memory requirements in two-player zero-sum games. We also show that if we consider games played on infinite game graphs, the arena-independent-finite-memory-determined objectives are exactly the omega-regular objectives, providing a converse to the landmark result on finite-memory determinacy of omega-regular objectives. These results generalize previous works about the class of objectives requiring no memory to implement winning strategies.Second, we identify natural classes of objectives for which precise memory requirements are surprisingly not fully understood. We introduce regular objectives (a subclass of the omega-regular objectives), which are simple objectives derived from regular languages. We effectively characterize their memory requirements for each player, and we study the computational complexity of deciding the existence of a small memory structure. We then move a step up in the complexity of the objectives and consider objectives definable with deterministic Büchi automata. We characterize the ones for which the first player needs no memory to implement winning strategies (a property called half-positionality). Thanks to this characterization, we show that half-positionality is decidable in polynomial time for this class of objectives. These results complement seminal results about memory requirements of classes of omega-regular objectives.; Les jeux sur graphes à deux joueurs et à somme nulle constituent un modèle central en informatique théorique. De tels jeux modélisent une interaction potentiellement infinie entre un système dit réactif et son environnement. Le système est considéré comme un joueur et souhaite garantir une spécification (traduite en un objectif de jeu). Son environnement est considéré comme un joueur antagoniste. Le but est de synthétiser automatiquement un contrôleur pour le système qui garantit la spécification peu importe le comportement de l'environnement, ce qui correspond à construire une stratégie gagnante dans le jeu dérivé.Une question cruciale dans cette problématique de synthèse est celle de la complexité des stratégies : si des stratégies gagnantes existent, à quel point peuvent-elles être simples et à quel point doivent-elles être complexes ? Une mesure standard de complexité des stratégies est la quantité de mémoire nécessaire pour implémenter des stratégies gagnantes pour un objectif donné. En d'autres termes, quelle quantité d'information faut-il retenir au sujet du passé pour prendre des décisions optimales concernant le futur ? Des preuves de l'existence de bornes sur les besoins en mémoire ont historiquement eu un impact important. Par exemple, de telles bornes ont mené à des preuves de décidabilité de théories monadiques du second ordre, et sont au cœur de nombreux algorithmes efficaces pour la synthèse. Les objectifs déterminés à mémoire finie (c'est-à-dire ceux qui admettent des stratégies gagnantes se limitant à une mémoire finie) sont particulièrement pertinents, car ils mènent à l'existence de contrôleurs pouvant être implémentés en pratique. Dans cette thèse, nous cherchons à améliorer la compréhension de la détermination à mémoire finie. Nous distinguons deux axes dans nos contributions.Premièrement, nous introduisons le concept de détermination à mémoire finie indépendante de l'arène, qui décrit les objectifs pour lesquels une unique structure automatique de mémoire suffit pour implémenter des stratégies gagnantes dans tous les jeux. Nous caractérisons cette propriété via des propriétés algébriques et de langages dans différents contextes (jeux joués sur des graphes finis ou infinis). Nous montrons en particulier que la compréhension des besoins en mémoire dans les jeux à un joueur (c'est-à-dire les jeux plus simples dans lesquels le même joueur contrôle toutes les actions) mène généralement à des bornes sur les besoins en mémoire dans les jeux à deux joueurs et à somme nulle. Nous montrons également que si l'on considère les jeux joués sur des graphes infinis, les objectifs déterminés à mémoire finie indépendante de l'arène sont exactement les objectifs oméga-réguliers, ce qui fournit une réciproque au célèbre théorème de détermination à mémoire finie de ces objectifs. Ces résultats généralisent des travaux précédents au sujet des objectifs pour lesquels aucune mémoire n'est nécessaire pour les stratégies gagnantes.Deuxièmement, nous identifions des classes naturelles d'objectifs pour lesquels les besoins en mémoire ne sont pas complètement établis. Nous introduisons les objectifs réguliers (une sous-classe des oméga-réguliers), qui sont des objectifs dérivés de langages réguliers. Nous donnons une caractérisation effective des besoins en mémoire de ces objectifs pour chacun des joueurs, et nous étudions la complexité de décider de l'existence d'une petite structure de mémoire. Nous considérons ensuite des objectifs plus complexes définissables avec des automates de Büchi déterministes. Nous caractérisons ceux pour lesquels le premier joueur n'a besoin d'aucune mémoire pour implémenter des stratégies gagnantes (une propriété appelée semi-positionnalité). Grâce à cette caractérisation, nous montrons que la semi-positionnalité est décidable en temps polynomial pour ces objectifs. Ces résultats complètent des travaux fondateurs sur les besoins en mémoire des objectifs oméga-réguliers.

Parmi tous les jeux de société joués par les humains au cours de l’histoire, le jeu de go était considéré comme l’un des plus difficiles à maîtriser par un programme informatique [Van Den Herik et al., 2002]; Jusqu’à ce que ce ne soit plus le cas [Silveret al., 2016]. Cette percée révolutionnaire [Müller, 2002, Van Den Herik et al., 2002] fût le fruit d’une combinaison sophistiquée de Recherche arborescente Monte-Carlo et de techniques d’apprentissage automatique pour évaluer les positions du jeu, mettant en lumière le grand potentiel de l’apprentissage automatique pour résoudre des jeux. L’apprentissage antagoniste, un cas particulier de l’optimisation multiobjective, est un outil de plus en plus utile dans l’apprentissage automatique. Par exemple, les jeux à deux joueurs et à somme nulle sont importants dans le domain des réseaux génératifs antagonistes [Goodfellow et al., 2014] ainsi que pour maîtriser des jeux comme le Go ou le Poker en s’entraînant contre lui-même [Silver et al., 2017, Brown andSandholm, 2017]. Un résultat classique de la théorie des jeux indique que les jeux convexes-concaves ont toujours un équilibre [Neumann, 1928]. Étonnamment, les praticiens en apprentissage automatique entrainent avec succès une seule paire de réseaux de neurones dont l’objectif est un problème de minimax non-convexe et non-concave alors que pour une telle fonction de gain, l’existence d’un équilibre de Nash n’est pas garantie en général. Ce travail est une tentative d'établir une solide base théorique pour l’apprentissage dans les jeux. La première contribution explore le théorème minimax pour une classe particulière de jeux non-convexes et non-concaves qui englobe les réseaux génératifs antagonistes. Cette classe correspond à un ensemble de jeux à deux joueurs et a somme nulle joués avec des réseaux de neurones. Les deuxième et troisième contributions étudient l’optimisation des problèmes minimax, et plus généralement, les inégalités variationnelles dans le cadre de l’apprentissage automatique. Bien que la méthode standard de descente de gradient ne parvienne pas à converger vers l’équilibre de Nash de jeux convexes-concaves simples, il existe des moyens d’utiliser des gradients pour obtenir des méthodes qui convergent. Nous étudierons plusieurs techniques telles que l’extrapolation, la moyenne et la quantité de mouvement à paramètre négatif. La quatrième contribution fournit une étude empirique du comportement pratique des réseaux génératifs antagonistes. Dans les deuxième et troisième contributions, nous diagnostiquons que la méthode du gradient échoue lorsque le champ de vecteur du jeu est fortement rotatif. Cependant, une telle situation peut décrire un pire des cas qui ne se produit pas dans la pratique. Nous fournissons de nouveaux outils de visualisation afin d’évaluer si nous pouvons détecter des rotations dans comportement pratique des réseaux génératifs antagonistes., Among all the historical board games played by humans, the game of go was considered one of the most difficult to master by a computer program [Van Den Heriket al., 2002]; Until it was not [Silver et al., 2016]. This odds-breaking break-through [Müller, 2002, Van Den Herik et al., 2002] came from a sophisticated combination of Monte Carlo tree search and machine learning techniques to evaluate positions, shedding light upon the high potential of machine learning to solve games. Adversarial training, a special case of multiobjective optimization, is an increasingly useful tool in machine learning. For example, two-player zero-sum games are important for generative modeling (GANs) [Goodfellow et al., 2014] and mastering games like Go or Poker via self-play [Silver et al., 2017, Brown and Sandholm,2017]. A classic result in Game Theory states that convex-concave games always have an equilibrium [Neumann, 1928]. Surprisingly, machine learning practitioners successfully train a single pair of neural networks whose objective is a nonconvex-nonconcave minimax problem while for such a payoff function, the existence of a Nash equilibrium is not guaranteed in general. This work is an attempt to put learning in games on a firm theoretical foundation. The first contribution explores minimax theorems for a particular class of nonconvex-nonconcave games that encompasses generative adversarial networks. The proposed result is an approximate minimax theorem for two-player zero-sum games played with neural networks, including WGAN, StarCrat II, and Blotto game. Our findings rely on the fact that despite being nonconcave-nonconvex with respect to the neural networks parameters, the payoff of these games are concave-convex with respect to the actual functions (or distributions) parametrized by these neural networks. The second and third contributions study the optimization of minimax problems, and more generally, variational inequalities in the context of machine learning. While the standard gradient descent-ascent method fails to converge to the Nash equilibrium of simple convex-concave games, there exist ways to use gradients to obtain methods that converge. We investigate several techniques such as extrapolation, averaging and negative momentum. We explore these techniques experimentally by proposing a state-of-the-art (at the time of publication) optimizer for GANs called ExtraAdam. We also prove new convergence results for Extrapolation from the past, originally proposed by Popov [1980], as well as for gradient method with negative momentum. The fourth contribution provides an empirical study of the practical landscape of GANs. In the second and third contributions, we diagnose that the gradient method breaks when the game’s vector field is highly rotational. However, such a situation may describe a worst-case that does not occur in practice. We provide new visualization tools in order to exhibit rotations in practical GAN landscapes. In this contribution, we show empirically that the training of GANs exhibits significant rotations around Local Stable Stationary Points (LSSP), and we provide empirical evidence that GAN training converges to a stable stationary point, which is a saddle point for the generator loss, not a minimum, while still achieving excellent performance.

Plus de 18 millions de joueurs ! Clash Royale est devenu en 2016 l’un des jeux vidéo téléchargeable gratuitement (free-to-play) parmi les plus populaires sur périphériques nomades (tablettes, smartphones, etc.). Comparé à ses concurrents qui ont adopté un modèle économique similaire, il ne semble présenter aucun mécanisme de gameplay intrusif ou bloquant. Bien au contraire, il se montre ludique, fédérateur et immersif. Pourtant, cet article démontre qu’un mécanisme plus insidieux est bel et bien présent dans Clash Royale, reposant sur un paradoxe amenant un joueur, au fur et à mesure qu’il progresse dans les parties, à se sentir à la fois incité au jeu, puis soudainement inhibé ! A travers un processus de pression sociale croissante, basé sur une structure de clan fortement hiérarchique et un système de communication autorisant les moqueries, les joueurs peuvent se retrouver malgré eux enfermés dans un « dilemme du prisonnier », avec comme seul échappatoire l’arrêt du jeu (le temps de regagner confiance en eux), ou alors l’achat de bonus facultatifs afin de devenir plus compétitifs. Le jeu vidéo entre ici dans une nouvelle dimension où la communauté peut vous conduire à votre propre perte. Entrons dans l’arène ! More than 18 million players! In 2016, Clash Royale became one of the most popular free-to-play video games on mobile devices (tablets, smartphones, etc.). Compared to its competitors who have adopted a similar business model, it does not appear to have any intrusive or blocking gameplay mechanics. On the contrary, it is playful, unifying and immersive. This article shows that a more insidious mechanism is indeed present in Clash Royale, based on a paradox which incites a player, as they progress in the games, to feel both prompted to play, and then suddenly inhibited! Through an increasing social pressure, based on a strong hierarchical clan structure and a system of communication that permits or facilitates mockery, players may find themselves locked up in a "prisoner’s dilemma", with the only escape route of gambling (to regain self-confidence by slowing up their time), or else the purchase of optional bonuses in order to become more competitive. To this end, video game brings and enters into a new dimension where the community can lead you to your own loss. Let’s enter the arena!

This thesis contributes to the economic theory literature in three aspects: price dynamics in financial markets with asymmetric information belief updating and equilibrium refinements in signaling games, and introducing ambiguity in limit pricing theory. In chapter 2, we formulate a zero-sum trading game between a better informed sector and a less 1nformed sector to endogenously determine the underlying price dynamics. In this model, player 1 is informed of the state (L) but is uncertain about player 2's belief about the state, because player 2 is informed through some message (M) related to the state. If L and M are independent, then the price proces s will be a Continuous Martingale of Maximal Variation (CMMV), and player 1 can benefit from his informational advantage. However, if L and M are not independent, player 1 will not reveal his information during the trading process, therefore, he does not benefit from his informational advantage. In chapter 3, I propose a definition of Hypothesis Testing Equilibrium (HTE) for general signaling games with non-Bayesian players nested, by an updating rule according to the Hypothesis Testing model characterized by Ortoleva (2012). An HTE may differ from a sequential Nash equilibrium because of dynamic inconsistency. However, in the case in which player 2 only treats a zero-probability message as an unexpected news, an HTE is a refinement of sequential Nash equilibrium and survives the intuitive Critenon in general signaling games but not vice versa. We provide an existence theorem covering a broad class of signaling games often studied in economics. In chapter 4, I introduce ambiguity in a standard industry organization model, in which the established firm is either informed of the true state of aggregate demand or is under classical measurable uncertainty about the state, while the potential entrant is under Knightian uncertainty (ambiguity) about the state. I characterize the conditions under which limit pricing emerges in equilibria, and thus ambiguity decreases the probability of entry. Welfare analysis shows that limit pricing is more harmful in a market with higher expected demand than in a market with lower expected demand., Cette thèse est une contribution à la théorie économique sur trois aspects: la dynamique de prix dans les marchés financiers avec asymétrie d’information, la mise à jour des croyances et les raffinements d'équilibre dans les jeux de signaux, et l'introduction de l'ambiguïté dans la théorie du prix limite. Dans le chapitre 2, nous formalisons un jeu d'échange à somme nulle entre un secteur mieux informé et un autre qui l'est moins, pour déterminer de façon endogène, la dynamique du prix sous-jacent. Dans ce modèle, joueur 1 est informé de la conjoncture (L) mais est incertain de la croyance de joueur 2, car ce dernier est seulement informé à travers un message (M) qui est lié à cette conjoncture. Si L et M sont indépendants, alors le processus de prix sera une Martingale Continue à Variation Maximale (CMMV) et joueur 1 peut disposer de cet avantage informationnel. Par contre, si L et M ne sont pas indépendants, joueur 1 ne révèlera pas son information pendant le processus, et il ne bénéficiera donc pas de son avantage en matière d'information. Dans le chapitre 3, je propose une définition de l'équilibre de Test d'hypothèse (HTE) pour des jeux de signaux généraux, avec des joueurs non-Bayésiens qui sont soumis à une règle de mise à jour selon le modèle de vérification d'hypothèse caractérisé par Ortoleva (2012). Un HTE peut être différent d'un équilibre séquentiel de Nash en raison d'une incohérence dynamique. Par contre, dans le cas où joueur 2 traite seulement un message à probabilité nulle comme nouvelle inespérée, un HTE est un raffinement d'équilibre séquentiel de Nash et survit au critère intuitif dans les jeux de signaux généraux mais pas inversement. Nous fournissons un théorème d'existence qui couvre une vaste classe de jeux de signaux qui sont souvent étudiés en économie. Dans le chapitre 4, j'introduis l’ambiguïté dans un modèle d'organisation industrielle classique, dans lequel l'entreprise déjà établie est soit informée de la vraie nature de la demande agrégée, soit soumise à une incertitude mesurable classique sur la conjoncture, tandis qu'un éventuel nouvel arrivant fait face à une incertitude a la Knight (ambiguïté) concernant cette conjoncture. Je caractérise les conditions sou lesquelles le prix limite émerge en équilibre, et par conséquent l'ambigüité diminue la probabilité d'entrée. L'analyse du bien-être montre que le prix limite est plus nocif dans un marché où la demande escomptée est plus élevée que dans un autre où celle-ci est moindre.

The paper proposes a theory of ambiguous electoral competition. A platform is ambigous if voters may interpret it as different policy proposals. An ambiguous platform puts more or less emphasis on alternative policies so that it is more or less easily interpreted as one policy or the other. I suppose that a party can monitor exactly this platform design but cannot target its communications to individuals one by one. Each individual votes according to her understanding of the parties' platforms but dislikes ambiguity. It is shown that this electoral competition has no Nash equilibrium. Nevertheless its max-min strategies are the optimal strategies of the Downsian game in mixed strategies. Furthermore, if parties behave prudently enough and if the voters aversion to ambiguity is small enough, these strategies do form an equilibrium., L'article propose une théorie de la compétition électorale ambigüe. Une plate-forme est ambigüe si les votants peuvent l'interpréter de différentes manières. Une telle plate-forme met plus ou moins de poids sur sur les différentes options possibles de sorte qu'elle est plus ou moins facilement interprétée comme une politique ou une autre. On fait l'hypothèse que les partis politiques peuvent contrôler exactement leurs plate-formes mais ne peuvent pas cibler celles-ci vers les votants individuellement. Chaque électeur vote d'après son interprétation des plate-formes des partis mais est averse à l'ambiguité. On montre que ce jeu de compétition électorale n'a pas d'équilibre de Nash. Cependant ses stratégies max-min sont les stratégies optimales du jeu Downsien en stratégies mixtes. De plus, si les partis se comportent de manière suffisament prudente par rapport à l'aversion pour l'ambiguité des électeurs, ces mêmes stratégies forment un équilibre.

In this thesis we describe some links between a) discrete and continuous time games and b) games with finitely many players and games with a continuum of players. A motivation to the subject and the main contributions are outlined in Chapter 2. The rest of the thesis is organized in three parts: Part I is devoted to differential games, describing the different approaches for establishing the existence of the value of two player, zero sum differential games in Chapter 3 and pointing out connections between them. In Chapter 4 we provide a proof of the existence of the value using an explicit description of ε-optimal strategies and a proof of the equivalence of minimax solutions and viscosity solutions for Hamilton-Jacobi-Isaacs equations in Chapter 5. Part II concerns discrete time mean field games. We study two models with different assumptions, in particular, in Chapter 6 we consider a compact action space while in Chapter 7 the action space is finite. In both cases we derive the existence of an ε-Nash equilibrium for a stochastic game with finitely many identical players, where the approximation error vanishes as the number of players increases. We obtain explicit error bounds in Chapter 7 where we also obtain the existence of an ε-Nash equilibrium for a stochastic game with short stage duration and finitely many identical players, with the approximation error depending both on the number of players and the duration of the stage. Part III is concerned with two player, zero sum stochastic games with short stage duration, described in Chapter 8. These are games where a parameter evolves following a continuous time Markov chain, while the players choose their actions at the nodes of a given partition of the positive real axis. The continuous time dynamics of the parameter depends on the actions of the players. We consider three different evaluations for the payoff and two different information structures: when players observe the past actions and the parameter and when players observe past actions but not the parameter., Cette thèse étudie les liens entre a) les jeux en temps discret et continu, et b) les jeux à très grand nombre de joueurs identiques et les jeux avec un continuum de joueurs. Une motivation pour ces sujets ainsi que les contributions principales de cette thèse sont présentées dans le Chapitre 1. Le reste de la thèse est organisé en trois parties. La Partie I étudie les jeux différentiels à somme nulle et à deux joueurs. Nous décrivons dans le Chapitre 3 trois approches qui ont été proposées dans la littérature pour établir l’existence de la valeur dans les jeux différentiels à deux joueurs et à somme nulle, en soulignant les liens qui existent entre elles. Nous fournissons dans le Chapitre 4 une démonstration de l’existence de la valeur à l’aide d’une description explicite des stratégies ε optimales. Le Chapitre 5 établit l’équivalence entre les solutions de minimax et les solutions de viscosité pour les équations de Hamilton-Jacobi-Isaacs. La Partie II porte sur les jeux à champ moyen en temps discret. L’espace d’action est supposé compact dans le Chapitre 6, et fini dans le Chapitre 7. Dans les deux cas, nous obtenons l’existence d’un ε- équilibre de Nash pour un jeu stochastique avec un nombre fini de joueurs identiques, où le terme d’approximation tend vers zéro lorsque le nombre de joueurs augmente. Nous obtenons dans le Chapitre 7 des bornes d’erreur explicites, ainsi que l’existence d’un ε-équilibre de Nash pour un jeu stochastique à durée d’étape évanescente et à un nombre fini de joueurs identiques. Dans ce cas, le terme d’approximation est fonction à la fois du nombre de joueurs et de la durée d’étape. Enfin, la Partie III porte sur les jeux stochastiques à durée d’étape évanescente, qui sont décrits dans le Chapitre 8. Il s’agit de jeux où un paramètre évolue selon une chaîne de Markov en temps continu, tandis que les joueurs choisissent leurs actions à des dates discrètes. La dynamique en temps continu dépend des actions des joueurs. Nous considérons trois évaluations différentes pour le paiement et deux structures d’information : dans un cas, les joueurs observent les actions passées et le paramètre, et dans l’autre, seules les actions passées sont observées.

The paper suggests that military history should be subjected to modelling based on the mathematical theories of rational choice, and especially the theory of games. This suggestion primarily concerns military events that have already been reported in narratives focusing on the agents' instrumental rationality, such as Clausewitz's narrative of the Waterloo campaign. By selecting relevant facts and hypotheses relative to this campaign and Napoléon's final collapse, we will investigate the decision he made on 17 June 1815 to detach part of his army against the Prussians he had defeated on the day before at Ligny. Military historians disagree on the rational sense of this crucial decision, but game theory is in a position both to illuminate it and decide between their interpretations. The model of this paper is a zero-sum, two-person game between Blücher and Napoléon and Grouchy, who are treated here as a single player. The calculated solution makes it clear that it could have been a cautious strategy on the Emperor's part to divide his army as he did, a conclusion which goes some way towards clearing him from the charges of factual mistake and even irrationality that have been laid against him by a majority of commentators since Clausewitz. Once this result is obtained, the paper moves up to the reflective and methodological plane. It compares the main objections that can be raised against its formalization with those already levelled against the recent, so-called analytic narrative school. On this score, we conclude that military campaigns - especially, though not exclusively, from the 19th century - provide a better opportunity for successful application of rational choice theories that the political examples thus far favoured by the North American school. We generalize the argument by investigating the conflict between mathematical models of rational choice and narratives - that is, the historians' canonical mode of expression. As the paper eventually suggests, the two may be reconciled. This conclusion is argued on the basis of Clausewitz's methodological precedent and an analysis of the concepts of a narrative (in general), a historical narative and an event., L'article propose d'appliquer à l'histoire militaire les modèles venus des théories mathématiques du choix rationnel et, plus particulièrement, de la théorie des jeux. La proposition vise avant tout les événements militaires dont il préexiste des récits ordonnés par la rationalité instrumentale des acteurs, comme celui que Clausewitz consacre à la campagne de Waterloo. Reprenant sélectivement les faits de cette campagne et les hypothèses qu'a suscitées l'échec final de Napoléon, on étudie la décision qu'il prit le 17 juin 1815 de lancer un détachement de son armée contre les Prussiens battus la veille à Ligny. Les historiens militaires ne s'accordent pas sur le sens rationnel de cette décision capitale, mais la théorie des jeux permet de l'éclairer tout en les départageant. Le modèle développé ici est un jeu à somme nulle opposant Blücher à Napoléon et Grouchy, considérés comme un seul joueur. Le calcul de la solution fait apparaître que la division de l'armée à laquelle procéda l'Empereur pouvait être une stratégie prudente de sa part, ce qui l'acquitte jusqu'à un certain point des accusations d'erreur factuelle ou même d'irrationalité qui dominent le commentaire depuis Clausewitz. Une fois obtenu ce résultat, l'article se développe sur le plan réflexif et méthodologique. Il compare les objections principales qu'on peut faire à sa formalisation et celles qu'on a déjà élevées contre l'école récente dite du "récit analytique". Il conclut sur ce point que les campagnes militaires - notamment, mais non exclusivement celles du XIXe siècle - offrent aux théories du choix rationnel des applications plus faciles à mener que les exemples politiques jusqu'à présent privilégiés dans le courant nord-américain. Amplifiant le propos, l'article examine le conflit des modèles mathématisés du choix rationnel avec le récit, mode d'expression canonique de l'histoire. Il propose une conciliation qui se fonde à la fois sur le précédent méthodologique de Clausewitz et sur une analyse des concepts de narration, de récit historique et d'événement.

This dissertation consists of three parts, the first two in game theory and the third one in theoretical biology. The first part studies the correlated equilibrium concept, due to Aumann. We first investigate the properties and applications of the dual reduction technique, introduced by Myerson. We then use this technique to show that the set of games with a unique correlated equilibrium is open, which is not true for Nash equilibrium, and to characterize the class of games with a Nash equilibrium in the relative interior of the correlated equilibrium polytope. In the two-player case, this class of games generalizes two-person zero-sum games. Two other contributions are also presented.The second part deals with evolutionary games and studies the link between evolutionary dynamics and static strategic concepts. We show in particular that evolutionary dynamics may eliminate all strategies in the support of at least one correlated equilibrium. This occurs under any monotonic dynamics whose vector field depends continuously on the payoffs, and for open sets of games and initial conditions. Furthermore, elimination of all strategies in the support of Nash equilibria occurs under any smooth myopic adjustment dynamics and, under the replicator dynamics or the best-response dynamics, from almost all initial conditions.The third part, co-written, studies the factors driving cell differentiation, and especially germ-soma differentiation in volvocine green algae.; La thèse se compose de trois parties dont les deux premières se rattachent à la théorie des jeux et la troisième à la biologie théorique. La première partie est consacrée à l'étude des équilibres corrélés. Après avoir étudié les propriétés de la techique de réduction duale et développé ses applications, nous utilisons cette technique pour montrer que l'ensemble des jeux ayant un unique équilibre corrélé est ouvert, ce qui n'est pas vrai des équilibres de Nash, et pour caractériser la classe des jeux dont le polytope des équilibres corrélés contient un équilibre de Nash dans son intérieur relatif. Cette classe étend et généralise celle des jeux à somme nulle. Deux autres contributions sont également présentées. La deuxième partie est consacrée aux jeux d'évolution, et étudie le lien entre l'issue de processus évolutifs et les concepts stratégiques statiques. Nous montrons notamment que les dynamiques d'évolution peuvent éliminer toutes les stratégies appartennant au support d'au moins un équilibre corrélé, et ce pour n'importe quelle dynamique monotone et pour des ensembles ouverts de jeux et de conditions initiales. L'élimination de toutes les stratégies dans le support des équilibres de Nash se produit sous toutes les dynamiques d'adaptation myope régulières et, sous la dynamique des réplicateurs ou la dynamique de meilleure réponse, à partir de presque toutes les conditions initiales. La troisième partie, co-écrite, étudie les déterminants de la séparation entre lignée germinale et lignée somatique chez les algues vertes volvocales.

This dissertation consists of three parts, the first two in game theory and the third one in theoretical biology. The first part studies the correlated equilibrium concept, due to Aumann. We first investigate the properties and applications of the dual reduction technique, introduced by Myerson. We then use this technique to show that the set of games with a unique correlated equilibrium is open, which is not true for Nash equilibrium, and to characterize the class of games with a Nash equilibrium in the relative interior of the correlated equilibrium polytope. In the two-player case, this class of games generalizes two-person zero-sum games. Two other contributions are also presented.The second part deals with evolutionary games and studies the link between evolutionary dynamics and static strategic concepts. We show in particular that evolutionary dynamics may eliminate all strategies in the support of at least one correlated equilibrium. This occurs under any monotonic dynamics whose vector field depends continuously on the payoffs, and for open sets of games and initial conditions. Furthermore, elimination of all strategies in the support of Nash equilibria occurs under any smooth myopic adjustment dynamics and, under the replicator dynamics or the best-response dynamics, from almost all initial conditions.The third part, co-written, studies the factors driving cell differentiation, and especially germ-soma differentiation in volvocine green algae., La thèse se compose de trois parties dont les deux premières se rattachent à la théorie des jeux et la troisième à la biologie théorique. La première partie est consacrée à l'étude des équilibres corrélés. Après avoir étudié les propriétés de la techique de réduction duale et développé ses applications, nous utilisons cette technique pour montrer que l'ensemble des jeux ayant un unique équilibre corrélé est ouvert, ce qui n'est pas vrai des équilibres de Nash, et pour caractériser la classe des jeux dont le polytope des équilibres corrélés contient un équilibre de Nash dans son intérieur relatif. Cette classe étend et généralise celle des jeux à somme nulle. Deux autres contributions sont également présentées. La deuxième partie est consacrée aux jeux d'évolution, et étudie le lien entre l'issue de processus évolutifs et les concepts stratégiques statiques. Nous montrons notamment que les dynamiques d'évolution peuvent éliminer toutes les stratégies appartennant au support d'au moins un équilibre corrélé, et ce pour n'importe quelle dynamique monotone et pour des ensembles ouverts de jeux et de conditions initiales. L'élimination de toutes les stratégies dans le support des équilibres de Nash se produit sous toutes les dynamiques d'adaptation myope régulières et, sous la dynamique des réplicateurs ou la dynamique de meilleure réponse, à partir de presque toutes les conditions initiales. La troisième partie, co-écrite, étudie les déterminants de la séparation entre lignée germinale et lignée somatique chez les algues vertes volvocales.

This paper is concerned both with the comparative geometry of Nash and correlated equilibria, and with a generalization of zero-sum games based on correlated equilibria. The set of correlated equilibrium distributions of any finite game in strategic form is a polytope, which contains the Nash equilibria. I characterize the class of games such that this polytope (if not a singleton) contains a Nash equilibrium in its relative interior. This class of games, though not defined by some antagonistic property, is shown to include and generalize two-player zero-sum games., Ce papier porte à la fois sur la géométrie des équilibres de Nash et des équilibres corrélés et sur une généralisation des jeux à sommes nulles fondée sur les équilibres corrélés. L'ensemble des distributions d'équilibres corrélés de n'importe quel jeu fini est un polytope, qui contient les équilibres de Nash. Je caractérise la classe des jeux tels que ce polytope (s'il ne se réduit pas à un singleton) contienne un équilibre de Nash dans son intérieur relatif. Bien que cette classe de jeux ne soit pas définie par une propriété d'antagonisme entre les joueurs, je montre qu'elle inclut et qu'elle généralise la classe des jeux à deux joueurs et à somme nulle.