期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2001
卷号：2001
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：Many results on repeated games played by nite 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
mlogm
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 mlogm
n is
close to 0, almost no sequence can be predicted with a coordination
ratio signi cantly larger than the minimal one.
