# Patience of Matrix Games

3 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
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 :
Document type :
Journal articles
Domain :
Complete list of metadata

Cited literature [19 references]

https://hal.inria.fr/hal-00843052
Contributor : Elias Tsigaridas <>
Submitted on : Wednesday, July 10, 2013 - 11:59:39 AM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Wednesday, April 5, 2017 - 9:20:17 AM

### File

MatrixGamePatience_revision.pd...
Files produced by the author(s)

### Citation

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Vladimir V. Podolskii, Elias Tsigaridas. Patience of Matrix Games. Discrete Applied Mathematics, Elsevier, 2013, ⟨10.1016/j.dam.2013.05.008⟩. ⟨hal-00843052⟩

Record views