A note on degrees of presentation of games as relational structures (Q912772)

This paper considers concepts of recursion-theoretic complexity in terms of the structure of Turing degrees of unsolvability for abstract games of the form \(\Gamma =<A,\prec >\), where A is a space of outcomes for a von Neumann cooperative game with arbitrary cardinality of players, and \(\succ\) is a dominance relation defined on pairs of outcomes in the space A. Weak versus strong concepts of recursive presentation are defined using the R.E. degrees and it is proved that no structure of the form \(\Gamma =<A,\prec >\) which is isomorphic to the space of primitive recursive reals when the dominance relation defined by the ordering on the positive part of A can be recursively presented in the strong sense, despite the fact that the dominance relation in this case is recursive. The notion of weak presentation coincides with R.E. presented, and in the special case when the dominance relation is extended to a linear ordering we show that a countable abstract game \(\Gamma =<A,\prec >\) possesses a degree of its isomorphic class only if that degree is \(\underset \tilde{} O\) and thus the game \(\Gamma =<A,\prec >\) is isomorphic to some game \(\Gamma_ 0=<A,\prec_ 0>\) whose degree of presentation is strongly recursive.