On Solving Mean Payoff Games Using Pivoting Algorithms

DOI10.1142/S0217595918500355zbMath1400.90282OpenAlexW2890187817MaRDI QIDQ4689394

S. K. Neogy, Prasenjit Mondal, Debasish Ghorui, Abhijit Kar Gupta

Publication date: 16 October 2018

Published in: Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0217595918500355

zbMATH Keywords

mean payoff gamegeneralized linear complementarity problemCottle-Dantzig algorithmequivalent linear complementarity problemsmatrix classes in linear complementarity problemszero-mean partition problem

Mathematics Subject Classification ID

Linear programming (90C05) 2-person games (91A05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Faster algorithms for mean-payoff games
• Completely mixed strategies for two structured classes of semi-Markov games, principal pivot transform and its generalizations
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Cyclic games and linear programming
• Positional strategies for mean payoff games
• The complexity of stochastic games
• Extensions of two person zero sum games
• The complexity of mean payoff games on graphs
• The generalized linear complementarity problem revisited
• Mean Cost Cyclical Games
• PIVOTING ALGORITHMS FOR SOME CLASSES OF STOCHASTIC GAMES: A SURVEY
• TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
• Duality Between Invariant Spaces for Max-Plus Linear Discrete Event Systems
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• A Simple P-Matrix Linear Complementarity Problem for Discounted Games
• Linear complementarity problems solvable by A single linear program
• Fundamentals of Computation Theory
• On Nonterminating Stochastic Games
• Bimatrix Equilibrium Points and Mathematical Programming
• A generalization of the linear complementarity problem
• Stochastic Games with Perfect Information and Time Average Payoff
• Stochastic Games