Québec Université Laval, Bibliothèque 2013

J'ai étudié trois problèmes d'optimisation dans les graphes et les jeux combinatoires.Tout d'abord, les codes identifiants dans les graphes où les sommets font faces à des failles: les codes cherchent à repérer les failles pour les réparer. On s'est intéressé aux codes identifiants dans les graphes circulants en utilisant des plongements de ces graphes dans des grilles infinies.Ensuite, j'ai étudié le jeu de marquage de sommets et le jeu de coloration d'arêtes: ici deux joueurs se font face, le premier cherche à construire une coloration correcte (ou un marquage correct) et le deuxième cherche à l'en empêcher. Pour le jeu de marquage on s'est intéressé aux changements de stratégie gagnante lorsqu'on modifie le graphe. Pour le jeu de coloration d'arêtes on a donné une stratégie gagnante pour le premier joueur pourvu que le graphe considéré admette une certaine décomposition sur les arêtes. On améliore notamment des résultats sur les graphes planaires.Enfin j'ai étudié les jeux à tas purement de casse: deux joueurs à tour de rôle prennent un tas et le cassent en un certain nombre de tas non vides. On s'intéresse aux stratégies gagnantes lorsque les joueurs jouent sur un unique tas contenant n jetons. Ces jeux de pure casse semblent, à l'oeil nu, être réguliers. On a montré que c'est effectivement le cas pour certains et on a donné un test qui permet de déterminer la régularité cas par cas. Un seul cas ne semble pas correspondre à cette régularité: son comportement reste un mystère.En conclusion, je me suis intéressé à trois problèmes bilatéraux qui utilisent différentes méthodes et qui remplissent des propos différents dans le domaine de la combinatoire / I studied three optimization problems on graphs and combinatorial games.First, identifying codes were studied : vertices couteract faults. Identifying codes help locate the fault to repare it. We focused on circulant graphs by embedding them on infinite grids.Then, the marking and the coloring games were studied : two player games were one player wants to build something (a proper coloration or a proper marking) and the other wants to prevent the first player from doing so. For the marking game we studied the evolution of the strategy when modifying the graph. For the coloring game we defined a new edge-wise decomposition of graphs and we defined a new strategy on this decomposition that improves known results on planar graphs.In the end, I studied pure breaking games : two players take turns to break a heap of tokens in a given number of non-empty heaps. We focused on winning strategies for the game starting with a unique heap on n tokens. These games seem, on first sight, to be all regular : we showed this is the case for some of them and we gave a test to study one game at a time. Only one of these games does not seem to be regular, its behavior remains a mystery.To sum up, I studied three bilateral problems that use different methods and have different purposes in combinatorics

L’émergence des matériaux composites dans le domaine aéronautique a permis d’alléger considérablement les structures. Cependant l’adaptation du processus d’assemblage aux contraintes imposées par la présence de ces matériaux n’est pas encore complète. De nombreuses opérations considérées comme non-productives sont nécessaires pour garantir le respect des nouvelles exigences. Dans le cadre du projet européen LOCOMACHS, l’utilisation d’un outil de simulation d’assemblage est envisagée afin de limiter le recours à ces opérations. Ces travaux s’inscrivent dans le cadre de la validation, par la mesure, des modèles utilisés pour la simulation d’assemblage flexible. Une méthode d’évaluation de la géométrie d’un composant souple est mise en œuvre afin de compenser par simulation numérique les effets de l’environnement sur le composant lors de sa mesure. Une analyse de sensibilité de la méthode aux variations des différents paramètres de mesure et de simulation est réalisée afin de définir un cadre pour la mise en œuvre. Une analyse modale des écarts à une géométrie de référence contribue à la correction de certains paramètres du modèle utilisé pour réaliser la compensation par simulation. Cette géométrie de référence est obtenue par une méthode de retournement appliquée dans un contexte flexible, afin d'annuler certains effets de l'environnement sur la géométrie mesurée du composant. Le jeu entre les composants assemblés est la caractéristique géométrique prépondérante dans un assemblage de structure aéronautique composite. La simulation d’assemblage, à partir des mesures réalisées sur les composants souples, permet d’évaluer le jeu entre les composants avant leur assemblage. Des méthodes de mesure de jeu dans un assemblage de composants souples sont proposées, et leur mise en œuvre expérimentale est réalisée. La confrontation des jeux mesurés et simulés permet de souligner d’une part les performances de l’outil de simulation, et d’autre part les difficultés liées à la modélisation des environnements de mesure et d’assemblage réels. / The emergence of composite materials in aeronautics leads to lighter structures. However, these new materials induce new constraints to the assembly process. The adaptation is not yet complete. Indeed many operations are necessary to respect the new requirements, but are considered as non-productive. In the context of the European project LOCOMACHS, an assembly simulation tool is developed to limit the use of these operations. This thesis relates to the validation, from the measure, of the models used for flexible assembly simulation. A method to evaluate the geometry of a flexible component is implemented. The method compensates, by simulation, the effects of the environment on the component during its measurement. A sensitivity analysis of the method against changes in various measurement parameters and simulation parameters is performed in order to define a framework for implementation. Parameters of the model used to perform the compensation by simulation are not representative of the actual behavior. A modal analysis of deviations to a chosen reference geometry contributes to the adjustment of these parameters. This reference geometry is obtained by a reversal method applied in a flexible context to cancel some of the effects of the environment on the measured geometry of the component. The gap between the assembled components is the geometric key characteristic in an assembly of aeronautical composite structure. The assembly simulation, from measuring data of flexible components, enables to evaluate the gap between the components prior to assembly. Gap measurement methods in an assembly of flexible components are proposed, and they have been experimentally performed. The comparison of measured and simulated gaps highlights the performance of the simulation tool, and the difficulties in modeling actual measurement environment and actual assembly environment.

