RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Главная страница
О проекте
Программное обеспечение
Классификаторы
Полезные ссылки
Пользовательское
соглашение

Поиск публикаций
Поиск ссылок

RSS
Текущие выпуски
Архивные выпуски
Что такое RSS






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Discrete Appl. Math., 2013, том 161, выпуск 16, страницы 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

Аннотация: 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)}$.

Финансовая поддержка Номер гранта
Danish National Research Foundation
National Natural Science Foundation of China 61061130540
60911130369
Министерство образования и науки Российской Федерации
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


Реферативные базы данных:

Тип публикации: Статья
Поступила в редакцию: 28.09.2012
Исправленный вариант: 08.05.2013
Язык публикации: английский

Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dma2

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:18

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018