50. Value-Positivity for Matrix Games
Invited abstract in session TB-2: Strategic games, stream Game theory.
Thursday, 10:00 - 11:30Room: C 103
Authors (first author is the speaker)
| 1. | Raimundo Saona
|
| Intitute of Science and Technology Austria |
Abstract
Matrix games are the most basic problem in Game Theory, but robustness to small perturbations is not yet fully understood.
A perturbed matrix game is one where the entries depend on a parameter which varies smoothly around zero. We introduce two new concepts:
(a) value-positivity if, for every sufficiently small error, there is a strategy that guarantees the value of the error-free matrix game; and
(b) uniform value-positivity if there exists a fixed strategy that guarantees, for every sufficiently small error, the value of the error-free matrix game.
While the first concept captures the dependency of optimal strategies to small perturbations, the second naturally arises where the data is uncertain and a strategy should remain optimal despite that uncertainty.
In this paper, we provide explicit polynomial-time algorithms to solve these two problems for any polynomially perturbed matrix game.
For (a), we further provide a functional form for the error-dependent optimal strategy.
Last, we translate our results into robust solutions for LPs.
Keywords
- Optimization under uncertainty and applications
- Linear and nonlinear optimization
Status: accepted
Back to the list of papers