On the complexity of coordination

Many results on repeated games played by finite automata rely on the complexity of the exact implementation of a coordinated play of length n. For a large proportion of sequences, this complexity appears to be no less than n. We study the complexity of a coordinated play when allowing for a few mismatches. We prove the existence of a constant C such that if (m log m /n) >= C, almost all sequences of length n can be predicted by an automaton of size m with a coordination rate close to 1. This contrasts with Neyman [6] that shows that when (m log m/n) is close to 0, almost no sequence can be predicted with a coordination ratio significantly larger than the minimal one.