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.

In contexts involving multiple agents (players), determining how they can cooperate through the formation of coalitions and how they can share surplus benefits coming from the collaboration is crucial. This can provide decision-aid to players and analysis tools for policy makers regulating economic markets. Such settings belong to the field of cooperative game theory. A critical element in this area has been the size of the representation of these games: for each possible partition of players, the value of each coalition on it must be provided. Symmetric partition function form games (SPFGs) belong to a class of cooperative games with two important characteristics. First, they account for externalities provoked by any group of players joining forces or splitting into subsets on the remaining coalitions of players. Second, they consider that players are indistinct, meaning that only the number of players in each coalition is relevant for the SPFG. Using mixed-integer programming, we present the first representation of SPFGs that is polynomial on the number of players in the game. We also characterize the family of SPFGs that we can represent. In particular, the representation is able to encode exactly all SPFGs with five players or less. Furthermore, we provide a compact representation approximating SPFGs when there are six players or more and the SPFG cannot be represented exactly. We also introduce a flexible framework that uses stability methods inspired from the literature to identify a stable social-welfare maximizing game outcome using our representation. We showcase the value of our compact (approximated) representation and approach to determine a stable partition and payoff allocation to a competitive market from the literature., Dans tout contexte impliquant plusieurs agents (joueurs), il est impératif de déterminer comment les agents coopéreront par la formation de coalitions et comment ils partageront les bénéfices supplémentaires issus de la collaboration. Ceci peut fournir une aide à la décision aux joueurs, ou encore des outils d'analyse pour les responsables en charge de réguler les marchés économiques. De telles situations relèvent de la théorie des jeux coopérative. Un élément crucial de ce domaine est la taille de la représentation de ces jeux : pour chaque partition de joueurs possible, la valeur de chaque coalition qu'on y retrouve doit être donnée. Les jeux symétriques à fonction de partition (SPFG) appartiennent à une classe de jeux coopératifs possédant deux caractéristiques principales. Premièrement, ils sont sensibles aux externalités, provoquées par n'importe quel groupe de joueurs qui s'allient ou défont leurs alliances, qui sont ressenties par les autres coalitions de joueurs. Deuxièmement, ils considèrent que les joueurs sont indistincts, et donc que seul le nombre de joueurs dans chaque coalition est à retenir pour représenter un SPFG. Par l'utilisation d'outils de programmation mixte en nombres entiers, nous présentons la première représentation de SPFG qui est polynomiale en nombre de joueurs dans le jeu. De surcroît, nous caractérisons la famille des SPFG qu'il est possible de représenter, qui inclut notamment tous les SPFG de cinq joueurs ou moins. De plus, elle dispose d'une approximation compacte pour le cas où, dans un jeu à six joueurs ou plus, le SPFG ne peut pas être représenté de façon exacte. Également, nous introduisons un cadre flexible qui utilise des méthodes visant la stabilité inspirées par la littérature pour identifier, à l'aide de notre représentation, une issue stable qui maximise le bien-être social des joueurs. Nous démontrons la valeur de notre représentation (approximée) compacte et de notre approche pour sélectionner une partition stable et une allocation des profits dans une application de marché compétitif provenant de la littérature.

L’apprentissage automatique repose pour un bon nombre de problèmes sur la minimisation d’une fonction de coût, pour ce faire il tire parti de la vaste littérature sur l’optimisation qui fournit des algorithmes et des garanties de convergences pour ce type de problèmes. Cependant récemment plusieurs modèles d’apprentissage automatique qui ne peuvent pas être formulé comme la minimisation d’un coût unique ont été propose, à la place ils nécessitent de définir un jeu entre plusieurs joueurs qui ont chaque leur propre objectif. Un de ces modèles sont les réseaux antagonistes génératifs (GANs). Ce modèle génératif formule un jeu entre deux réseaux de neurones, un générateur et un discriminateur, en essayant de tromper le discriminateur qui essaye de distinguer les vraies images des fausses, le générateur et le discriminateur s’améliore résultant en un équilibre de Nash, ou les images produites par le générateur sont indistinguable des vraies images. Malgré leur succès les GANs restent difficiles à entrainer à cause de la nature antagoniste du jeu, nécessitant de choisir les bons hyperparamètres et résultant souvent en une dynamique d’entrainement instable. Plusieurs techniques de régularisations ont été propose afin de stabiliser l’entrainement, dans cette thèse nous abordons ces instabilités sous l’angle d’un problème d’optimisation. Nous commençons par combler le fossé entre la littérature d’optimisation et les GANs, pour ce faire nous formulons GANs comme un problème d’inéquation variationnelle, et proposons de la littérature sur le sujet pour proposer des algorithmes qui convergent plus rapidement. Afin de mieux comprendre quels sont les défis de l’optimisation des jeux, nous proposons plusieurs outils afin d’analyser le paysage d’optimisation des GANs. En utilisant ces outils, nous montrons que des composantes rotationnelles sont présentes dans le voisinage des équilibres, nous observons également que les GANs convergent rarement vers un équilibre de Nash mais converge plutôt vers des équilibres stables locaux (LSSP). Inspirer par le succès des GANs nous proposons pour finir, une nouvelle famille de jeux que nous appelons adversarial example games qui consiste à entrainer simultanément un générateur et un critique, le générateur cherchant à perturber les exemples afin d’induire en erreur le critique, le critique cherchant à être robuste aux perturbations. Nous montrons qu’à l’équilibre de ce jeu, le générateur est capable de générer des perturbations qui transfèrent à toute une famille de modèles., Many machine learning (ML) problems can be formulated as minimization problems, with a large optimization literature that provides algorithms and guarantees to solve this type of problems. However, recently some ML problems have been proposed that cannot be formulated as minimization problems but instead require to define a game between several players where each player has a different objective. A successful application of such games in ML are generative adversarial networks (GANs), where generative modeling is formulated as a game between a generator and a discriminator, where the goal of the generator is to fool the discriminator, while the discriminator tries to distinguish between fake and real samples. However due to the adversarial nature of the game, GANs are notoriously hard to train, requiring careful fine-tuning of the hyper-parameters and leading to unstable training. While regularization techniques have been proposed to stabilize training, we propose in this thesis to look at these instabilities from an optimization perspective. We start by bridging the gap between the machine learning and optimization literature by casting GANs as an instance of the Variational Inequality Problem (VIP), and leverage the large literature on VIP to derive more efficient and stable algorithms to train GANs. To better understand what are the challenges of training GANs, we then propose tools to study the optimization landscape of GANs. Using these tools we show that GANs do suffer from rotation around their equilibrium, and that they do not converge to Nash-Equilibria. Finally inspired by the success of GANs to generate images, we propose a new type of games called Adversarial Example Games that are able to generate adversarial examples that transfer across different models and architectures.

Les rivières, lacs et aquifères transfrontaliers à travers la planète sont des catalyseurs de tension internationale. Le partage des ressources en eau entre les États est sujet à des défis de plus en plus aigus avec une demande en constante croissance et une variabilité de l’offre exacerbée par les changements climatiques. Cet enjeu bénéficie de peu d’encadrement juridique alors que les accords entre États riverains sont exceptionnels et peu efficaces et que le droit en la matière est controversé. Ce mémoire se veut une étude de trois méthodes d’analyse en droit international public des conflits dans le partage de ces cours d’eau partagés en utilisant l’exemple de la construction d’un ouvrage hydraulique d’envergure sur le Nil Bleu, dont l’Éthiopie, le Soudan et l’Égypte sont les tributaires. Une première méthode consiste à étudier les instruments régionaux qui ont tenté d’attribuer les eaux transfrontières et les droits de développement industriel. Une seconde approche propose d’examiner l’application du droit multilatéral et coutumier relatif aux utilisations des cours d'eau internationaux à des fins autres que la navigation. La troisième démarche vise à déterminer l’étendue et les bénéfices de l’obligation de coopérer en droit international public. Une fois ces trois méthodes appliquées, l’auteur arrive à la conclusion que les instruments régionaux du bassin du Nil et le droit international applicable, notamment codifié dans la Convention sur le droit relatif aux utilisations des cours d'eau internationaux à des fins autres que la navigation, n’offrent aucune solution juridique définitive en raison (i) de l’absence de force contraignante ou (ii) de conflits interprétatifs irréconciliables. Quant à elle, l’obligation de coopérer, quoi que limitée dans son étendue, est source d’optimisme., Transboundary rivers, lakes and aquifers around the world are catalysts for international tension. The sharing of water resources between States is subject to increasingly acute challenges with a constantly growing demand and a variability of supply exacerbated by climate change. This issue benefits from limited legal guidance, while agreements between riparian states are exceptional and inefficient and the law in this area is controversial. This paper examines three methods of analysis in public international law of conflicts in the sharing of these shared watercourses, using the example of the construction of a major hydraulic structure on the Blue Nile, of which Ethiopia, Sudan and Egypt are tributaries. A first approach is to examine the regional instruments that have attempted to allocate transboundary waters and industrial development rights. A second approach proposes to examine the application of multilateral and customary international law relating to the non-navigational uses of international watercourses. The third approach seeks to determine the scope and benefits of the duty to cooperate under public international law. After applying these three methods, the author concludes that the regional instruments of the Nile Basin and the applicable international law, notably codified in the Convention on the Law of Non-Navigational Uses of International Watercourses, do not offer any firm legal solution due to (i) lack of binding force or (ii) irreconcilable interpretative conflicts. As for the obligation to cooperate, although limited in scope, it is a source of optimism.

