The Complexity of Computing Best-Response Automata in Repeated Games

Itzhak Gilboa (1)

1 TAU - Tel Aviv University

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.

Keywords: Complexity; Computing; Best-Response Automata; Repeated Games

Domains: Economy and decision science

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