Dynamics of min-max functions

Function F:Rⁿ→Rⁿ which are expansive in the l∞ norm and homogeneous, F_i(x₁+h,···x_n+h) = F_i(x₁, ···, x_n)+h, (so-called topical functions) have appeared recently in the work of several authors. They include (after suitable transformation) nonnegative matrices, Leontieff substitution systems, Bellman operators of games and of Markov decisions processes, examples arising from discrete event systems (digital circuits, computer networks, etc) and the min-max functions studied in this paper. Any topical function F can be approximated by min-max functions in a way which preserves some of the dynamics of F. We attempt, therefore, to clarify the dynamics of min-max functions, with a view to developing a generalized Perron-Frobenius theory for topical functions. Our main concern is with the existence of generalized fixed points, where F(x₁, ···, x_n) = (x₁+h, ···, x_n+h), which correspond to nonlinear eigenvectors, and with the cycle time vector, X(F) = lim_k→∞F^k (x)/ k ∈ Rⁿ, which generalizes the spectral radius. The Duality Conjecture for min-max functions asserts that this limit always exists, shows how it can be calculated and implies the strong result that F has a fixed point if, and only if, X(F) = (h, ···, h). We use an analogue of Howard's policy improvement scheme from optimal control to prove a fixed point theorem of equivalent strength, which is independent of the Duality Conjecture, and we give a proof of the Conjecture itself for n = 2.