Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419934 | Discrete Applied Mathematics | 2013 | 20 Pages |
Abstract
For matrix games we study how small nonzero probability must be used in optimal strategies. We show that for n×nn×n win–lose–draw games (i.e. (−1,0,1)(−1,0,1) matrix games) nonzero probabilities smaller than n−O(n)n−O(n) are never needed. We also construct an explicit n×nn×n win–lose game such that the unique optimal strategy uses a nonzero probability as small as n−Ω(n)n−Ω(n). This is done by constructing an explicit (−1,1)(−1,1) nonsingular n×nn×n matrix, for which the inverse has only nonnegative entries and where some of the entries are of value nΩ(n)nΩ(n).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Vladimir V. Podolskii, Elias Tsigaridas,