The Minds of Many: Opponent Modeling in a Stochastic Game

1 Introduction

Opponent modelling is a technique to recognize the strategy of an opponent and make predictions about their behaviour. In AI, opponent modelling is used for decision making by exploiting sub-optimal opponents [Ganzfried and Sandholm, 2011].

One technique that can be used in opponent modeling is Theory of Mind (ToM) [Goldman, 2012]. ToM is a concept from psychology that describes the higher cognitive mechanism of attributing unobservable mental content, such as beliefs, desires and intentions to others. ToM is used by humans to form models for predicting the behaviour, decisions and actions of other individuals. ToM is a bounded rationality model [Brennan and Lo, 2012], and as such is suitable to simulate human decision making in agents. Typically, this is a done recursively using nested beliefs - a process referred to as higher-order ToM. That is, an agent A can not only form beliefs about what another agent B would do, but also about what the other agent B would believe about agent A or what the other agent B believes the agent A to know about them, etc.

In this paper, we propose a multi-agent ToM model (MToM) that extends an existing computational ToMmodel. In contrast to De Weerd et al., [2013b], who model one adversary, our model allows multiple opponents to be considered at the same time. Thus, agents have to model other agents' views of them and their views of other agents. Humans have limited ability to model multiple opponents, so they resort to stereotyping [Fiske, 2000]. We introduce a mechanism to model stereotyping that segments opponents into categories, which are then treated as single opponents in MToM.

We validate our MToM model using a stochastic multiplayer game. ToMmodels are particularly useful in stochastic games due to the fact that recognizing the strategies of opponents gives a player a significant advantage. The stochastic game used in the experiments is the Common Pool Resource Game (CPRG) [Sethi and Somanathan, 1996; von der Osten et al., 2017], a large-scale social dilemma. This game is particularly suitable as a demonstration for MToM, as in reality individual behaviour is dependent on beliefs about the behaviour of other individuals [Cavalcanti et al., 2010]. Outcomes of the game depend on the cumulative actions of all agents, hence it is critical to predict other agents' actions. Furthermore, the CPRG is a difficult game in the context of AI, as it presents agents with multiple challenges: nondeterministic game dynamics, partial observability and unknown adversaries.

We show the MToM model can be used to predict agents' actions and demonstrate the model's behaviour under uncertainty by detailing the impact of perfect and imperfect knowledge. Furthermore we show the effect of using different orders of ToM. We establish that MToM agents are able to estimate the the sophistication of their opponents' strategy, especially in non-homogeneous populations.

2 RelatedWork

Research in psychology has dealt with the topic of ToM quite extensively [Perner, 1999; Goldman, 2012]. Psychologists investigate ToM as a tool of human cognition that equips them with an evolutionary advantage. As an integrated part of a more general model of bounded rationality it helps explain human behavior accurately [Robalino and Robson, 2012; Brennan and Lo, 2012]. ToM is often viewed from an evolutionary perspective [Kimbrough et al., 2014] and it was found that natural selection favours intention recognition, which enables the evolution of cooperation [Pereira et al., 2012].

Such concepts have been formalised in computational models, such as in interactive POMDPs [Gmytrasiewicz and Doshi, 2005], in which agents explicitly contains a nested model of other agents in the environment. These have been used to successfully model human-agent settings, such as in PsychSim [Pynadath and Marsella, 2005].

De Weerd et al. [2015] apply ToM to the tacit communication game to support the hypothesis that ToM facilitates cooperative behaviour. This application of ToM shows its potential in the field of AI. Other approaches [Yoshida et al., 2008; Pereira et al., 2011] keep a model to learn beliefs about opponents' actions and a separate model to infer the complexity of opponent strategies, whereas De Weerd et al. [2013b] integrate beliefs about opponent behaviour with inference about the sophistication of their strategies (see integration of different orders of ToM in Section 3). Furthermore, a game theoretic advantage of ToM is that it allows agents to infer the opponents degree of sophistication [Yoshida et al., 2008].

