An exponential lower bound for Cunningham's rule (Q507321)

The paper proves an exponential lower bound on Cunningham's rule (least recently considered or round robin rule) in the contexts of parity games, Markov decision processes (MDPs), acyclic unique sink orientations of hypercubes (AUSOs), and linear programs (LPs). The main result of the paper is the exponential lower bound on the number of improving switches in parity games employing Cunningham's rule to move from the initial strategy to the terminal one. The authors then use a known conection between parity games and MDPs to obtain an exponential lower bound on the number of policy iterations in MDPs that use an analogue of Cunningham's rule. Then using another known connection between MDPs and LPs, the result for Cunningham's rule in LP pivoting is obtained. Finally it is hown that the parity games introduced before give rise to AUSOs, where Cunningham's rule then follows an exponentially long path. This AUSO can be realized as a polytope, in fact the same polytope that results from the transformation of the parity game to and MDP and then to an LP.