Roland P. Malhamé

Rabih Salhab, Jerome Le Ny, Roland P. Malhamé

We consider a dynamic collective choice problem where a large number of players are cooperatively choosing between multiple destinations while being influenced by the behavior of the group. For example, in a robotic swarm exploring a new environment, a robot might have to choose between multiple sites to visit, but at the same time it should remain close to the group to achieve some coordinated tasks. We show that to find a social optimum for our problem, one needs to solve a set of Linear Quadratic Regulator problems, whose number increases exponentially with the size of the population. Alternatively, we develop via the Mean Field Games methodology a set of decentralized strategies that are independent of the size of the population. When the number of agents is sufficiently large, these strategies qualify as approximately socially optimal. To compute the approximate social optimum, each player needs to know its own state and the statistical distributions of the players' initial states and problem parameters. Finally, we give a numerical example where the cooperative and noncooperative cases have opposite behaviors. Whereas in the former the size of the majority increases with the social effect, in the latter, the existence of a majority is disadvantaged.

Rabih Salhab, Roland P. Malhamé, Jerome Le Ny

Inspired by successful biological collective decision mechanisms such as honey bees searching for a new colony or the collective navigation of fish schools, we consider a mean field games (MFG)-like scenario where a large number of agents have to make a choice among a set of different potential target destinations. Each individual both influences and is influenced by the group's decision, as well as the mean trajectory of all the agents. The model can be interpreted as a stylized version of opinion crystallization in an election for example. The agents' biases are dictated first by their initial spatial position and, in a subsequent generalization of the model, by a combination of initial position and a priori individual preference. The agents have linear dynamics and are coupled through a modified form of quadratic cost. Fixed point based finite population equilibrium conditions are identified and associated existence conditions are established. In general multiple equilibria may exist and the agents need to know all initial conditions to compute them precisely. However, as the number of agents increases sufficiently, we show that 1) the computed fixed point equilibria qualify as epsilon Nash equilibria, 2) agents no longer require all initial conditions to compute the equilibria but rather can do so based on a representative probability distribution of these conditions now viewed as random variables. Numerical results are reported.

Rabih Salhab, Roland P. Malhamé, Jerome Le Ny

We consider a class of dynamic collective choice models with social interactions, whereby a large number of non-uniform agents have to individually settle on one of multiple discrete alternative choices, with the relevance of their would-be choices continuously impacted by noise and the unfolding group behavior. This class of problems is modeled here as a so-called Min-LQG game, i.e., a linear quadratic Gaussian dynamic and non-cooperative game, with an additional combinatorial aspect in that it includes a final choice-related minimization in its terminal cost. The presence of this minimization term is key to enforcing some specific discrete choice by each individual agent. The theory of mean field games is invoked to generate a class of decentralized agent feedback control strategies which are then shown to converge to an exact Nash equilibrium of the game as the number of players increases to infinity. A key building block in our approach is an explicit solution to the problem of computing the best response of a generic agent to some arbitrarily posited smooth mean field trajectory. Ultimately, an agent is shown to face a continuously revised discrete choice problem, where greedy choices dictated by current conditions must be constantly balanced against the risk of the future process noise upsetting the wisdom of such decisions.Even though an agent's ultimately chosen alternative is random and dictated by its entire noise history and initial state, the limiting infinite population macroscopic behavior can still be predicted. It is shown that any Nash equilibrium of the game is defined by an a priori computable probability matrix characterizing the manner in which the agent population ultimately splits among the available alternatives.