Emergent behaviours in multi-agent systems with Evolutionary Game Theory

Abstract

The mechanisms of emergence and evolution of collective behaviours in dynamical Multi-Agent Systems (MAS) of multiple interacting agents, with diverse behavioral strategies in co-presence, have been undergoing mathematical study via Evolutionary Game Theory (EGT). Their systematic study also resorts to agent-based modelling and simulation (ABM) techniques, thus enabling the study of aforesaid mechanisms under a variety of conditions, parameters, and alternative virtual games. This paper summarises some main research directions and challenges tackled in our group, using methods from EGT and ABM. These range from the introduction of cognitive and emotional mechanisms into agents’ implementation in an evolving MAS, to the cost-efficient interference for promoting prosocial behaviours in complex networks, to the regulation and governance of AI safety development ecology, and to the equilibrium analysis of random evolutionary multi-player games. This brief aims to sensitize the reader to EGT based issues, results and prospects, which are accruing in importance for the modeling of minds with machines and the engineering of prosocial behaviours in dynamical MAS, with impact on our understanding of the emergence and stability of collective behaviours. In all cases, important open problems in MAS research as viewed or prioritised by the group are described.

Keywords

Evolutionary Game Theory emergent behaviours collective behaviours cooperation AI regulation agent-based modelling

1. Introduction

The problem of promoting the emergence and stability of diverse collective behaviours in populations of abstract individuals have been undergoing mathematical study via Evolutionary Game Theory (EGT) [3,51,60,76]. They have attracted sustained attention from fields as diverse as Multi-Agent Systems (MAS), Economics, Biology and Social Sciences.

Since its inception, EGT has become a powerful mathematical framework for the modelling and analysis of complex, dynamical MAS [36,54,65], in biological, social contexts as well as computerised systems [28,67,68,75,82]. It has been used widely and successfully to study numerous important and challenging questions faced by many disciplines and societies, such as: what are the mechanisms underlying the evolution of cooperative behaviour at various levels of organisation (from genes to human society) [61,67]? How to mitigate existential risks such as those posed by climate change [74,75] or advanced Artificial Intelligence (AI) technologies [45]? What are the roles of cognition and emotions in behavioural evolution [28,69]?

In EGT, the payoff agents obtained from interacting with other agents in the system, is interpreted as individual fitness. An important property in EGT is the so called frequency dependent selection, where the fitness of an individual does not only depend on its strategy, but also on the composition of the population in relation with (multiple) other strategies, naturally leading to a dynamical approach. EGT was originated back in 1973 with John Maynard Smith and George R. Price’s formalisation of animal contests, extending classical game theory [83] to provide the mathematical criteria that can be used to predict the evolutionary outcomes of interaction among competing strategies [57].

Diverse mathematical approaches and methods for analysing EGT models have been developed over the years. These include continuous approaches such as replicator equations which assume large population limits, unusually requiring analysis of systems of differential equations [54]. In finite size systems, stochastic approaches are required and usually approximations methods are needed (e.g. using mean-field analysis). Here computer simulations and methods from statistical physics, such as Monte Carlo simulations, are very useful to analyse highly complex systems where analytical results are hard to achieve, for example, when populations are distributed on complex networks [67].

Resorting to these complementary approaches, we have been tackling a number of fundamental research challenges in MAS and collective behaviour studies. First, we initiated the introduction in an evolving MAS, of cognitive and emotional capabilities, as inspired on techniques and theories of AI, namely those pertaining to intention recognition, commitment, trust and guilt (Section 2). Second, we initiated baseline EGT models that capture the complex ecology of choices associated with a competition for domain supremacy using AI technology, allowing ones to formally explore various regulatory proposals of AI development (Section 3). Third, we introduced cost-efficient optimisation problems in dynamical MAS on complex networks in order to capture various stochastic aspects of MAS interactions and evolution over time (Section 4). Finally, we described our extensive analysis of statistical properties of the number of (stable) equilibria in a random evolutionary multi-player game, providing insights on generic equilibrium properties of large, dynamical MAS (Section 5).

2. Cognitive and emotional mechanisms for promoting prosocial behaviours in dynamical MAS

In its simplest form, a cooperative act is metaphorically described as the act of paying a cost to convey a benefit to someone else. If two players simultaneously decide to cooperate or not, the best possible response will be to try to receive the benefit without paying the cost. In an evolutionary setting, we may also wonder why would natural selection equip selfish individuals with altruistic tendencies while it incites competition between individuals and thus apparently rewards only selfish behavior? Several mechanisms responsible for promoting cooperative behavior have been recently identified, ranging from kin and group ties, to different forms of reciprocity and networked populations (see surveys in [61,67,76]).

Moreover, more complex strategies based on the evaluation of interactions between third parties allow the emergence of kinds of cooperation that are immune to exploitation because then interactions are channelled to just those who cooperate. Questions of justice and trust, with their negative (punishment) and positive (help) incentives, are fundamental in games with large diversified groups of individuals gifted with intention recognition capabilities. In allowing them to choose amongst distinct behaviours based on suggestive information about the intentions of their interaction partners – these in turn influenced by the behaviour of the individual himself – individuals are also influenced by their tolerance to error or noise in the communication. One hopes that, to start with, understanding these capabilities can be transformed into mechanisms for spontaneous organization and control of swarms of autonomous robotic agents [6], these being envisaged as large populations of agents where cooperation can emerge, but not necessarily to solve a priory given goals, as in distributed MAS.

Intention recognition. The ability of recognizing (or reading) intentions of others has been observed and shown to play an important role in many cooperative interactions, both in humans and primates [58,80]. Intentions and their recognition play a central role in morality, as shown for example in studies on the doctrines of double and triple effect [53]. However, most studies on the evolution of cooperation, grounded on evolutionary dynamics and game theory, have neglected the important role played by a basic form of intention recognition in behavioral evolution. In our work [38–40,47], we have addressed explicitly this issue, characterizing the dynamics emerging from a population of intention recognizers.

