Patience of Matrix Games

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)}$.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2013, 〈10.1016/j.dam.2013.05.008〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00843052
Contributeur : Elias Tsigaridas <>
Soumis le : mercredi 10 juillet 2013 - 11:59:39
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : mercredi 5 avril 2017 - 09:20:17

Fichier

MatrixGamePatience_revision.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

300

Téléchargements de fichiers

197