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.
Type de document :
Article dans une revue
Journal of Economic Theory, Elsevier, 1988, vol. 45, pp. 342-352. 〈10.1016/0022-0531(88)90274-8〉
Liste complète des métadonnées

https://hal-hec.archives-ouvertes.fr/hal-00756286
Contributeur : Amaury Bouvet <>
Soumis le : jeudi 22 novembre 2012 - 16:49:12
Dernière modification le : jeudi 22 novembre 2012 - 16:49:34

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

196