Loebian cooperation in the tiling agents problem

The tiling agents problem is about formalizing how AIs can create successor AIs that are at least as smart. Here’s a toy model I came up with, which is similar to Benya’s old model but simpler. A computer program X is asked one of two questions:

  • Would you like some chocolate?

  • Here’s the source code of another program Y. Do you accept it as your successor?


Program X will be called a “winner” if is says “yes” to chocolate, every program Y accepted as successor by X also says “yes” to chocolate, every program Z accepted as successor by Y also says “yes” to chocolate, and so on. Otherwise X will be called a “loser”.

Let’s also assume that X has access to a provability oracle for Peano arithmetic (PA), to avoid dealing with logical uncertainty.

Here’s some simple winning programs:

  1. Always say “yes” to chocolate. Refuse to accept any successor.

  2. Always say “yes” to chocolate. Accept Y as successor iff Y has the same source code as X.

  3. Always say “yes” to chocolate. Accept Y as successor iff PA proves that Y is a winner.

Unfortunately (1) is too restrictive, (2) is too sensitive to implementation details, and (3) refuses to accept itself as successor for Goedelian reasons. How do we write a more general winning program?

Note that all programs above are analogous to strategies in the Prisoner’s Dilemma with visible source code: (1) is defection, (2) is quining cooperation, and (3) is simulating the opponent. But in the PD we also have Loebian cooperation! We could try applying it to our problem naively, like this:

  1. Always say “yes” to chocolate. Accept Y as successor iff PA proves that “X is a winner” implies “Y is a winner”.

At first glance that program looks nice. It accepts itself as successor, and also accepts all programs that PA proves to be winners. Unfortunately it also accepts all losers, because the sentence “X accepts Y” becomes provable for Loebian reasons.

But not all is lost! Here’s a better way to apply Loebian cooperation to our problem:

  1. Always say “yes” to chocolate. Accept Y as successor iff PA proves that Y can’t lose in fewer steps than X.

(More precisely, for all n such that X can’t lose in n steps, Y also can’t lose in n steps.)

Proof that X is a winner: X can’t lose in one step by construction. Therefore Y can’t lose in one step, as long as PA is sound. Therefore X can’t lose in two steps. Therefore Y can’t lose in two steps, as long as PA is sound. And so on, QED.

It’s easy to see that X accepts itself as successor, as well as modifications of itself, and also accepts all programs that PA proves to be winners. So it seems to be quite general. And the condition “Y can’t lose in fewer steps than X” also makes sense philosophically, because it means “X doesn’t move toward losing”.

Followup questions: I’m not sure if this is related to Benya’s parametric polymorphism, what’s the right analogy between self-modification and game theory, or how far it can be generalized.

What do you think?