zbMATH — the first resource for mathematics

Learning to coordinate; a recursion theoretic perspective. (English) Zbl 0943.03034
Summary: We consider two players each of whom attempts to predict the behavior of the other, using no more than the history of earlier predictions. Behaviors are limited to a pair of options, conventionally denoted by 0, 1. Such players face the problem of learning in coordinate choices. The present paper formulates their situation recursion-theoretically, and investigates the prospects for success. A pair of players build up a matrix with two rows and infinitely many columns, and are said to “learn” each other if cofinitely many of the columns show the same number in both rows (either 0 or 1). Among other results we prove that there are two collections of players that force all other players to choose their camp. Each collection is composed of players that learn everyone else in the same collection, but no player that learns all members of one collection learns any member of the other.

03D80 Applications of computability and recursion theory
68Q32 Computational learning theory
91A26 Rationality and learning in game theory
Full Text: DOI