Les problèmes de gestion optimale de l'information sont omniprésents sur les marchés financiers (délit d'initié, problèmes de défaut, etc). Leurs études nécessitent une conception stratégique des interactions entre agents : les ordres placés par un agent informé influencent les cours futurs des actifs par l'information qu'ils véhiculent. Cette possibilité d'influencer les cours n'est pas envisagée par la théorie classique de la finance. Le cadre naturel de l'étude des interactions stratégiques est la théorie des jeux. Cette thèse a précisément pour objet de développer une théorie financière basée sur la théorie des jeux. Nous prendrons comme base l'article de De Meyer et Moussa Saley , "On the origin of Brownian Motion in finance". Cet article modélise les interactions entre deux teneurs de marché asymétriquement informés sur le futur d'un actif risqué par un jeu répété à somme nulle à information incomplète. Cette étude montre en particulier que le mouvement Brownien, souvent utilisé en finance pour décrire la dynamique des prix, a une origine partiellement stratégique : il est introduit par les acteurs informés afin de tirer un bénéfice maximal de leur information privée. Cette thèse traite de diverses extensions de ce modèle concernant l'influence de la grille des prix, l'asymétrie bilatérale d'information, le processus de diffusion de l'information.

Dans le contexte de transition vers un système électrique décentralisé et intelligent, nous abordons le problème de la gestion des flexibilités de consommation électriques. Nous développons différentes méthodes basées sur l'optimisation distribuée et la théorie des jeux.Nous commençons par adopter le point de vue d'un opérateur central en charge de la gestion des flexibilités de plusieurs agents. Nous présentons un algorithme distribué permettant le calcul des profils de consommations des agents optimaux pour l'opérateur.Cet algorithme garantit la confidentialité des agents~: les contraintes individuelles, ainsi que le profil individuel de consommation de chaque agent, ne sont jamais révélés à l'opérateur ni aux autres agents.Ensuite, nous adoptons dans un second modèle une vision plus décentralisée et considérons un cadre de théorie des jeux pour la gestion des flexibilités de consommation.Cette approche nous permet en particulier de modéliser les comportements stratégiques des consommateurs.Dans ce cadre, une classe de jeux adéquate est donnée par les jeux de congestion atomiques fractionnables.Nous obtenons plusieurs résultats théoriques concernant les équilibres de Nash dans cette classe de jeux, et nous quantifions l'efficacité de ces équilibres en établissant des bornes supérieures sur le prix de l'anarchie.Nous traitons la question du calcul décentralisé des équilibres de Nash dans ce contexte en étudiant les conditions et les vitesses de convergence des algorithmes de meilleure réponse et de gradient projeté.En pratique un opérateur peut faire face à un très grand nombre de joueurs, et calculer les équilibres d'un jeu de congestion dans ce cas est difficile.Afin de traiter ce problème, nous établissons des résultats sur l'approximation d'un équilibre dans les jeux de congestion et jeux agrégatifs avec un très grand nombre de joueurs et en présence de contraintes couplantes.Ces résultats, obtenus dans le cadre des inégalités variationnelles et sous certaines hypothèses de monotonie, peuvent être utilisés pour calculer un équilibre approché comme solution d'un problème de petite dimension.Toujours dans la perspective de modéliser un très grand nombre d'agents, nous considérons des jeux de congestion nonatomiques avec contraintes couplantes et avec une infinité de joueurs hétérogènes~: ce type de jeux apparaît lorsque les caractéristiques d'une population sont décrites par une fonction de distribution paramétrique.Sous certaines hypothèses de monotonie, nous prouvons que les équilibres de Wardrop de ces jeux, définis comme solutions d'une inégalité variationnelle de dimension infinie, peuvent être approchés par des équilibres de Wardrop symétriques de jeux annexes, solutions d'inégalités variationnelles de petite dimension.Enfin, nous considérons un modèle de jeu pour l'étude d'échanges d'électricité pair-à-pair au sein d'une communauté de consommateurs possédant des actifs de production électrique renouvelable.Nous étudions les équilibres généralisés du jeu obtenu, qui caractérisent les échanges possibles d'énergie et les consommations individuelles.Nous comparons ces équilibres avec la solution centralisée minimisant le coût social, et nous évaluons l'efficacité des équilibres via la notion de prix de l'anarchie. / In the context of smart grid and in the transition to decentralized electric systems, we address the problem of the management of distributed electric consumption flexibilities. We develop different methods based on distributed optimization and game theory approaches.We start by adopting the point of view of a centralized operator in charge of the management of flexibilities for several agents. We provide a distributed and privacy-preserving algorithm to compute consumption profiles for agents that are optimal for the operator.In the proposed method, the individual constraints as well as the individual consumption profile of each agent are never revealed to the operator or the other agents.Then, in a second model, we adopt a more decentralized vision and consider a game theoretic framework for the management of consumption flexibilities.This approach enables, in particular, to take into account the strategic behavior of consumers.Individual objectives are determined by dynamic billing mechanisms, which is motivated by the modeling of congestion effects occurring on time periods receiving a high electricity load from consumers.A relevant class of games in this framework is given by atomic splittable congestion games.We obtain several theoretical results on Nash equilibria for this class of games, and we quantify the efficiency of those equilibria by providing bounds on the price of anarchy.We address the question of the decentralized computation of equilibria in this context by studying the conditions and rates of convergence of the best response and projected gradients algorithms.In practice an operator may deal with a very large number of players, and evaluating the equilibria in a congestion game in this case will be difficult.To address this issue, we give approximation results on the equilibria in congestion and aggregative games with a very large number of players, in the presence of coupling constraints.These results, obtained in the framework of variational inequalities and under some monotonicity conditions, can be used to compute an approximate equilibrium, solution of a small dimension problem.In line with the idea of modeling large populations, we consider nonatomic congestion games with coupling constraints, with an infinity of heterogeneous players: these games arise when the characteristics of a population are described by a parametric density function.Under monotonicity hypotheses, we prove that Wardrop equilibria of such games, given as solutions of an infinite dimensional variational inequality, can be approximated by symmetric Wardrop equilibria of auxiliary games, solutions of low dimension variational inequalities.Again, those results can be the basis of tractable methods to compute an approximate Wardrop equilibrium in a nonatomic infinite-type congestion game.Last, we consider a game model for the study of decentralized peer-to-peer energy exchanges between a community of consumers with renewable production sources.We study the generalized equilibria in this game, which characterize the possible energy trades and associated individual consumptions.We compare the equilibria with the centralized solution minimizing the social cost, and evaluate the efficiency of equilibria through the price of anarchy.

