Capturing collective conflict dynamics with sparse social circuits

We discuss a set of computational techniques, called Inductive Game Theory, for extracting strategic decision-making rules from time series data and constructing probabilistic social circuits. We construct these circuits by connecting component individuals and groups with strategies in a game and propose an inductive approach to reconstructing the edges. We demonstrate this approach with conflict behavior in a society of pigtailed macaques by identifying significant patterns in decision-making by individuals. With the constructed circuit, we then capture macroscopic features of the system that were not specified in the construction of the initial circuit, providing a mapping between individual level behaviors to collective behaviors over the scale of the group. We extend on previous work in Inductive Game Theory by more efficiently searching the space of possible strategies by grouping individuals into socially relevant sets to produce a more efficient, parsimonious specification of the underlying interactions between components. We discuss how we reduce the dimensionality of these circuits using coarse-graining or compression to build cognitive effective theories for collective behavior.


INTRODUCTION
A central problem in the study of collective behavior is how functionally significant macroscopic properties arise out of individual or microscopic interactions. The most common approach to studying the relationship between the micro and macro in biological systems is dynamical systems and pattern formation (for examples, see Sumpter, 2006;Ball, 2009;Couzin, 2009;Payne et al., 2013). A complementary approach is to treat the micro to macro mapping explicitly as a computation.
A macroscopic property can be said to be an output of a computation if it can take on values that have functional consequences at the group or component level, is the result of a distributed and coordinated sequence of component interactions under the operation of a strategy set, and is a stable output of input values that converges (terminates) in biologically relevant time  .
The input to the computation is the set of elements implementing the rules or strategies. The input plus the strategies constitute the system's microscopic behavior. My collaborators and I have developed novel computational techniques, called Inductive Game Theory ] Krakauer 2011][Lee et al. 2014], to extract strategic decision-making rules from correlations observed in the time series data and reconstruct the microscopic behavior.
In biological systems, there are typically multiple components interacting. Hence the computation of the macroscopic output is inherently collective, meaning we must examine how different configurations of strategies affect the macroscopic output ]. We describe the space of microscopic configurations using Markovian, probabilistic, "social" circuits ] Krakauer 2011][Lee et al. 2014].
Here, we briefly illustrate this approach using time series data collected on conflict dynamics from an animal society model system-a large, captive group of captive pigtailed macaques (Macaca nemestrina) (n = 47). We start with very simple time series data on which individuals were present in a conflict. This gives us a time series of binary fight participation vectors. Given this input of individual identities, our output is the distribution of fight sizes, which has been shown to have functional consequences for individuals in the study system ]. We ask whether individuals decide to join fights based on participation in the last fight (say between their allies and adversaries), what are their decision-making strategies, and how do these strategies collectively produce the distribution of fight sizes?