Despite the Vygotskian intelligence hypothesis suggesting that higher-order ToM allows individuals to cooperate more effectively [Moll and Tomasello, 2007], higher-order ToM has an advantage over lower-order ToM, but becomes ineffective beyond the second order [De Weerd et al., 2013b; 2013a], i.e., person A estimates what person B estimates person A estimates person B will do [zero order: person A estimates what person B will do; first order: person A estimates what person B estimates person A will do]. The reason for this might lie in the biological cost in humans (brain power) on one hand, and the mathematical limitations of the model (over-fitting when dealing with lower orders of ToM) on the other hand. However, the limited sophistication of ToM in humans is not necessarily a consequence of biological costs, but can be explained by cooperation favouring lower orders of ToM [Devaine et al., 2014].

We are not the first to consider ideas of segmentation. Albrecht et al. [2016] use agent types to generalise agents with similar behaviour. The difference between our stereotyping and that of Albrecht et al. is that we create a behavioural profile of a type, rather than assigning a probability that an agent is of that particular type. Felli et al.. [2015] propose agent models, and define 'stereotypical reasoning' about individuals or groups of agents. Similar to Albrecht et al. though, they do not aim to learn the segments, but merely to prescribe them manually.

3 Model

3.1 Multi-ToM

The model used in this paper is an extension of the De Weerd et al., [2013b] model, conceptualized for one player and one opponent. In principle this model can be used for any order of ToM, but for the sake of simplicity, we limit the description to the first two orders.

A zero-order theory of mind (ToM0) agent i starts out with a set of beliefs b about the other agent j, which is a set of probabilities that indicate the likelihood that the opposing agent j takes a certain action aj ∈ Aj in a particular state s ∈ S of the game:

where Aj is the set of actions performed by agent j and S is the set of possible game states (see Section 4.1).

In the multi-agent extension of De Weerd's ToM model, an agent i has to keep zero-order beliefs not just about one opponent, but about multiple:

in which n is the total number of agents participating in the game and b(0) j is the belief of agent i about agent j. Using this set of beliefs, agent i can assign a value Φ to playing a certain action itself given the likelihood of the opposing agents j playing a particular action, based on the pay-off πi agent i will get. This is done by summing over all possible permutations of actions of all other agents:

with permutation σk (also called permutation with repetition/of a multi-set or tuple) consisting of actions ak ∈ A out of the set of all permutations Kn-1. The agent will then choose the action ai that maximizes this value Φ with a decision function t∗i :

A first-order theory of mind (ToM1) agent keeps its zeroorder beliefs b(0) , but also has first-order beliefs b(1) ; that is, a set of probabilities that describe agent i's estimate of an agent j's zero-order beliefs. The beliefs b(1) thus describe what agent i believes agent j believes about agent k (where k can also be agent i). The first-order beliefs do not only include the zero-order beliefs of other agents j about agent i, but also about each other:

where b(1) j,k represents the belief agent i has that agent j believes about k. Given this set of first-order beliefs, agent i can make a prediction ˆa(1) j of agent j's action by mimicking agent j's decision process with its decision function t∗ given its beliefs b(1) about agent j's zero-order beliefs:

The agent i now has a prediction ˆa(1) j of each of its opponents actions based on its first-order beliefs and its own zero-order belief b(0) indicating the probability of the opponent playing a certain action. These two are integrated to form a combined estimate of opponent behaviour. An agent i has a certain confidence cj1 - the extent to which ToM1 governs their decisions - in its first-order beliefs b(1) . An agent has a different confidence for each first-order belief about agent j, and uses that confidence to weight the influence of its first-order beliefs when integrating zero-order beliefs and first-order prediction. The integration function U produces an integrated zero-order belief that weighs in the first-order prediction:

Agent i can now use this integrated belief to make a decision with its decision function t∗ :

Given the actual action ˜aj of opponent j and agent i's own actual action ˜ai, the confidence cj1 is updated with

