Lower bounds on degrees of game-theoretic structures (Q1106754)

This paper considers certain game-theoretic structures as relational structures \({\mathcal A}=<A,R_ 1,...,R_ n>\), where A is a non-empty set and each \(R_ j\) is a finitary relation on A for all \(j=1,...,n\). If for some recursive function g, \(A=Rng\;g\) and if for all \(j=1,...,n\) if \(R_ j\) is an m-ary relation on A such that \(Dom(R_ j)\) is an r.e. subset of \(A^ m=g({\mathbb{N}})^ m\), then we say that the game-theoretic structure \({\mathcal A}=<A,R_ 1,...,R_ n>\) is recursively presented with index g. For \({\mathcal A}_ g\) a recursively presented structure let \(\Phi: Alt_{{\mathcal A}_ g}\to Out_{{\mathcal A}_ g}\) be the task correspondence for \({\mathcal A}_ g\) that associates elements of an alternative space with elements of an outcome space. The Turing degree of the structure \({\mathcal A}_ g\) is defined to be deg(\({\mathcal A}_ g):=\deg (\text{graph}(\Phi))\) and is the degree of complexity of a computable realization of the task of \({\mathcal A}_ g\). If deg(graph(\(\Phi)\))\(\neq 0\), then the realization of the task associated with the game \({\mathcal A}_ g\) is not recursive. The partial ordering of the Turing degrees is used to rank the minimal degrees of unsolvability (i.e. \(\deg({\mathcal A}_ g)\neq 0)\) associated with recursive presentations of the following game-theoretic structures: (i) \(\Gamma_ g:\) Infinite stage Gale-Stewart games, (ii) \({\mathcal U}_ g:\) prioric Banach-Mazur games, (iii) \({\mathcal C}_ g:\) Single-player choice functions, (iv) \({\mathcal A}_ g:\) Walrasian models of general equilibrium, (v) \({\mathcal B}_ g:\) N-person non-cooperative games in the sense of Nash. The results of the paper are the following: Theorem 1. \(Sup\{\min(\deg(\Gamma_ g))\), \(\min(\deg({\mathcal U}_ g))\}\leq 0'.\) Theorem 2. \(0'<Inf\{\min(\deg({\mathcal C}_ g))\), \(\min(\deg({\mathcal A}_ g))\}.\) Corollary. \(Sup\{\min (\deg (\Gamma_ g))\), \(\min(\deg({\mathcal U}_ g))\}< \min(\deg({\mathcal B}_ g)).\) From theorem 1, minimal degrees of unsolvability for the structures \(\Gamma_ g\) and \({\mathcal U}_ g\) are bounded by the interval (0,0'] in \({\mathcal D}\), the set of Turing degrees of reducibility; and thus by the results of \textit{C. G. Jockush} and \textit{R. I. Soare} [Pac. J. Math. 40, 605-616 (1972; Zbl 0232.02031)] we have the characterization of minimal degrees for these structures as precisely the degrees of members of special recursively bounded \(\Pi^ 0_ 1\)-classes.