STRATEGY EXTRACTION AND CIRCUIT CONSTRUCTION
We begin by defining a space of strategies. Since we are interested in how individuals join fights and have limited a priori our input data to identity of fight participants, we can represent this space of strategies as c(n, m), where m-tuplet of individuals in the fight at time t is determined by the behavior of an n-tuplet of individuals in the fight at time t − 1 [DeDeo et al. 2010]. We restrict the C(n, m) 1:2 • ED Lee, BC Daniels, DC Krakauer and JC Flack space we explore to C(1, 1), C(2, 1), and C(1, 2) the simplest strategies in the space as cognitive and behavioral data indicate that the macaques are capable of using these strategies.
Choosing C(n, m) specifies the identity of the vertices between which can allow for strategic connections. The directed edges correspond to strategic information from m to n and we compute these as N (i) is the total number of events in which the n-tuplet i participated at all times t−1, and N (j t |i t−1 ) is the number of events in which the m-tuplet j participated at t given i in the previous event. N null is the average calculated over time permutations of the fights while maintaining the participation integrity of each event (e.g. we only shuffle the order of events; we do not shuffle participation).
The ∆P corresponds to a measurement of how often j follows i as a deviation from shuffle time series. Positive (negative) values indicate that j is more (less) likely to follow i than by chance. Since ∆P is normalized to −1 to 1, we interpret these values probabilistically where negative values correspond to a suggestion of strategic avoidance in the following fight.
We use the list of ∆P found for each C(n, m) strategy class to construct a social circuit for each strategy class. By modulating how we account for these causal relationships, we end up with multiple alternative circuits, or a family of circuits for each C(n, m) strategy class. Each circuit in the family is a model of the micro-macro relationship and so serves as a hypothesis for how strategies combine over nodes (inputs) to produce to the target output [Lee et al. 2014]. We test the circuits against each other in simulation to determine which can best recover the actual measured macroscopic behavior of our system and other fine grained statistics.
We find that (1) a variant of the C(2, 1) circuit, with the measured ∆P , captures some important features of the microscopic behavior of the system, (2) but that the distribution of fight sizes is degenerate over configurations of the C(2, 1) circuit parameter space. Although our analyses support the conclusion that the distribution of fight sizes results from the summed contributions of the ∆P in the C(2, 1) circuit, we note that the degeneracy of the distribution of fight sizes for C(2, 1) parameter space coupled to the observation that the C(2, 1) circuit is extremely complex with many precise, tiny parameters, suggests that the exact measured values of ∆P may not matter. A natural next step is to systematically reduce the dimensionality of the circuit. Our goal is two-fold: to find the a parsimonious description of the generative process that is also consistent with what we know about the information the monkeys use to make decisions-a cognitive effective theory.

SPARSE SOCIAL CIRCUIT CONSTRUCTION
Our approach is to compress the time series data to build a more compact circuit. Using a technique from neuroscience called sparse coding [Olshausen and Field 1997], we extract the individuals and subgroups that are regular and predictable conflict participants [Daniels et al. 2012]. We show an example from this process in Figure 3. Between these sparse groups, we search for ∆P strategies as specified in Eq 1, a space we denote as C(s i , s j ), where the sizes of groups 1 ≤ |s i |, |s i | ≤ 5. Consistent with previous results ], we find more significant C(2, 1) and less significant C(1, 1) strategies than would be expected from a null permutation of the data. On the other hand, we also find evidence for other strategy classes beyond the three explored in previous work.
Since we expect that important social groups in the data set constitute relevant features for strategy formation, we also allow for strategies of the form C(s i , 1), that is information that individuals use to form strategic decisions based on previous participation of a sparse group. Even with this addition, we have ∼12 sparse groups and so the number of strategic edges that can exist on this graph are several Capturing collective conflict dynamics with sparse social circuits • 1:3 orders smaller than the bipartite C(2, 1), a lesser cognitive burden on individuals who might use a similar model to predict conflict behavior.
Compared to other models that have been proposed for this system, the C(s i , s j &1) sparse circuit constitutes a comparatively reasonable fit despite being far more cognitively and computationally parsimonious in the number of possible strategies. Fig. 1. Example of sparse basis circuit obtained by sparse coding. Individuals in light blue circles are part of groups in dark blue. Individuals not in basis groups are green. For example, individual Vf is in a basis group alone. Eo and Ob appear in multiple different basis groups in this solution. We only show the top 15 largest ∆P significant with p ≤ 0.05; these are all positive. This circuit is simpler than the C(2, 1) network in so far as it has many fewer nodes and these nodes are composed of the regular and predictable individuals.

CONCLUSION
We have proposed an approach for reconstructing the microscopic, strategic behavior of components and individuals in social systems. This approach involves extracting component decision-making strategies from time series data on competitive interactions and constructing circuits that specify how these strategies combine to produce functionally important macroscopic properties that describe social structure.
With the exception of a few life history variables, it is not yet known what the important macroscopic properties are in biological and social systems. As we refine our understanding of the micro to macro mapping through construction of "full" circuits capturing the detailed microscopic behavior and prune these circuits to construct cognitive effective theories for the macroscopic output, we gain insight into the what properties of the time series data constitute the "right" input and hence the building blocks of our system. By investigating whether our most accurate, empirically justified circuits can also account for other potentially important macroscopic properties, we can begin to establish which macroscopic properties might be fundamental and what their relation is to one another, thereby moving towards a thermodynamics of biological collectives ].