American Institute of Mathematical Sciences

A famous result in game theory known as Zermelo's theorem says that ''in chess either White can force a win, or Black can force a win, or both sides can force at least a draw". The present paper extends this result to the class of all finite-stage two-player games of complete information with alternating moves. It is shown that in any such game either the first player has a winning strategy, or the second player has a winning strategy, or both have unbeatable strategies.

Pareto optimality and Nash equilibrium are two standard solution concepts for cooperative and non-cooperative games, respectively. At the outset, these concepts are incompatible-see, for instance, [7] or [10]. But, on the other hand, there are particular games in which Nash equilibria turn out to be Pareto-optimal [1], [4], [6], [18], [20]. A class of these games has been identified in the context of discrete-time potential games [13]. In this paper we introduce several classes of deterministic and stochastic potential differential games [12] in which open-loop Nash equilibria are also Pareto optimal.

We present an analysis of different classes of alternate games from different perspectives, including game theory, logic, bounded rationality and dynamic programming. In this paper we review some of these approaches providing a methodological framework which combines ideas from all of them, but emphasizing dynamic programming and game theory. In particular we study the relationship between games in discrete and continuous time and state space and how the latter can be understood as the limit of the former. We show how in some cases the Hamilton-Jacobi-Bellman equation for the discrete version of the game leads to a corresponding HJB partial differential equation for the continuous case and how this procedure allow us to obtain useful information about optimal strategies. This analysis yields another way to compute subgame perfect equilibrium.

In 1980 Steven Smale introduced a class of strategies for the Iterated Prisoner's Dilemma which used as data the running average of the previous payoff pairs. This approach is quite different from the Markov chain approach, common before and since, which used as data the outcome of the just previous play, the memory-one strategies. Our purpose here is to compare these two approaches focusing upon good strategies which, when used by a player, assure that the only way an opponent can obtain at least the cooperative payoff is to behave so that both players receive the cooperative payoff. In addition, we prove a version for the Smale approach of the so-called Folk Theorem concerning the existence of Nash equilibria in repeated play. We also consider the dynamics when certain simple Smale strategies are played against one another.

The new digital economy has renewed interest in how digital agents can innovate. This follows the legacy of John von Neumann dynamical systems theory on complex biological systems as computation. The Gödel-Turing-Post (GTP) logic is shown to be necessary to generate innovation based structure changing Type 4 dynamics of the Wolfram-Chomsky schema. Two syntactic procedures of GTP logic permit digital agents to exit from listable sets of digital technologies to produce novelty and surprises. The first is meta-analyses or offline simulations. The second is a fixed point with a two place encoding of negation or opposition, referred to as the Gödel sentence. It is postulated that in phenomena ranging from the genome to human proteanism, the Gödel sentence is a ubiquitous syntactic construction without which escape from hostile agents qua the Liar is impossible and digital agents become entrained within fixed repertoires. The only recursive best response function of a 2-person adversarial game that can implement strategic innovation in lock-step formation of an arms race is the productive function of the Emil Post [58] set theoretic proof of the Gödel incompleteness result. This overturns the view of game theorists that surprise and innovation cannot be a Nash equilibrium of a game.