Cette thèse propose des modèles, méthodes et outils destinés aux game designers de jeux thérapeutiques. Le problème de conception le plus fondamental des jeux thérapeutiques est le gameplay, c'est-à-dire des objectifs de jeu et des actions que le joueur doit effectuer pour atteindre ces objectifs. Dans un jeu thérapeutique, le gameplay doit à la fois produire l'effet thérapeutique et motiver le patient à suivre son protocole. Les problèmes sous-jacents de celui-ci sont l'évaluation médicale et ludique du jeu, et l'échange de connaissances entre game designers et experts santé. Nous proposons une méthode de game design de jeu thérapeutique allant de la définition du problème à l'évaluation. Cette méthode intègre les autres solutions que nous proposons, notamment le modèle player/game/therapy et une méthode de formalisation du gameplay. / This PhD thesis explores the field of therapeutic games in order to propose methods and tools for the game designer of such games. The most fundamental design problem of therapeutic games is the gameplay, ie. the game objectives and the actions the player does to address the objectives. In therapeutic game, the gameplay must, at the same time, provide the therapeutic effects and motivate the patient to follow his protocol. The sub-problems of this are 1. the two-fold evaluation (medical and motivation), 2. the exchange of knowledge between game designers and health experts. We propose a therapeutic game design method which begins with the problem definition and ends with the two-fold evaluation. This method integrates the other solutions we propose, particularly the player / game / therapy model and a method to formalize the gameplay.