with nested beliefs being updated as follows:

where λ is the learning speed of an agent. Belief integration not only includes updating first-order beliefs about agent i but also about all other agents, using their corresponding observed actions ˜a, i.e., agent i observing agent j's action does not only prompt an update of b(0) j but also b(1) 1,j , b(1) 2,j , etc. Note that for the experiments in this paper we limit the order of ToM to first-order beliefs. For a visualization of how MToM is applied, see Figure 2.

In the experiments in Section 4, agents either have complete knowledge (CI) of the game dynamics, or the pay-off π is not known to agents, but approximated by means of Q-Learning [Watkins and Dayan, 1992]. Agents learn their expected pay-off given other agents' contributions and their own decision in a given game state. The resulting Q-values are a qualitative representation of the pay-off magnitude and can serve as a pay-off estimation in place of the known payoff function.

Correspondingly, the action selection mechanism consists of either choosing the action with the best value (t∗ , see Equation 4) when the pay-off is known, or Boltzmann/Softmax selection when the pay-off is unknown; i.e., actions are selected with a probability proportional to their value:

3.2 Segmentation

With an increasing number of agents, not only does the computational complexity of a simulation rise exponentially (see Figure 1), the model also becomes increasingly unrealistic in modelling human behaviour. When confronted with too much information to process at once, humans resort to stereotyping to generalize details and still make reasonably accurate predictions [Oakes et al., 1994; Fiske, 2000; Kashima et al., 2000]. Stereotyping is the generalization of individual behaviour to a group to simplify decisions and evaluations. For this reason we introduce a mechanism to segment agents into groups according to their observed history of actions. There are several ways to approach this, and to demonstrate MToM we have chosen a straightforward approach [Camerer et al., 2015; Kashima et al., 2000]: an agent j's action aj,r in round r, averaged over the last ∆t rounds of the game, is assumed to be representative of its behaviour:

Given a predefined number of categories C ∈ N∗ , an agent falls into category v when

When agents are segmented, the corresponding groups are treated as single agents, thus reducing the computational cost and simulating stereotyping as described above. This process is repeated periodically throughout the game to be able to assess and reassess opponent behaviour accurately.

3.3 Complexity Analysis

Theorem 1. The space complexity of MToM is O(n2 ) with O = Θ = Ω.

Proof. There are two data structures used by the model: the zero-order beliefs b(0) about each agent, thus of size n, and the first-order beliefs b(1) about each agent and their beliefs about each other (bar their beliefs about themselves), thus of size n-1×n-2 (see Equations 2 & 5 respectively). Hence, the total size of the data structures used is n × n = n2 . Furthermore, the data structures are static, making the worst case space complexity the same as the best and average cases. ■

Theorem 2. The time complexity of MToM is O(nmn ) with m = ‖A‖.

Proof. For zero-order MToM, the expected pay-offs using zero-order beliefs b(0) about other agents are calculated by summing over all permutations of actions a of all agents n multiplied. The number of permutations is then ‖A‖n (see Equation 3). For first-order MToM, predictions for each other agent's action are made by mimicking their zero-order decision process given b(1) , thus repeating zero-order MToM n - 1 times: n - 1‖A‖n (see Equation 6). The integration of first and zero-order beliefs takes one iteration of the belief table b(0) , i.e., n operations (see Equation 7), and the update process of both belief tables takes n2 and n operations respectively (see Equation 9 & 10). The overall action selection uses the integrated beliefs, taking an additional n - 1 times: n - 1‖A‖n operations (see Equation 8), resulting in 2(n - 1)‖A‖n + n2 + 2n operations for an agent decision. Figure 1 presents the computation steps measured in the experiments. For segmentation the time complexity is reduced to: O(CmC ). For d orders of ToM, the time complexity is O(mnn ) to the d-th power of n. ■

4 Experimental Design

4.1 Game Model

