On Solving Mean Payoff Games Using Pivoting Algorithms

S. K. Neogy (), Prasenjit Mondal, Abhijit Gupta () and Debasish Ghorui ()
Additional contact information
S. K. Neogy: Indian Statistical Institute, Delhi Center, New Delhi 110016, India
Prasenjit Mondal: Mathematics Department, Government General Degree College, Ranibandh, Bankura 722135, India
Abhijit Gupta: Indian Statistical Institute, Kolkata Center, Kolkata 700108, India
Debasish Ghorui: Mathematics Department, Jadavpur University, Kolkata 700032, India

Asia-Pacific Journal of Operational Research (APJOR), 2018, vol. 35, issue 05, 1-26

Abstract: Two classical pivoting algorithms, due to Lemke and Cottle–Dantzig, are studied on linear complementarity problems (LCPs) and their generalizations that arise from infinite duration two-person mean payoff games (MPGs) under zero-mean partition problem. Lemke’s algorithm was studied in solving MPGs via reduction to discounted payoff games or to simple stochastic games. We provide an alternative and efficient approach for studying the LCPs arising from the MPGs without any reduction. A binary MPG can easily be formulated as an LCP which has always terminated in a complementary solution in numerical experiments, but has not yet been proven either the processability of MPG’s by Lemke’s algorithm or a counter example that it will not terminate with a solution. Till now, the processability of MPG’s by Lemke’s algorithm remains open. A general MPG (with arbitrary outgoing arcs) naturally reduces to a generalized linear complementarity problem (GLCP) involving a rectangular matrix where the vertices are represented by the columns and the outgoing arcs from each vertex are represented by rows in a particular block. The noteworthy result in this paper is that the GLCP obtained from an MPG is processable by Cottle–Dantzig principal pivoting algorithm which terminates with a solution. Several properties of the matrix which arise in this context are also discussed.

Keywords: Mean payoff game; zero-mean partition problem; GLCP; Cottle–Dantzig algorithm; equivalent LCP; matrix classes in LCP (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595918500355
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:35:y:2018:i:05:n:s0217595918500355

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595918500355

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().