Rare sont les études empiriques qui, palliant limites langagières de l’enfant, ont investigué la symptomatologie psychologique et comportementale de l’abus sexuel auprès des enfants en examinant les séquelles de ce trauma au travers le jeu libre. Conséquemment, l’objectif de la présente étude est de relever le profil socioaffectif de deux groupes d’enfants abusés sexuellement dont l’un démontre une capacité à jouer préservée et l’autre se caractérise par une activité ludique limitée. En outre, cette recherche vise à identifier les variables relatives aux profils dégagés qui discriminent de façon plus spécifique chacun des deux groupes d’enfants à l’étude. L’échantillon est constitué de 50 enfants abusés sexuellement âgés entre 3 et 6 ans. Tel que prédit, les résultats démontrent que les enfants ayant un potentiel ludique limité, comparativement aux enfants où le potentiel est préservé, sont caractérisés par un surcroît de comportements de nature anxio-dépressive. De plus, ils démontrent un nombre significativement plus élevé de comportements dissociatifs et leur profil symptomatologique est davantage « Internalisé ». Ces résultats supportent l'idée que l'abus sexuel, agissant comme traumatisme, perturbe la capacité à jouer de deux manières différentes : soit il bloque l'accès au jeu chez certains enfants, soit il trouble l’activité ludique en elle-même chez un autre groupe.

Cette étude traite des pratiques ludiques et des représentations liées au jeu en tant que mode d’action et d’interaction chez les Inuit Iglulingmiut (Arctique oriental canadien). Elle propose un examen diachronique de différentes formes de jeu privilégiées par les membres de cette société, qui a connu d’importantes transformations d’ordre religieux et économique au cours du XXe siècle (christianisation et déclin du chamanisme, puis sédentarisation et intégration à une économie de marché…). Partant du constat selon lequel les descriptions livrées par divers observateurs présents dans l’Arctique canadien au XIXe et au début du XXe siècle soulignaient la fréquence et/ou la place significative des activités ludiques dans la vie quotidienne des groupes inuit rencontrés, la présente étude met en lumière certaines fonctions sociales et portées symboliques qui étaient et/ou sont encore associées au jeu chez les Iglulingmiut, en interrogeant plus particulièrement la place du jeu dans les processus liés à la construction de la personne d’une part, et dans les pratiques rituelles collectives vouées à assurer la reproduction et la continuité du groupe (ou bien encore sa mise en scène « culturelle ») d’autre part. / Playing for happiness and good fortune. Ludic practices and the significance of play among the Inuit of the Iglulik region (Eastern Canadian Arctic). This study deals with some of the uses of play (as a way of acting and interacting) among the Inuit of the Iglulik region in the Eastern Canadian Arctic. It examines diachronically various games practiced by the Iglulingmiut (including both children and adults), in order to identify continuities and changes in the forms of play developed in Iglulingmiut society before and after historical ruptures such as the conversion to Christianity and especially, the transition from a semi-nomadic life based on hunting to a settled life characterized by integration to the wider market economy. Observing that many descriptions made by the explorers and the ethnographers of the nineteenth and early twentieth centuries emphasized the importance of ludic practices in the everyday life of the Inuit groups met in this part of the Canadian Arctic, this research further reflects on the significance of play among the Iglulingmiut, both in socialization processes and in ritual gatherings serving to ensure the reproduction of the group or the cohesion and continuity of the « community », from semi-nomadic times until today.

