Computer Science – Computer Science and Game Theory
Scientific paper
2010-02-08
Computer Science
Computer Science and Game Theory
26 pages, 13 figures, 1 table
Scientific paper
This paper presents a technique for approximating, up to any precision, the set of subgame-perfect equilibria (SPE) in discounted repeated games. The process starts with a single hypercube approximation of the set of SPE. Then the initial hypercube is gradually partitioned on to a set of smaller adjacent hypercubes, while those hypercubes that cannot contain any point belonging to the set of SPE are simultaneously withdrawn. Whether a given hypercube can contain an equilibrium point is verified by an appropriate mathematical program. Three different formulations of the algorithm for both approximately computing the set of SPE payoffs and extracting players' strategies are then proposed: the first two that do not assume the presence of an external coordination between players, and the third one that assumes a certain level of coordination during game play for convexifying the set of continuation payoffs after any repeated game history. A special attention is paid to the question of extracting players' strategies and their representability in form of finite automata, an important feature for artificial agent systems.
Burkov Andriy
Chaib-draa Brahim
No associations
LandOfFree
An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-123831