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.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) in its series CORE Discussion Papers with number
2001047.
Cited by: (explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.)
Did you know? Each page is provided with a technical contact, in case something is not right with the supplied information. See under "publisher info".