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.
This research was supported in part by EPSRC projects EP/D067170/1, EP/E022030/1, and EP/D063191/1 (DIMAP).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Condon, A.: The complexity of stochastic games. Information and Computation 96, 203–224 (1992)
Condon, A.: On algorithms for simple stochastic games. In: Advances in Computational Complexity Theory, pp. 51–73. American Mathematical Society (1993)
Cottle, R.W., Dantzig, G.B.: Complementary pivot theory of mathematical programming. Linear Algebra and Its Applications 1, 103–125 (1968)
Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic Press (1992)
Derman, C.: Finite State Markov Decision Processes. Academic Press (1972)
Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer, Heidelberg (1997)
Gärtner, B., Morris, W.D., Rüst, L.: Unique sink orientations of grids. In: Jünger, M., Kaibel, V. (eds.) IPCO 2005. LNCS, vol. 3509, pp. 210–224. Springer, Heidelberg (2005)
Gärtner, B., Rüst, L.: Simple stochastic games and P-matrix generalized linear complementarity problems. In: Liśkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 209–220. Springer, Heidelberg (2005)
Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press (1985)
Johnson, C.R., Tsatsomeros, M.J.: Convex sets of nonsingular and P-matrices. Linear and Multilinear Algebra 38, 233–239 (1995)
Kojima, M., Noma, T., Megiddo, N., Yoshise, A. (eds.): A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. LNCS, vol. 538. Springer, Heidelberg (1991)
Lemke, C.E.: Bimatrix equilibrium points and mathematical programming. Management Science 11, 681–689 (1965)
Mangasarian, O.L.: Linear complementarity problems solvable by a single linear program. Mathematical Programming 10, 263–270 (1976)
Puri, A.: Theory of Hybrid Systems and Discrete Event Systems. PhD thesis, University of California, Berkeley (1995)
Shapley, L.S.: Stochastic games. Proc. Nat. Acad. Sci. U.S.A. 39, 1095–1100 (1953)
Stickney, A., Watson, L.: Digraph models of Bard-type algorithms for the linear complementarity problem. Mathematics of Operations Research 3, 322–333 (1978)
Svensson, O., Vorobyov, S.: Linear complementarity and P-matrices for stochastic games. In: Virbitskaite, I., Voronkov, A. (eds.) PSI 2006. LNCS, vol. 4378, pp. 408–421. Springer, Heidelberg (2007)
Szabó, T., Schurr, I.: Jumping doesn’t help in abstract cubes. In: Integer Programming and Combinatorial Optimization (IPCO). LNCS, vol. 11, pp. 225–235. Springer, Heidelberg (2005)
Szabó, T., Welzl, E.: Unique sink orientations of cubes. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 547–555 (2001)
Vöge, J., Jurdziński, M.: A discrete strategy improvement algorithm for solving parity games (Extended abstract). In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 202–215. Springer, Heidelberg (2000)
Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theoretical Computer Science 158, 343–359 (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jurdziński, M., Savani, R. (2008). A Simple P-Matrix Linear Complementarity Problem for Discounted Games. In: Beckmann, A., Dimitracopoulos, C., Löwe, B. (eds) Logic and Theory of Algorithms. CiE 2008. Lecture Notes in Computer Science, vol 5028. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69407-6_32
Download citation
DOI: https://doi.org/10.1007/978-3-540-69407-6_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69405-2
Online ISBN: 978-3-540-69407-6
eBook Packages: Computer ScienceComputer Science (R0)