The Role of Network Topology and Opponent Information in Shaping Cooperation in Multi-Agent Reinforcement Learning Systems
Authors: Seongho Son, Stephen Hailes, Mirco Musolesi
Organizations: Department of Computer Science, University College London · UCL Centre for Artificial Intelligence, University College London · Department of Computer Science and Engineering, University of Bologna
Several works have investigated the influence of graph topology on cooperation among artificial agents, while the majority of the literature has focused on modelling agents' adaptation through strategy imitation, which relies solely on the cumulative payoffs of others. This paper investigates scenarios in which each agent learns to play the two-player Iterated Prisoner's Dilemma (IPD) using deep reinforcement learning. Each agent is represented as a node in a graph, where its neighbours constitute the pool of opponents with whom it can interact. During each IPD episode, agents are provided with different types of information about their opponent, consisting of action history and opponent identity. Experimental results across different graph topologies show that the number of neighbours per node and the average path length are the main factors affecting the emergence of cooperation. We also show that, while partner selection fosters mutual cooperation by limiting the diversity of the opponent pool, providing agents with the identity of their opponent hinders the proliferation of cooperative strategies.
Figures & tables
PD
C
D
C
(R, R)
(S, T)
D
(T, S)
(P, P)
Table 1: (a) General format of payoff matrix used for an episode of Prisoner’s Dilemma (left). (b) Payoff matrix used in each interaction of Iterated Prisoner’s Dilemma (right).
Figure 1: Visual summary of IPD on graphs, from the perspective of i th agent. For each interaction round, each agent selects an opponent among its neighbours in the graph with uniform probability. Both experiences of playing with opponents that agent i selected or the agent being selected by one of its neighbours are used for training the dilemma-playing policy πi .
Figure 2: Visual summary of IPD with partner selection, from the perspective of i th agent. For each interaction round, each agent selects an opponent among the other N−1 agents using partner selection module ηsel,πi . The partner selection module is trained with only the experience of agent i selecting an opponent, as the action of partner selection aseli is the index of the selected opponent.
Figure 3: Experimental results per graph type with parameters for graph generation (ER, WS and BA from the left, respectively).
Figure 4: Experimental results per graph type with average path length per graph (ER, WS and BA from the left, respectively).
Figure 5: Relation between graph generation parameters and average path length (ER, WS and BA from the left, respectively).
Figure 6: Experimental results of partner selection experiment. Dots represent the average proportion of mutual cooperation in the last 100 interaction rounds of 20 runs, while vertical intervals represent 95% confidence intervals of each experiment setting. Experiments conducted without having identity information in the states of dilemma-playing agents are coloured in green, while experiments which included binary encoding of the opponent’s identity index are coloured in orange. Except for the experiment with identity information and action history length l=1 , which showed significantly lower level of mutual cooperation, all the other experiments’ confidence intervals overlap.
Figure 7: Learning dynamics of partner selection experiment without opponent identity ( l=1,5,10 from the left, respectively).
Figure 8: Learning dynamics of partner selection experiment with opponent identity ( l=1,5,10 from the left, respectively).
Q(sC,C)>Q(sC,D)
Q(sC,C)≤Q(sC,D)
Q(sD,C)>Q(sD,D)
cooperator
reverser
Q(sD,C)≤Q(sD,D)
retaliator
defector
Table 2: Possible strategies in experiments where l=1 , opponent identity excluded from state information.
Figure 9: Interaction patterns in the IPD across different graph structures (ER, WS and BA from the top, respectively). Each graph shows results of one of the runs in each experiment setting. Each node represents an agent in the population. Colours of the nodes represent types of interactions the agent has experienced the most in the last 100 interaction rounds. Colours of the edges represent types of interactions that have occurred the most between the two nodes each edge is connecting.
Figure 10: Interaction patterns in the IPD with partner selection without identity ( l=1,5,10 from the top, respectively). Each graph shows results of one of the 20 runs in each experiment setting. Edges have directions as each agent can select their interaction partners. Agents that mainly cooperate playing IPD (blue, purple nodes) are being selected from other agents, while agents that mainly exploit others (green nodes) are not being selected.
Figure 11: Dynamics of inequality (Gini coefficient) of partner selection between agents per 100 interaction rounds. Shaded areas show 95% confidence interval across 20 runs.
Figure 12: Dynamics of inequality (Gini coefficient) of proportion of different types of interactions. pmc (upper left), pue (upper right) and pmd (bottom left) denote the proportion of mutual cooperation, unilateral exploitation ( sucker defined in Section 2.1 ) and mutual defection in 100 interaction rounds respectively. Shaded areas show 95% confidence interval across 20 runs.
Figure 13: IPD interaction patterns with partner selection and binary-encoded identity ( l=1,5,10 from the top, respectively). Each graph shows results of one of the 20 runs in each experiment setting. When the length of the action history is 1, partner selections are highly concentrated. This concentration is alleviated as the history length gets longer, enabling more mutual cooperation to emerge in the population as experiment proceeds.
Cooperative multi-agent reinforcement learning (MARL) trains agents to coordinate toward shared goals under partial information and decentralized control.