The Complexity of Computing Best-Response Automata in Repeated Games

Abstract : The following problem is examined: given a game and the opponents' finite automata, find a best-response automaton for a certain player in the repeated game. It is shown that the problem is relatively "easy" (i.e., of polynomial time complexity) if the number of players is fixed, but "difficult" otherwise.
Complete list of metadatas

https://hal-hec.archives-ouvertes.fr/hal-00756286
Contributor : Antoine Haldemann <>
Submitted on : Thursday, November 22, 2012 - 4:49:12 PM
Last modification on : Thursday, November 22, 2012 - 4:49:34 PM

Links full text

Identifiers

Collections

Citation

Itzhak Gilboa. The Complexity of Computing Best-Response Automata in Repeated Games. Journal of Economic Theory, Elsevier, 1988, vol. 45, pp. 342-352. ⟨10.1016/0022-0531(88)90274-8⟩. ⟨hal-00756286⟩

Share

Metrics

Record views

237