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