A Simple P-Matrix Linear Complementarity Problem for Discounted Games

DOI10.1007/978-3-540-69407-6_32MaRDI QIDQ3507443zbMATH OpenOpenAlexFDO

Authors Marcin Jurdziński, Rahul Savani

Publication date 19 June 2008

Published in Logic and Theory of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69407-6_32

zbMATH Keywords

Discounted gamelinear complementarity problemP-matrixstrategy improvement algorithmunique sink orientationzero-sum game

Mathematics Subject Classification ID

2-person games (91A05) Stochastic games, stochastic differential games (91A15)

Recommendations

• Fundamentals of Computation Theory
• Linear complementarity and P-matrices for stochastic games
• Linear complementarity and discounted switching controller stochastic games
• The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games
• Linear complementarity algorithms for infinite games

Cites work

• A unified approach to interior point algorithms for linear complementarity problems: A summary
• Bimatrix Equilibrium Points and Mathematical Programming
• Complementary pivot theory of mathematical programming
• Convex sets of nonsingular and P:–Matrices
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• Finite state Markovian decision processes
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 1670778 (Why is no real title available?)
• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• Jumping Doesn’t Help in Abstract Cubes
• Linear complementarity and P-matrices for stochastic games
• Linear complementarity problems solvable by A single linear program
• Matrix Analysis
• Stochastic Games
• The complexity of mean payoff games on graphs
• The complexity of stochastic games
• Unique Sink Orientations of Grids

Cited in

(10)

• Linear complementarity and discounted switching controller stochastic games
• Linear complementarity algorithms for infinite games
• Linear complementarity and P-matrices for stochastic games
• scientific article; zbMATH DE number 1059233 (Why is no real title available?)
• The complexity of all-switches strategy improvement
• On solving mean payoff games using pivoting algorithms
• Towards solving 2-TBSG efficiently
• Completely mixed strategies for two structured classes of semi-Markov games, principal pivot transform and its generalizations
• Two choices are enough for P-LCPs, USOs, and colorful tangents
• Generalized principal pivot transforms, complementarity theory and their applications in stochastic games

This page was built for publication: A Simple P-Matrix Linear Complementarity Problem for Discounted Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3507443)