the neighbors as its baseline utility. Formally we have: $$v_i^*(O_i) = \min_{j \in O_i}v_i^j.$$

For each unknown potential partner $j \in \bar O_i$ to interact with, agent $i$ is faced with two aspects of uncertainties: agent $j$’s behavior, and the payoff matrix $G_i^j$. For a previously unseen partner $j$’s behavior, it can be estimated using the observed expected behaviors from agent $i$’s existing neighborhood, while the payoff matrix $G_i^j$ has to be learned through repeated interactions after agent $i$ and $j$ are connected through rewiring. Therefore, agent $i$’s estimation of expected benefit $x_i^j$ from interacting with an unknown agent $j$ can be formalized as follows: $$x_i^j = \max_{m \in A_j}\bar p_i^j(m)x_m + \left(1 - \bar p_i^j(m)\right)\alpha,$$ where $x_i^j$ is a stochastic variable and $F_j^i(x)$ denotes the corresponding cumulative distribution function of $x_i^j$, and $\alpha$ is the payoff under mis-coordination. $\bar{p}_i^j(m)$ is agent $i$’s estimated probability of agent $j$ choosing action $m$ within its neighborhood. As no interaction has been made between agent $i$ and the unknown peer $j \in \bar O_i$ before, the distribution over agent $j$’s actions can not be observed a prior but estimated from the neighbors which once interact with agent $j$.

Intuitively, it is reasonable for 