Intention recognition was implemented using Bayesian Network probabilistic methods, taking into account the information of current signals of intent, as well as the mutual trust and tolerance accumulated from previous one-on-one play experience – including how an agent’s previous defections may influence another agent’s intent – but without resorting to information gathered regarding agents’ overall reputation in the population. A player’s present intent can be understood here as how he is going to behave in the next round, whether by cooperating or defecting. Intention recognition can also be learned from a corpus of prior interactions among game strategies, where each strategy can be envisaged and detected as players’ (possibly changing) intent to behave in a certain way [28]. In both cases, we experimented with populations with different proportions of diverse strategies in order to calculate, in particular, what is the minimum fraction of individuals capable of intention recognition for cooperation to emerge, invade, prevail, and persist.

It is noteworthy that intention recognition techniques have been studied actively in AI for several decades [1,10,33,73,79], with several applications such as for improving human-computer interactions, assisting living, moral reasoning, and team work [34,72]. In most of these applications the agents engage in repeated interactions with each other. Our results suggest that equipping the agents with an ability to recognize intentions of others can improve their cooperation and reduce misunderstanding that can result from noise and mistakes.

The notions of intentions used in our two models have been specialized for the concrete game-theoretical contexts in place. A more general definition, e.g. as described in Bratman’s seminal work [7], can accommodate for intention changes or even abandonment. For instance, a player can change his intention or strategy before the next interaction or round of game takes place. That aspect was not considered in our EGT models, as players can change their strategy only at the end of a generation [77]. We envisage a convenient extension to that direction since our intention recognition methods – performed through Bayesian Network inference techniques, as described in [35] – can cope with intention changes and abandonment.

Commitments. Agents make commitments towards others when they give up options in order to influence others. Most commitments depend on some incentive that is necessary to ensure that an action (or even an intention) is in the agent’s interest and thus will be carried out in the future [25,59]. Asking for prior commitments can just be used as a strategy to clarify the intentions of others, whilst at the same time manifesting our own [41,47]. All parties then clearly know to what they commit and can refuse such a commitment whenever the offer is made [36].

In our work [30,36,42,43], we investigate analytically and numerically whether costly commitment strategies, in which players propose, initiate and honor a deal, are viable strategies for the evolution of cooperative behavior. Resorting the EGT mathematical analysis and simulations, we have shown that when the cost of arranging a commitment is justified with respect to the benefit of cooperation, substantial levels of cooperation can be achieved, especially when one insists on sharing the arrangement cost [43]. On the one hand, such commitment proposers can get rid of fake committers by proposing a strong enough compensation cost. On the other hand, they can maintain a sufficient advantage over the commitment free-riders, because a commitment proposer will cooperate with players alike herself, while the latter defect among themselves. We have also compared the commitment strategy with the simple costly punishment strategy – an important one for the evolution of cooperation [23] – where no prior agreements are made. The results show that the first strategy leads to a higher level of cooperation than the latter one. Furthermore, we have shown that these observations regarding evolutionary viability of commitment-based strategies are also applicable to other collective behaviours including coordination [62,63] and AI safety [31].

It is noteworthy that there has been an extensive literature of AI and MAS research on commitment, e.g., [8,12,78,85], but the main concern therein is how to formalize different aspects of commitment and how a commitment mechanism can be implemented in multi-agent interactions to enhance these (e.g. for improved collaborative problem solving [85]), especially in the context of classical game theory. Our work would provide insights into the design of MAS that rely on commitments or punishment in order to promote collective behaviour among agents [52].

Trust in autonomous systems (hybrid MAS). The actions of intelligent agents, such as chatbots, recommender systems, and virtual assistants are typically not fully transparent to the user [5]. Consequently, users take the risk that such agents act in ways opposed to the users’ preferences or goals [56]. It is often argued that people use trust as a cognitive shortcut to reduce the complexity of such interactions.

In our recent work [46], we study this by using EGT modelling to examine the viability of trust-based strategies in the context of an iterated prisoner’s dilemma game [77]. We show that these strategies can reduce the opportunity cost of verifying whether the action of their co-player was actually cooperative, and out-compete strategies that are always conditional, such as Tit-for-Tat. We argue that the opportunity cost of checking the action of the co-player is likely to be greater when the interaction is between people and intelligent artificial agents, because of the reduced transparency of the agent.

In our work, trust-based strategies are reciprocal strategies that cooperate as long as the other player is observed to be cooperating. Unlike classic reciprocal strategies, once mutual cooperation has been observed for a threshold number of rounds they stop checking their co-player’s behaviour every round, and instead only check it with some probability. By doing so, they reduce the opportunity cost of verifying whether the action of their co-player was actually cooperative. We demonstrate that these trust-based strategies can out-compete strategies that are always conditional, such as Tit-for-Tat, when the opportunity cost is non-negligible.

We argue that this cost is likely to be greater when the interaction is between people and intelligent agents within a hybrid MAS, since the interaction becomes less transparent to the user (e.g. when it is done over the internet), and artificial agents have limited capacity to explain their actions compared to humans [71]. Consequently, we expect people to use trust-based strategies more frequently in interactions with intelligent agents. Our results provide new, important insights into the design of mechanisms for facilitating interactions between humans and intelligent agents, where trust is an essential factor.

Trust is a commonly observed mechanism in human interactions, and discussions on the role of trust are being extended to social interactions between humans and intelligent machines [2]. It is therefore important to understand how people behave when interacting with those machines; particularly, whether and when they might exhibit trust behaviour towards them? Answering this is crucial for designing mechanisms to facilitate human-intelligent machine interactions, e.g. in engineering pro-sociality in a hybrid society of humans and machines [65].

Guilt. Machine ethics involving the capacity for artificial intelligence to act morally is an open project for scientists and engineers [70]. One important concern is how to represent emotions that are thought to modulate human moral behaviour, such as guilt, in computational models. Upon introspection, guilt is present as a feeling of being worthy of blame for a moral offence. Burdened with guilt, an agent may then act to restore a blameless internal state in which this painful emotion is no longer present.

