The Complexity of Computing a Best Response Automaton in Repeated Games with Mixed Strategies

I examine the complexity of computing a best response automaton in a two-person repeated game when there is uncertainty about the automaton selected by the other player. There are two versions of this problem: 1. Finding a best response automaton. 2. Deciding if a given automaton is a best response. It is shown that these problems are ‘difficult’ (i.e. not polynomial). Next it is shown that if the size of the support of the distribution of the other player’s automata is known in advance, (for example when it is known that the other player is restricted to automata of a certain size), the problems are polynomial. The problems are polynomial even if there is uncertainty in the game that will be played (i.e. even it is a repeated game with incomplete information).