Large Deviations in Multi-Agent Systems
Abstract
Large multi-agent systems are basic models in wide variety of disciplines, ranging from the social sciences to engineering and the physical sciences. In many applications, these systems are best understood from a game-theoretic perspective, with each agent being endowed with a payoff function that it aims to maximize. To obtain a dynamic model of agents behavior, one also assigns each agent a revision protocol, which describes how the agent uses the information it possesses to decide when to switch actions, and which action to choose. Dynamic multi-agent models of this sort are the central objects of study in evolutionary game theory. Such models have a range of applications of direct relevance to the Army s mission. These applications include congestion and congestion abatement in highway and data networks, conflict between users and signal jammers in communications networks, sensor coverage problems, target assignment for weapons systems, and choices of political allegiances under unstable regimes. Most work in evolutionary game theory has focused on two questions. One, equilibrium convergence, considers which multi-agent systems will achieve equilibrium configurations over moderate time spans. The other, long-run equilibrium selection, considers models in which agents sometimes choose suboptimal actions, and describes which equilibrium will be played in a large proportion of periods over long enough time spans. For a full understanding of large multi-agent systems, one must address a third question: that of equilibrium breakdown. Here the aim is to understand how and when equilibrium is likely to unravel, and which new equilibrium, if any, is likely to arise in its place. While such questions are of basic importance, they have attracted limited attention in the literature, in part because of the technical demands they impose. We use methods from large deviations theory to study escape from and transitions among equilibria in large multi-agent systems. The analysis of large deviations in games takes the theory of equilibrium convergence as its prerequisite, and in turn, this analysis provides new, general, tractable methods for the study of equilibrium selection. In the basic model considered here, the behavior of revising agents is described by a noisy best response protocol, under which a revising agent typically chooses an optimal action, but places positive probability on all actions. To account for agents incentives to avoid costly mistakes, we assume that the probability of any given suboptimal choice depends on its payoff consequences. We first consider the question of large deviations in the large population limit, holding the noise level in agents decisions fixed. We establish a large deviations principle, which describes the rate of decay of the probability of observing sample paths from any given set as the population size grows large. This description is couched in terms of solutions to optimal control problems. Combining this result with other techniques should provide exact characterizations of escape from, transitions among, and long-run selection of equilibria. We then study the large population double limit, in which the former limit is followed by taking the noise level to zero. Taking this second limit makes the control problems noted above much more amenable to analysis. In order to solve the latter optimal control problems, we propose new results on solutions of HJB equations with state constraints. These results should allow the control problems to be solved in far more environments than is possible using the existing theory. Finally, we introduce computational tools for testing the validity of the theory s predictions away from the limiting regime, for examining the effects of agent heterogeneity, and for studying local and mid-range interactions among agents situated in networks.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 11, 2018
- Source ID
- W911NF1710134
Entities
People
- William H. Sandholm
Organizations
- Army Contracting Command
- United States Army
- University of Wisconsin–Madison