Inspired by psychological and evolutionary studies, we have constructed an EGT model representing guilt in order to study its role in promoting pro-social behaviour [69]. We modelled guilt in terms of two characteristics. First, guilt involves a record of transgressions which is formalised by the number of offences. Second, guilt involves a threshold over which the guilty agent must alleviate the associated emotional pain, in the case of our models, through apology [44], and also by involving self-punishment [69], as required by the guilty feelings, both of which affect the payoff for the guilty agent. With this work, we were able to show that cooperation does not emerge when agents alleviate guilt without considering their co-players’ attitudes about the alleviation of guilt too. In that case, guilt-prone agents are easily dominated by agents who do not express guilt or who are without motivation to alleviate their own guilt. When, on the other hand, the tendency to alleviate guilt is mutual, and the guilt-burdened agent alleviates guilt in interactions with co-players who also act to alleviate guilt when similarly burdened, then cooperation thrives.

From a MAS perspective, including mixed social-technological communities encompassing potentially autonomous artificial agents, and invoking the so-called “value alignment” problem [24], our models confirm that conflicts can be avoided when morally salient emotions, like guilt, help to guide participants toward acceptable behaviours. In this context, systems involving possible future artificial moral agents may be designed to include guilt, so as to align agent-level behaviour with human expectations, thereby resulting in overall social benefits through improved cooperation, as evinced by our prospective work on modelling guilt.

3. Governance of artificial intelligence development: A game-theoretical approach

Rapid technological advancements in Artificial Intelligence (AI), together with the growing deployment of AI in new application domains such as robotics, face recognition, self-driving cars, genetics, are generating an anxiety which makes companies, nations and regions think they should respond competitively [9,55]. AI appears for instance to have instigated a race among chip builders, simply because of the requirements it imposes on the technology. Governments are furthermore stimulating economic investments in AI research and development as they fear of missing out, resulting in a racing narrative that increases further the anxiety among stake-holders [9].

Races for supremacy in a domain through AI may however have detrimental consequences since participants to the race may well ignore ethical and safety checks in order to speed up the development and reach the market first. AI researchers and governance bodies, such as the EU, are urging to consider together both the normative and the social impact of major technological advancements concerned [16]. However, given the breadth and depth of AI and its advances, it is not an easy task to assess when and which AI technology in a concrete domain needs to be regulated. This issue was, among others, highlighted in the recent EU White Paper on AI [16] and the UK National AI strategy.

Several proposals for mechanisms on how to avoid, mediate, or regulate the development and deployment of AI [9,15,64]. Essentially, regulatory measures such as restrictions and incentives are proposed to limit harmful and risky practices in order to promote beneficial designs [4]. Examples include financially supporting the research into beneficial AI and making AI companies pay fines when found liable for the consequences of harmful AI.

Fig. 1.

Frequency of unsafe behaviour as a function of development speed (s) and the disaster risk ( $p_{r}$ ). Panel A, in absence of incentives [45], the parameter space can be split into three regions. In regions (I) and (III), safe and unsafe/innovation, respectively, are the preferred collective outcome also selected by natural selection, thus no regulation being required. Region (II) requires regulation as safe behaviour is preferred but not the one selected. Panel B, when unsafe behaviour is sanctioned unconditionally [37], while unsafe behaviour is reduced in region II, over-regulation occurs in region III, reducing beneficial innovation. Panel C, unsafe behaviour is sanctioned only in presence of a voluntary commitment [31], unsafe behaviour is significantly reduced in region II while avoiding over-regulation.

Although such regulatory measures may provide solutions for particular scenarios, one needs to ensure that they do not overshoot their targets, leading to a stifling of novel innovations, hindering investments into the development into novel directions as they may be perceived to be too risky [27,55,84]. Worries have been expressed by different organisations and academic societies that too strict policies may unnecessarily affect the benefits and societal advances that novel AI technologies may have to offer. Regulations affect moreover big and small tech companies differently: A highly regulated domain makes it more difficult for small new start-ups, introducing an inequality and dominance of the market by a few big players [55]. It has been emphasised that neither over-regulation nor a laissez-faire approach suffices when aiming to regulate AI technologies. In order to find a balanced answer, one clearly needs to have first an understanding of how a competitive development dynamic actually could work and how governance choices impact this dynamic, a task well-suited for dynamic systems or agent-based models.

In our recent work [15,31,37,45], we examine this problem using EGT modelling, see Fig. 1. We first developed a baseline model describing a development competition where technologists can choose a safe (SAFE) vs risk-taking (UNSAFE) course of development [45]. Namely, it considers that to reach domain supremacy through AI in a certain domain, a number of development steps or technological advancement rounds are required [45]. In each round the technologists (or players) need to choose between one of two strategic options: to follow safety precautions (the SAFE action) or ignore safety precautions (the UNSAFE action). Because it takes more time and more effort to comply with precautionary requirements, playing SAFE is not just costlier, but implies slower development speed too, compared to playing UNSAFE. Moreover, there is a probability that a disaster occurs if UNSAFE developments take place during this competition (see [45] for a full description).

We demonstrate that unconditional sanctioning will negatively influence social welfare in certain conditions of a short-term race towards domain supremacy through AI technology [37], leading to over-regulation of beneficial innovation (see Fig. 1B). Since data to estimate the risk of a technology is usually limited (especially at an early stage of its development or deployment), simple sanctioning of unsafe behaviour (or reward of safe behaviour) could not fully address the issue.

To solve this critical over-regulation dilemma in AI development, we propose an alternative approach, which is to allow technologists or race participants to voluntarily commit themselves to safe innovation procedures, signaling to others their intentions [47,59]. Specifically, this bottom-up, binding agreement (or commitment) is established for those who want to take a safe choice, with sanctioning applied to violators of such an agreement. It is shown that, by allowing race participants to freely pledge their intentions and enter (or not) in bilateral commitments to act safely and avoid risks, accepting thus to be sanctioned in case of misbehavior, high levels of the most beneficial behaviour, for the whole, are achieved in all regions of the parameter space, see Fig. 1C.

