The complexity of interacting automata
Gossner, O.
, Hernández, P. & Peretz, R.
(2016).
The complexity of interacting automata.
International Journal of Game Theory,
45(1), 461-496.
https://doi.org/10.1007/s00182-015-0521-7
, Hernández, P. & Peretz, R.
(2016).
The complexity of interacting automata.
International Journal of Game Theory,
45(1), 461-496.
https://doi.org/10.1007/s00182-015-0521-7
This paper studies the interaction of automata of size m. We characterise statistical properties satisfied by random plays generated by a correlated pair of automata with m states each. We show that in some respect the pair of automata can be identified with a more complex automaton of size comparable to mlogm . We investigate implications of these results on the correlated min–max value of repeated games played by automata.