Modal SAT: Self Cooperation

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^{'}$ 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} (B) = C \leftrightarrow \neg □^{i} ⊥$ .

We define $M^{'}$ by

$M^{'} (B) = C$ if $\neg □^{n + 1} ⊥$ and $□ (\neg □^{n} ⊥ \to B (C o o p e r a t e B o t) = C)$ and $\neg □ (\neg □^{n - 1} ⊥ \to B (C o o p e r a t e B o t) = C)$
$M^{'} (B) = D$ if $\neg □^{n + 2} ⊥$ and $□ (\neg □^{n + 1} ⊥ \to B (C o o p e r a t e B o t) = C)$ and $\neg □ (\neg □^{n} ⊥ \to B (C o o p e r a t e B o t) = C)$
$M^{'} (B) = C$ if $\neg □^{n + 3} ⊥$ and $□ (\neg □^{n + 1} ⊥ \to B (X_{n}) = C)$ and $□ (\neg □^{n + 2} ⊥ \to B (X_{n + 1}) = D)$
$M^{'} (B) = M (B)$ otherwise

Rule 1 says that $M^{'}$ cooperates with $X_{n}$ , rule 2 says that $M^{'}$ defects against $X_{n + 1}$ , and rule 3 says that $M^{'}$ cooperates with anyone who (provably assuming $\neg □^{n + 1} ⊥$ ) cooperates with $X_{n}$ and (provably assuming $\neg □^{n + 2} ⊥$ )defects against $X_{n + 1}$ . Thus, $M^{'}$ 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 □^{n - 1} ⊥$ . For 3, this is because these bots cannot distinguish between $X_{n}$ and $X_{n + 1}$ .

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

$□$

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^{'}$ differ on that bot from all other bots, so that $M^{'}$ 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.