In [15], we explore how different interaction structures among race participants can alter collective choices and requirements for regulatory actions. We show when participants portray a strong diversity in terms of connections and peer-influence (as modelled through scale free networks), the conflicts that exist in homogeneous settings [45] are significantly reduced, thereby reducing the need for taking regulatory actions.

Overall, our results are directly relevant for the design of self-organized AI governance mechanisms and regulatory policies that aim to ensure an ethical and responsible AI technology development process (such as the one proposed in the EU White Paper).

It is noteworthy that all our above-mentioned works focused on the binary extremes of race participants’ behaviour, safe or unsafe development, in an effort to focus an already expansive problem into a manageable discussion. The addition of conditional, mixed, or random strategies could provide the basis for a novel piece of work. Also, as observed with conditionally safe players in the well-mixed scenario, we envisage that these additions would show little to no effect in the early regime, with the opposite being true for the late regime, at least in homogeneous network settings. Finally, it would be important to clarify the combined effects of incentive and/or commitment mechanisms within a complex network setting.

4. Cost-efficient interference for promoting collective behaviours in complex networks

As discussed, the problem of promoting the evolution of collective behaviour within populations of self-regarding individuals has been intensively investigated across diverse fields of behavioural, social and computational sciences [60,67]. In most studies, a desired collective behaviour such as cooperation, coordination, trust and fairness, are assumed to emerge from the combined actions of participating individuals within the populations, without taking into account the possibility of external interference and how it can be performed in a cost-efficient way. However, in many scenarios, such behaviours are advocated and promoted by an exogenous decision maker, who is not part of the system (e.g. the United Nation interferes in political systems for conflict resolution or the World Wildlife Fund organisation interferes in ecosystems to maintain biodiversity). Thus, a new set of heuristics capable of engineering a desired collective behaviour in a self-organised MAS is required [65].

In our work, we bridged this gap by employing EGT analysis and ABM simulations, to study cost-efficient interference strategies for enhancing cooperation, fairness and AI safety in the context of social games, for both well-mixed [19,48,49] and networked populations (including square lattice and scale free networks) [13,14,32].

In a well-mixed population, each player interacts with all others in the population while in a structured population the player interacts with its immediate neighbors. A player’s fitness is its averaged payoff over all its interactions, which is then used for strategy update (through social learning) [77]. Namely, a player A with fitness $f_{A}$ chooses to copy the strategy of a randomly selected player in the population (well-mixed) or randomly selected neighbor (structured) with a probability given by the Fermi function, ${(1 + e^{β (f_{A} - f_{B})})}^{- 1}$ , where β represents the intensity of selection [81]. When $β = 0$ corresponds to neutral drift while $β \to \infty$ leads to increasingly deterministic selection. Weak or even close to neutral selections (small β) are abundant in nature, while the strong selection regime has been reported as predominant in social settings. As an alternative to this stochastic update rule, one can also consider a deterministic update in which agents copy, if advantageous, the most successful player in their neighbourhood.

An interference strategy or scheme can be generally defined as a sequence of decisions about which players in the population to invest in (i.e. reward the player an amount, denoted by θ), in order to achieve the highest level of cooperation while minimising the total cost of investment. These decisions can be made by considering different aspects of the population such as its global statistics and/or its structural properties. In the context of a well-mixed population, an interference scheme solely depends on its composition (e.g., how many cooperators and defectors players there are at the time of decision making). In this case, we have derived analytical conditions for which a general interference scheme can guarantee a given level of desired behaviour while at the same time minimising the total cost of investment (e.g., for rewarding cooperative behaviours), and show that the results are highly sensitive to the intensity of selection by interference [19,48]. Moreover, we have studied a specific class of interference strategies that make investments whenever the number of players with a desired behaviour (e.g., cooperative or fair players) reaches a certain threshold, denoted by t ( $\forall t \in {1, \dots, N - 1}$ ), showing that there is a wide range of t that it outperforms standard institutional incentive strategies – which unconditionally interfere into the system regardless of its composition, corresponding to $t = N - 1$ [11].

With a structured population, individuals (even of the same strategy) might reside in different kinds of neighborhood (with different cooperativeness levels), and therein local information might be useful to enhance cost-efficiency and cooperation. To this end, we test several interference paradigms [13,14,32] that make investment decisions based on a player’s current level of desirable behaviour (e.g., the number of cooperators in the neighborhood), and compared their efficiency with the population-based strategies (as in the well-mixed case). Furthermore, in this context, we study the impact of social diversity, employed using heterogeneous networks of interaction (e.g. scale free networks). We show that social diversity indeed substantially influences the choice of investment approaches available to institutions. Investment is not trivial in these settings, contrary to the findings in well-mixed and lattice populations [14]. Counterintuitively, incentivising positive behaviour can lead to the exploitation of cooperators, harming pro-sociality in lieu of fostering it. We observe that highly clustered scale-free networks make it easy to select the most effective candidates for receiving endowments.

The interference mechanisms we have proposed thus far have advanced the literature on external interference, but our contribution in this regard remains incipient. Future works include analysis of more complex interference strategies such as those vary the cost of investment over time or combine different forms of incentives [11,29]. We might also resort to more complex optimisation algorithms and control theory techniques, to solve the bi-objective optimisation problem posed by cost-effective interference, therefore identifying solutions that are robust across a wider range of MAS interaction settings.

5. Equilibrium statistics in random evolutionary games

Random evolutionary games, in which the payoff entries are random variables, have been employed extensively to model multi-agent strategic interactions in which very limited information about them is available, or where the environment changes so rapidly and frequently that one cannot describe the payoffs of their inhabitants’ interactions [18,21,26,50]. Equilibrium points of such a dynamical system are the compositions of strategy frequencies where all the strategies have the same average accumulated payoff (or fitness). They thus predict potential co-existence of different strategic behaviours in a dynamical MAS.

