The Complexity of Computing Best-Response Automata in Repeated Games - Archive ouverte HAL Access content directly
Journal Articles Journal of Economic Theory Year : 1988

The Complexity of Computing Best-Response Automata in Repeated Games

(1)
1

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.

Dates and versions

hal-00756286 , version 1 (22-11-2012)

Identifiers

Cite

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⟩

Collections

HEC
94 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More