Unformatted text preview:

CAN A TURING PLAYER IDENTIFY ITSELF DAVID K LEVINE AND AND BAL ZS SZENTES A BSTRACT We show that the problem of whether two Turing Machines are functionally equivalent is undecidable and explain why this is significant for the theory of repeated play and evolution Keywords Economic Theory Game Theory JEL Classification A1 A2 1 I NTRODUCTION Consider the basic problem of cooperation in a Prisoner s dilemma type situation Cooperative outcomes must be enforced by punishing free riders to do so it is necessary to identify free riders so that they can be punished This observation is a feature of the literature on repeated play with bounded rationality and in the theory of the evolution of cooperation In both cases a good strategy is to give some sort of secret handshake to determine if the opponent is of the same type and so should be cooperated with or a different type that should be punished In the setting of play between finite state machines the handshake is described in Rubinstein 1986 in the evolutionary setting by Robson 1990 Typically these secret handshakes take the form of some sort of signalling during the course of play but any strategy must be generated by an algorithm and in some circumstances it may be able to inspect the opponents algorithm prior to play this has obvious advantages over testing the opponent during the course of play An explicit theory along these lines can be found in Levine and Pesendorfer 2002 Of course an algorithm may be described in many ways from a strategic perspective what is important is not details of the algorithm but rather its functionality Is my opponent going to cheat so I should do likewise Is he going to engage in a strategy that leaves him open to exploitation Date First Version 20th January 2006 This Version 16th March 2006 UCLA and The University of Chicago Corresponding Author David K Levine Department of Economics UCLA Los Angeles CA 90095 USA Phone Fax 310 825 3810 Email david dklevine com Bal sz Szentes Department

Loading Unlocking...

Join to view CAN A TURING PLAYER IDENTIFY ITSELF? and access 3M+ class-specific study document.

We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CAN A TURING PLAYER IDENTIFY ITSELF? and access 3M+ class-specific study document.


By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?