In random games, due to the randomness of the payoff entries, it is essential to study statistical properties of equilibria. How to determine the distribution of internal equilibria in random evolutionary games is an intensely investigated subject with numerous practical ramifications in diverse fields including MAS, evolutionary biology, social sciences and economics, providing essential understanding of complexity in a dynamical system, such as its behavioural, cultural or biological diversity and the maintenance of polymorphism. Properties of equilibrium points, particularly the probability of observing the maximal number of equilibrium points, the attainability and stability of the patterns of evolutionarily stable strategies have been studied [26,50]. However, as these prior works used a direct approach that consists of solving a system of polynomial equations, the mathematical analysis was mostly restricted to evolutionary games with a small number of players, due to the impossibility of solving general polynomial equations of a high degree (according to Abel–Ruffini’s theorem).

In our work, we analyse random evolutionary games with an arbitrary number of players [17,18,21]. The key technique that we develop is to connect the number of equilibria in an evolutionary game to the number of real roots of a system of multi-variate random polynomials [22]. Assuming that we consider d-player n-strategy evolutionary games, then the system consists of $n - 1$ polynomial equations of degree $d - 1$ : $\begin{matrix} \sum_{\begin{array}{c} 0 ⩽ k_{1}, \dots, k_{n - 1} ⩽ d - 1, \\ \sum_{i = 1}^{n - 1} k_{i} ⩽ d - 1 \end{array}} β_{k_{1}, \dots, k_{n - 1}}^{i} (\begin{matrix} d - 1 \\ k_{1}, \dots, k_{n} \end{matrix}) \prod_{i = 1}^{n - 1} y_{i}^{k_{i}} = 0, \end{matrix}$ for $i = 1, \dots, n - 1$ . Here $β_{k_{1}, \dots, k_{n - 1}}^{i} : = α_{k_{1}, \dots, k_{n}}^{i} - α_{k_{1}, \dots, k_{n}}^{n}$ where $α_{k_{1}, \dots, k_{n}}^{i_{0}} : = α_{i_{1}, \dots, i_{d - 1}}^{i_{0}}$ is the payoff of the focal player and $k_{i}$ , $1 ⩽ i ⩽ n$ , with $\sum_{i = 1}^{n} k_{i} = d - 1$ , is the number of players using strategy i in ${i_{1}, \dots, i_{d - 1}}$ . In [18], we analyze the mean number $E (n, d)$ and the expected density $f (n, d)$ of internal equilibria in a general d-player n-strategy evolutionary game when the individuals’ payoffs are independent, normally distributed. We provide computationally implementable formulas of these quantities for the general case and characterize their asymptotic behaviour for the two-strategy games (i.e. $E (2, d)$ and $f (2, d)$ ), estimating their lower and upper bounds as d increases. For instance, under certain assumptions on the payoffs, we obtain

Asymptotic behaviour of $E (2, d)$ : $\begin{matrix} \sqrt{d - 1} ≲ E (2, d) ≲ \sqrt{d - 1} ln (d - 1) . \end{matrix}$ As a consequence, ${lim}_{d \to \infty} \frac{ln E (2, d)}{ln (d - 1)} = \frac{1}{2}$ .

Explicit formula of $E (n, 2)$ : $E (n, 2) = \frac{1}{2^{n - 1}}$ .

For a general d-player n-strategy game, as supported by extensive numerical results, we describe a conjecture regarding the asymptotic behaviours of

E (n, d)

and

f (n, d)

. We also show that the probability of seeing the maximal possible number of equilibria tends to zero when d or n respectively goes to infinity and that the expected number of stable equilibria is bounded within a certain interval.

In [20], we generalize our analysis for random evolutionary games where the payoff matrix entries are correlated random variables. In social and biological contexts, correlations may arise in various scenarios particularly when there are environmental randomness and interaction uncertainty such as when individual contributions are correlated to the surrounding contexts (e.g. due to limited resource). We establish a closed formula for the mean numbers of internal (stable) equilibria and characterize the asymptotic behaviour of this important quantity for large group sizes and study the effect of the correlation. The results show that decreasing the correlation among payoffs (namely, of a strategist for different group compositions) leads to larger mean numbers of (stable) equilibrium points, suggesting that the system or population behavioral diversity can be promoted by increasing independence of the payoff entries.

As a further development, in [21] we derive a closed formula for the distribution of internal equilibria, for both normal and uniform distributions of the game payoff entries. We also provide several universal upper and lower bound estimates, which are independent of the underlying payoff distribution, for the probability of obtaining a certain number of internal equilibria. The distribution of equilibria provides more elaborate information about the level of complexity or the number of different states of biodiversity that will occur in a dynamical system, compared to what obtained with the expected number of internal equilibria.

In short, by connecting EGT to random polynomial theory, we have achieved new results on the expected number and distribution of internal equilibria in multi-player multi-strategy games. Our studies provide new insights into the overall complexity of dynamical MAS, as the numbers of players and strategies in a MAS interaction increase. As the theory of random polynomials is rich, we expect that our novel approach can be extended to obtain results for other more complex models in population and learning dynamics such as the replicator-mutator equation and evolutionary games with environmental feedback.

6. Concluding remarks

Since its inception, research in EGT has been both exciting and challenging, as well as highly rewarding and inspiring. Analysing large-scale dynamical MAS of multiple interacting agents, with diverse strategic behaviours in co-presence, is highly complex and requires innovative combinations of diverse mathematical methods and simulation techniques [67]. On the other hand, EGT research has proven extremely powerful and found its applications in so many fields, leading to important findings often being reported in prestigious venues.

Despite the many years of active research, there are still a number of important open problems in EGT research. The problem of explaining the mechanisms of collective behaviour such as cooperation and altruism, is still far from settled [66]. Also, extending and generalising the existing set of mathematical techniques and modelling tools to capture and understand realistic and ever more complex systems, is crucial. For example, modern societies become increasingly more convoluted with the advancement of technologies, changing the way humans live and interact with others. How EGT can be applied to model this hybrid society and understand its dynamics is very challenging [65]. But solving it can prove very rewarding as it can provide insights to design appropriate mechanisms to ensure the greatest benefit for our societies, or at least to avoid existential risks that we might otherwise have to face.

