The Library
A simple P-matrix linear complementarity problem for discounted games
Tools
Jurdzinski, Marcin and Savani, Rahul (2008) A simple P-matrix linear complementarity problem for discounted games. In: 4th Conference on Computability in Europe (CiE 2008), Athens, Greece, 15-20 Jun 2008. Published in: Logic and Theory of Algorithms, 5028 pp. 283-293. ISBN 9783540694052. doi:10.1007/978-3-540-69407-6_32 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.
Abstract
The values of a two-player zero-sum binary discounted game are characterized by a P-matrix linear complementarity problem (LCP). Simple formulas are given to describe the data of the LCP in terms of the game graph, discount factor, and rewards. Hence it is shown that the unique sink orientation (USO) associated with this LCP coincides with the strategy valuation USO associated with the discounted game. As an application of this fact, it is shown that Murty's least-index method for P-matrix LCPs corresponds to both known and new variants of strategy improvement algorithms for discounted games.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
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: | Logic and Theory of Algorithms | ||||
Publisher: | Springer | ||||
ISBN: | 9783540694052 | ||||
ISSN: | 0302-9743 | ||||
Editor: | Beckmann, A and Dimitracopoulos, C and Lowe, B | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | 5028 | ||||
Number of Pages: | 11 | ||||
Page Range: | pp. 283-293 | ||||
DOI: | 10.1007/978-3-540-69407-6_32 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 4th Conference on Computability in Europe (CiE 2008) | ||||
Type of Event: | Conference | ||||
Location of Event: | Athens, Greece | ||||
Date(s) of Event: | 15-20 Jun 2008 |
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 |