Re-formalizing PD

The Pri­soner’s Dilemma has been dis­cussed to death here on OB/​LW, right? Well, here’s a cou­ple new twists to some­what… uh… ex­pand the dis­cus­sion.

Warn­ing: pro­gram­ming and math ahead.

Sce­nario 1

Imag­ine a PD tour­na­ment be­tween pro­grams that can read each other’s source code. In ev­ery match, player A re­ceives the source code of player B as an ar­gu­ment, and vice versa. Matches are one-shot, not iter­ated.

In this situ­a­tion it’s pos­si­ble to write a pro­gram that’s much bet­ter than “always defect”. Yes, in an or­di­nary pro­gram­ming lan­guage like C or Python, no fu­tur­is­tic su­per­in­tel­li­gent or­a­cles re­quired. No, Rice’s the­o­rem doesn’t cause any prob­lems.

Here’s an out­line of the pro­gram:

 //​ be­gin PREFIX
Strat­egy main(SourceCode other)
{
//​ get source code of this pro­gram from “be­gin PREFIX” to “end PREFIX”,
//​ us­ing or­di­nary quine (self-print­ing pro­gram) tech­niques
String PREFIX = ”...”

if (other.be­gin­sWith(PREFIX))
re­turn Strat­egy.COOPERATE;
else
re­turn any­thingElse(other);
}
//​ end PREFIX

//​ from this point you can write any­thing you wish
Strat­egy any­thingElse(SourceCode other)
{
re­turn Strat­egy.DEFECT;
}

Some fea­tures of this pro­gram:

  • It co­op­er­ates with it­self.

  • It co­op­er­ates with any other pro­gram that be­gins with PREFIX.

  • It’s im­pos­si­ble to cheat, be­cause op­po­nents that be­gin with PREFIX can’t not co­op­er­ate with this pro­gram.

  • Other au­thors now have an in­cen­tive to in­clude PREFIX in their pro­grams, mov­ing their origi­nal logic into the “any­thingElse” sub­rou­tine. This mod­ifi­ca­tion has no down­side.

So, in­tro­duc­ing such a pro­gram into the tour­na­ment should lead to a chain re­ac­tion un­til ev­ery­one co­op­er­ates. Un­less I’ve missed some­thing. What say ye?

Edit: the last point and the con­clu­sion were wrong. Thanks to War­ri­gal for point­ing this out.

    Sce­nario 2

    Now imag­ine an­other tour­na­ment where pro­grams can’t read each other’s source code, but are in­stead given ac­cess to a perfect simu­la­tor. So pro­grams now look like this:

    Strat­egy main(Ob­jec­tCode self, Ob­jec­tCode other, Si­mu­la­tor simu­la­tor) {...}

    and can call simu­la­tor.simu­late(Ob­jec­tCode a, Ob­jec­tCode b) ar­bi­trar­ily many times with any ar­gu­ments. To give play­ers a chance to avoid bot­tom­less re­cur­sion, we also make available a ran­dom num­ber gen­er­a­tor.

    Prob­lem: in this set­ting, is it pos­si­ble to write a pro­gram that’s bet­ter than “always defect”?

    The most gen­eral form of a rea­son­able pro­gram I can imag­ine at the mo­ment is a cen­tipede:

    1. Pro­gram­mer in­vents a num­ber N and a se­quence of real num­bers 0 < p1 < p2 < … < pN < 1.

    2. Pro­gram gen­er­ates a ran­dom num­ber 0 < r < 1.

    3. If r < p1, co­op­er­ate.

    4. Si­mu­late the op­po­nent’s re­ac­tion to you.

    5. If op­po­nent defects, defect.

    6. Other­wise if r < p2, co­op­er­ate.

    7. And so on un­til N.

    Ex­er­cise 1: when (for what N and pi) does this pro­gram co­op­er­ate against it­self? (To co­op­er­ate, the re­cur­sive tree of simu­la­tions must ter­mi­nate with prob­a­bil­ity one.)

    Ex­er­cise 2: when does this pro­gram win against a sim­ple ran­dom­iz­ing op­po­nent?

    Ex­er­cise 3: what’s the con­nec­tion be­tween the first two ex­er­cises, and does it im­ply any gen­eral the­o­rem?

    Epilogue

    Or­di­nary hu­mans play­ing the PD othen rely on as­sump­tions about their op­po­nent. They may con­sider cer­tain in­var­i­ant prop­er­ties of their op­po­nent, like al­tru­ism, or run men­tal simu­la­tions. Such wet­ware pro­cesses are in­her­ently hard to model, but even a half-hearted at­tempt brings out startling and rigor­ous for­mal­iza­tions in­stead of our usual vague in­tu­itions about game the­ory.

    Is this di­rec­tion of in­quiry fruit­ful?

    What do you think?