7. Acknowledgement

I would like to thank my group members (both current and former), Theodor Cimpeanu, Marcus Krellner, Cedric Perret, Bianca Ogbo, Zainab Alalawi, and Aiman Elgarig, and my collaborators, Luis Moniz Pereira, Tom Lenaerts, Francisco C. Santos, Hong Duong, Long Tran-Thanh, Luis A. Martinez-Vaquero, Alessandro Di Stefano, Raymond Chiong, and Simon Powers, who have made all the works reported here possible. T.A.H. is supported by Future of Life Institute AI safety grant (RFP2-154) and Leverhulme Research Fellowship (RF-2020-603/9).

References

S.V.

Albrecht and

Stone, Autonomous agents modelling other agents: A comprehensive survey and open problems, Artificial Intelligence258 (2018), 66–95. doi:10.1016/j.artint.2018.01.002.

Andras,

Esterle,

Guckert,

T.A.

Han,

P.R.

Lewis,

Milanovic,

Payne,

Perret,

Pitt,

S.T.

Powers,

Urquhart and

Wells, Trusting intelligent machines: Deepening trust within socio-technical systems, IEEE Technology and Society Magazine37(4) (2018), 76–83. doi:10.1109/MTS.2018.2876107.

Axelrod, The Evolution of Cooperation, Basic Books, New York, 1984.

S.D.

Baum, On the promotion of safe and socially beneficial artificial intelligence, AI & Society32(4) (2017), 543–551. doi:10.1007/s00146-016-0677-0.

Beldad,

Hegner and

Hoppen, The effect of virtual sales agent (VSA) gender – product gender congruence on product advice credibility, trust in VSA and online vendor, and purchase intention, Computers in Human Behavior60 (2016), 62–72. doi:10.1016/j.chb.2016.02.046.

Bonabeau,

Dorigo and

Theraulaz, Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, USA, 1999.

M.E.

Bratman, Intention, Plans, and Practical Reason, The David Hume Series, CSLI, 1987.

Castelfranchi and

Falcone, Trust Theory: A Socio-Cognitive and Computational Model, Wiley Series in Agent Technology, Wiley, 2010. ISBN 0470028750.

Cave and

ÓhÉigeartaigh, An AI race for strategic advantage: Rhetoric and risks, in: AAAI/ACM Conference on Artificial Intelligence, Ethics and Society, 2018, pp. 36–40.

10.

Charniak and

R.P.

Goldman, A Bayesian model of plan recognition, Artificial Intelligence64(1) (1993), 53–79. doi:10.1016/0004-3702(93)90060-O.

11.

Chen,

Sasaki,

Å.

Brännström and

Dieckmann, First carrot, then stick: How the adaptive hybridization of incentives promotes cooperation, Journal of The Royal Society Interface12(102) (2015), 20140935. doi:10.1098/rsif.2014.0935.

12.

A.K.

Chopra and

M.P.

Singh, Multiagent commitment alignment, in: AAMAS’2009, 2009, pp. 937–944.

13.

Cimpeanu,

T.A.

Han and

F.C.

Santos, Exogenous rewards for promoting cooperation in scale-free networks, in: ALIFE 2019, MIT Press, 2019, pp. 316–323. doi:10.1162/isal_a_00181.

14.

Cimpeanu,

Perret and

T.A.

Han, Cost-efficient interventions for promoting fairness in the ultimatum game, Knowledge-Based Systems233 (2021), 107545. doi:10.1016/j.knosys.2021.107545.

15.

Cimpeanu,

F.C.

Santos,

L.M.

Pereira,

Lenaerts and

T.A.

Han, Artificial intelligence development races in heterogeneous settings, Scientific Reports12(1) (2022), 1–12. doi:10.1038/s41598-021-99269-x.

16.

Commission, White paper on Artificial Intelligence – An European approach to excellence and trust, Technical Report, European Commission, 2020, Accessed May 26, 2020 https://ec.europa.eu/info/sites/info/files/commission-white-paper-artificial-intelligence-feb2020_en.pdf.

17.

M.H.

Duong

et al., Statistics of the number of equilibria in random social dilemma evolutionary games with mutation, The European Physical Journal B94(8) (2021), 1–13. doi:10.1140/epjb/s10051-021-00181-0.

18.

M.H.

Duong and

T.A.

Han, Analysis of the expected density of internal equilibria in random evolutionary multi-player multi-strategy games, Journal of Mathematical Biology73(6) (2016), 1727–1760. doi:10.1007/s00285-016-1010-8.

19.

M.H.

Duong and

T.A.

Han, Cost efficiency of institutional incentives for promoting cooperation in finite populations, Proceedings of the Royal Society A477(2254) (2021), 20210568. doi:10.1098/rspa.2021.0568.

20.

M.H.

Duong,

H.M.

Tran and

T.A.

Han, On the expected number of internal equilibria in random evolutionary games with correlated payoff matrix, Dynamic Games and Applications (2018). doi:10.1007/s13235-018-0276-4.

21.

M.H.

Duong,

H.M.

Tran and

T.A.

Han, On the distribution of the number of internal equilibria in random evolutionary games, Journal of Mathematical Biology78(1) (2019), 331–371. doi:10.1007/s00285-018-1276-0.

22.

Edelman and

Kostlan, How many zeros of a random polynomial are real?, Bull. Amer. Math. Soc. (N. S.)32(1) (1995), 1–37. doi:10.1090/S0273-0979-1995-00571-9.

23.

Fehr and

Gachter, Altruistic punishment in humans, Nature415 (2002), 137–140. doi:10.1038/415137a.

24.

Gabriel, Artificial intelligence, values, and alignment, Minds and machines30(3) (2020), 411–437. doi:10.1007/s11023-020-09539-2.

25.

