of interacting with agent $j$ by taking the aforementioned uncertainties into consideration.

Before making a rewiring decision, each agent first needs to evaluate the benefits of interacting with each neighbor. One natural way is to use the optimistic assumption, i.e., computing the expected payoff of selecting different actions based on the estimated policy of a neighbor and picking the action with the highest expected value. In other words, agent $i$ evaluates the expected payoff $v_i^j$ of interacting with agent $j \in O_i$ by using the highest expected payoff that can be received among all possible actions $A_i$. Formally we have: $$v_i^j = \max_{m \in A_j}p_i^j(m)u_m + \left(1 - p_i^j(m)\right)\alpha,$$ where $u_m$ represents the explicit payoff when both players choose action $m$ by sampling $x_m$ from $F_m(x)$ during historic interactions, and $\alpha$ is for the mis-coordination payoff. $p_i^j(m)$ denotes agent $i$’s estimated probability of agent $j$ choosing action $m$. The value of $p_i^j(m)$ can be easily obtained as the empirical frequency distribution of agent $j$’s actions based on historical interactions and other advanced techniques such as weighting more on recent experiences may also be considered. Provided there is no need to rewire, we use agent $i$’s worst-case expected payoff among all 