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.
Venue: Modalidad Vía Online.
Speaker: Raimundo Saona
Affiliation: Institute of Science and Technology Austria (IST Austria)
Coordinator: José Verschae