On the complexity of coordination

On the complexity of coordination

0.00 Avg rating0 Votes
Article ID: iaor2004663
Country: United States
Volume: 28
Issue: 1
Start Page Number: 127
End Page Number: 140
Publication Date: Feb 2003
Journal: Mathematics of Operations Research
Authors: ,
Abstract:

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 that shows that when (m ln 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.

Reviews

Required fields are marked *. Your email address will not be published.