Link to original article
Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: Some constructions for proof-based cooperation without Löb, published by James Payor on March 21, 2023 on LessWrong.
This post presents five closely-related ways to achieve proof-based cooperation without using Löb's theorem, and muses on legible cooperation in the real world.
I'm writing this as a follow-up to Andrew Critch's recent post, to share more of my perspective on the subject.
We're going to dive straight into the weeds. (I'm planning to also write a more accessible explainer post soon.)
The ideas
Idea #1: try to prove AB
I claim the following are sufficient for robust cooperation:
A↔□(AB)
B□A
A tries to prove that AB, and B tries to prove A. The reason this works is that B can prove that A□A, i.e. A only cooperates in ways legible to B. (Proof sketch: A↔□X□□X↔□A.)
The flaw in this approach is that we needed to know that A won't cooperate for illegible reasons. Otherwise we can't verify that B will cooperate whenever A does.
This indicates to me that "AB" isn't the right "counterfactual". It shouldn't matter if A could cooperate for illegible reasons, if A is actually cooperating for a legible one.
Idea #2: try to prove □AB
We can weaken the requirements with a simple change:
A□(□AB)
B□A
Note that this form is close to the lemma discussed in Critch's post.
In this case, the condition □AB is trivial. And when the condition activates, it also ensures that □A is true, which discharges our assumption and ensures B is true.
I still have the sense that the condition for cooperation should talk about itself activating, not A. Because we want it to activate when that is sufficient for cooperaion. But I do have to admit that □AB works for mostly the right reasons, comes with a simple proof, and is the cleanest two-agent construction I know.
Idea #3: factor out the loop-cutting gadget
We can factor the part that is trying to cut the loop out from A, like so:
A□X
B□A
X↔□(XB); or alternatively
X↔□(□XB)
This gives the loop-cutting logic a name, X. Now X can refer to itself, and roughly says "I'll legibly activate if I can verify this will cause B to be true". The key properties of X are that □X□B, and $\Box (\Box X \rightarrow \Box B)
Like with idea #2, we just need A to reveal a mechanism by which it can be compelled to cooperate.
Idea #4: everyone tries to prove □methem
What about three people trying to cooperate? We can try applying lots of idea #2:
A□(□AB∧C)
B□(□BA∧C)
C□(□CA∧B)
And, this works! Proof sketch:
Under the assumption of □C:
A□(□AB∧C)□(□AB)
B□(□BA∧C)□(□BA)
A and B form a size-2 group, which cooperates by inductive hypothesis
□CA∧B, since we proved A and B under the assumption
C and □C follow from (2)
A and B also follow, from (2) and (3)
The proof simplifies the group one person at a time, since each person is asking "what would happen if everyone else could tell I cooperate". This lets us prove the whole thing by induction. It's neat that it works, though it's not the easiest thing to see.
Idea #5: the group agrees to a shared mechanism or leader
What if we factor out the choosing logic in a larger group? Here's one way to do it:
A□X
B□X
C□X
X↔□(□XA∧B∧C)
This is the cleanest idea I know for handling the group case. The group members agree on some trusted leader or process X. They set things up so X activates legibly, verifies things in a way trusted by everyone, and only activates when it verifies this will cause cooperation.
We've now localized the choice-making in one place. X proves that □XA∧B∧C, X activates, and everyone cooperates.
Closing remarks on groups in the real world
Centralizing the choosing like in idea #5 make the logic simpler, but this sort of approach is prone to manipulation and other problems when the verification is not reliably done. This means I don't unambiguously prefer idea #5 to idea #4, in which everyone is doing their own le...
view more