Вероятностный подход к игре в угадывание в случайной среде

Вероятностный подход к игре в угадывание в случайной среде

Ковалевский А. П.
Дискретный анализ и исследование операций, 31, 1, 35-51 (2024)
Скачать статью

УДК 519.83 
DOI: 10.33048/daio.2024.31.781

Аннотация:

В статье формализуется и решается следующая игра двух лиц. Некоторый вопрос задан первому игроку. Второй игрок знает правильный ответ. Кроме того, оба игрока знают все возможные варианты ответа и их априорные вероятности. Второй игрок должен выбрать подмножество заданной мощности ответов-обманок. Первый игрок выбирает один из предложенных вариантов ответа. Первый игрок выигрывает у второго игрока единицу, если он угадал правильный ответ, и нуль иначе. Эта игра сводится к матричной игре. Однако матрица игры имеет большую размерность, из-за чего классический метод, основанный на решении пары двойственных задач линейного программирования, не может быть реализован для каждой индивидуальной задачи, поэтому необходимо разработать метод радикального понижения размерности.

Всё множество таких игр разбивается на два класса. Надравномерный класс игр характеризуется тем условием, что наибольшая из априорных вероятностей больше вероятности выбора ответа наудачу, а подравномерный класс соответствует противоположному неравенству: каждая из априорных вероятностей при умножении на общее число предъявляемых первому игроку ответов не превосходит единицы. Для каждого из этих двух классов решение расширенной матричной игры сводится к решению задачи линейного программирования существенно меньшей размерности. Для подравномерного класса игра переформулируется в терминах теории вероятностей. Условие на оптимальность смешанной стратегии формулируется с помощью теоремы Байеса. Для надравномерного класса решение игры использует вспомогательную задачу, относящуюся к подравномерному классу. Для обоих классов доказаны результаты о вероятностях угадывания правильного ответа при использовании оптимальных смешанных стратегий обоими игроками, а также разработаны алгоритмы получения этих стратегий. В подравномерном классе оптимальная смешанная стратегия первого игрока — выбирать ответ наудачу, а в надравномерном — выбирать наиболее вероятный ответ. Оптимальные смешанные стратегии второго игрока имеют значительно более сложную структуру. 
Библиогр. 7.

Литература:
  1. Borovkov A. A. Mathematical statistics. New York: Gordon and Breach, 1998. 570 p.
     
  2. Bradley S. P., Hax A. C., Magnanti T. L. Applied mathematical programming. Boston: Addison-Wesley, 1977. 716 p.
     
  3. Hörner J., Rosenberg D., Solan E., Vieille N. On a Markov game with one-sided information // Oper. Res. 2010. V. 58, No. 4-2. P. 1107–1115.
     
  4. Li S., Chen M., Wang Y., Wu Q. A fast algorithm to solve large-scale matrix games based on dimensionality reduction and its application in multiple unmanned combat air vehicles attack-defense decision-making // Inf. Sci. 2022. V. 594. P. 305–321.
     
  5. Lipton R. J., Young N. E. Simple strategies for large zero-sum games with applications to complexity theory // Proc. 26th Annu. ACM Symp. Theory of Computing (Montreal, Canada, May 23–25, 1994). New York: ACM, 1994. P. 734–740.
     
  6. Neumann J., Morgenstern O. Theory of games and economic behavior. Princeton: Princeton Univ. Press, 2007. 776 p.
     
  7. Wei Ch.-Y., Lee Ch.-W., Zhang M., Luo H. Last-iterate convergence of decentralized optimistic gradient descent-ascent in infinite-horizon competitive Markov games // Proc. Mach. Learn. Res. 2021. V. 134. P. 4259–4299.

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева СО РАН (проект № FWNF–2022–0010).

Ковалевский Артём Павлович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: artyom.kovalevskii@gmail.com

Статья поступила 9 августа 2023 г. 
После доработки — 5 сентября 2023 г. 
Принята к публикации 22 сентября 2023 г.

Abstract:

The following game of two persons is formalized and solved in the paper. Player 1 is asked a question. Player 2 knows the correct answer. Moreover, both players know all possible answers and their a priori probabilities. Player 2 must choose a subset of the given cardinality of deception answers. Player 1 chooses one of the proposed answers. Player 1 wins one from Player 2 if he/she guessed the correct answer and zero otherwise. This game is reduced to a matrix game. However, the game matrix is of large dimension, so the classical method based on solving a pair of dual linear programming problems cannot be implemented for each individual problem. Therefore, it is necessary to develop a method to radically reduce the dimension. 

The whole set of such games is divided into two classes. The superuniform class of games is characterized by the condition that the largest of the a priori probabilities is greater than the probability of choosing an answer at random, and the subuniform class corresponds to the opposite inequality — each of the a priori probabilities when multiplied by the total number of answers presented to Player 1 does not exceed one. For each of these two classes, the solving the extended matrix game is reduced to solving a linear programming problem of a much smaller dimension. For the subuniform class, the game is reformulated in terms of probability theory. The condition for the optimality of a mixed strategy is formulated using the Bayes theorem. For the superuniform class, the solution of the game uses an auxiliary problem related to the subuniform class. For both classes, we prove results on the probabilities of guessing the correct answer when using optimal mixed strategies by both players. We present algorithms for obtaining these strategies. The optimal mixed strategy of Player 1 is to choose an answer at random in the subuniform class and to choose the most probable answer in the superuniform class. Optimal mixed strategies of Player 2 have much more complex structure. 
Bibliogr. 7.

References:
  1. A. A. Borovkov, Mathematical Statistics (Gordon and Breach, New York, 1998).
     
  2. S. P. Bradley, A. C. Hax, and T. L. Magnanti, Applied Mathematical Programming (Addison-Wesley, Boston, 1977).
     
  3. J. Hörner, D. Rosenberg, E. Solan, and N. Vieille, On a Markov game with one-sided information, Oper. Res. 58 (4-2), 1107–1115 (2010).
     
  4. S. Li, M. Chen, Y. Wang, and Q. Wu, A fast algorithm to solve large-scale matrix games based on dimensionality reduction and its application in multiple unmanned combat air vehicles attack-defense decision-making, Inf. Sci. 594, 305–321 (2022).
     
  5. R. J. Lipton and N. E. Young, Simple strategies for large zero-sum games with applications to complexity theory, in Proc. 26th Annu. ACM Symp. Theory of Computing (Montreal, Canada, May 23–25, 1994) (ACM, New York, 1994), pp. 734–740.
     
  6. J. Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton Univ. Press, Princeton, 2007).
     
  7. Ch.-Y. Wei, Ch.-W. Lee, M. Zhang, and H. Luo, Last-iterate convergence of decentralized optimistic gradient descent-ascent in infinite-horizon competitive Markov games, Proc. Mach. Learn. Res. 134, 4259–4299 (2021).