Files:
Abstract:
For matrix games we study how small nonzero probability must be used in optimal strategies. We show that for $n \times n$ win-lose-draw games (i.e. $(-1,0,1)$ matrix games) nonzero probabilities smaller than $n^-O(n)$ are never needed. We also construct an explicit $n \times n$ win-lose game such that the unique optimal strategy uses a nonzero probability as small as $n^-\Omega(n)$. This is done by constructing an explicit $(-1,1)$ nonsingular $n \times n$ matrix, for which the inverse has only nonnegative entries and where some of the entries are of value $n^\Omega(n)$.
BibTeX:
@article{hansen:hal-00843052,
hal_id = {hal-00843052},
url = {http://hal.inria.fr/hal-00843052},
title = {{Patience of Matrix Games}},
author = {Hansen, Kristoffer Arnsfelt and Ibsen-Jensen, Rasmus
and Podolskii, Vladimir V. and Tsigaridas, Elias},
abstract = {{For matrix games we study how small nonzero
probability must be used in optimal strategies. We
show that for $n \times n$ win-lose-draw games
(i.e.\ $(-1,0,1)$ matrix games) nonzero
probabilities smaller than $n^{-O(n)}$ are never
needed. We also construct an explicit $n \times n$
win-lose game such that the unique optimal strategy
uses a nonzero probability as small as
$n^{-\Omega(n)}$. This is done by constructing an
explicit $(-1,1)$ nonsingular $n \times n$ matrix,
for which the inverse has only nonnegative entries
and where some of the entries are of value
$n^{\Omega(n)}$.}},
keywords = {Matrix Games, Ill-conditioned Matrices, Nonnegative
Inverse},
language = {English},
affiliation = {Department of Computer Science [Aarhus] , Russian
Academy of Sciences [Moscou] , Laboratoire
d'Informatique de Paris 6 - LIP6 , POLSYS - INRIA
Paris-Rocquencourt},
publisher = {Elsevier},
journal = {Discrete Applied Mathematics},
audience = {international },
year = 2013,
url = {http://hal.inria.fr/hal-00843052},
}
Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02