Au cours de cette thèse nous nous sommes intéressé à un jeu minimax différentiel et multi-étages à horizon fini (échéance), motivé par un problème d'évaluation d'options européennes. Le jeu différentiel est en dimension 3 plus temps. Il comporte une commande à la fois continue et impulsionnelle et une commande bornée, ainsi qu'un coût terminal discontinu dans le cas d'une option "digitale" dont l'étude constitue le coeur de la thèse. Ce jeu résulte d'une approche par commande robuste sur l'ensemble des trajectoires de prix permises par l'hypothèse du modèle de marché à intervalles pour le cours de l'actif sur lequel est assise l'option. Du point de vue des techniques financières, notre but est de développer en parallèle une théorie d'évaluation d'options en temps continu et en temps discret, en présence de coûts de transaction et à modèle de marché invariant. Nous obtenons la prime et la stratégie de transaction conseillées au cours du jeu. Notre théorie se veut donc une théorie normative (d'aide à la décision). Pour chaque jeu différentiel, nous utilisons une analyse géométrique des trajectoires extrémales et singulières du jeu qualitatif impulsionnel à cible unique à l'échéance, avec des outils géométriques de la théorie d'Isaacs-Breakwell. Cette analyse nous permet de résoudre complètement le problème. La solution obtenue s'avère riche en variétés singulières de codimension 2, à savoir qu'elle exhibe une dispersion, des variétés équivoques et une variété focale. Cette étude géométrique aboutit à une formule de représentation de la fonction Valeur. faisant intervenir la solution d'un système de deux EDP linéaires couplées du premier ordre. Nous complétons cette étude par une vérification analytique, plus classique, qui consiste à montrer que la fonction construite par la formule de représentation est solution de viscosité de l'équation d'Isaacs associée à un jeu différentiel standard sans commande impulsionnelle ayant la même valeur que le jeu initial. Pour chaque jeu multi-étages, la résolution se fait par le biais d'un algorithme de programmation dynamique classique. Cet algorithme aboutit à une formule de représentation de la Valeur, dont la forme est assez similaire à celle de la solution du jeu différentiel. Il en découle un algorithme rapide applicable en pratique. Nous montrons également la convergence monotone décroissante de la solution du jeu multi-étages vers celle du jeu différentiel lorsque le pas de temps tend vers 0, aussi bien pour une option "vanille" que "digitale", sans changer de modèle d'actif au fur et à mesure que l'on réduit le pas de temps. En conséquent, l'algorithme rapide en temps discret fournit une bonne approximation de la solution (prime et stratégie) en temps continu. Nous terminons ce manuscrit par une analyse critique de la solution du point du vue financier avec en particulier une étude de la robustesse du modèle de marché et une comparaison avec la théorie de F.Black et M.Scholes. Nous insistons sur le fait qu'en aucun cas nous n'avons la prétention de proclamer une quelconque supériorité de notre théorie sur celle de F.Black et M.Scholes. Nous souhaitons seulement montrer qu'elle peut être une alternative en temps discret et/ou en présence de coûts de transaction significatifs, au détriment de la complétude du modèle de marché.

Cette thèse présente les résultats d'expérimentations visant à mettre en évidence des mécaniques de jeu utiles pour aider le joueur à développer une posture plus réflexive sur la manière dont il prend une décision. Notre approche consiste à mettre le joueur en défaut en exploitant ses biais de raisonnement, permettant dans un second temps de l’amener à mieux cerner ses processus décisionnels. A ce titre, nous cherchons à placer le joueur en excès de confiance dans le cadre spécifique d'un jeu vidéo. Pour mesurer le comportement, le joueur doit utiliser un outil intégré au déroulement de la partie : un système de mise au travers duquel il renseigne sa confiance en ses chances de succès. Deux jeux spécifiques ont été développés en vue de mesurer l’influence des biais sur la confiance du joueur : un se focalise sur l’influence des biais d’ancrage et de confirmation, l’autre sur l’influence du biais de l'effet difficile / facile d’autre part. / This thesis introduces the results of experiments testing specific game mechanics to help the players to develop reflective decision making. Our approach is, firstly, to bias the players’ judgment. Then, through the bias awareness, we want to help them to have a better understanding about their judgment processes. To do this, we try to place the player in an overconfident state while playing video games. To measure their behavior, the players must use an integrated tool to the game progression: a bet system through which they assess on their confidence in their chances of success. Two games were developed to measure the influence of the biases on the confidence of the player: one focusing on the effect of anchoring and confirmation biases, another one on the hard / easy effect.