agent $i$ to establish new connection with any unknown potential partner $j$ if rewiring leads to higher expected payoff. The difference between expected payoff $x_i^j$ and baseline value causes a incoming benefit which is promising to pay back the rewiring cost $c_i^j$ and to generate better payoffs in further interactions. Otherwise, agent $i$ should keep its current neighborhood unchanged. During each rewiring phase, each agent $i$ has to unlink a bad-performance neighbor first before rewiring. Note that there is no need for agent $i$ to consider those agents already disconnected during previous rewiring, since the expected payoff of interacting with discarded agent $j$ is obviously below the current interaction baseline, i.e. $v_i^j < v_i^*(O_i)$. Each agent’s situated environments are continuously changing as it breaks old connections and establishes new ones, which also influences the following interactions and rewiring decisions thereafter. Therefore, each agent is actually faced with a sequential rewiring decision-making problem. Formally, we propose modeling the above sequential rewiring problem for each agent $i$ as an Markov Decision Process (MDP), $M_i=<S_i,A_i,P_i,R_i>$ as follows:

-   A finite set of states $S_i$: each state $\epsilon$ of agent $i$ can be represented as a tuple $<\bar O_i, y_i>$, in which $\bar O_i$ 