This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Gossner, O. Articles by Hernández, P. Search for Related Content

On the Complexity of Coordination

THEMA, UMR CNRS 7536, Université Paris X-Nanterre, 200 avenue de la République, 92001 Nanterre, France, and CORE, 34 Voie du Roman Pays, Université Catholique de Louvain, Louvain, Belgique
CORE, 34 Voie du Roman Pays, Université Catholique de Louvain, Louvain, Belgique
ogossner{at}u-paris10.fr
hernandez{at}core.ucl.ac.be

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 ln m)/n C, for almost any sequence of length n, there exists an automaton of size m that achieves a coordination ratio close to 1 with it. Moreover, we show that one can take any constant C such that C > e|X|ln |X|, where |X| is the size of the alphabet from which the sequence is drawn. Our result contrasts with Neyman (1997) that shows that when (mln m)/n is close to 0, for almost no sequence of length n there exists an automaton of size m that achieves a coordination ratio significantly larger 1/|X| with it.

Key Words: Coordination; complexity; automata

This article has been cited by other articles:

				J. Renault, M. Scarsini, and T. Tomala A Minority Game with Bounded Recall Mathematics of Operations Research, November 1, 2007; 32(4): 873 - 889. [Abstract] [PDF]

				O. Gossner and T. Tomala Empirical Distributions of Beliefs Under Imperfect Observation Mathematics of Operations Research, February 1, 2006; 31(1): 13 - 30. [Abstract] [PDF]