  We investigate the duality relation between linear programs over grids
(Grid-LPs) and generalized linear complementarity problems (GLCPs) with hidden
K-matrices. The two problems, moreover, share their combinatorial structure
with discounted Markov decision processes (MDPs). Through proposing reduction
schemes for the GLCP, we obtain a strongly polynomial reduction from Grid-LPs
to linear programs over cubes (Cube-LPs). As an application, we obtain a scheme
to reduce discounted MDPs to their binary counterparts. This result also
suggests that Cube-LPs are the key problems with respect to solvability of
linear programming in strongly polynomial time. We then consider two-player
stochastic games with perfect information as a natural generalization of
discounted MDPs. We identify the subclass of the GLCPs with P-matrices that
corresponds to these games and also provide a characterization in terms of
unique-sink orientations. A strongly polynomial reduction from the games to
their binary counterparts is obtained through a generalization of our reduction
for Grid-LPs.
