{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T04:54:01Z","timestamp":1648616041099},"reference-count":28,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2018,10]]},"abstract":"<jats:p> Two classical pivoting algorithms, due to Lemke and Cottle\u2013Dantzig, 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\u2019s 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\u2019s by Lemke\u2019s algorithm or a counter example that it will not terminate with a solution. Till now, the processability of MPG\u2019s by Lemke\u2019s 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\u2013Dantzig principal pivoting algorithm which terminates with a solution. Several properties of the matrix which arise in this context are also discussed. <\/jats:p>","DOI":"10.1142\/s0217595918500355","type":"journal-article","created":{"date-parts":[[2018,9,4]],"date-time":"2018-09-04T08:09:16Z","timestamp":1536048556000},"page":"1850035","source":"Crossref","is-referenced-by-count":0,"title":["On Solving Mean Payoff Games Using Pivoting Algorithms"],"prefix":"10.1142","volume":"35","author":[{"given":"S. K.","family":"Neogy","sequence":"first","affiliation":[{"name":"Indian Statistical Institute, Delhi Center, New Delhi 110016, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prasenjit","family":"Mondal","sequence":"additional","affiliation":[{"name":"Mathematics Department, Government General Degree College, Ranibandh, Bankura 722135, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhijit","family":"Gupta","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute, Kolkata Center, Kolkata 700108, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debasish","family":"Ghorui","sequence":"additional","affiliation":[{"name":"Mathematics Department, Jadavpur University, Kolkata 700032, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2018,9,26]]},"reference":[{"key":"S0217595918500355BIB001","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196711006674"},{"key":"S0217595918500355BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.04.029"},{"key":"S0217595918500355BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-010-0105-x"},{"key":"S0217595918500355BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"S0217595918500355BIB007","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/013\/04"},{"key":"S0217595918500355BIB008","volume-title":"Introduction to Algorithms","author":"Cormen TH","year":"2001","edition":"2"},{"key":"S0217595918500355BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80010-2"},{"key":"S0217595918500355BIB010","volume-title":"The Linear Complementarity Problem","author":"Cottle RW","year":"1992"},{"key":"S0217595918500355BIB012","doi-asserted-by":"publisher","DOI":"10.1137\/090747191"},{"key":"S0217595918500355BIB013","first-page":"A334","volume":"20","author":"Ehrenfeucht A","year":"1973","journal-title":"Notices of the American Mathematical Society"},{"key":"S0217595918500355BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/BF01768705"},{"key":"S0217595918500355BIB015","first-page":"185","volume-title":"DIMACS Series in Discrete Mathematics","volume":"31","author":"Emerson EA","year":"1997"},{"key":"S0217595918500355BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/11537311_19"},{"key":"S0217595918500355BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(88)90012-2"},{"key":"S0217595918500355BIB018","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.12.5.359"},{"key":"S0217595918500355BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"S0217595918500355BIB021","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.11.7.681"},{"key":"S0217595918500355BIB022","doi-asserted-by":"publisher","DOI":"10.1137\/1011093"},{"key":"S0217595918500355BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580671"},{"key":"S0217595918500355BIB024","doi-asserted-by":"publisher","DOI":"10.1142\/S0219198901000385"},{"key":"S0217595918500355BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592211"},{"key":"S0217595918500355BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/s00245-016-9362-4"},{"key":"S0217595918500355BIB027","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(76)90178-5"},{"key":"S0217595918500355BIB028","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.4.817"},{"key":"S0217595918500355BIB029","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.39.10.1953"},{"key":"S0217595918500355BIB030","doi-asserted-by":"publisher","DOI":"10.1007\/11775096_8"},{"key":"S0217595918500355BIB031","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.04.012"},{"key":"S0217595918500355BIB032","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00188-3"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595918500355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T21:01:03Z","timestamp":1565125263000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595918500355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,26]]},"references-count":28,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2018,9,26]]},"published-print":{"date-parts":[[2018,10]]}},"alternative-id":["10.1142\/S0217595918500355"],"URL":"https:\/\/doi.org\/10.1142\/s0217595918500355","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,26]]}}}