Gintis, Game Theory Evolving, Princeton University Press, Princeton, 2000.

26.

C.S.

Gokhale and

Traulsen, Evolutionary games in the multiverse, Proc. Natl. Acad. Sci. USA107(12) (2010), 5500–5504. doi:10.1073/pnas.0912214107.

27.

G.K.

Hadfield, Rules for a Flat World: Why Humans Invented Law and How to Reinvent It for a Complex Global Economy, Oxford University Press, 2017.

28.

T.A.

Han, Intention Recognition, Commitments and Their Roles in the Evolution of Cooperation: From Artificial Intelligence Techniques to Evolutionary Game Theory Models, Springer, 2013. ISBN 978-3-642-37511-8.

29.

T.A.

Han, Emergence of social punishment and cooperation through prior commitments, in: AAAI, 2016, pp. 2494–2500.

30.

T.A.

Han, Institutional incentives for the evolution of committed cooperation: Ensuring participation is as important as enhancing compliance, Journal of The Royal Society Interface19(188) (2022), 20220036. doi:10.1098/rsif.2022.0036.

31.

T.A.

Han,

Lenaerts,

F.C.

Santos and

L.M.

Pereira, Voluntary safety commitments provide an escape from over-regulation in AI development, Technology in Society68 (2022), 101843. doi:10.1016/j.techsoc.2021.101843.

32.

T.A.

Han,

Lynch,

Tran-Thanh and

F.C.

Santos, Fostering cooperation in structured populations through local and global interference strategies, in: IJCAI-ECAI, AAAI Press, 2018, pp. 289–295.

33.

T.A.

Han and

L.M.

Pereira, State-of-the-art of intention recognition and its use in decision making – a research summary, AI Communication Journal26(2) (2013), 237–246. doi:10.3233/AIC-130559.

34.

T.A.

Han and

L.M.

Pereira, Intention-based decision making and its applications, in: Human Behavior Recognition Technologies: Intelligent Applications for Monitoring and Security,

Guesgen and

Marsland, eds, IGI Global, 2013, pp. 174–211, Chapter 9. doi:10.4018/978-1-4666-3682-8.ch009.

35.

T.A.

Han and

L.M.

Pereira, Context-dependent incremental decision making scrutinizing the intentions of others via Bayesian network model construction, Intelligent Decision Technologies7(4) (2013), 293–317. doi:10.3233/IDT-130170.

36.

T.A.

Han,

L.M.

Pereira and

Lenaerts, Evolution of commitment and level of participation in public goods games, Autonomous Agents and Multi-Agent Systems31(3) (2017), 561–583. doi:10.1007/s10458-016-9338-4.

37.

T.A.

Han,

L.M.

Pereira,

Lenaerts and

F.C.

Santos, Mediating artificial intelligence developments through negative and positive incentives, PLOS ONE16(1) (2021), e0244592. doi:10.1371/journal.pone.0244592.

38.

T.A.

Han,

L.M.

Pereira and

F.C.

Santos, The role of intention recognition in the evolution of cooperative behavior, in: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI’2011),

Walsh, ed., AAAI, 2011, pp. 1684–1689.

39.

T.A.

Han,

L.M.

Pereira and

F.C.

Santos, Intention recognition promotes the emergence of cooperation, Adaptive Behavior19(3) (2011), 264–279.

40.

T.A.

Han,

L.M.

Pereira and

F.C.

Santos, Corpus-based intention recognition in cooperation dilemmas, Artificial Life journal18(4) (2012), 365–383. doi:10.1162/ARTL_a_00072.

41.

T.A.

Han,

L.M.

Pereira and

F.C.

Santos, Intention recognition, commitment and the evolution of cooperation, in: 2012 IEEE Congress on Evolutionary Computation, IEEE, 2012, pp. 1–8.

42.

T.A.

Han,

L.M.

Pereira and

F.C.

Santos, The emergence of commitments and cooperation, in: AAMAS’2012, 2012, pp. 559–566.

43.

T.A.

Han,

L.M.

Pereira,

F.C.

Santos and

Lenaerts, Good agreements make good friends, Scientific reports3 (2013), 2695. doi:10.1038/srep02695.

44.

T.A.

Han,

L.M.

Pereira,

F.C.

Santos and

Lenaerts, Why is it so hard to say sorry: The evolution of apology with commitments in the iterated prisoner’s dilemma, in: IJCAI’2013, AAAI Press, 2013, pp. 177–183.

45.

T.A.

Han,

L.M.

Pereira,

F.C.

Santos and

Lenaerts, To regulate or not: A social dynamics analysis of an idealised AI race, Journal of Artificial Intelligence Research69 (2020), 881–921.

46.

T.A.

Han,

Perret and

S.T.

Powers, When to (or not to) trust intelligent machines: Insights from an evolutionary game theory analysis of trust in repeated games, Cognitive Systems Research68 (2021), 111–124. doi:10.1016/j.cogsys.2021.02.003.

47.

T.A.

Han,

F.C.

Santos,

Lenaerts and

L.M.

Pereira, Synergy between intention recognition and commitments in cooperation dilemmas, Scientific reports5 (2015), 9312. doi:10.1038/srep09312.

48.

T.A.

Han and

Tran-Thanh, Cost-effective external interference for promoting the evolution of cooperation, Scientific reports8 (2018), 15997. doi:10.1038/s41598-018-34435-2.

49.

T.A.

Han,

Tran-Thanh and

N.R.

Jennings, The cost of interference in evolving multiagent systems, in: 14th International Conference on Autonomous Agents and Multiagent Systems, 2015, pp. 1719–1720.

50.

T.A.

Han,

Traulsen and

C.S.

Gokhale, On equilibrium properties of evolutionary multi-player games with random payoff matrices, Theoretical Population Biology81(4) (2012), 264–272. doi:10.1016/j.tpb.2012.02.004.

51.

Hardin, The tragedy of the commons, Science162 (1968), 1243–1248. doi:10.1126/science.162.3859.1243.

52.

M.R.