La littérature sur les entrevues d’enquête du milieu policier a mis en évidence les facteurs associés à la confession. Des recherches ont montré que la confession est associée à des suspects plus jeunes (Deslauriers-Varin & St-Yves, 2010; Viljoen, et al., 2005); des personnes d'origine caucasienne (St-Yves, 2002; Viljoen, et al., 2005); des célibataires (St-Yves, 2002); et le type de crime (Moston et coll., 1992; Phillips et Brown, 1998). La recherche a également examiné le rôle de la quantité et la nature de la preuve (p.ex., Brimbal & Luke, 2019 ; Deslauriers-Varin, et al., 2011, 2020 ; Moston & Engelberg, 2011), la manière dont les preuves sont présentées (p.ex., l'utilisation stratégique des preuves; Clemens et al., 2020 ; Granhag et al., 2013), et le rôle des enquêteurs et des techniques d'enquête (p.ex., May, et al., 2017; Snook et al., 2015; Wachi, et al., 2014). Cependant, la littérature sur l'entrevue d’enquête a mis l'accent sur les mesures de corrélation entre la confession et les variables qui peuvent l'influencer comme si elle était stable dans le temps. Pourtant, il existe des preuves que la confession pourrait être un processus instable influencé par des éléments contextuels. Par exemple, des chercheurs ont évoqué le changement de décision (vers l'aveu ou vers le déni) qui s'opère avec les suspects dans le cadre d'un interrogatoire (Bull & Soukara, 2010; Deslauriers-Varin, et al., 2011a ; Walsh et Bull, 2012). Plus récemment, dans la littérature, les chercheurs se sont engagés dans un virage clair vers une analyse de l'entrevue d’enquête qui prenait en compte des différents aspects dynamiques de la situation tel que l’ordre des comportements dans le temps (p.ex., Kelly, et al., 2016 ; Yang, et al., 2017). Pour participer à ce virage et contribuer à la recherche dans le domaine, nous proposons une nouvelle conceptualisation de l'entrevue d’enquête à travers une nouvelle perspective théorique : la Théorie des Jeux. Une discussion sur la théorie et ses concepts est suivie de deux articles empiriques qui visent à mieux étudier les entrevues. Le premier article explore l'influence mutuelle des deux participants sur l’obtention d’information pertinente à l’enquête. Des entretiens enregistrés sur vidéo liés à l'exploitation sexuelle d'enfants sur internet (n = 130) ont été utilisés et les différents comportements des suspects et des enquêteurs ont été analysés pour déterminer s'ils impliquaient (1) l'établissement d'un rapport/le déni actif, (2) la collaboration, (3) la confrontation, (4) l’émotion/réponse, et (5) l’obtention d'informations liées à l’enquête. Les résultats ont montré que les informations pertinentes à l'enquête sont souvent fournies peu de temps après qu'un suspect a offert des informations supplémentaires ou s’est montré émotif (par exemple, pleure). Lorsque l’enquêteur présente des preuves, la probabilité que des informations supplémentaires soient fournies par le suspect augmente immédiatement. Cependant, établir un rapport avec le suspect est efficace à plus long terme alors qu’un effet positif n'est pas immédiatement observé. En utilisant le même échantillon, la deuxième étude explore l'hétérogénéité des stratégies et des comportements des suspects lors d’une entrevue d’enquête ainsi que la stabilité de ces profils dans le temps puisque les comportements des suspects est un sujet rarement abordé dans la littérature contrairement aux comportements de l’interviewer. L'analyse a permis d'identifier la présence de cinq profils différents : 1) Positif ; 2) Justifiant ; 3) Accepter ; 4) Contrôler ; 5) Irrité. L'analyse temporelle montre également que la majorité des suspects restent dans le même profil au cours de l'entretien. Cette thèse a permis d’instaurer une base théorique et méthodologique pour l'étude des interactions sociales asymétriques à travers l'utilisation de la perspective de la Théorie des Jeux. Plus particulièrement, le contexte de l'entrevue d’enquête des délinquants sexuels en ligne a été observé et les résultats pointent vers le fait que l'interaction sociale qui a lieu dans la salle d'interrogatoire est influencée par les stratégies de l’interviewer et du suspect. De plus, les décisions prises par le suspect aux cours de l’entrevue sont explorées et semblent être associés à leurs préférences. La thèse accorde également une attention particulière à la notion complexe de temps ainsi que son impact sur les comportements et propose une évaluation temporelle continue de l'interaction plutôt que de segmenter l’entrevue tel que vu dans la littérature. Les résultats visent à développer une nouvelle façon d’étudier l’entrevue d’enquête afin d’éventuellement fournir des outils pratiques aux policiers sur le type de stratégies à utiliser selon le temps dont ils disposent et sur le type de suspect avec lequel ils travaillent. Les résultats contribuent également à établir des méthodologies pour l’analyse de d'autres types d'interactions asymétriques qui sont courantes dans le domaine de la criminologie. Considérer l’entrevue d’enquête comme étant une interaction sociale représentant un processus qui évolue dans le temps fournit un point de départ pour la création de directives pratiques pour aider les praticiens à accroître la collaboration des suspects., The literature on police investigative interviewing has highlighted the factors associated with confession. Research has shown that confession is associated with younger suspects (Deslauriers-Varin & St-Yves, 2010; Viljoen, et al., 2005); individuals of Caucasian origin (St-Yves, 2002; Viljoen, et al., 2005); single individuals (St-Yves, 2002); and individuals who have committed less serious crime (Moston et al., 1992; Phillips & Brown, 1998). Research also examines the role of evidence strength (e.g., Brimbal & Luke, 2019; Deslauriers-Varin, et al., 2011, 2020; Moston & Engelberg, 2011), the way in which evidence is presented (e.g., strategic use of evidence; Clemens et al., 2020; Granhag et al., 2013), and the role of police investigators and investigative techniques (e.g., May, et al., 2017; Snook et al., 2015; Wachi, et al., 2014). However, the literature on investigative interviewing has emphasized measures of correlation between confession and the variables that may influence it as if they were stable over time. Yet, there is evidence that confession could be an unstable process influenced by contextual elements. For example, researchers have raised the change in decision (towards confession or even towards denial) that operates with suspects in the context of an interrogation (Bull & Soukara, 2010, Deslauriers-Varin, et al., 2011a; Walsh & Bull, 2012; Verhoeven, 2018). More recently in the literature, researchers engaged in a clear shift toward a more dynamic analysis of investigative interview (e.g., Kelly, et al., 2016; Yang, et al., 2017). To contribute to the research in this field, we propose a new conceptualization of the investigative interview through a new theoretical perspective: Game Theory. A discussion on the theory and its concept leads to two empirical articles that aim to study interviews more effectively. The first one explores the dynamic influence of both participants, the interviewer and the suspect, on suspect's disclosure. Videotaped interviews related to online child sexual exploitation (n=130) were analyzed and the different behaviors of suspects and interviewers were analyzed to determine if they involved (1) rapport building/active denial, (2) collaboration, (3) confrontation, (4) emotion/response, and (5) elicitation of information related to the case. Results showed that information relevant to the investigation is often provided shortly after a suspect has offered additional information or given responses that meet emotional needs (e.g., justifications). The interviewer’s use of available evidence increases the likelihood that additional information will be provided, while the ability to build a rapport with the suspect is effective in the longer term, even if a positive effect is not immediately observed. The second study explores the heterogeneity of strategies and behaviors of suspects during an interview as well as the stability of those profiles as suspects behaviors is a subject that have been overlooked in the literature contrarily to interviewers behaviors. The analysis helped identify the presence of five different profiles: 1) Positive; 2) Justifying; 3) Accepting; 4) Controlling; 5) Irritated. The temporal analysis also shows that the probability that a suspect will continue to exhibit the same profile over the course of the interview is high. This thesis allows to set a theoretical and methodological basis to the study of asymmetrical interaction through the use of the Game Theory perspective. More particularly, the context of investigative interviewing of online sex offenders has been observed and the results point toward the fact that both the suspect and the interviewer influence the course of the social interaction that takes place in the interrogation room. Moreover, the decisions of the suspects have been explored and seems to be taken according to their preferences. The thesis also gives particular attention to the complex notion of time and its influence on behavior and proposes, in the fourth chapter, a continuous timeline evaluation of the interaction instead of a segmented analysis. The findings help develop a new line of research with innovative methods in order to eventually provide practical tools to police investigators on the matter of the type of strategies to use according to the amount of time they have and on the type of suspect they are working with. The findings also contribute to setting methodologies for other types of asymmetrical interaction which are common in the field of criminology. Seeing the interviews as being an interaction process provides a starting point for the creation of practical guidelines to help practitioners increase suspect collaboration during investigative interviews.

