Post 2 in in Modal SAT series. In this post, we show that SC Modal SAT is equivalent to Modal SAT.

For this, we need just need to prove the following theorem:

Theorem: If there exists a modal agent $M$ such that $C_i$ cooperates with $M$ for each $C_i\in C$ and such that $M$ defects against $D_i$ for each $D_i\in D$, then there exists an $M^{\prime }$ which satisfies the above properties and cooperates with itself.

Proof: Let $n$ be greater than the total number of boxes in agents in $C$ and $D$. Consider the agents $X_n$ and $X_{n+1}$ defined by $X_i\left(B\right)=C\leftrightarrow \neg {\square }^i\perp$.

We define $M^{\prime }$ by

1. $M^{\prime }\left(B\right)=C$ if $\neg {\square }^{n+1}\perp$ and $\square (\neg {\square }^n\perp \to B(CooperateBot)=C)$ and $\neg \square (\neg {\square }^{n-1}\perp \to B(CooperateBot)=C)$

2. $M^{\prime }\left(B\right)=D$ if $\neg {\square }^{n+2}\perp$ and $\square (\neg {\square }^{n+1}\perp \to B(CooperateBot)=C)$ and $\neg \square (\neg {\square }^n\perp \to B(CooperateBot)=C)$

3. $M^{\prime }\left(B\right)=C$ if $\neg {\square }^{n+3}\perp$ and $\square (\neg {\square }^{n+1}\perp \to B(X_n)=C)$ and $\square (\neg {\square }^{n+2}\perp \to B(X_{n+1})=D)$

4. $M^{\prime }\left(B\right)=M\left(B\right)$ otherwise

Rule 1 says that $M^{\prime }$ cooperates with $X_n$, rule 2 says that $M^{\prime }$ defects against $X_{n+1}$, and rule 3 says that $M^{\prime }$ cooperates with anyone who (provably assuming $\neg {\square }^{n+1}\perp$) cooperates with $X_n$ and (provably assuming $\neg {\square }^{n+2}\perp$)defects against $X_{n+1}$. Thus, $M^{\prime }$ cooperates with itself.

For any bot $B$ with fewer than $n$ boxes, the conditions of 1, 2, and 3 are all false. For 1 and 2, this is because the actions of such bots against CoopearteBot stabilize by the time you assume $\neg {\square }^{n-1}\perp$. For 3, this is because these bots cannot distinguish between $X_n$ and $X_{n+1}$.

Therefore $M^{\prime }$ behaves the same as $M$ on all inputs with fewer than $n$ boxes, so $M^{\prime }$ cooperates with every bot in $C$ and defects against every bot in $D$.

$\square$

Note that I was lazy here, and took way more longer to cooperate with myself than I had to. In principle, if there are only $k$ bots that I need to consider (including bots I need to consider because they are referenced by bots I care about), then regardless of how many boxes are in each bot, It should be possible to achieve self cooperation within $2{\log }_{2}k$ worlds of the Kripke frame. That is, ${\log }_{2}k$ worlds to identify a single bot that is distinguishable from all other bots, and another ${\log }_{2}k$ worlds to ensure that the actions of $M^{\prime }$ differ on that bot from all other bots, so that $M^{\prime }$ can identify itself without changing its behavior against any other bot.

EDIT: Actually, I think $\log k$ + a small constant should suffice, but it does not matter much.