On the complexity of coordination
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  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.
(This abstract was borrowed from another version of this item.)
|Date of creation:||2001|
|Date of revision:|
|Contact details of provider:|| Postal: |
Phone: 33 1 34 25 60 63
Fax: 33 1 34 25 62 33
Web page: http://thema.u-cergy.fr
More information through EDIRC
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.:
- Abreu, Dilip & Rubinstein, Ariel, 1988. "The Structure of Nash Equilibrium in Repeated Games with Finite Automata," Econometrica, Econometric Society, vol. 56(6), pages 1259-81, November.
- Ehud Kalai & William Stanford, 1986.
"Finite Rationality and Interpersonal Complexity in Repeated Games,"
679, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Kalai, Ehud & Stanford, William, 1988. "Finite Rationality and Interpersonal Complexity in Repeated Games," Econometrica, Econometric Society, vol. 56(2), pages 397-410, March.
- Ben-Porath Elchanan, 1993. "Repeated Games with Finite Automata," Journal of Economic Theory, Elsevier, vol. 59(1), pages 17-32, February.
When requesting a correction, please mention this item's handle: RePEc:ema:worpap:2001-21. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Marion Oury)The email address of this maintainer does not seem to be valid anymore. Please ask Marion Oury to update the entry or send us the correct address
If references are entirely missing, you can add them using this form.