Stochastic games are Markov Decision Processes (MDP) in which state transitions and pay-offs depend on the behaviour of other agents [Condon, 1992]. A stochastic game is typically defined by the quadruple (S,A, P,R) with a finite set of players [Shapley, 1953; Mertens and Neyman, 1981]. As a case study, we use an instance of a stochastic game - the Common Pool Resource Game (CPRG). Figure 2 illustrates the thought processes of agents using MToM in a representative CPRG (an abstract fisheries game).

In the CPRG, a group of individuals harvest a resource (the state space S) and each individual decides their effort x at a cost c to invest in harvesting (the action space A). The combined effort of the group X, along with the state of the resource N, determines their pay-off π (the reward R). The state of the resource is in turn dependent on the harvest H, as well as its growth G (described by the transition probabilities between states P). The goal of the population as a whole is to harvest the resource sustainably, whereas the individual goal is to maximize the pay-off from harvesting. As the population grows larger, it becomes increasingly difficult to harvest both sustainably and profitably. The CPRG is formulated as a stochastic game as follows. The state space S describes the level of the resource N:

The action space A describes the actions available to an individual agent. In the CPRG, an action is a level of investment x into harvesting the resource. The range of actions depends on the number of agents n participating in the game:

Note that both state and action space are discretized into finite sets. The transition between states is represented as probabilities P dependent on the current state and action. In the CPRG, these transitions depend on the actions of all agents, and are governed by coupled differential equations describing resource dynamics, particularly the harvest H and growth G:

Finally, agents receive a reward determined by the reward function R, depending on the invested effort X of all agents and the level of the resource N:

with the pay-off π being the agents proportional fraction of harvest according to its invested effort x with resource level N. The cumulative pay-off A = ∑tmax t=0 π and the resource level N are used as performance measures for the CPRG.

The harvest returns and resource growth are determined by a set of coupled differential equations and not usually known to the participants of the game. A detailed description of the game dynamics can be found in von der Osten et al. [2017]. The uncertainty in estimating pay-offs and the dynamic resource behaviour makes this an interesting application of opponent modeling. Furthermore there are usually multiple participants in this type of game, resulting in decision making becoming more complex as populations increase.

4.2 Setup

In the first experiment, we demonstrate the efficacy of MToM as an opponent modelling mechanism, under the assumptions of either complete information or uncertainty. The population is fixed size (n = 5, independent variable). Different zero (MToM0) and first-order (MToM1) agents are compared with an optimal baseline (OPT) - which knows the pay-offs and actions of all agents - and a population of random agents (RND). In the second experiment, we examine the scalability and relative robustness of the segmentation process. The population ranged from n = 10 to n = 50 with increments of 10, and the number of categories ranging from C = 1 to C = 4. The third set of experiments is used to determine the success of stereotyping facilitated by the inference of opponent sophistication in MToM given non-homogeneous populations. The population size is fixed (n = 10) using C = 1 category for segmentation. Populations are made up of MToM0/MToM1 agents and 20/30/40/50% RND agents (independent variable h). Each simulation is run for 5000 rounds, with each setting repeated 50 times. We ran one-way ANOVA with subsequent post-hoc Tukey HSD tests. Table 1 shows the parameters and variables used in the experiments.

Agents use MToM as their strategy to play the stochastic game (see Figure 2). The success of the agents is defined by the outcome of the game. Therefore, the measures taken are: (1) the level of the resource N that describes the sustainability of the system; and (2) the average agent assets ¯ A, which is symptomatic of an agent's goal of profit maximization. Ideally, the resource N stays on a stable positive level (see the baseline optimal agent type), whereas the assets A would grow. It is difficult for agents to harvest the resource in a stable and profitable manner (only 7% of the action space A are profitable and sustainable [von der Osten et al., 2017]), even more so with increasing population, as the impact of an individual action on the overall outcome decreases.

5 Results and Discussion

5.1 MToM

