The Complexity of Computing Best-Response Automata in Repeated Games

Itzhak Gilboa

Post-Print from HAL

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.

Keywords: Complexity; Computing; Best-Response Automata; Repeated Games (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (24)

Published in Journal of Economic Theory, 1988, vol. 45, pp. 342-352. ⟨10.1016/0022-0531(88)90274-8⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
Journal Article: The complexity of computing best-response automata in repeated games (1988)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-00756286

DOI: 10.1016/0022-0531(88)90274-8

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().