Accession Number:



Large Deviations in Multi-Agent Systems

Descriptive Note:

[Technical Report, Final Report]

Corporate Author:

University of Wisconsin - Madison

Personal Author(s):

Report Date:


Pagination or Media Count:



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. 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. In our first major goal, 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.


Subject Categories:

  • Operations Research

Distribution Statement:

[A, Approved For Public Release]