.png){kind=icon}
.png){kind=icon}
Return
Computing equilibria in discounted dynamic games
.png){kind=icon}
PRE
AI
DOI：10.1016/j.amc.2015.07.068.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Game theory (GT) is an essential formal tool for interacting entities: however computing equilibria in GT is a hard problem. When the same game can be played repeatedly over time, the problem becomes even more complicated. The existence of multiple game states makes the problem of computing equilibria in such games extremely difficult. In this paper, we approach this problem by first proposing a method to compute a nonempty subset of approximate (up to any precision) subgame-perfect equilibria in repeated games. We then demonstrate how to extend this method to approximate all subgame-perfect equilibria in a repeated game, and also to solve more complex games, such as Markov chain games and stochastic games. We observe that in stochastic games, our algorithm requires additional strong assumptions to become tractable, while in repeated and Markov chain games it allows approximating all subgame-perfect equilibria reasonably fast and under considerably weaker assumptions than previous methods. (C) 2015 Elsevier Inc. All rights reserved.
Keywords:
Game theory
Repeated games
Stochastic games
Markov chain games
Subgame-perfect equilibria
Automaton
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W