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
References listed on IDEAS
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.:
- Ben-Porath, E., 1991.
"Repeated games with Finite Automata,"
7-91, Tel Aviv - the Sackler Institute of Economic Studies.
- 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.
- 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.
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: (Stefania Marcassa)
If references are entirely missing, you can add them using this form.