National audience; Pour fluidifier le trafic, parfois la solution consiste à fermer une route à la circulation. Étonnant non ? Cette situation fut observée en 1990 à New York lorsque la municipalité décida de fermer temporairement la 42e rue, l'une des plus congestionnées de la ville. Contre toute attente, cela a réduit les embouteillages sur le réseau ! C'est l’une des premières illustrations en situation réelle du paradoxe de Braess, un phénomène mis en évidence de manière théorique en 1968 par le mathématicien allemand du même nom…[Pour en savoir plus voir l'article Interstices]

Robots are gradually making their way from industries and laboratories into our daily lives. Whetherthey serve as companions, teachers, receptionists, cleaners, or meet other needs, these robots aim toimprove our quality of life. However, robots' decisional autonomy remains the major challenge inrobotics. To increase the robot's autonomy, the researchers tend, on the one hand, to classify thecollaborations based on different criteria to gather the commonalities between the human-robotcollaborations. The goal is to detect the similar steps that the robot must be able to accomplish toperform the various tasks. On the other hand, other works focus on enhancing one or many of the fieldsrequired to set up a human-robot collaboration. The robot must perform four standard steps to set up ahuman-robot collaboration: perception, decision-making, motion execution, and evaluation. This thesis aims to optimize the human-robot collaboration performance by improving the robot'sdecision-making process. We evaluate the collaboration performance based on different changeableperformance metrics. Hence, an optimized collaboration aims to benefit humans, such as getting thetask done faster or reducing the effort of human agents. However, an unoptimized collaboration willbring nothing to humans or, on the contrary, will represent a nuisance, such as slowing them down oroverloading them, even if the task is finally accomplished. We start by developing a global framework that optimizes the robot's decision-making process. Weapply this framework to a non-intuitive assembly task, i.e., complex cognitive processing is required tofind the right place for each piece of the proposed assembly game. We want to enhance the task time tocompletion by a collaborative human-robot team without having to increase its physical capabilities(i.e., perception, trajectory planning, or low-level control). Our proposed framework can improvehuman-robot collaboration while considering different performance metrics. These metrics areconsidered regardless of the behavior of the human agent. We then apply this framework to a second application more complex (i.e., deforming a soft object)that requires increasing the robot's manipulation dexterity by improving its low-level control. Indeed,we will consider this second application that requires increasing the robot's manipulation dexterity tomaximize the optimization of the collaboration performance. A human-robot collaborative team willhave to co-manipulate the soft object to make it reach desired shapes. The collaborative team canachieve this application using a deep reinforcement learning approach. The idea is to train the agent (asingle-arm robot or a dual-arm robot) in simulation and to test it in real by replacing the second roboticarm with the human agent.; Les robots se fraient progressivement un chemin depuis les industries et les laboratoires jusqu’à notre vie quotidienne. Qu'ils servent de compagnons, d'enseignants, de réceptionnistes, de nettoyeurs ou répondent à d'autres de nos besoins, ces robots ont pour objectif d'améliorer notre qualité de vie. Cependant, l'autonomie décisionnelle des robots reste un défi majeur dans le domaine de la robotique. Pour augmenter l'autonomie du robot, les chercheurs ont tendance à classer les collaborations en fonction de différents critères afin de rassembler les points communs entre les collaborations homme-robot. L'objectif est de détecter les étapes similaires que le robot doit être capable d'accomplir pour réaliser les différentes tâches. D'autre part, d'autres travaux visent à améliorer un ou plusieurs des domaines nécessaires pour qu'une collaboration homme-robot soit mise en place. Le robot doit effectuer quatre étapes standards pour mettre en place une collaboration homme-robot : la perception,la prise de décisions, l'exécution de mouvements et l'évaluation. Cette thèse se concentre sur l'optimisation des performances de la collaboration homme-robot en améliorant le processus décisionnel du robot. Nous évaluons la performance de la collaboration à l'aide de différentes métriques modifiables de performance. Ainsi, une collaboration optimisée a pour but d'apporter des bénéfices aux humains, tels que l'accomplissement plus rapide de la tâche ou la réduction de l'effort des agents humains. En revanche, une collaboration non optimisée n'apportera rien aux humains ou, au contraire, représentera une nuisance, comme le fait de les ralentir ou de les surcharger et ce même si la tâche est finalement accomplie. Nous commençons par développer un framework global qui optimise le processus décisionnel du robot. Nous appliquons ce framework à une tâche d'assemblage non intuitive, c'est-à-dire qu'un raisonnement cognitif complexe est nécessaire pour trouver le bon endroit où placer chaque pièce du jeu d'assemblage proposé. Nous voulons améliorer la réalisation de la tâche par une équipe homme-robot collaborative sans avoir à augmenter les capacités physiques de ce dernier (à savoir la perception,la planification de trajectoires ou le contrôle bas-niveau). Le framework que nous proposons peut améliorer la collaboration homme-robot en prenant en compte différentes métriques de performance. Ces métriques sont prises en compte indépendamment du comportement de l'humain. Nous appliquons ensuite ce framework à une deuxième application plus complexe (à savoir la déformation d'un objet mou) qui nécessite d'augmenter la dextérité de manipulation du robot en améliorant son contrôle bas-niveau. En effet, nous prenons en considération cette deuxième application,qui nécessite d'augmenter la dextérité de manipulation du robot, afin de maximiser l'optimisation de la performance de la collaboration. Une équipe collaborative homme-robot devra co-manipuler un objet déformable afin de lui faire atteindre des formes désirées. L'équipe collaborative peut réaliser cette application à l'aide d'une approche d'apprentissage par renforcement profond. L'idée est d'entraîner l'agent (un robot à un ou deux bras) en simulation et de le tester en situation réelle et ce en remplaçant le second bras robotique par l'agent humain.

This HDR manuscript presents recent Information-Theoretic tools that bring new insights into Game Theoretical problems, such as the coordination of players’ actions and the processing of strategic information. Although Information Theory and Game Theory have distinct fields of application, these two theories rely on similar mathematical tools. Such problems arise for the design of autonomous devices and for the study of the behavior of rational agents. New generations of communication networks involve devices that take decisions with greater autonomy. These machines observe their environment, interact, cooperate with other machines or with humans, adapt dynamically to their environment and to the topology of the network. The lossy source coding theorem of Shannon (1959) is the cornerstone of our study. Given a communication capacity constraint, this theorem characterizes the optimal coding scheme to compress an information source. The coding performances are evaluated via a fidelity criterion which we interpret as a cost function to be minimized. We revisit this coding problem by adopting a Game-Theoretical point of view, in which each player optimizes his own cost function which depends on the actions of other players. First, we investigate the capacity of an encoder and a decoder to coordinate their actions with the symbols of an information source. For this purpose, the action sequence of the encoder encapsulates a degraded version of the source symbols, which serves to coordinate the future actions of the decoder. We characterize the solutions of several instances of the coordination problem in Chap. IV, and in Chap. V, we extend these results in several directions, i.e. for channel state leakage problems, for decentralized control problems and for strong coordination problems. The strategic nature of the information transmission is studied in Chap. VI when the communication is passed through a noisy channel. We consider that the encoder commits to implementing a signalling strategy before it observes the source symbols, as in the Bayesian persuasion game. As perspectives, we will study the impact of communication constraints on the transmission of strategic information in mechanism design problems, as in Jackson and Sonnenschein (2007), and in cheap talk games, see Crawford and Sobel (1982). Another direction of research consists in deepening optimization problems that arise in strategic coding, by using tools from Graph Theory and Convex Optimization. We believe that these results will also bring a new point of view on open problems in repeated games with imperfect observation and incomplete information. The goal is to build a theory that encompasses the standard coding results in Information Theory, and the results for the sender-receiver games., Ce manuscrit d’HDR présente des résultats récents de Théorie de l’Information qui apportent un éclairage nouveau sur des problèmes de Théorie des Jeux, tels que la coordination des actions des joueurs ou le traitement de l’information stratégique. Bien que la Théorie de l’Information et la Théorie des Jeux aient des champs d’application distincts, ces deux théories s’appuient sur des outils mathématiques similaires. Les problèmes de coordination et d’information stratégique se posent pour la conception de réseaux d’appareils autonomes et pour l’étude du comportement d’agents rationnels. Les nouvelles générations de réseaux de communication intègrent des appareils qui prennent des décisions avec une plus grande autonomie. Ces machines observent leur environnement, interagissent, coopèrent avec d’autres machines ou avec des humains, s’adaptent dynamiquement à leur environnement et à la topologie du réseau. Le théorème de codage de source avec perte de Shannon (1959) est la pierre angulaire de notre étude. Étant donnée une contrainte de capacité de communication, ce théorème caractérise le schéma de codage optimal pour compresser une source d’information. Les performances du codage sont évaluées via un critère de fidélité que nous interprétons comme une fonction de coût à minimiser. Nous revisitons ce problème de codage en adoptant le point de vue de la Théorie des Jeux, dans lequel chaque joueur optimise sa propre fonction de coût qui dépend des actions des autres joueurs. Tout d’abord, nous étudions la capacité d’un encodeur et d’un décodeur à coordonner leurs actions avec les symboles générés par une source d’information. A cet effet, la suite d’actions de l’encodeur encapsule une version dégradée des symboles de source, qui sert à coordonner les futures actions du décodeur. Nous caractérisons les solutions de plusieurs instances du problème de coordination au Chap. IV, et au Chap. V, nous étendons ces résultats dans plusieurs directions, pour des problèmes de fuite d’état de canal, pour des problèmes de contrôle décentralisé et pour des problèmes de coordination forte. Le caractère stratégique de la transmission de l’information est étudié au Chap. VI lorsque les joueurs communiquent à travers un canal bruité. Nous considérons un encodeur s’engage à mettre en œuvre une stratégie, avant que les symboles de sources soient tirés, comme dans le jeu de persuasion Bayésienne. En guise de perspectives, nous étudierons l’impact des contraintes de communication sur la transmission d’informations stratégiques dans les problèmes de “mechanism design” de Jackson and Sonnenschein (2007), et dans les jeux de “cheap talk” de Crawford and Sobel (1982). Une autre direction de recherche consiste à approfondir les problèmes d’optimisation qui apparaissent pour le codage stratégique, en utilisant des outils issus de la Théorie des Graphes et de l’Optimisation Convexe. Nous pensons que ces résultats apporteront un point de vue nouveau sur les problèmes ouverts en jeux répétés avec observation imparfaite et information incomplète. L’objectif est de construire une théorie qui englobe les résultats de codage standard en théorie de l’information et les résultats pour les jeux “sender-receiver”.

Defining precisely one’s choices and methodological objectives is required when using game theory. Moreover, the proximity between certain game theoryconcepts and those of a future-oriented approach, has allowed a futurist reading of the results of this study; Defining precisely one's choices and methodological objectives is required when using game theory. Moreover, the proximity between certain game theory concepts and those of a future-oriented approach, has allowed a futurist reading of the results of this study. Résumé : L'utilisation de la théorie des jeux sur des problématiques territoriales nécessite de définir précisément les choix et les objectifs méthodologiques. En outre, la proximité entre certains concepts de la théorie des jeux et ceux de la prospective permet une lecture prospective des résultats obtenus.

Les entreprises reposent sur le recrutement pour garantir leur développement et améliorer leur compétitivité dans le marché. Le recrutement est un processus complexe qui met en relation l’offreur et le demandeur d’emploi, sa difficulté réside au niveau de l’interaction entre ces deux agents dont chacun opte pour des comportements spécifiques sous un contexte caractérisé par l’asymétrie d’information. Le recours à la théorie des jeux comme outil d’analyse des stratégies des agents concorde parfaitement à notre objectif dans cet article à saisir les comportements de l’offreur – demandeur lors de la phase d’évaluation, notamment les conditions avancées par le demandeur d’emploi et les propositions de l’offreur d’emploi. Nous avons élaboré un modèle simplifié qui présente les facteurs qui influencent ces conditions et ces propositions lors d’un entretien. Nous avons constaté trois modes stratégiques sont appliquées : (1) stratégie du marché rationnel, dont chaque agent opte pour des stratégies rationnelles au sens économique, (2) stratégie du marché déséquilibré, dont nous avons mobilisé les théories de réciprocité en économie comportementale pour comprendre des comportements de chaque agent (3) stratégie du marché efficient, dont chaque agent opte souvent pour le choix optimal au sens de Pareto.

Software systems are ubiquitous, and their reliability is often crucial, especially for theones operating in embedded hardware, where the energetic sobriety moreover matters.To bring reliable guarantees, formal methods have been used for many years, with greatsuccess, among them automata based techniques and the renowned model checkingapproach. Instead of manually building a model, and verify it afterwards, anotherparadigm consists in automatically synthesising such correct by construction software,using game theory. Two players, the controller and an environment, are fighting oneagainst the other in a zero-sum game played on a graph of all possible configurations ofthe system. Energy, or other quantitative metrics of interest, are then modelled by theaddition of weights in the games. While some results have been obtained in the presenceof non-negative weights only, my objective has been to incorporate negative weights inthe picture, to model richer quantitative behaviours. This manuscript aims at studyinga combination of reachability objective with the total-payoff metrics, i.e. shortest-pathgames where one player wants to reach a target of the graph while minimising thecumulated weight. Our study starts with the case of finite graph games, with the searchfor efficient algorithms to compute optimal values and strategies. We then continue byadding clocks and time constraints in the games, in order to design efficient programssatisfying some real-time specifications. This leads to a notoriously difficult class ofgames where undecidability emerges very quickly. Our work consists into the search forfragments with decidable results, either by limiting the number of clocks, or the cyclicbehaviours in the game. A last chapter also studies the use of stochasticity in strategiesin order to limit the amount of memory needed for players to play optimally., Les systèmes logiciels sont omniprésents et leur fiabilité est souvent cruciale, en parti-culier pour ceux qui fonctionnent dans du matériel embarqué, où la sobriété énergétiqueest aussi un paramètre crucial. Pour apporter des garanties sûres, les méthodes formellessont utilisées depuis de nombreuses années, avec beaucoup de succès, avec entre autresdes techniques basées sur les automates et le célèbre model checking. Au lieu de créermanuellement un logiciel, son modèle et de vérifier celui-ci dans un deuxième temps, unautre paradigme consiste à synthétiser automatiquement un logiciel correct par construc-tion, en utilisant la théorie des jeux. Deux joueurs, le contrôleur et un environnement,s’affrontent dans un jeu à somme nulle joué sur un graphe de toutes les configurations dusystème. L’énergie, ou d’autres mesures quantitatives selon le problème envisagé, sontensuite modélisées par l’ajout de poids dans les jeux. Certains résultats préliminairesavaient été obtenus en présence de pondérations positives uniquement, mon objectif a étéd’autoriser l’usage de poids négatifs permettant de modéliser des données quantitativesplus riches. Ce manuscrit résume mes contributions dans l’étude d’une combinaison d’unobjectif d’accessibilité avec une métrique de gain total : on s’intéresse donc à des jeux deplus court chemin où un joueur veut atteindre une cible du graphe tout en minimisantle poids accumulé. Notre étude commence par le cas des jeux sur graphes finis, avec larecherche d’algorithmes efficaces pour calculer les valeurs et stratégies optimales. Nouscontinuons ensuite en ajoutant des horloges et des contraintes de temps dans les jeux,afin de concevoir des programmes efficaces satisfaisant certaines spécifications temps-réel.Cela conduit à une classe de jeux notoirement difficiles où l’indécidabilité émerge trèsrapidement. Notre travail consiste en la recherche de fragments possédant des résultatsdécidables, soit en limitant le nombre d’horloges, soit les comportements cycliques du jeu.Un dernier chapitre étudie également l’utilisation de randomisation dans les stratégiesafin de limiter la quantité de mémoire nécessaire pour que les joueurs jouent de manièreoptimale.

The objective of this PhD thesis is the study of policy learning within general-sum non-cooperative games (in particular the social dilemmas) in order to model cooperative interactions between telecom providers. First, it has been interesting to study the behavior of learning agents (such as reinforcement learning (RL) policies or multi-armed bandits) in an iterated prisoner’s dilemma (IPD). The first conclusions show that RL polices struggle to converge towards mutual cooperation. Given this observation, it becomes important to focus on simple strategies like Tit-for-tat (TFT) which will eventually be added to more complex policies (such Deep RL). The main contributions of the thesis were initially improvements proposal for simple two-player strategies such as continuous TFT. We then turned to N-player prisoner dilemma models. We have introduced an extension allowing to model a cooperation that is not necessarily bilateral and can be potentially circular, which then led to a proposal for a suitable strategy, based on continuous TFT and graph-processing algorithms. Secondly, we extended the previous paradigm to the formalism of sequential social dilemmas (SSD) (an existing extension of the IPD that extends the atomic actions of players into complex RL policies). To address this new game model, we then proposed a strategy that uses RL policies and TFT strategies. Finally, we carried out some simulations in a Telecom context. The first contribution was the implementation of a multi-provider environment for the cooperation simulation. A few simulations were then carried out: some of the previously developed strategies were used to study the agent’s behavior in various multi-provider scenarios of cooperation.; L’objectif de la thèse est l’étude de l’apprentissage de politiques au sein de jeux non-coopératifs à somme non-nulle (de type dilemmes sociaux) dans le but de modéliser des interactions de coopération entre opérateurs de Télécom. Pour commencer, il a été intéressant d’étudier le comportement d’agents apprenants (tels que des politiques d’apprentissage par renforcement (RL) ou des bandits manchots) dans un dilemme du prisonnier itéré (IPD). Les premières conclusions montrent que le RL peine à converger vers des politiques de coopération mutuelles. Étant donné ce constat, il devient important de nous intéresser à des stratégies simples comme le Tit-for-tat (TFT) qui viendront à terme s’ajouter à des politiques plus complexes de type RL. Les principales contributions de la thèse ont été dans un premier temps des propositions d’améliorations de stratégies simples à deux joueurs telles que le TFT continu. Nous nous sommes ensuite intéressés aux modèles de dilemmes du prisonnier à N joueurs. Nous avons introduit une extension qui permet de modéliser une coopération non nécessairement bilatérale et potentiellement circulaire, ce qui a conduit alors à une proposition de stratégie adaptée, basée sur du TFT continu et des algorithmes de traitement de graphe. Dans un second temps, nous avons étendu le paradigme précédent au formalisme des dilemmes sociaux séquentiels (une extension existante de l'IPD qui permet d’étendre les actions atomiques des joueurs en des politiques plus complexes). Pour adresser ce nouveau modèle de jeu, nous avons alors proposé une stratégie qui utilise des politiques de RL et des stratégies de TFT. Enfin, nous avons procédé à quelques simulations dans un contexte Télécom. La première contribution a été l’implémentation d’un environnement de simulation de collaboration multi-opérateurs. Quelques simulations ont été ensuite conduites : les stratégies précédemment développées ont été mises en jeu dans divers scénarios de coopération multi-opérateurs.

Autonomous control and navigation of mobile robots received a lot of attention due to the ability of robots to carry out sophisticated tasks in a complex environment with a high level of precision and efficiency. The majority of control problems related to mobile robots involved go-to-goal, object tracking, and path following consist a target with pre-defined behavior. As such, the control design does not take into account the future behavior of the target. In surveillance, interception, pursuit-evasion problems, the future behavior of the target must be taken into consideration. These problems where the agent plays against an adversary are best tackled using game theory which provides the best strategy for winning. However, game-theoretic algorithms required a lot of information on the opponent to take into account the optimal strategy of the opponent, which is the worst-case scenario from the perspective of the player. This information requirement often restricts the application of game theory on mobile robots. Also, the majority of the works found in the literature proposed offline solutions applied to holonomic systems. This PhD thesis proposed three different solutions to non-cooperative game problems based on the opponent's information available to each player. The proposed solutions are online in nature with the ability to incorporate obstacles avoidance. Also, the controllers designed are applied on nonholonomic mobile robots first in a simulation then validated experimentally in a similar environment. In the first part of the work, the point-stabilization problem in a complex environment was handled using Nonlinear Model Predictive Control(NMPC) with Static and dynamic obstacles avoidance which revolves around the target position. Secondly, the problem was modified to involve a moving target that has a conflicting objective to form a pursuit-evasion game. The problem was solved using Nonlinear Model Predictive Control where two stabilizing approaches are compared. The NMPC method works such that only the current states of the opponent are known to each player. Next, a game-theoretic algorithm that requires all the information of the opponent was proposed. Next, another method called Limited information Model Predictive Control was proposed to solve the same problem where only the current position of the opponent is known. The methods are compared in terms of capture time, computation time, ability to incorporate obstacle avoidance, and robustness to noise and disturbance. A new problem that lies at the intersection between the point stabilization and pursuit-evasion problem was formulated and solved using game-theoretic model predictive control. The problem is called the Differential Game of Target Defense(DGTD) which involves interception of a moving object before reaching a static target. Finally, all the proposed controllers are validated experimentally using two mobile robots and the Motion Capture platform of the laboratory., Le contrôle et la navigation autonomes des robots mobiles ont reçu beaucoup d'attention en raison de la capacité des robots à effectuer des tâches sophistiquées dans un environnement complexe avec un haut niveau de précision et d'efficacité. La majorité des problèmes de contrôle liés aux robots mobiles concernaient l'atteinte d'un but, le suivi d'un objet et le suivi d'une trajectoire consistant en une cible au comportement prédéfini. Ainsi, la conception du contrôle ne prend pas en compte le comportement futur de la cible. Dans les problèmes de surveillance, d'interception, de poursuite-évasion, le comportement futur de la cible doit être pris en considération. Ces problèmes où l'agent joue contre un adversaire sont mieux abordés en utilisant la théorie des jeux qui fournit la meilleure stratégie pour gagner. Cependant, les algorithmes de la théorie des jeux nécessitent beaucoup d'informations sur l'adversaire pour prendre en compte la stratégie optimale de l'adversaire, qui est le pire scénario du point de vue du joueur. Cette exigence d'information limite souvent l'application de la théorie des jeux aux robots mobiles. De plus, la majorité des travaux trouvés dans la littérature proposaient des solutions hors ligne appliquées aux systèmes holonomiques. Cette thèse de doctorat a proposé trois solutions différentes aux problèmes de jeux non-coopératifs basées sur l'information de l'adversaire disponible pour chaque joueur. Les solutions proposées sont en ligne par nature et ont la capacité d'intégrer l'évitement des obstacles. De plus, les contrôleurs conçus sont appliqués sur des robots mobiles nonholonomes d'abord dans une simulation puis validés expérimentalement dans un environnement similaire. Dans la première partie du travail, le problème de la stabilisation du point dans un environnement complexe a été traité à l'aide d'une commande prédictive de modèle non linéaire (NMPC) avec évitement statique et dynamique des obstacles qui tourne autour de la position cible. Ensuite, le problème a été modifié pour impliquer une cible mobile qui a un objectif conflictuel pour former un jeu de poursuite-évasion. Le problème a été résolu à l'aide d'une commande prédictive par modèle non linéaire où deux approches de stabilisation sont comparées. La méthode NMPC fonctionne de telle sorte que seuls les états actuels de l'adversaire sont connus de chaque joueur. Ensuite, un algorithme de théorie des jeux qui nécessite toutes les informations de l'adversaire a été proposé. Ensuite, une autre méthode appelée contrôle prédictif par modèle à information limitée a été proposée pour résoudre le même problème où seule la position actuelle de l'adversaire est connue. Les méthodes sont comparées en termes de temps de capture, de temps de calcul, de capacité à intégrer l'évitement des obstacles et de robustesse au bruit et aux perturbations. Un nouveau problème qui se situe à l'intersection entre la stabilisation ponctuelle et le problème de poursuite-évasion a été formulé et résolu à l'aide de la commande prédictive par modèle de la théorie des jeux. Le problème est appelé le jeu différentiel de défense de cible (DGTD) qui implique l'interception d'un objet mobile avant d'atteindre une cible statique. Enfin, tous les contrôleurs proposés sont validés expérimentalement à l'aide de deux robots mobiles et de la plateforme de capture de mouvement du laboratoire.

This thesis addresses the question of computing game-theoretic equilibria in N-player games, and focuses particularly on the question of computing equilibria in N-player games when N is tremendously large. The thesis' body starts with methods to converge to three different types of equilibria in N-player games: correlated equilibria, coarse-correlated equilibria, and alpha-Rank. All three equilibria are converged-to using an alteration of Policy Space Response Oracle (PSRO), a popular population-based algorithm which computes a number of different policies and finds the optimal way to mix them in order to converge. More specifically, this alteration uses the target equilibrium and an innovative new-policy-computing algorithm to reach said equilibrium. We prove the convergence of our method to these equilibria of interest, and enlarge it to a broader class of equilibria which we define.This answers the initial thesis question regarding converging towards any equilibrium in any finite N-player game. However, these PSRO-derived approaches are heavily dependent on the number of players in their game: the more players there are, the more difficult it becomes for them to find an equilibrium, and this difficulty quickly becomes prohibitive. The second part of the thesis is therefore concerned with overcoming this difficulty when the number of agents is extremely large, by considering that their number is infinite. Paradoxically, this approximation simplifies equilibrium computation by eliminating combinatorial effects. We first analyze what becomes of correlated and coarse-correlated equilibria in Mean-Field games, derive their new expressions, properties, and their behavior when they are reused in N-player games. Under suitable conditions, reusing a Mean-Field (coarse-) correlated equilibrium in an N-player game yields an mathcal{O}left( frac{1}{sqrt{N}} right -approximate (coarse-) correlated equilibrium. We then address the question of computing Mean-Field (coarse-) correlated equilibria. We show that two popular algorithms converge towards Mean-Field coarse-correlated equilibria, but in a spatially-complex way, via the notion of Mean-Field regret minimization. We introduce another variant of PSRO, Mean-Field PSRO, capable of converging towards correlated, coarse-correlated and Nash equilibria in all Mean-Field games of our framework. This is done by the use of black-box optimizers for Nash equilibria, and of no-adversarial-regret algorithms for (coarse-) correlated equilibria. These equilibria are also simplified by the introduction of a new compression method, bandit compression.Finally, the thesis ends with an application of Game-Theoretical equilibria in a real-world situation: soccer penalty kicks. The game-theoretic analysis serves the purpose of analyzing how optimal the behavior of players is, characterizing each player's behavioral tendencies, and providing strategic suggestions to improve penalty kick outcomes, Cette thèse traite la question du calcul et de l'estimation d'équilibres de théorie des jeux dans des jeux à N-joueurs. Elle se concentre en particulier sur les jeux N-joueurs où N est extrêmement large. Le corps de cette thèse commence par décrire des méthodes permettant de converger vers trois types d'équilibres : corrélés, faiblement-corrélés (coarse-correlated), et alpha-Rank. Ces trois équilibres sont atteints via une altération de PSRO, un algorithme basé sur une population, c'est à dire qui calcule différentes stratégies et une manière optimale de les combiner. Plus spécifiquement, cette altération utilise l'équilibre recherché et un nouveau type d'algorithme calculant une nouvelle stratégie pour atteindre l'équilibre mentionné. Nous prouvons que notre méthode converge vers les équilibres que nous examinons, et élargissons ce résultat à une plus large classe d'équilibres que nous définissons.Ces développements apportent une réponse à la question initiale de la thèse portant sur la convergence vers tout équilibre de théorie des jeux dans tout jeu fini à N-joueurs. Cependant, les méthodes dérivées de PSRO mentionnées plus haut peinent à converger rapidement lorsque N est élevé. Pour des valeurs de N très élevées, il devient presque impossible de trouver des équilibres en un temps raisonnable. La seconde partie de cette thèse porte donc sur la question de contourner la complexité provenant du nombre d'agents, en considérant que leur nombre est en fait infini. Paradoxalement, cette approximation simplifie le calcul d'équilibres parce qu'elle élimine tout effet combinatoire provenant des N joueurs. Nous analysons d'abord ce que deviennent les équilibres (faiblement-) corrélés sous l'approximation des jeux à Champ Moyen (Jeux avec une infinité de joueurs), décrivons leur nouvelle expression, leurs propriétés, et leur comportement lorsqu'ils sont réutilisés dans un jeu à N-joueurs. Etant données des conditions raisonnables, réutiliser un équilibre à Champ Moyen dans un jeu à N-joueurs produit un équilibre (faiblement-) corrélé mathcal{O}left( frac{1}{sqrt{N}} right) -approximatif.La thèse aborde ensuite le sujet de calculer des équilibres (faiblement-) corrélés à Champ Moyen. Elle montre que deux algorithmes populaires convergent vers des équilibres faiblement-corrélés à Champ Moyen, d'une façon inefficace spatialement, via la notion de minimisation de regret à Champ Moyen. Nous définissons ensuite une nouvelle variante de PSRO, PSRO à Champ Moyen, capable de converger vers des équilibres corrélés, faiblement corrélés et de Nash dans tout jeu à Champ Moyen conforme à notre formulation. Ce résultat est obtenu via l'utilisation d'optimiseurs boite-noire pour le Nash; et d'algorithmes sans-regret-adversarial pour les équilibres corrélés et faiblement corrélés. Ces équilibres sont aussi simplifiés via l'utilisation d'un nouvel algorithme de compression, "compression de bandits". Enfin, la thèse est conclue par une application d'équilibres de théorie des jeux dans une situation réelle : les tirs au but, lors de matchs de balle-aux-pieds qui devrait être popularisé pour ce sport populaire, arrivé en Angleterre grâce à la France lors du Camp du Drap d'Or. L'analyse de théorie des jeux sert à analyser l'optimalité des stratégies adoptées par les joueurs, à caractériser les tendances comportementales de chaque joueur, et à leur faire des suggestions afin qu'ils puissent améliorer leurs comportements lors de tirs-aux-but

Ce livre repense l’indépendance des banques centrales en la mettant en perspective historique. Remédiant à la vision unidimensionnelle de la littérature, il reformule la question afin de saisir son caractère dual et de penser l’indépendance des banques centrales vis-à-vis des banques commerciales., This book puts central bank independence into historical perspective with the aim of rethinking it. Since the economic literature suffers from a one-dimensional view, it reformulates the question in order to capture its dual character and to think central bank independence from commercial banking.

Decision theory and game theory are both interdisciplinary domains that focus on modeling and studying decision-making processes. On the one hand, decision theory aims to account for the possible behaviors of an agent with respect to an uncertain situation. It thus provides several frameworks to describe the decision-making processes in this context, including that of belief functions. On the other hand, game theory focuses on multi-agent decisions, typically with probabilistic uncertainty (if any), hence the so-called class of Bayesian games. In this paper, we extend Bayesian games to the theory of belief functions. We obtain a more expressive class of games we refer to as Bel games; it make it possible to better capture human behaviors with respect to lack of information. Next, we prove an extended version of the so-called Howson-Rosenthal's theorem, showing that Bel games can be turned into games of complete information, i.e., without any uncertainty. Doing so, we embed this class of games into classical game theory and thereby enable the use of existing algorithms. Using the Coq proof assistant, we formalize a theory of belief functions, and formally verify three different proofs of Howson-Rosenthal's theorem.

Simulation modeling in economics has historically been viewed as an alternative to mainstream analytic technique, and as such has generally and intentionally avoided the focus on rational behavior and equilibrium reasoning that is characteristic of game-theoretic approaches. The emerging methodology of empirical game-theoretic analysis (EGTA) attempts to bridge agent-based simulation and game theory, combining the flexibility of simulation with the discipline of rationality criteria. The basic idea is to estimate a restricted game model from data generated by systematic simulation over a space of heuristic strategy profiles. EGTA enables a standard form of strategic analysis for complex economic scenarios previously addressed only in severely stylized form. Historiquement, la modélisation par simulation en économie s’est développée comme alternative aux techniques analytiques courantes. De ce fait, elle a généralement et sciemment évité de traiter de la rationalité et du raisonnement à l’équilibre, qui sont au cœur de la théorie des jeux. La nouvelle méthodologie d’analyse empirique de jeux (EGTA en anglais) tente de faire le pont entre la simulation à agents multiples et la théorie des jeux, combinant la flexibilité de la simulation avec la discipline des critères de rationalité. L’idée principale est d’estimer un modèle de jeu réduit à partir de données générées par des simulations systématiques sur un espace heuristique des profils de stratégie. L’EGTA fournit une norme stratégique pour analyser les scénarios économiques complexes qui étaient auparavant modélisés uniquement sous des formes fortement stylisées.

This thesis deals with formal methods based on timed automata, their actions upon reality, and the informations that can be learned from it. It proposes different contributions in three separate domains: game theory and formal test generation, seen as a way to control a system using formal methods; state estimation, that deduce the possible configurations of a system from observations by the mean of a formal construction; active model learning, that propose to construct a formal model of a system by requesting observations out of it, directing them as needed for the task.As diverse as they may seem, these contributions are linked by the underlying formalism, abstractions and preoccupations that characterizes interactions between formal models and reality. Furthermore, they benefit from one another in practice, forming a virtuous loop: the capacity to learn from reality allows for better models, that in turn permit a finer control of the real systems, which helps the learning processes.We link these different contributions together based on the grounds above, and advocate for a greater rapprochement between learning and formal methods and communities.; Cette thèse traite des méthodes formelles utilisant les automates temporisés, de leurs actions sur la réalité, et des informations que l’on peut apprendre grâce à ces observations. Elle propose différentes contributions dans trois domaines distincts : la théorie des jeux et la génération de tests, vue comme un moyen de contrôler un système à l’aide de méthodes formelles ; l’estimation d’état, qui déduit les configurations possibles d’un système à partir d’observations au moyen d’une construction formelle ; l’apprentissage actif de modèles, qui propose de construire un modèle d’un système en lui demandant des observations, en les orientant selon les besoins de la tâche.Aussi diverses qu’elles puissent paraître, ces contributions sont liées par le formalisme sous-jacent, les abstractions utilisées et les préoccupations qui caractérisent les interactions entre les modèles formels et la réalité. De plus, elles bénéficient les unes des autres dans la pratique, formant un cercle vertueux : la capacité d’apprendre de la réalité permet de meilleurs modèles, qui à leur tour permettent un contrôle plus fin des systèmes, ce qui favorise les processus d’apprentissage.Nous relions ces différentes contributions entre elles sur la base des motifs ci-dessus, et nous plaidons pour un rapprochement entre les méthodes et les communautés d’apprentissage de modèles et de méthodes formelles.

Cette thèse est composée de trois chapitres qui traitent de la problématique de la régulation optimale des émissions de carbone pour atténuer le changement climatique. Dans le premier chapitre, nous analysons les interactions stratégiques entre un cartel, exportant une ressource non renouvelable génératrice de pollution, et deux pays importateurs hétérogènes qui souhaitent atténuer les dommages dus à la pollution. Les pays importateurs différent selon leur demande de la ressource et selon leur degré d’exposition au stock (mondial) de pollution. Les pays importateurs fixent de manière non coopérative des taxes carbone sur la consommation de la ressource polluante et le cartel exportateur fixe son prix à la production. En utilisant équilibre de Nash en boucle ouverte, nous obtenons des solutions explicites des trajectoires temporelles des taxes carbone, du prix au producteur et du stock de pollution. Nous montrons que lorsque les pays importateurs agissent de manière non coopérative, à un temps fini, le prix à la production bondit et le pays importateur le plus touché par la pollution cesse de demander la ressource. Nos résultats numériques basés sur la caractérisation explicite de l’équilibre non coopératif montrent qu’une plus grande symétrie par rapport aux coûts de la pollution conduit à une augmentation plus rapide du stock de pollution en début d’horizon temporel, mais à un stock de pollution de long terme plus faible et un bien-être total plus élevé. Dans le deuxième chapitre, Nous analysons les effets des ajustements carbone bilatéraux aux frontières sur les taxes carbone dans un jeu non coopératif entre deux pays symétriques ouverts ayant des firmes en concurrence imparfaite en présence de pollution transfrontalière. Nous comparons également dans ce chapitre les résultats de ce jeu avec ceux de deux benchmarks (soient, le jeu non coopératif sans ajustements carbone aux frontières et la solution efficace). Nous constatons que lorsque les pays souffrent peu de la pollution, seuls des équilibres symétriques existent. En revanche, si les pays souffrent suffisamment de la pollution, seuls des équilibres asymétriques existent. Les taxes sur le carbone en équilibres symétriques sont plus élevées que les taxes efficaces, tandis que l’inverse est vrai pour les équilibres asymétriques. Dans tous les cas d’intérêt, le bien-être total à l’équilibre du jeu non coopératif avec ajustements carbone aux frontières est supérieur à celui du jeu non coopératif sans ajustements carbone aux frontières. Lorsque les coûts de la pollution sont suffisamment bas, il existe un niveau d’ajustement carbone aux frontières tel que les taxes d’équilibre non coopératif sont efficaces. Enfin, dans le cas où les pays souffrent suffisamment de la pollution, le niveau optimal d’ajustement carbone aux frontières peut être partiel ou total selon les paramètres du modèle. Nous étudions enfin, dans le dernier chapitre, un jeu de pollution frontalière non coopératif entre respectivement deux pays et trois pays fixant des taxes carbone en présence d’ajustements carbone aux frontières et avec présence d’une concurrence imparfaite sur le marché international des biens polluants. Les pays sont asymétriques quant à leur volonté de payer pour la réduction des émissions mondiales de carbone. Dans nos modèles, seul le pays le plus touché impose un ajustement carbone aux frontières. Nous montrons que, contrairement à la littérature existante utilisant des modèles à deux pays avec un seul marché, le pays le plus touché préfère très généralement utiliser un ajustement carbone total aux frontières (c’est-à -dire un tarif qui ajuste exactement les écarts entre sa propre taxe carbone et celles des autres pays) à un ajustement carbone partiel aux frontières. De plus, un ajustement carbone total aux frontières est optimal pour le bien-être global dans la plupart des cas d’intérêt., This thesis is composed of three chapters which concern the problem of the optimal regulation of carbon emissions to mitigate climate change. In the first chapter, we analyze strategic interactions between a resource cartel exporting a non-renewable stock pollutant and two heterogeneous importing countries, who want to mitigate pollution damages. The importing countries differ with respect to market size and with respect to how strongly they are affected by the (global) stock of pollution. The importing countries non cooperatively set emissions taxes and the exporting cartel sets its producer price. Using open loop Nash equilibrium, we obtain explicit solutions for the time paths of the carbon taxes, the producer price and the stock of pollution. We show that when the countries act non cooperatively, at a finite time, the producer price jumps and the country that is most affected by pollution stops demanding the resource. Our numerical results based on the explicit characterization of the non-cooperative equilibrium yield that more symmetry with respect to the cost of pollution leads to faster increase of the stock of pollution initially, but to a lower long-term stock and higher total discounted welfare. In the second chapter, we analyzes the effects of bilateral border tax adjustments on carbon taxes in a non-cooperative game between two symmetric open countries trading in an oligopolistic framework with cross-border pollution. We also contrast the results of this BTA game with those of two benchmarks (the non-cooperative game without BTA and the efficient solution). We note that when countries suffer little from pollution, only symmetric equilibria exist. By contrast, if countries suffer sufficiently from pollution, only asymmetric equilibria exist. Carbon taxes in symmetric equilibria are higher than the efficient taxes, while the opposite is true for the asymmetric equilibria. In all cases of interest, the total welfare in the equilibrium of the non cooperative game with BTA is higher than that in the equilibrium of the non cooperative game without BTA. If the cost of pollution is sufficiently low, there is a level of BTA such that non cooperative equilibrium taxes are efficient. Finally, in the case where the countries suffer a lot from pollution, the optimal level of BTA can be partial or full depending on the parameters of the model. Finally, in the last chapter, we study a non-cooperative transboundary pollution game between respectively two countries and three countries setting carbon taxes in the presence of a Border Tax Adjustment (BTA) and with imperfect competition in the international polluting goods market. Countries are asymmetric with respect to their willingness to pay for reductions of global emissions. In our models, only the most affected country imposes a BTA. We show that, unlike in the existing literature using two-country models with only one market, the most affected country generally prefers using a full BTA, a tariff that fully adjusts for the differences between its own carbon tax and those in other countries, to a partial BTA. Moreover, a full BTA is optimal for the global welfare in most cases of interest.

In sequential learning (or repeated games), data is acquired and treated on the fly and an algorithm (or strategy) learns to behave as well as if it got in hindsight the state of nature, e.g., distributions of rewards. In many real life scenarios, learning agents are not alone and interact, or interfere, with many others. As a consequence, their decisions have an impact on the other and, by extension, on the generating process of rewards. We aim at studying how sequential learning algorithms behave in strategic environments, when facing and interfering with each others. This thesis thus considers different problems, where some interactions between learning agents arise and provides computationally efficient algorithms with good performance (small regret) guarantees.When agents are cooperative, the difficulty of the problem comes from its decentralized aspect, as the different agents take decisions solely based on their observations. In this case, we propose algorithms that not only coordinate the agents to avoid negative interference with each other, but also leverage the interferences to transfer information between the agents, thus reaching performances similar to centralized algorithms. With competing agents, we propose algorithms with both satisfying performance and strategic (e.g., epsilon-Nash equilibria) guarantees.This thesis mainly focuses on the problem of multiplayer bandits, which combines different interactions between learning agents in a formalized online learning framework. Both for the cooperative and competing case, algorithms with performances comparable to the centralized case are proposed.Other sequential learning instances are also considered in this thesis. We also propose a strategy reaching centralized performances for decentralized queuing systems. For online auctions, we suggest to balance short and long term rewards with a utility/privacy trade-off. It is formalized as an optimization problem, that is equivalent to Sinkhorn divergence and benefits from the recent advances on Optimal Transport. We also study social learning with reviews, when the quality of the product varies over time., En apprentissage séquentiel (ou jeux répétés), les données sont acquises et traitées à la volée et un algorithme (ou stratégie) apprend à se comporter aussi bien que s'il avait pu observer l'état de nature, par exemple les distributions des gains. Dans de nombreuses situations réelles, de tels agents intelligents ne sont pas seuls et interagissent ou interfèrent avec d'autres. Ainsi, leurs décisions ont un impact direct sur les autres agents et indirectement sur leurs propres gains à venir. Nous étudions de quelle manière les algorithmes d'apprentissage séquentiel peuvent se comporter dans des environnements stratégiques quand ils sont confrontés à d'autres agents. Cette thèse considère différents problèmes où certaines interactions entre des agents intelligents apparaissent, pour lesquels nous proposes des algorithmes efficaces en termes de calcul avec de bonnes garanties de performance (faible regret).Lorsque les agents sont coopératifs, la difficulté du problème vient de son aspect décentralisé, étant donné que les agents prennent leurs décisions en se basant seulement sur leurs propres observations. Dans ce cas, les algorithmes proposés non seulement coordonnent les agents afin d'éviter des interférences entre eux, mais ils utilisent également ces interférences pour transférer de l'information entre les agents. Cela permet d'obtenir des performances comparables aux meilleurs algorithmes centralisés. Avec des agents en concurrence, nous proposons des algorithmes avec des garanties satisfaisantes, à la fois en terme de performance et de stratégie (epsilon-équilibre de Nash par exemple).Cette thèse s'intéresse principalement au problème de bandits à plusieurs joueurs, combinant différentes interactions entre agents intelligents dans le cadre de l'apprentissage séquentiel. Des algorithmes comparables au cas centralisés sont proposés, lorsque les agents sont coopératifs, mais aussi lorsqu'ils sont compétitifs.D'autres exemples d'apprentissage séquentiel sont considérés dans cette thèse. Une stratégie comparable au cas centralisé est également proposé pour les systèmes de file d'attente. Pour les enchères en ligne, nous proposons de balancer les gains court et long terme à travers un dilemne utilité/confidentialité. Ce dilemne est formalisé par un problème d'optimisation, equivalent à la minimisation de la divergence Sinkhorn et qui bénéficie des récents progrès en transport optimal.Nous étudions aussi l'apprentissage social avec revues, lorsque la qualité du produit est variable dans le temps.

In sequential learning (or repeated games), data is acquired and treated on the fly and an algorithm (or strategy) learns to behave as well as if it got in hindsight the state of nature, e.g., distributions of rewards. In many real life scenarios, learning agents are not alone and interact, or interfere, with many others. As a consequence, their decisions have an impact on the other and, by extension, on the generating process of rewards. We aim at studying how sequential learning algorithms behave in strategic environments, when facing and interfering with each others. This thesis thus considers different problems, where some interactions between learning agents arise and provides computationally efficient algorithms with good performance (small regret) guarantees.When agents are cooperative, the difficulty of the problem comes from its decentralized aspect, as the different agents take decisions solely based on their observations. In this case, we propose algorithms that not only coordinate the agents to avoid negative interference with each other, but also leverage the interferences to transfer information between the agents, thus reaching performances similar to centralized algorithms. With competing agents, we propose algorithms with both satisfying performance and strategic (e.g., epsilon-Nash equilibria) guarantees.This thesis mainly focuses on the problem of multiplayer bandits, which combines different interactions between learning agents in a formalized online learning framework. Both for the cooperative and competing case, algorithms with performances comparable to the centralized case are proposed.Other sequential learning instances are also considered in this thesis. We also propose a strategy reaching centralized performances for decentralized queuing systems. For online auctions, we suggest to balance short and long term rewards with a utility/privacy trade-off. It is formalized as an optimization problem, that is equivalent to Sinkhorn divergence and benefits from the recent advances on Optimal Transport. We also study social learning with reviews, when the quality of the product varies over time.; En apprentissage séquentiel (ou jeux répétés), les données sont acquises et traitées à la volée et un algorithme (ou stratégie) apprend à se comporter aussi bien que s'il avait pu observer l'état de nature, par exemple les distributions des gains. Dans de nombreuses situations réelles, de tels agents intelligents ne sont pas seuls et interagissent ou interfèrent avec d'autres. Ainsi, leurs décisions ont un impact direct sur les autres agents et indirectement sur leurs propres gains à venir. Nous étudions de quelle manière les algorithmes d'apprentissage séquentiel peuvent se comporter dans des environnements stratégiques quand ils sont confrontés à d'autres agents. Cette thèse considère différents problèmes où certaines interactions entre des agents intelligents apparaissent, pour lesquels nous proposes des algorithmes efficaces en termes de calcul avec de bonnes garanties de performance (faible regret).Lorsque les agents sont coopératifs, la difficulté du problème vient de son aspect décentralisé, étant donné que les agents prennent leurs décisions en se basant seulement sur leurs propres observations. Dans ce cas, les algorithmes proposés non seulement coordonnent les agents afin d'éviter des interférences entre eux, mais ils utilisent également ces interférences pour transférer de l'information entre les agents. Cela permet d'obtenir des performances comparables aux meilleurs algorithmes centralisés. Avec des agents en concurrence, nous proposons des algorithmes avec des garanties satisfaisantes, à la fois en terme de performance et de stratégie (epsilon-équilibre de Nash par exemple).Cette thèse s'intéresse principalement au problème de bandits à plusieurs joueurs, combinant différentes interactions entre agents intelligents dans le cadre de l'apprentissage séquentiel. Des algorithmes comparables au cas centralisés sont proposés, lorsque les agents sont coopératifs, mais aussi lorsqu'ils sont compétitifs.D'autres exemples d'apprentissage séquentiel sont considérés dans cette thèse. Une stratégie comparable au cas centralisé est également proposé pour les systèmes de file d'attente. Pour les enchères en ligne, nous proposons de balancer les gains court et long terme à travers un dilemne utilité/confidentialité. Ce dilemne est formalisé par un problème d'optimisation, equivalent à la minimisation de la divergence Sinkhorn et qui bénéficie des récents progrès en transport optimal.Nous étudions aussi l'apprentissage social avec revues, lorsque la qualité du produit est variable dans le temps.

This article proposes an algebraic approach to incompletegames allowing the modelling of problems where the agentshave different types of knowledge, complex utility functions(bi-criteria for example) and can use a whole family ofdecision rules. We show that, when the plausibility measureis decomposable, such games can be transformed in lineartime into hypergraphical games (without uncertainty), thusgeneralizing algebraically and to any number of playersHowson and Rosental’s Theorem., Cet article propose une approche algébrique des jeux incomplets, ce qui permet de capturer des problèmes où des agents ont différents types de connaissances, des fonctions d'utilité complexes (bi-critères par exemple) et peuvent utiliser toute une gamme de règles de décision. Nous montrons que, lorsque la mesure de plausibilité est décomposable, de tels jeux peuvent être transformés en temps linéaire en jeux hypergraphiques (sans incertitude), généralisant ainsi de manière algébrique et à un nombre quelconque de joueurs le théorème de Howson et Rosental [10].