RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB

 Discrete Appl. Math., 2013, Volume 161, Issue 16, Pages 2440–2459 (Mi dma2)

Patience of matrix games

K. A. Hansena, R. Ibsen-Jensena, V. V. Podolskiib, E. Tsigaridascd

a Aarhus University, Denmark
b Steklov Mathematical Institute, Russia
c INRIA Paris-Rocquencourt, France
d Universite Pierre et Marie Curie (Paris 6), France

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)}$.

 Funding Agency Grant Number Danish National Research Foundation National Natural Science Foundation of China 6106113054060911130369 Ministry of Education and Science of the Russian Federation Agence Nationale de la Recherche ANR-09-BLAN-0371-01 European Union's Seventh Framework Programme Hansen and Ibsen-Jensen acknowledge support from the Danish National Research Foundation and The National Science Foundation of China (under the grant 61061130540) for the Sino-Danish Center for the Theory of Interactive Computation, within which this work was performed. They also acknowledge support from the Center for Research in Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. The research of Podolskii is partially supported by the Russian Foundation for Basic Research and the programme ‘‘Leading Scientific Schools’’. Part of the research was done during the author’s visit to Aarhus University. Tsigaridas is partially supported by the EXACTA grant of the National Science Foundation of China (NSFC 60911130369) and the French National Research Agency (ANR-09-BLAN-0371-01) and by FP7 Marie Curie Career Integration Grant.

DOI: https://doi.org/10.1016/j.dam.2013.05.008

Bibliographic databases:

Revised: 08.05.2013
Accepted:10.05.2013
Language: