• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Patience of matrix games

Discrete Applied Mathematics. 2013. Vol. 161. No. 16-17. P. 2440-2459.
Podolskii V. V., Hansen K. A., Ibsen-Jensen R., Tsigaridas E. P.

For matrix games we study how small nonzero probability must be used in optimal strategies. We show that for n×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×n win–lose game such that the unique optimal strategy uses a nonzero probability as small as n−Ω(n). This is done by constructing an explicit (−1,1)nonsingular n×n matrix, for which the inverse has only nonnegative entries and where some of the entries are of value nΩ(n).