Strategic Inference in Adversarial Encounters Using Graph Matching

Abstract

There are many situations where we need to determine the most likely strategy that another team is following. Their strategy dictates their most likely next actions by selecting the optimal policy from their set of policies. In this scenario, there is a hierarchical, multi-agent, multi-team environment where the teams are built on layers of agents working together at each level to coordinate their behaviors, such as SiMAMT. We can think of a strategy as a hierarchically layered policy network that allows for teams to work together as a group while maintaining their own personalities. They can also shift from one policy to another as the situation dictates. SiMAMT creates an environment like this where sets of such teams can work together as allies or team up against others as adversaries. In this context, we wish to have a set of teams working as allies facing another set of teams as adversaries. One alliance should be able to analyze the actions of another alliance to determine the most likely strategy that they are following, thus predicting their next actions as well as the next best actions for the current alliance. To accomplish this, the algorithm builds graphs that represent the alignment (i.e., the constellation) of the various agent’s policies and their movement dependency diagrams (MDDs). These graphs are a clear way to represent the individual agent’s policies and their aggregation into a strategy. In this instance, the edges of the graphs represent choices that the policy can make while the vertices represent the decision junctures. This creates a map of the various agents as they move through a progression of decisions, where each decision is made at a decision juncture, and each edge shows the probabilistic progression from each of those decisions. These graphs can show the likelihood of actions taken at each level of the hierarchy, thus encoding the behaviors of the agents, their groups, the teams, and the alliances. We wish to demonstrate that these graphs can represent large sets of teams or alliances and that each alliance can use these representations to coordinate their own behavior while analyzing the behaviors of other alliances. Further, we wish to show that an alliance can make a decision in interactive time on which policy from within their strategy set should be in place based on their observations of other alliance’s strategies. To do so, the algorithm will build a probabilistic graph based on the observed actions of the other alliances by observing the actions taken by each agent within that alliance. It can then compare that probabilistic graph with known graph strategies or those that it has learned along the way. We present this methodology and verify it with experimentation confirmed in the conclusions in this paper.