𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complexity of winning strategies

✍ Scribed by Andreas Blass

Publisher
Elsevier Science
Year
1972
Tongue
English
Weight
606 KB
Volume
3
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Rabin has given an example of a game with recursive rules but no recursive winning strategy. We show that such a game always has a hyperarithmetical winning strategy, but arbitrarily high levels of the hyperarithmetical hierarchy may be needed. We also exhibit a recursively enumerable game which has no hyperarithmetical winning strategy.

πŸ“œ SIMILAR VOLUMES

Games and winning strategies
Games and winning strategies
✍ R.J.R. Back; J. von Wright πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 565 KB
Winning strategies in club games and the
Winning strategies in club games and their applications
✍ Bernhard KΓΆnig πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 135 KB

Namba lemma, club game, two cardinal diamond. MSC (2010) 03E05, 03E10 We present results concerning winning strategies and tactics in club games on Pω 1 λ. We show that there is generally no winning tactic for the player trying to get inside the club. The bound-countable game turns out to be rather

Simple Adaptive Strategy Wins the Prison
Simple Adaptive Strategy Wins the Prisoner's Dilemma
✍ CHRISTOPH HAUERT; OLAF STENULL πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 276 KB

The prisoner's dilemma has become the leading paradigm to explain the evolution of cooperation among selfish individuals. Here, we present an adaptive strategy that implements new mechanisms to process information about past encounters. The history of moves is summarized in an internal state which t