Computer Science – Computer Science and Game Theory
Scientific paper
2009-09-30
Computer Science
Computer Science and Game Theory
Scientific paper
The performance of two pivoting algorithms, due to Lemke and Cottle and Dantzig, is studied on linear complementarity problems (LCPs) that arise from infinite games, such as parity, average-reward, and discounted games. The algorithms have not been previously studied in the context of infinite games, and they offer alternatives to the classical strategy-improvement algorithms. The two algorithms are described purely in terms of discounted games, thus bypassing the reduction from the games to LCPs, and hence facilitating a better understanding of the algorithms when applied to games. A family of parity games is given, on which both algorithms run in exponential time, indicating that in the worst case they perform no better for parity, average-reward, or discounted games than they do for general P-matrix LCPs.
Fearnley John
Jurdzinski Marcin
Savani Rahul
No associations
LandOfFree
Linear Complementarity Algorithms for Infinite 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 Linear Complementarity Algorithms for Infinite Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear Complementarity Algorithms for Infinite Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-590346