A Class of Linear Quadratic Dynamic Multi-Agent Discrete Choice Models with Congestion Effects

Dans cette thèse, nous étudions une catégorie de modèles dynamiques associés à des choix collectifs discrets. À cette fin, nous considérons un nombre d’agents qui, sur un horizon temporel donné, se déplacent vers l’une de multiples destinations tout en minimisant une fonction de coût quadratique. Cette fonction de coût dépend à la fois de la congestion, de l’effet du stress ressenti par les agents ainsi que l’énergie dépensée lors du déplacement des agents. La congestion est simulée par l’introduction de termes négatifs liés au degré de séparation des agents dans la fonction de coût. Cette technique nous permet d’obtenir une expression analytique de la solution, mais apporte également de nouveaux défis analytiques par rapport aux modèles similaires précédemment étudiés dans la littérature. Cette thèse se consacre ainsi à l’étude de deux scénarios distincts : le cas non-coopératif et le cas à intérêt commun. Dans le contexte du modèle non coopératif, où chaque agent cherche à minimiser sa propre fonction coût, nous utilisons la méthodologie des jeux à champ moyen pour étudier le comportement d’un grand nombre d’agents. De plus, on limite les choix accessibles à chaque agent en fonction de sa position initiale (généralement, seules les destinations les plus proches sont déclarées accessibles). À la différence des modèles linéaires quadratiques, où les déplacements des agents sont influencés par la moyenne globale de la population, dans le modèle proposé, la trajectoire de chaque agent n’est influencée que par les cohortes dont l’intersection de l’ensemble des destinations accessibles avec celui de l’agent en question est non vide. Par conséquent, chaque destination agit comme un noeud dans un réseau fini. Cette configuration confère une structure de réseau au jeu à champ moyen en question et s’inscrit dans la lignée des efforts récents visant à traiter les jeux à champ moyen impliquant plusieurs populations avec des interactions non locales. Dans notre analyse du modèle, nous élaborons des stratégies décentralisées pour chaque agent, qui convergent vers un équilibre de Nash au fur et à mesure que le nombre d’agents augmente. De plus, nous identifions des conditions suffisantes pour que le problème possède une solution. Dans le cadre du modèle collectif à intérêt commun, où les agents collaborent pour minimiser un coût commun, on n’impose aucune restriction à l’accès des agents aux destinations et la fonction du coût commun dépend de la moyenne globale de la population. Cependant, la résolution de ce modèle nécessite la résolution d’un système d’équations dont la taille augmente exponentiellement avec la taille de la population. Dans la littérature, plusieurs techniques ont été suggérées pour aborder ce défi, mais elles imposent des contraintes restrictives sur le choix des paramètres du modèle, qui s’avèrent incompatibles avec le modèle proposé. L’approche de résolution proposée exploite les symétries du modèle. En premier lieu, elle consiste à démontrer qu’il est possible de résoudre de manière équivalente un nombre de problèmes de commande optimale linéaire quadratique correspondant au nombre de destinations, suivi par un problème de transport optimal paramétré par la fraction d’agents optant pour chacune des destinations. Pour simplifier davantage la recherche de la solution, nous établissons un système approprié d’équations limites, dont la solution est utilisée pour définir une stratégie permettant d’approcher la solution optimale du problème initial, en particulier lorsque le nombre d’agents devient important. Le caractère convexe de la fonction coût limite est aussi établi et cela permet de simplifier considérablement les calculs de politiques sous-optimale de bonne qualité.

Abstract

In this thesis, we study a class of dynamic models associated with discrete collective decisions. We consider a number of agents who, during a given time period, move towards one of multiple destinations while minimizing a quadratic cost function. This cost function depends on congestion, the stress experienced by agents, and the energy used during agents’ movement. Congestion is simulated by introducing negative terms in the cost function. This technique allows the analytical tractability of the solution, but also brings new analytical challenges compared to similar models previously studied in the literature. This thesis is dedicated to the study of two distinct scenarios: the non-cooperative case and the identical interest case. In the context of the non-cooperative model, where each agent seeks to minimize its own cost function, we use the mean field game approach to study the behavior of a large number of agents. Additionally, we limit the accessible choices for each agent based on their initial position (usually only the closest destinations are accessible). Unlike previous linear quadratic models where the agents’ movements were influenced by the overall population state average trajectory, in the proposed model, only cohorts sharing the same set of accessible destinations can influence the trajectory of a specific agent. As a result, each destination acts as a node in a finite network. This configuration confers a network structure to the mean field game in question and is in line with recent efforts to address mean-field games involving multiple populations with non-local interactions. In our analysis of the model, we develop decentralized strategies for each agent that converge to a Nash equilibrium as the number of agents increases. Furthermore, we identify sufficient conditions ensuring the proposed model well-posedness. As for the identical interest model, where agents collaborate to minimize a common cost, no restrictions are imposed on the agents’ access to destinations, and the common cost function depends on the overall population average. However, solving this model requires solving a system of equations whose size increases exponentially with the population size. While various techniques have been proposed in the literature to tackle such systems, they often impose restrictive constraints on the choice of model parameters, which are found to be incompatible with the proposed model. Our resolution approach exploits the problem symmetries. It consists of showing that identifying a solution to our model is equivalent to solving a number of linear quadratic regulator problems equal to the number of destinations, followed by an optimal transport problem parameterized by the fraction of agents choosing each destination. Then, we further reduce the solution search complexity by defining an appropriate system of limiting equations, whose solution is used to obtain an asymptotically optimal strategy. We also show the convexity of the limiting cost function, which considerably simplify the computation of the suboptimal policies.