Gossner, Olivier
Hernandez, Penélope
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.
Bibliographic reference |
Gossner, Olivier ; Hernandez, Penélope. On the complexity of coordination. CORE Discussion Papers ; 2001/47 (2001) |
Permanent URL |
http://hdl.handle.net/2078.1/4202 |