describes the set of potential partners of agent $i$ and $y_i = v_i^*(O_i)$ is agent $i$’s current baseline value.

-   A finite set of actions $A_i$: agent $i$’s action set under $\epsilon$ is $A_i(\epsilon) = \{\bar O_i, \textbf{Null}\}$ which consists of actions of rewiring with an agent in $\bar O_i$ and the **Null** action for not rewiring.

-   A transition function $P_i$: $P_i(\epsilon,a,\epsilon')$ represents the probability of reaching state $\epsilon'$ after taking action $a$ under state $\epsilon$. The transition is probabilistic because the value of baseline $y_i$ may change stochastically. If agent $i$ rewires agent $j \in \bar O_i$, the new baseline $y_i' = v_i^*({O_i}')$ with the updated ${O_i}'$ is determined by new included neighbor $j$ and left neighbors after breaking the worst-performing connection.

-   A reward function $R_i$: $R_i(\epsilon,a)$ denotes the reward of executing action $a$ under state $\epsilon$, e.g., $R_i(\epsilon) = -c_i^j$ if agent $i$ chooses to rewire agent $j$ and $R_i(\epsilon) = 0$ if stops rewiring.

Under the above MDP formulation, our goal is to construct a rewiring strategy $\pi_i(\epsilon)$ specifying which new connection to establish, or to not rewire under each state $\epsilon$. We start with a short-sight version where each agent is only interested in 