Collective Stochastic Discrete Choice Problems: A MIN-LQG Game Formulation

On étudie dans cette thèse une classe de problèmes dynamiques concernant des choix collectifs discrets. Il s'agit de situations où un grand nombre d'agents exercent un effort pendant un horizon de temps fini pour se déplacer de leur position initiale et être à la fin de l'horizon aux alentours d'un nombre fini d'alternatives. En bougeant, ils doivent minimiser leurs efforts. De plus, le trajet de chaque agent est influencé par le comportement global de la population (l'effet social). Par exemple, un groupe de robots explorant un terrain doivent bouger de leurs positions initiales pour visiter plusieurs sites d'intérêt en minimisant leurs efforts. Le groupe peut se diviser en plusieurs sous-groupes, mais la taille de chacun doit rester suffisamment grande pour accomplir quelques tâches collectives, par exemple, des missions de secours. Ces problèmes sont aussi reliés aux élections, où les électeurs changent continuellement leurs opinions jusqu'au moment de décider pour qui ils veulent voter. Durant ce processus de choix d'un candidat, l'électeur optimise ses efforts pour ajuster son opinion et rester dans la zone de confort, c'est-à-dire, proche des opinions des autres. Le but de cette thèse est de comprendre les comportements individuels des agents et en déduire le comportement global de la population, et cela, lorsque les agents prennent leurs décisions de façon soit non-coopérative, soit coopérative. En d'autres termes, pour chacun des deux cas, on répond aux questions suivantes : comment un agent choisit-il sous l'influence de l'effet social? Peuton prédire le comportement global de la population et la distribution des choix entre les alternatives? On modélise les problèmes des choix discrets non-coopératifs par une nouvelle classe de jeux dynamiques non-coopératifs qu'on nomme “min-LQG”. Ce sont des versions modifiées des jeux LQG où les coûts individuels incluent un coût final qui est la distance minimale à l'ensemble des alternatives pour modéliser le phénomène des choix discrets. On étudie deux cas. Dans le premier (min-LQG dégénéré), on considère des agents décrits par des équations différentielles avec des conditions initiales aléatoires, alors que dans le deuxième (min-LQG non-dégénéré), leurs dynamiques sont des équations différentielles stochastiques. On utilise la méthodologie des jeux à champs moyen pour analyser les jeux. On développe des stratégies décentralisées, où chaque agent peut implémenter la sienne en observant son état et la distribution de probabilité des états initiaux des agents. Ces stratégies convergent vers un équilibre de Nash lorsque le nombre d'agents tend vers l'infini. Dans le cas dégénéré, un agent fait son choix d'alternative avant de bouger en se basant sur son état initial. Mais, dans le cas non-dégénéré, il ne peut plus s'engager à un choix dès le début.

Abstract

This thesis studies a class of dynamic collective discrete choice problems, whereby a large number of agents have to settle on one of a set of available alternatives within a finite time. Motion in choice space involves a control effort and it is socially influenced, in that the agents' paths are influenced by the aggregate behavior of the group. For example, a large collection of geographically dispersed robots exploring an unknown terrain must move with least energy expenditure from their initial randomly spread positions towards one of multiple potential sites of interest to visit. They do so, however, while trying to remain grouped to achieve some collective tasks, such as search and rescue. Another example is a mechanistic model of elections, where voters evolve continuously in opinion space until they form a final decision regarding who they should vote for. Until voters settle on a candidate, changes in their opinions will involve a mental strain, but at the same time, adhering to an individual opinion when it currently deviates from that of the majority will cause some level of discomfort. Even though both examples qualify as dynamic collective choice problems, they differ in the manner the agents make their choices. In the robotic example, a designer or social planner coordinates the robots' paths to optimize a global cost, while in the second example, the voters, left without any central coordinator, update their opinions selfishly irrespective of whether they make others better or worse-off. This suggests a classification of dynamic collective choice problems into cooperative and noncooperative types respectively. This work aims at modeling these problems and understanding how the population behaves on the microscopic (individual) and macroscopic (population) levels. In other words, we try to answer the following main questions: how does an agent make its choice under the social effect? Can one anticipate the evolution of the agents' state probability distribution (macroscopic behavior) along the time interval, and that of the agents' ultimate choices over the alternatives? We formulate the non-cooperative problem as a dynamic non-cooperative game with a socalled “min-LQG” individual cost. This consists of a modified version of the linear quadratic Gaussian performance index that includes a choice-related minimization term in the final cost to capture the discrete choice aspect. We study two cases. In the first one, the degenerate case, the agents' states evolve according to a set of linear ordinary differential équations with the only source of randomness being their initial conditions. In the second one, the non-degenerate case, besides their random initial conditions, agents are subjected to random noise, thus evolving according to stochastic differential equations.