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.

Mots clés: Complexity; Computing; Best-Response Automata; Repeated Games

Domaines: Economie et sciences de la décision

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⟩