Content area
What follows is the result of the author’s investigation into the logical foundations of the theory of games. This investigation was carried out from a decidedly recursion-theoretic point of view, where we understand recursion theory to be that branch of logic which is fundamentally concerned, not with computability, but with definability. Consequently, this is a dissertation in recursion theory.
In the course of his investigation the author was led to the earliest and most significant theorem of game theory, namely: von Neumann’s minimax theorem for finite two-person zero-sum games. This result is regarded as the foundation of game theory, even by von Neumann himself, who remarked that the subject could not exist without it. Here we are primarily concerned with the minimax theorem and the logical principles involved in its proof.
The statements which comprise the dissertation have been organized in the following manner. Statements 1.1–1.35 are a computational study: There it is proved that the optimal strategies of any two-person zero-sum game of imperfect information are explicitly uniformly recursive in the specification of the game itself. In fact, it is proved that this holds for a particularly abstract generalization of the minimax theorem. So while the minimax theorem guarantees the existence of an equilibrium value, the results of Statements 1.1–1.35 confirm that the value can in fact be found in principle.
Statements 2.1–2.24 are foundational in scope: Here it is shown that the minimax theorem in two dimensions is provable in a formal axiomatic system which corresponds to constructive mathematics. The upshot of this result is that although standard and familiar proofs of the minimax theorem rely on highly non-constructive mathematical principles such as compactness, only relatively elementary ones are actually needed to prove the theorem in ℝ2.
Statements 3.1–3.27 contain an analysis of the compactness principles which recur in proofs of the minimax theorem and in equilibrium theorems in economics and game theory more broadly. Three such principles are the Brouwer fixed point theorem, the KKM theorem, and weak K̈onig’s lemma. These are generally believed to be equivalent: indeed, contains a formal derivation of the equivalence of Brouwer’s fixed-point theorem and weak K̈onig’s lemma. In Statements 3.1–3.27 it is proved that the KKM theorem is equivalent to weak K̈onig’s lemma, thus tying these results together and formally verifying the belief of the community on this topic.