maximizing its one-shot payoff after rewiring. The utility $U(\pi_i,\epsilon)$ of a policy $\pi_i$ can be defined recursively as follows,

$$U(\pi_i,\epsilon) =
    \left\{
                 \begin{array}{lr}
                 \int_{-\infty}^\infty U(\pi_i, \epsilon') \;\text{d}F_{x_{\pi_i(\epsilon)}}^i(x)
             & \text{if} \ \pi_i(\epsilon) \in \bar O_i, \\
                 -c_i^{\pi_i(\epsilon)} \\
             y_i & \text{otherwise stop.}
                 \end{array}
    \right.$$

where $\epsilon' = <\bar O_i \backslash \{\pi_i(\epsilon)\},y_i'\}>$ denotes the new rewiring state after agent $\pi_i(\epsilon)$ is rewired, where $y_i'$ is the new expected baseline payoff as the neighborhood $O_i$ is altered.

Our final goal is to find an optimal policy $\pi_i^* = arg\max_{\pi_i} U(\pi_i,\epsilon)$ among all feasible policies, which considers the following: either not rewire and obtain baseline $y_i$, or rewire an unknown partner $j \in \bar O_i$ by sampling $x$ from $x_i^j$ at cost $c_i^j$, while taking the following into account:

-   $x \le y_i$: this indicates the expected payoff interacting with agent $j$ is not better than its current baseline and $x$ should be the new baseline value after rewiring. Thus the expected utility under state $<\bar O_i, y_i>$ becomes $-c_i^j + U(\pi_i^*,<\bar O_i \backslash \{j\},x>)$;

-   $x >y_i$: the expected payoff interacting with agent $j$ is higher than our baseline value. In this case, the expected utility under state $<\bar O_i, y_i>$ becomes $-c_i^j 