size $N$ increases significantly since the number of reachable peers for each agent is usually much smaller than the number of agents in whole populations, i.e. $n = |\bar O_i| \ll |N|$.

After rewiring phase, each agent proceeds to interact with an agent randomly selected from its neighborhood. We consider the following three representative learning strategies in the literature as agents’ learning strategies.

-   $\emph{Fictitious play(FP)}$. FP is a well-known learning approach in literature. Agent $i$ keeps a frequency count of agent $j$’s decisions from a history of past moves and assumes that the opponent is playing a mixed strategy represented by this frequency distribution. Agent $i$ chooses the best-response action $m$ to that mixed strategy to maximize its expected payoff. Formally we have: $$m = \arg\max_{m \in A_j}p_i^j(m)u_m + \left(1 - p_i^j(m)\right)\alpha,$$ where $p_i^j(m)$ is agent $i$’s estimated distribution over agent $j$’s actions and $u_m$ is the payoff when both agent $i$ and $j$ choose action $m$, exactly the same in Eq.1.

-   $\emph{Joint Action Learner (JAL)}$ [@claus1998dynamics]. JAL is a classic Multiagent Reinforcement Learning algorithm under the assumptions that each agent can observe the actions of other agents. A JAL agent learns its Q-values for joint actions. Formally, 