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, JUN 15-20, 2008. Published in: LOGIC AND THEORY OF ALGORITHMS, 5028 pp. 283-293.

Full text not available from this repository.

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 (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Series Name:	LECTURE NOTES IN COMPUTER SCIENCE
Journal or Publication Title:	LOGIC AND THEORY OF ALGORITHMS
Publisher:	SPRINGER-VERLAG BERLIN
ISBN:	978-3-540-69405-2
ISSN:	0302-9743
Editor:	Beckmann, A and Dimitracopoulos, C and Lowe, B
Date:	2008
Volume:	5028
Number of Pages:	11
Page Range:	pp. 283-293
Identification Number:	10.1007/978-3-540-69407-6_32
Publication Status:	Published
Title of Event:	4th Conference on Computability in Europe (CiE 2008)
Location of Event:	Athens, GREECE
Date(s) of Event:	JUN 15-20, 2008
URI:	http://wrap.warwick.ac.uk/id/eprint/29852

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item