A failed solution to open-source game theory

In open-source game theory there are two standard approaches: simulate what the opponent will play against you (Robust program equilibrium, Oesterheld 2019), or prove it (Robust Cooperation in the Prisoner's Dilemma: Program Equilibrium via Provability Logic, Barasz et al. 2014).

Proving the behaviour of an arbitrary program is very challenging, and is certainly out of my skill set. Simulating the opponent is a more intuitive route to me, and a good example is EpsilonGroundedFairBot. For illustration purposes, I shall write strategies as callable Python classes.

class EpsilonGroundedFairBot:
    def __call__(self, opponent):
        if random.random() < ε:
            return C
        return opponent(self)

This struggles with potentially having long run times, and with generalising to more than two players. Each call to EpsilonGroundedFairBot leads, on average, to (1-ε) further calls. Simulating n opponents makes that n(1-ε), which is bigger than 1 once n is 2 or more and ε is small, so the calls multiply instead of dying out. There are solutions, such as randomly selecting one opponent to simulate, but I wondered if we could do better.

I wanted to see if we can cut out nested simulation loops by instead searching for a property in the opponent. Let us call this property nice: a nice agent is one that will not attempt to exploit an opponent it believes will cooperate. Then I can try strategies of the form: if my opponent is nice, cooperate, otherwise defect.

The hope is that this gives a cooperative equilibrium. Such a strategy is itself nice — it only defects on agents that would have exploited it — so a population of them recognises each other and cooperates, while any agent that deviates towards exploitation gets identified and defected against. Nobody simulates anybody, and cooperation is still a best response. However, I cannot get this to work.

A first attempt: probing by simulation

An obvious try is to use simulation to see what the opponent will play against CooperateBot, a strategy that cooperates whatever it faces.

class NiceProbeSimulator:
    def __call__(self, opponent):
        if opponent(CooperateBot) == C:
            return C
        return D

EpsilonGroundedFairBot is nice, because it can only defect if its opponent does, so it will surely cooperate against CooperateBot. NiceProbeSimulator(EpsilonGroundedFairBot) returns cooperation quickly, after two nested calls.

However, NiceProbeSimulator can be easily defeated by testing whether you are playing against a naive opponent — one that does not look at the strategy of its opponent at all — and behaving differently against them:

class AntiNiceProbeSimulator:
    def __call__(self, opponent):
        try:
            return opponent(None)
        except:
            return D

The general lesson is that any test run against a naive strategy can be spotted. The opponent can see who it is playing, so it can always tell the test apart from the real game and answer them differently. Patching this particular trick will not help.

A second attempt: probing by inspection

My second, more serious attempt is to achieve this via inspection. If allowed to view the opponent's source code, a program could edit it as follows: replace any call to me with the value C. Analysis of the edited code then determines whether it can still return D, and cooperates if it cannot.

The intuition is that a nice agent only defects because a simulation came back D. Replace the simulations with C and it has no route to D left.

class NiceProbeInspector:
    def __call__(self, opponent):
        modified_opponent = replace_opponent_calls_to_C(opponent)
        if returns_C_against_me(modified_opponent):
            return C
        return D

This removes the nested simulations, because I only analyse a modified version of the opponent which has had its simulations taken out. After modification, EpsilonGroundedFairBot returns C on both branches, and the analyser trivially identifies that every reachable return is C. This is still proving, but in the easy case: what makes proof hard is the fixed point running through the opponent's reasoning about me, and the edit deletes it, leaving a program that no longer calls back into me at all.

If we are not careful, though, this can be exploited by using the fact that all simulated calls now come back C:

class AntiNiceProbeInspector:
    def __call__(self, opponent):
        if opponent(DefectBot()) == C:
            return C
        return D

Here "opponent(DefectBot())" is replaced with C, which enters a logical path that is otherwise never taken, and the agent is wrongly certified. The fix is to sharpen the definition of niceness: a nice program cooperates against a program it believes will cooperate against it. So the only calls that matter are the ones about me, in both directions. I replace only calls of the form "opponent(self)", leaving "opponent(DefectBot())" alone and unresolvable, so AntiNiceProbeInspector is correctly judged not nice. And I bind the opponent's argument to my own source, so a comparison such as "isinstance(opponent, DefectBot)" resolves to false and the branch disappears.

Can we make these edits? Restrictions on how strategies may interact are needed to keep the rule meaningful. We would need to forbid aliasing, copying and rebinding of the opponent, since otherwise the replacement can be obfuscated away with a call such as "dummy = opponent; dummy(self)".

Two problems that remain

Suppose all of that could be made to work with some implementation. Two problems remain, and I do not think either is a bug that a further patch removes.

First: strategies that never simulate

What about strategies that do not simulate their opponents at all? The mirror, NiceProbeInspector(NiceProbeInspector), fails to produce C,C. It never calls "opponent(self)", so the replacement changes nothing, the analyser cannot resolve what is left, and we get D,D.

Fixing this means recognising when a strategy inspects what its opponent does against it, and substituting in the belief that the opponent cooperates. That raises a further question: if a strategy modifies its opponent and then simulates or inspects this object, should those calls be replaced too? NiceProbeInspector is exactly such a strategy, so answering "no" leaves the mirror broken. But modifications in general cannot be replaced with C, or we open the door to a variant of AntiNiceProbeInspector that rewrites the opponent's code to "return D" and inspects that.

Second: niceness without recognition

Niceness has a failure mode of its own: an agent can be prepared to cooperate against nice agents, but fail to identify them. There can be a gap between what my opponent does assuming that I will cooperate, and what it will do when it actually plays against me, even though I judge it to be nice and cooperate.

class BudgetBot:
    def __call__(self, opponent):
        try:
            with timeout(1):
                return opponent(self)
        except Timeout:
            return D

NiceProbeInspector(BudgetBot) correctly judges BudgetBot to be nice, and cooperates. The replacement leaves nothing expensive behind, so the timeout cannot fire and the analyser certifies it. However, in genuine play, if simulating NiceProbeInspector in BudgetBot(NiceProbeInspector) takes too long, BudgetBot will defect.

N.B. This is not specific to inspection. BudgetBot will time out against EpsilonGroundedFairBot as readily as against NiceProbeInspector: any agent that must reach a conclusion about its opponent under a resource bound can fail to reach it, whatever method it uses.

Conclusion

These two problems point in opposite directions. The first is my recogniser failing to certify an agent I would want to cooperate with; the second is an agent I have correctly certified failing to certify me.

What I would want to know next is whether there is a property that rules out both exploitation and failure-to-recognise, and whether it can be tested without going back to simulation.

Discuss