The first experiment demonstrates the feasibility and performance of MToM in a stochastic game. Figure 3 shows the development of the resource N and the average agent assets ¯ A in a time series over 5000 rounds. Agents with complete knowledge of the pay-offs (CI) satisfy both performance measures. Note results for differing levels of MToM(CI) are exactly the same, hence they are not distinguishable on the graph. When presented with uncertainty, their pay-offs decrease slightly, and a difference in the results for alternative orders of ToM becomes visible: MToM0 performs better than MToM1. MToM0 surpasses both models with complete information (possibly due to overestimating adversary behaviour).

5.2 MToMwith Segmentation

The second experiments confirms the appropriateness of segmentation as a means of scaling the MToM model for increasing numbers of agents. Figure 4 shows a population of 10 agents playing the CPRG using segmentation with different granularity. Results of these experiments unveil several insights: Agents with perfect information generally perform better than agents without. Furthermore, even with complete information, only the MToM1 agents manage to increase their assets, even though all agent types can maintain the resource. This is contrary to the results of the first experiment, where no differences between the MT oM0 and MT oM1 levels were apparent for agents with complete information.

More interesting, however, is the development with increasing C. For MToM1 with complete information, more categories are beneficial, whereas MToM0 and MToM1 are better off with treating the entire population as one opponent.

Without complete information, MToM0 performed better thanMToM1, indicating that the gains from higher-order ToM depends on how much information is available. Moreover, the results illustrate that either one category, or an increasing granularity of categories promises better results. Note that the drop in assets for two categories is related to the threshold of the categories lying between the observed behaviour of agents, making their assessment inaccurate.

Figure 5 show an increasing population of agents using a fixed segmentation (C = 2) under complete information. This demonstrates the ability for segmentation to scale to larger populations. While the agents are able to maintain the resource, their profitability decreases initially. With larger population sizes, first-order MToM agents are able to make profit. This behaviour is attributed to resource dynamics.

5.3 MToM in Non-Homogeneous Populations

In the final set of experiments, the performance of agents is tested against unknown adversaries. Figure 6 presents the results of simulations with 10 agents, a certain fraction h of which are random (RND) agents. The results indicate that in a non-homogeneous scenario, complete information leads to pronounced differences. As expected, populations perform worse when RND agents are present, however, the effect is more distinct when facing uncertainty in pay-offs. Nonetheless, MToM0 and MToM1 agents scale linearly with the number of unknown opponents. The difference between them becomes less distinct when the population is more wellmixed, otherwise MToM0 performs better. This result is consistent with the previous experiment. It should be noted that RND agents perform badly when compared to the other models (see Figure 3). This means that having even a small fraction of RND agents in the game makes the profitability metric almost impossible to achieve.

Figure 7 provides important insights into the segmentation process. The plot shows the distribution of agents in categories after every assessment. As RND agents select actions uniformly, they would usually fall in the middle of the action space. MToM agents tend to take restrained actions. While the groups are mixed in the beginning, agents are more distinctly segmented into RND (mostly categories 2/3) and MToM (mostly category 1) opponents, demonstrating the integrated approach of opponent modelling and strategy sophistication works well with MToM.

6 Conclusion

This paper has examined an interesting application of ToM in groups using a stochastic game as a case study. The results demonstrate that MToM is a useful approach to use when modelling multiple opponents. MToM performs robustly under uncertainty and it scales with increasing numbers of agents provided it is combined with segmentation into groups based on stereotyping. When agents have complete information about game pay-offs, MT oM1 outperforms MToM0. In contrast, when there is uncertainty in game pay-offs lower MToM0 performs better. This suggests that higher-order ToM only gains an advantage over lower-order ToM, or other simpler strategies, if enough information is available. A similar distinction in model performance was evident when segmentation granularity was considered. As the number of categories increases, ToM under uncertainty performs worse, whereas ToM with complete information performs better in terms of the stochastic game metrics.

Two research directions will be explored in future work. Firstly, we will explore alternative segmentation mechanisms. Secondly, we aim to apply MToM applications such as security games, trading, or other stochastic and economic games.