The complexity of computing best-response automata in repeated games

DOI10.1016/0022-0531(88)90274-8zbMath0649.90105OpenAlexW1979592899MaRDI QIDQ1106110

Itzhak Gilboa

Publication date: 1988

Published in: Journal of Economic Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0531(88)90274-8

zbMATH Keywords

repeated gamepolynomial time complexitybest-response automaton

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Multistage and repeated games (91A20)

Related Items (18)

NP-completeness in hedonic games ⋮ Finite automata play repeated prisoner's dilemma with information processing costs ⋮ Computing equilibria: a computational complexity perspective ⋮ Complexity of games and bounded rationality ⋮ Bounded rationality, strategy simplification, and equilibrium ⋮ Rationality and bounded rationality ⋮ Bottom-up design of strategic options as finite automata ⋮ A complete characterization of infinitely repeated two-player games having computable strategies with no computable best response under limit-of-means payoff ⋮ On players with a bounded number of states ⋮ Nash and correlated equilibria: Some complexity considerations ⋮ The complexity of computing a best response automaton in repeated games with mixed strategies ⋮ Predicting the effects of intervention and sabotage in a bounded complex game ⋮ Modeling emotions and reason in agent-based systems ⋮ Computational complexity in additive hedonic games ⋮ Limitations of learning in automata-based systems ⋮ Plausible cooperation ⋮ Bayesian boundedly rational agents play the finitely repeated prisoner's dilemma ⋮ Computability, complexity and economics

Cites Work

• Finite automata play the repeated prisoner's dilemma
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of computing best-response automata in repeated games