The Library
Linear complementarity algorithms for infinite games
Tools
Tools
Tools
Fearnley, John, Jurdzinski, Marcin and Savani, Rahul (2010) Linear complementarity algorithms for infinite games. In: 36th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlyn, Czech Republic, January 23-29, 2010. Published in: Lecture Notes in Computer Science, Vol.5901 pp. 382-393.
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/978-3-642-11266-9
Abstract
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.
| Item Type: | Conference Item (UNSPECIFIED) |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science > Computer Science |
| Series Name: | Lecture Notes in Computer Science |
| Journal or Publication Title: | Lecture Notes in Computer Science |
| Publisher: | Springer |
| ISBN: | 978-3-642-11265-2 |
| ISSN: | 0302-9743 |
| Editor: | VanLeeuwen, J and Muscholl, A and Peleg, D and Pokorny, J and Rumpe, B |
| Date: | 2010 |
| Volume: | Vol.5901 |
| Number of Pages: | 12 |
| Page Range: | pp. 382-393 |
| Identification Number: | 10.1007/978-3-642-11266-9 |
| Status: | Not Peer Reviewed |
| Publication Status: | Published |
| Title of Event: | 36th Conference on Current Trends in Theory and Practice of Computer Science |
| Type of Event: | Conference |
| Location of Event: | Spindleruv Mlyn, Czech Republic |
| Date(s) of Event: | January 23-29, 2010 |
| URI: | http://wrap.warwick.ac.uk/id/eprint/5461 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
