The Library
Linear complementarity algorithms for infinite games
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. ISBN 978-3-642-11265-2. doi:10.1007/978-3-642-11266-9 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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, Engineering and Medicine > 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 | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Volume: | Vol.5901 | ||||
Number of Pages: | 12 | ||||
Page Range: | pp. 382-393 | ||||
DOI: | 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 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |