Stability in Matrix Games.

Abstract:  We consider the simplest game, Matrix Games, and basic stability questions on the value and strategies upon perturbations on the payoff matrix. Considering polynomial perturbations, we design polynomial-time algorithms for the following tasks: (a) ensuring that, for every sufficiently small error, there is a strategy to guarantee that the value is at least the value of the error-free case; (b) ensuring that there is a fixed strategy to guarantee that, for every sufficiently small error, the value is at least the value of the error-free case; and (c) computing the analytical form of the value of the game upon perturbations. We also make the connection with Linear Programming, just as Mills did in 1956 for a related problem.

Posted on Jun 7, 2021 in ACGO, Seminars