RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
Main page
About this project
Software
Classifications
Links
Terms of Use

Search papers
Search references

RSS
Current issues
Archive issues
What is RSS






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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 61061130540
60911130369
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:

Received: 28.09.2012
Revised: 08.05.2013
Accepted:10.05.2013
Language:

Linking options:
  • http://mi.mathnet.ru/eng/dma2

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:32

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020