Hasan and

Raja, Emergence of cooperation using commitments and complex network dynamics, in: IEEE/WIC/ACM Intl Joint Conferences on Web Intelligence and Intelligent Agent Technologies, 2013, pp. 345–352.

53.

M.D.

Hauser, Moral Minds, How Nature Designed Our Universal Sense of Right and Wrong, Little Brown, 2007.

54.

Hofbauer and

Sigmund, Evolutionary Games and Population Dynamics, Cambridge University Press, Cambridge, 1998.

55.

K.-F.

Lee, AI Superpowers: China, Silicon Valley, and the New World Order, Houghton Mifflin Harcourt, 2018.

56.

Luhmann, Trust and Power, John Wiley & Sons, Chichester, 1979.

57.

Maynard Smith and

G.R.

Price, The logic of animal conflict, Nature246 (1973), 15–18. doi:10.1038/246015a0.

58.

A.N.

Meltzoff, Imitation and other minds: The “Like Me” hypothesi, in: Perspectives on Imitation: From Neuroscience to Social Science. Imitation, Human Development, and Culture, MIT Press, Cambridge, MA, 2005, pp. 55–77.

59.

R.M.

Nesse, Evolution and the Capacity for Commitment, Foundation Series on Trust, Russell Sage, 2001. ISBN 9780871546227.

60.

M.A.

Nowak, Evolutionary Dynamics, Harvard University Press, Cambridge, MA, 2006.

61.

M.A.

Nowak, Five rules for the evolution of cooperation, Science314 (2006), 1560–1563. doi:10.1126/science.1133755.

62.

N.B.

Ogbo,

Cimpeanu,

Di Stefano and

T.A.

Han, Shake on it: The role of commitments and the evolution of coordination in networks of technology firms, in: 2022 Artificial Life Conference, MIT Press, 2022.

63.

N.B.

Ogbo,

Elragig and

T.A.

Han, Evolution of coordination in pairwise and multi-player interactions via prior commitments, Adaptive Behavior (2021), 1059712321993166.

64.

O’Keefe,

Cihon,

Garfinkel,

Flynn,

Leung and

Dafoe, The windfall clause: Distributing the benefits of AI for the common good, in: Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, 2020, pp. 327–331. doi:10.1145/3375627.3375842.

65.

Paiva,

F.P.

Santos and

F.C.

Santos, Engineering pro-sociality with autonomous agents, in: Thirty-Second AAAI Conference on Artificial Intelligence, 2018.

66.

Pennisi, How did cooperative behavior evolve?, Science309(5731) (2005), 93–93. doi:10.1126/science.309.5731.93.

67.

Perc,

J.J.

Jordan,

D.G.

Rand,

Wang,

Boccaletti and

Szolnoki, Statistical physics of human cooperation, Physics Reports687 (2017), 1–51. doi:10.1016/j.physrep.2017.05.004.

68.

L.M.

Pereira,

T.A.

Han and

A.B.

Lopes, Employing AI to better understand our morals, Entropy24(1) (2021), 10. doi:10.3390/e24010010.

69.

L.M.

Pereira,

Lenaerts,

L.A.

Martinez-Vaquero and

T.A.

Han, Social manifestation of guilt leads to stable cooperation in multi-agent systems, in: AAMAS, 2017, pp. 1422–1430.

70.

L.M.

Pereira and

A.B.

Lopes, Machine Ethics: From Machine Morals to the Machinery of Morality, Springer, 2020.

71.

Pu and

Chen, Trust-inspiring explanation interfaces for recommender systems, Knowledge-Based Systems20(6) (2007), 542–556. doi:10.1016/j.knosys.2007.04.004.

72.

Roy,

Bouchard,

Bouzouane and

Giroux, A hybrid plan recognition model for Alzheimer’s patients: Interleaved-erroneous dilemma, in: Proceedings of IEEE/WIC/ACM International Conference on Intelligent Agent Technology, 2007, pp. 131–137.

73.

Sadri, Logic-based approaches to intention recognition, in: Handbook of Research on Ambient Intelligence: Trends and Perspectives, 2011, pp. 346–375.

74.

F.C.

Santos and

J.M.

Pacheco, Risk of collective failure provides an escape from the tragedy of the commons, Proc. Natl. Acad. Sci. USA (2011). doi:10.1073/pnas.1015648108.

75.

F.P.

Santos,

Mascarenhas,

F.C.

Santos,

Correia,

Gomes and

Paiva, Picky losers and carefree winners prevail in collective risk dilemmas with partner selection, Autonomous Agents and Multi-Agent Systems34(2) (2020), 1–29.

76.

Sigmund, The Calculus of Selfishness, Princeton Univ. Press, 2010.

77.

Sigmund,

De Silva,

Traulsen and

Hauert, Social learning promotes institutions for governing the commons, Nature466 (2010), 861–863. doi:10.1038/nature09203.

78.

M.P.

Singh, Norms as a basis for governing sociotechnical systems, ACM Transactions on Intelligent Systems and Technology (TIST)5(1) (2013), 21.

79.

Sukthankar,

Geib,

Bui,

Pynadath and

R.P.

Goldman, Plan, Activity, and Intent Recognition: Theory and Practice, Newnes, 2014.

80.

Tomasello, Origins of Human Communication, MIT Press, 2008.

81.

Traulsen,

M.A.

Nowak and

J.M.

Pacheco, Stochastic dynamics of invasion and fixation, Phys. Rev. E74 (2006), 11909. doi:10.1103/PhysRevE.74.011909.

82.

Tuyls and

Parsons, What evolutionary game theory tells us about multiagent learning, Artificial Intelligence171(7) (2007), 406–416. doi:10.1016/j.artint.2007.01.004.

83.

Von Neumann and

Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, 1944.

84.

Wooldridge, The Road to Conscious Machines: The Story of AI, Penguin UK, 2020.

85.

Wooldridge and

N.R.

Jennings, The cooperative problem-solving process, in: Journal of Logic and Computation, 1999, pp. 403–417.