Computing the smallest xed point of nonexpansive mappings arising in game theory and static analysis of programs
Éric Goubault · 2009
The problem of computing the smallest xed point of a monotone map arises classically in the study of zero-sum repeated games. It also arises in static analysis of programs by abstract interpretation. In this context, the discount rate may be negative. We characterize the minimality of a xed point in terms of the nonlinear spectral radius of a certain semidierential. We apply this characterization to design a policy iteration algorithm, which applies to the case of nite state and action spaces. The algorithm returns a locally minimal xed point, which turns out to be globally minimal when the discount rate is nonnegative.