\documentclass[11pt,twoside,reqno]{amsart}
\usepackage{daio}

%%%%%-----Авторы заполняют все аргументы в блоке команд ниже-----%%%%%%

%%---Номер УДК
\udc{519.83}

%%---Название статьи на русском и английском языках
\title[Вероятностный подход к игре в угадывание]{Вероятностный подход к игре в угадывание в случайной
среде}
\titleen[A probabilistic approach to the game of guessing]{A probabilistic approach to the game of guessing in a random
environment}

%%---Имена авторов на русском языке и в транлитерации на латиницу, краткие и полные
\author[1]{А. П. Ковалевский}		%1,2 --- указать, в каком порядке перечислять адреса автора
\authoren[1]{A. P. Kovalevskii}
\fullname{Ковалевский Артем Павлович}
\fullnameen{Artyom P. Kovalevskii}

%%---Адреса авторов на русском и английском языках в следующих форматах.
%%На русском:
%%---Организация,
%%---улица, дом, индекс город, страна
\address[1]{Институт математики им. С. Л. Соболева СО РАН,\\пр. Коптюга, 4, 630090 Новосибирск, Россия}
%%На английском:
%%---Организация,
%%---дом улица, индекс город, страна
\addressen[1]{Sobolev Institute of Mathematics,\\4 Koptjuga Street, 630090 Novosibirsk, Russia}

%%---Адреса электронной почты авторов
\email{artyom.kovalevskii@gmail.com}

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

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

 Табл.~0, ил.~0, библиогр.~7}
\abstracten{The following game of two persons is formalized and solved in the paper.
Some question is asked to Player 1. Player 2 knows the correct answer. Moreover, both players
know all possible answers and their prior probabilities.
Player 2 must choose a subset of the given cardinality of deception answers. Player 1 chooses one of the proposed answers.
Player 1 gets 1 from Player 2 if he guessed the correct answer, and 0 otherwise.
This game is reduced to a matrix game. However, the game matrix has a 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
method of radical reduction of dimension.

The whole set of such games is divided into two classes. 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 solution of the extended matrix game is reduced to the solution of 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 a 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 pesent 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. 

Tab.~0, illustr.~0, bibliogr.~7}

%%---Ключевые слова статьи на русском и английском языках
\keywords{матричные игры, вероятность угадывания, теорема Байеса, равновероятное распределение, решение в чистых стратегиях, решение в смешанных стратегиях.
}
\keywordsen{matrix games, guessing probability, Bayes' theorem, equiprobable distribution, solution in pure strategies, solution in mixed strategies.}

%%---Если необходимо, указание на грантовую поддержку на русском и английском языках
\thanks{Исследование выполнено при финансовой поддержке 
программы фундаментальных научных исследований СО РАН
 (проект FWNF-2022-0010)}
\thanksen{This research is supported by the Fundamental scientific research of the SB RAS (project FWNF-2022-0010)}

%%%%%-----Конец блока команд, заполняемых автором-----%%%%%%

\begin{document}

\thispagestyle{empty}
\settitle
\paperhead


\section{Введение}

Пусть игроку $\mathcal{A}$  задан некоторый вопрос, на который существует  $n$ ($n>2$) возможных вариантов ответа $O_1,\dots,O_n$. В каждом раунде игры правильный ответ на вопрос выбирается случайно и не зависит от предыстории. Вероятность для каждого возможного варианта ответа $O_i$ быть правильным постоянна и равна $r_i$. Ответы упорядочены таким образом, что $\quad r_1\geq r_2\geq\dots\geq r_n > 0$. Мы считаем этот порядок фиксированным и будем 
употреблять выражение <<наиболее вероятный ответ>> (из некоторого множества ответов) в значении <<ответ с наименьшим номером>>.


Игрок $\mathcal{A}$ знает вопрос и вероятности $r_1,\dots, r_n$. Игрок $\mathcal{B}$, помимо этого, знает правильный ответ. Игрок $\mathcal{B}$ предлагает игроку $\mathcal{A}$ угадать, какой ответ правильный, предоставляя выбор из $k$ вариантов, $1<k<n$. Задача игрока $\mathcal{B}$ --- по правильному ответу подобрать $k-1$ вариант ложных ответов так, чтобы вероятность того, что  $\mathcal{A}$ угадает, была наименьшей. Задача игрока $\mathcal{A}$ --- использовать алгоритм выбора из предложенных $k$ вариантов, при котором вероятность угадывания будет наибольшей.

Эта игра является антагонистической игрой двух лиц, и после усреднения по случайной среде, сформированной последовательностью номеров правильных ответов, формализуется как матричная игра (игра двух лиц с нулевой суммой, глава 13 в \cite{Neumann}). Игрок $\mathcal{B}$ выбирает, какие $k$ из $n$ возможных ответов
предложить. Более точно, игрок $\mathcal{B}$ в зависимости от варианта ответа, который верен для данного вопроса, выбирает другие варианты ответа, которые будут показаны игроку  $\mathcal{A}$ вместе с верным вариантом в случайном порядке. Игрок  $\mathcal{A}$ выбирает один из $k$ предложенных ответов. Средний выигрыш игрока  $\mathcal{A}$ при каждом выборе стратегий игроками равен вероятности угадывания верного 
ответа. 

Теорема 1 дает верхнюю и нижнюю цену игры и показывает, что верхняя цена игры больше нижней, то есть нет решения в чистых стратегиях. 
Однако решение этой игры в смешанных стратегиях неприемлемо с вычислительной точки зрения. Как будет показано ниже,
платежная матрица имеет размерность $(C^{k-1}_{n-1})^n \times k^{C^k_n}$, где $C^k_n$ --- биномиальный коэффициент. Классический подход 
(глава 17 в \cite{Neumann})  предполагает решение задачи линейного программирования с системой ограничений, определяемых платежной матрицей. Так как матрица имеет скорость роста много выше экспоненциальной (по количеству вариантов ответа), решение получить невозможно даже для малых $n$ и $k$.

В статьях \cite{Matrix_dim_reduction_1}, \cite{Matrix_dim_reduction_2} представлены общие методы понижения размерности для матричных игр. Они не подходят для изучаемой задачи, так как представленные в работах алгоритмы имеют псевдополиномиальную по максимальному из размерностей платежной матрицы временную сложность, что делает их неприменимыми. Необходимо понизить размерность задачи на основании
другого подхода.

Разрабатываемый в данной работе подход использует связи между теорией игр, теорией вероятностей и линейным программированием. Ряд полезных связей (кроме того, и с математической статистикой) изложен в  (\cite{Borovkov_MS}, глава 4).

Отнесем каждую индивидуальную задачу к одному из двух классов в зависимости от входных параметров. \textit{Надравномерный} класс игр
характеризуется условием  $r_1>\frac{1}{k}$, а  \textit{подравномерный} класс соответствует условию 
$r_1 \leq \frac{1}{k}$. Для этих двух классов существенно отличаются оптимальные смешанные стратегии игрока $\mathcal{A}$.
Для каждого из этих двух классов решение расширенной матричной игры сводится к решению задачи линейного программирования существенно меньшей размерности.


Теорема 2 содержит результат для подравномерного класса. Задача переформулируется в терминах теории вероятностей. Условие на оптимальность смешанной стратегии формулируется с помощью теоремы Байеса. Доказывается, что цена расширенной игры из этого класса равна $1/k$, 
оптимальной стратегией игрока $\mathcal{A}$ в надравномерном случае является смешанная стратегия <<выбирать варианты ответа равновероятно>>,
а оптимальная смешанная стратегия  игрока  $\mathcal{B}$ вычисляется решением задачи линейного программирования с матрицей
размерности $n\times C^k_n$.

Теорема 3 дает ответ для надравномерного класса. Она использует вспомогательную задачу, относящуюся к подравномерному классу. Цена расширенной игры из этого класса равна $r_1$, а оптимальной стратегией игрока $\mathcal{A}$ в надравномерном случае является чистая стратегия <<выбирать самый популярный ответ>>. Размерность задачи линейного программирования для отыскания оптимальной смешанной стратегии 
игрока  $\mathcal{B}$ остается той же, что и в теореме 2.  

Современная теория игр изучает, в частности, марковские матричные игры. В таких задачах предполагается, что платежная матрица изменяется от раунда к раунду, образуя цепь Маркова. Данную задачу также можно модифицировать, потребовав, чтобы последовательность правильных ответов образовывала марковскую цепь. В настоящее время теория марковских игр только развивается, и нет аналитических методов получения точного  решения \cite{Markov_game_1}. Тем не менее существуют эффективные алгоритмы получения приближенного решения, аппроксимирующего точное с любой точностью \cite{Markov_game_2}.


\section{Сведение к матричной игре}

Пусть $O_1,\ldots,O_n$ --- возможные варианты ответа, и событие $\{T=O_i\}$ означает, что верным является ответ с номером $i$.
 Тогда $r_i = {\bf P}(T=O_i)$.


 Игрок $\mathcal{B}$ для каждого варианта правильного 
ответа должен предложить $k-1$ ответ-ловушку. Игрок $\mathcal{A}$ для каждого варианта показанных ему ответов должен выбрать один ответ.

Чистые (детерминированные) стратегии игрока  $\mathcal{B}$ состоят в том, что по известному верному ответу
выбирается еще $k-1$ ответ, то есть каждому из ответов $O_i$ сопоставляется подмножество $B_i$
множества $\{O_1, \ldots, O_n\}\setminus\{O_i\}$. При этом множество $B_i$ содержит $k-1$ элемент: $|B_i|=k-1$.

Введем обозначения для стратегий игрока $\mathcal{B}$:

\[
\delta_{B_1\ldots B_n} = \left\{
\begin{array}{c}
B_1 , \ \mbox{если} \ T=O_1;\\
\ldots \\
B_n, \ \mbox{если} \ T=O_n.
\end{array}
\right.
\]

Число чистых стратегий игрока $\mathcal{B}$ --- это возведенное в степень $n$ число способов выбрать $k-1$ элемент из $n-1$ элемента:
\[
\left(C_{n-1}^{k-1}\right)^n = \left(\frac{(n-1)!}{(k-1)!(n-k)!}\right)^n.
\]

Игрок $\mathcal{A}$ из предложенных вариантов ответа выбирает один. 
Чистая (детерминированная) стратегия этого игрока: из $k$-элементного множества ответов $A_i$ выбрать 
один ответ $D_i$. Ясно, что для каждого множества этот выбор можно сделать $k$ способами, а всего $k$-элементных множеств $m=C_n^k$ штук.
Мы будем предполагать, что  множества $A_i$ упорядочены. Конкретный порядок не играет роли. Удобно считать, что множества упорядочены в лексикографическом порядке номеров их элементов.

Введем обозначения для стратегий игрока $\mathcal{A}$:

\[
\theta_{D_1\ldots D_m} = \left\{
\begin{array}{c}
D_1 , \ \mbox{если множество ответов } \ A_1;\\
\ldots \\
D_m, \ \mbox{если множество ответов} \ A_m.
\end{array}
\right.
\]

Таким образом, получено следующее утверждение:

\begin{claim}
Число чистых стратегий  игрока  $\mathcal{A}$ равняется 
\[
M:=k^{C_n^k}=k^\frac{n!}{k!(n-k)!},
\]
число чистых стратегий игрока $\mathcal{B}$ равняется  
\[
N:=\left(C_{n-1}^{k-1}\right)^n = \left(\frac{(n-1)!}{(k-1)!(n-k)!}\right)^n.
\]
\end{claim}


{\bf Пример 1.} Пусть $n=3$, $k=2$.
У каждого из игроков $2^3=8$ стратегий.
Опишем их детально. 
Стратегии игрока $\mathcal{B}$:
\[
\delta_{ijs} = \left\{
\begin{array}{c}
\mbox{показывать дополнительно ответ } i , \ \mbox{если верный ответ} \ 1;\\
\mbox{показывать дополнительно ответ } j , \ \mbox{если верный ответ} \ 2;\\
\mbox{показывать дополнительно ответ } s , \ \mbox{если верный ответ} \ 3;\\
\end{array}
\right.
\]

Стратегии игрока  $\mathcal{A}$:
\[
\theta_{ijs} = \left\{
\begin{array}{c}
\mbox{выбирать ответ } i , \ \mbox{если показывают ответы } \ 1 \mbox{ и } 2;\\
\mbox{выбирать ответ } j, \ \mbox{если показывают ответы } \ 1 \mbox{ и } 3;\\
\mbox{выбирать ответ } s , \ \mbox{если показывают ответы } \ 2 \mbox{ и } 3.\\
\end{array}
\right.
\]

Выигрыш игрока $\mathcal{A}$ (равный потерям игрока $\mathcal{B}$) в каждой ситуации, то есть при каждом сделанном игроками выборе --- это вероятность того, что игрок $\mathcal{A}$ угадает верный ответ.
Поэтому соответствующий паре стратегий ($\theta_{D_1\ldots D_m}$, $\delta_{B_1\ldots B_n}$) элемент платежной матрицы равен
\[
\varphi_{st}= \varphi(\theta_{D_1\ldots D_m}, \delta_{B_1\ldots B_n})=\sum_{i = 1}^n r_i \left( \sum\limits_{j = 1}^{C^k_n} {\bf 1}(A_j = B_i\cup \{O_i\}, \ D_j = O_i)\right),
\]
\[
s=1,\ldots M, \ t=1,\ldots,N.
\]



Вернемся к примеру 1 ($k= 2 , n=3$). Здесь три вероятности $r_1~\ge~r_2~\ge~r_3$. Платежная матрица равна: \\
\begin{tabular}{c|cccccccc}
 & $\delta_{211}$ & $\delta_{212}$ & $\delta_{231}$  & $\delta_{232}$ & $\delta_{311}$ & $\delta_{312}$ & $\delta_{331}$ & $\delta_{332}$ \\ \hline
  $\theta_{112}$	&$r_1$	&$r_1$	&$r_1+r_2$	&$r_1+r_2$	&$r_1$	&$r_1$	&$r_1+r_2$	&$r_1+r_2$ \\
 $\theta_{113}$	&$r_1$	&$r_1+r_3$&	$r_1$&	$r_1+r_3$&	$r_1$&	$r_1+r_3$&	$r_1$&	$r_1+r_3$ \\
  $\theta_{132}$ 	&$r_1+r_3$&	$r_1$&	1&	$r_1+r_2$&	$r_3$&	0&	$r_2+r_3$&	$r_2$\\
 $\theta_{133}$	&$r_1+r_3$	&$r_1+r_3$	&$r_1+r_3$	&$r_1+r_3$	&$r_3$	&$r_3$	&$r_3$	&$r_3$\\
 $\theta_{212}$	&$r_2$	&$r_2$	&$r_2$	&$r_2$	&$r_1+r_2$	&$r_1+r_2$	&$r_1+r_2$	&$r_1+r_2$\\
  $\theta_{213}$ 	&$r_2$	&$r_2+r_3$	&$0$	&$r_3$	&$r_1+r_2$	&$1$	&$r_1$	&$r_1+r_3$\\
  $\theta_{232}$	&$r_2+r_3$	&$r_2$	&$r_2+r_3$	&$r_2$	&$r_2+r_3$	&$r_2$	&$r_2+r_3$	&$r_2$\\
 $\theta_{233}$	&$r_2+r_3$	&$r_2+r_3$	&$r_3$	&$r_3$	&$r_2+r_3$	&$r_2+r_3$	&$r_3$	&$r_3$
\end{tabular}

Следующая теорема дает верхнюю и нижнюю цену игры.

\begin{theorem}
1) Нижняя цена игры 
\[
\max_{s \le M} \min_{t\le N} \varphi_{st}=r_1,
\]
соответствующая максиминная стратегия игрока $\mathcal{A}$ --- 
выбирать ответ с наименьшим номером из предъявленных (самый вероятный ответ).

2) Верхняя цена игры 
\[
\min_{t\le N} \max_{s \le M}  \varphi_{st}=\sum\limits_{i: \, 1+ik\le n} r_{1+ik}=r_1+r_{1+k}+\ldots >r_1,
\]
соответствующая минимаксная стратегия игрока $\mathcal{B}$: показывать вместе первые $k$ самых вероятных ответов (то есть ответы с номерами 
$1,\ldots,k$), вторые $k$ самых вероятных ответов (ответы с номерами 
$k+1,\ldots,2k$), и т.д. Если $n$ не кратно $k$, то в последний набор ответов включаются дополнительно первые $k(\lfloor n/k\rfloor+1)-n$ ответов.
\end{theorem}

{\bf Доказательство}

1) Максиминное решение означает, что игрок $\mathcal{A}$ выбирает свою чистую стратегию, а игрок $\mathcal{B}$, зная его чистую стратегию,
выбирает свою чистую стратегию так, чтобы минимизировать свой проигрыш. 

У игрока $\mathcal{A}$ есть чистая стратегия, состоящая в выборе ответа с наименьшим номером (наиболее вероятного ответа) из множества 
предъявленных ответов. В тех случаях, когда первый ответ является верным, игрок $\mathcal{B}$ обязан его предъявить. Так как вероятность 
первого ответа равна $r_1$, то выигрыш первого игрока составляет не меньше $r_1$. В тех случаях, когда первый ответ не является верным, игрок   
$\mathcal{B}$ показывает первый ответ в числе прочих, и игрок $\mathcal{A}$ выбирает его, при этом он выигрывает 0 (с вероятностью $1-r_1$).
Таким образом, чистая стратегия $s_0$, состоящая в выборе ответа с наименьшим номером, обеспечивает равенство
\[
 \min_{t\le N} \varphi_{s_0 t}=r_1.
\]

Покажем, что эта стратегия $s_0$ является максиминной, то есть ее замена на любую другую чистую стратегию не приводит к увеличению
минимального (по всем чистым стратегиям игрока $\mathcal{B}$) среднего выигрыша игрока $\mathcal{A}$.  Действительно, 
рассмотрим все такие множества $A_j$ предъявляемых игроку  $\mathcal{A}$ ответов, которые содержат конкретный ответ $O_i$.
Если хотя бы на одном из этих множеств игрок  $\mathcal{A}$ выбирает ответ, не равный $O_i$, то игрок $\mathcal{B}$ предъявляет
именно это множество в том случае, когда $O_i$ является верным ответом, и выигрыш игрока $\mathcal{A}$ в этом случае равен 0.

Поэтому будем предполагать, что существует ответ $O_i$, который выбирается игроком $\mathcal{A}$ для всех множеств, его содержащих. 
Тогда игрок $\mathcal{B}$ обязан показать одно из таких множеств, если $O_i$ является верным ответом, и это происходит с вероятностью $r_i$.
А если $O_i$ не является верным ответом, то игрок $\mathcal{B}$ также показывает одно из таких множеств $A_j$, включая в него ответ $O_i$
 наряду с верным ответом. Поэтому в любом случае, когда $O_i$ не является верным ответом, выигрыш игрока $\mathcal{A}$ равен 0.
Итого средний суммарный выигрыш равняется $r_i$. 

Следовательно,
\[
\max_{s \le M} \min_{t\le N} \varphi_{st}=\max_{i\le n} r_i=r_1.
\]


2) Минимаксное решение означает, что игрок $\mathcal{B}$ выбирает свою чистую стратегию, а игрок $\mathcal{A}$, зная его чистую стратегию,
выбирает свою чистую стратегию так, чтобы максимизировать свой выигрыш.  Каждому ответу $O_1,\ldots, O_{n}$  игрок $\mathcal{B}$ 
сопоставляет содержащее его множество $A_1,\ldots,A_{n}$. Если какие-либо из этих множеств совпадают, 
то игрок $\mathcal{A}$ не может различить, какой из ответов верен, и для максимизации среднего выигрыша выбирает наиболее вероятный ответ.
Средний выигрыш игрока $\mathcal{A}$ равен сумме наибольших вероятностей по всем различным множествам из $A_1,\ldots,A_{n}$.

 Доказательство проведем индукцией по $n$.

Базис индукции: пусть $n=k+1$ (минимально возможное значение). Множество $A_1$ содержит первый ответ и приносит игроку 
$\mathcal{A}$ выигрыш $r_1$. Так как $|A_1|=k$, то игрок $\mathcal{B}$ выбирает $k-1$ множество совпадающим с $A_1$ (что дает нулевые потери), а одно множество должно отличаться. Потери будут наименьшими (и равными $r_1+r_{k+1}$), если первые $k$ множеств совпадают, а последнее отличается. В частности, можно в множество $A_{k+1}$ добавить ответы $O_1,\ldots,O_{k-1}$.

Шаг индукции: предположим, что утверждение теоремы выполнено для $n\ge k+1$. Докажем, что оно верно для $n+1$. Рассмотрим два варианта.

Первый вариант: $n$ не кратно $k$. Тогда игрок  $\mathcal{B}$ сохраняет множества 
\[
A_1=\ldots=A_k=\{O_1,\ldots,O_k\},
\]
\[
\ldots
\]
\[
A_{k\lfloor n/k \rfloor-k +1}=\ldots=A_{k\lfloor n/k \rfloor}=\{O_{k\lfloor n/k \rfloor-k +1},\ldots,O_{k\lfloor n/k \rfloor }\},
\] 
и выбирает 
\[
A_{k\lfloor n/k \rfloor +1}=\ldots=A_{n+1}=\{O_{k\lfloor n/k \rfloor +1},\ldots,O_{n+1}\}
\] 
(если $n+1$ кратно $k$) или
\[
A_{k\lfloor n/k \rfloor +1}=\ldots=A_{n+1}=\{O_{k\lfloor n/k \rfloor +1},\ldots,O_{n+1},O_1,\ldots, O_{k- n-1+k\lfloor (n+1)/k \rfloor}\}
\] 
(если $n+1$ не кратно $k$),
что дает нулевое увеличение его средних потерь.
Так как при переходе от $n$ к $n+1$ его средние потери не могут уменьшиться (максимум берется по более широкому множеству), то оптимальность решения сохраняется.  

Второй вариант: $n$ делится нацело на $k$. Тогда игрок  $\mathcal{B}$ сохраняет все предыдущие множества и выбирает
\[
A_{n+1}=\{O_{n+1}, O_1, \ldots, O_{k-1}\}.
\]

Такой выбор является оптимальным, так как увеличивает цену простой игры на минимально возможную величину $r_{n+1}$.

Доказательство завершено.

Возвращаясь к примеру 1 ($k= 2 , n=3$), получаем, что здесь  
нижняя цена игры равна $r_1$,
верхняя цена игры  равна $r_1 + r_3$.


\section {Подравномерный случай}

Согласно теореме 1, нижняя цена простой игры всегда строго меньше верхней, поэтому надо рассматривать расширенную матричную игру,
в которой стратегии каждого из игроков выбираются случайно в соответствии с некоторым вероятностным распределением на множестве стратегий. 
Таким образом, есть три независимых в совокупности последовательности случайных величин: одна отвечает за выбор ответа, 
другая за выбор стратегии первым игроком, третья за выбор стратегии вторым игроком. Вероятностные распределения на соответствующих
множествах стратегий называются смешанными стратегиями игроков $\mathcal{A}$ и $\mathcal{B}$.

Классический метод решения расширенных матричных игр подразумевает решение пары двойственных задач линейного программирования.
Однако для данной игры матрица системы ограничений для задачи линейного программирования имеет размерность $M\times N = k^{C^k_n}  \times  \left(C_{n-1}^{k-1}\right)^n$. При $n = 6, k = 4$ размерность равна $  2^{30}\times 10^6$. Решение задачи даже в таком частном случае требует значительных вычислительных ресурсов. Кроме того, размерность растет со скоростью, сильно большей, чем экспоненциальная (по $n$). Решение задачи в такой постановке для приложений не представляется возможным. Необходимо искать методы понижения размерности системы ограничений, либо искать решение, основываясь на вероятностной постановке задачи.

Существуют алгоритмы понижения размерностей для матричных игр (например, \cite{Matrix_dim_reduction_1}, основанный на составлении новой эквивалентной  задачи линейного программирования, состоящей из выпуклой оболочки множества решений), однако в случае размерностей такого порядка, как в этой задаче, они остаются бесполезны. В статье \cite{Matrix_dim_reduction_1} предлагаемый алгоритм получает решение матричной игры за временную сложность $O(TN^2 + n^{3.5})$, где $N$ --- максимальная из размерностей платежной матрицы, $n$ --- размерность редуцированной матрицы, $T$ --- некоторый параметр, зависящий от матрицы. В любом случае необходимо провести псевдополиномиальное число операций над матрицей, что для данных размерностей практически невозможно на практике. Поэтому становится актуальным поиск другого метода решения.

Посмотрим на задачу с помощью формулы Байеса. Игрок $\mathcal{A}$ знает множество возможных ответов и 
априорные вероятности $r_1,...,r_n$ того, что соответствующий ответ будет верным. Также он видит предложенное подмножество $A_s$ из $k$ ответов, из которого он должен выбрать правильный ответ. Тогда, по формуле Байеса,  апостериорная вероятность того, что вариант $O_i$ будет верным $(T=O_i)$ при условии, что игрок $\mathcal{A}$ выбирает из множества $A_s$, равна

\[
P(T = O_i|A_s) = \frac{P(A_s|T = O_i)r_i}{P(A_s)}, \quad i \in A_s.
\]

Обозначим 
\[
q_{i,A_s}:=P(A_s|T = O_i).
\]

Игрок  $\mathcal{B}$ не может повлиять на априорные вероятности, однако может изменять апостериорные, чтобы уменьшить вероятность угадать верный ответ. Потребуем, чтобы условная вероятность быть верным ответом для любого элемента из данного подмножества была одинаковой. Для этого числитель этой дроби не должен зависеть от $i$, то есть для любых $1\le~s \le~ C_n^k$, \ $|A_s|=k$, \  $O_i \in A_s$ требуется существование 
$z_s\ge 0$ такого, что
\[
q_{i,A_s}=z_s/r_i.\]

Тем самым знания об априорном распределении становятся бесполезными, и у игрока $\mathcal{A}$ нет лучшей возможности, чем выбрать наугад из $k$ элементов. В новых обозначениях  условная вероятность того, что $i$--й элемент будет верным ответом, равна

\[
P(T = O_i|A_s) = \frac{z_s}{P(A_s)} , \ \ \  O_i \in A_s.
\]

Заметим, что для всех $i$
\[
	\sum\limits_{s :\,  O_i \in A_s}P(A_s|T = O_i) = P(\bigcup\limits_{s :\, O_i \in A_s}A_s|T = O_i) =1,
\]
тогда, умножив равенство на $r_i$, получим

\[
\sum\limits_{s :\, O_i \in A_s}P(A_s|T = O_i)r_i =\sum\limits_{s :\, O_i \in A_s} z_s =r_i,\ \  i = 1,...,n.
\]

Кроме того, $z_s \geq 0$ для любого $ A_s$.

Мы получили систему уравнений и неравенств для определения $z_s$ из $n$ уравнений с $C_n^k$ неизвестными, а также с условиями на знак:
\begin{equation}\label{bayes_under_system}
\left\{ 
\begin{array}{l}
\sum\limits_{s : \,O_i \in A_s} z_s =r_i,\ \  i = 1,...,n, \\
\\
z_s \geq 0, \ \ 1 \le s \le C_n^k.
\end{array}
\right.
\end{equation}

 Решив ее, можно получить вероятности для множества ответов $A_s: \, A_s \ni O_i$ при условии, что $O_i$ является верным ответом:

\begin{equation}\label{bayes_proba}
	P(A_s|T = O_i) = q_{i,A_s} = \frac{z_s}{r_i}.
\end{equation}

Запишем задачу линейного программирования, состоящую в максимизации суммы переменных при ограничениях в виде неравенств:

\begin{equation}\label{bayes_linprog}
\left\{ 
\begin{array}{l}
\gamma=\sum\limits_{s = 1}^{C^k_n}z_s \rightarrow \max, \\
\\
\sum\limits_{s :\, O_i \in A_s} z_s \le r_i,\ \  i = 1,...,n, \\
\\
z_s \geq 0, \ \ 1 \le s \le C_n^k.
\end{array}
\right.
\end{equation}

Здесь  задача максимизации суммы всех переменных введена искусственно, она будет использоваться для доказательства существования решения у системы (\ref{bayes_under_system}).




\begin{theorem}
    Если $r_1 \leq \frac{1}{k}$, то цена игры равна $\frac{1}{k}$,  задача линейного программирования (\ref{bayes_linprog})
     совместна, ее решение удовлетворяет ограничениям (\ref{bayes_under_system}), и оптимальной смешанной стратегией игрока $\mathcal{B}$ является выбор вероятностей в соответствии с   (\ref{bayes_proba}). При этом оптимальной является смешанная стратегия игрока $\mathcal{A}$, при которой варианты ответов выбираются равновероятно. 
    Если же $r_1 \textgreater \frac{1}{k}$, то система  (\ref{bayes_under_system}) не имеет решений, и равновероятная стратегия игрока $\mathcal{A}$ не является оптимальной.  
\end{theorem}

Доказательство

Пусть $(b_{is})$ -- матрица системы уравнений (\ref{bayes_under_system}), $i = 1,...,n$; $s = 1,...,C_n^k$. Тогда $b_{is} = 1$ тогда и только тогда, когда $i$--й элемент содержится в подмножестве $A_s$. Так как в любом $A_s$ содержится ровно $k$ элементов, то, сложив все уравнения, получим следующее: в правой части будет $\sum\limits_{i=1}^n r_i = 1$, а в левой $k\sum\limits_{i=1}^{C_n^k} z_s$, 
то есть 
\[
 	\sum\limits_{i=1}^{C_n^k}z_s = \frac{1}{k}.
\]

Тогда выигрыш игрока $\mathcal{A}$ при разыгрывании любой своей стратегии равен $\frac{1}{k}$, если система уравнений и неравенств совместна. 


Предположим, что $r_1 \textgreater \frac{1}{k}$ и $z_s \geq 0$ для всех $s$. Но тогда 

\[
\sum\limits_{s:\, O_1 \in A_s} z_s =r_1 \leq \sum\limits_{s = 1 }^{C^k_n} z_s = \frac{1}{k}, 
\]
чего не может быть.


Для доказательства совместности системы в подравномерном случае вспомним задачу линейного программирования (\ref{bayes_linprog}).
Рассмотрим двойственную задачу:
\begin{equation}\label{bayes_linprog_dual}
\left\{ 
\begin{array}{l}
\omega = \sum\limits_{i = 1}^n r_ix_i \rightarrow \min, \\
\\
\sum\limits_{j \in A_s} x_j \geq 1, \ \ s = 1,..., C^k_n, \\
\\
x_i \geq 0, \ \  i = 1,..., n.
\end{array}
\right.
\end{equation}


Из ограничений на знак переменных двойственной задачи следует, что $\omega$ ограничена снизу. Кроме того, решение 
\begin{equation}\label{bayes_dual_opt}
x_1 = x_2 = ... = x_n = \frac{1}{k}
\end{equation} 
является допустимым, и целевая функция для такого решения равна $\frac{1}{k}$. 
В силу теоремы двойственности, существует решение прямой задачи такое, что $\gamma_{\max} = \omega_{\min}$. 
Покажем, что в подравномерном случае решение (\ref{bayes_dual_opt}) оптимально, то есть всегда $\omega \geq \frac{1}{k}$.

Для этого изучим соседние к (\ref{bayes_dual_opt}) вершины симплекса. В этих вершинах одна из переменных становится базисной и принимает нулевое значение: $x_i=0$ для некоторого $i \in \{1,\ldots,n\}$. Небазисные переменные выражаются через базисные, поэтому
для всех $A_s$ таких, что $O_i \in A_s$, выполнено
\[
\sum_{j: \, O_j \in A_s \backslash\{O_i\}} x_j = 1, 
\]
при этом $|A_s|=k$.
В силу симметрии, $x_j = \frac{1}{k-1}$ для всех $j \ne i$.

Следовательно, соседние к  (\ref{bayes_dual_opt}) вершины симплекса имеют следующий вид: $x_i=0$ для некоторого $i \in \{1,\ldots,n\}$, 
и $x_j = \frac{1}{k-1}$ для всех $j \ne i$. Но в этих вершинах  
\[
\omega=\frac{1}{k-1}\sum_{j \ne i} r_j = \frac{1-r_i}{k-1}\ge \frac{1}{k}
\]
в силу условия подравномерности $r_i \le r_1 \le 1/k$.

Итак, (\ref{bayes_dual_opt}) является решением двойственной задачи, и 
все переменные принимают строго положительные значения. Значит, существует решение прямой задачи (\ref{bayes_linprog}), для которого все существенные ограничения
обратятся в строгие равенства 
%(Complementary Slackness Property, see Section 4.5 in \cite{Linprog}), 
(свойство дополняющей нежесткости, см. \S 4.5 в \cite{Linprog}), 
что означает существование неотрицательного решения системы уравнений (\ref{bayes_under_system}).

Теорема доказана.

\noindent
{\bf Пример 2.} Пусть  $n=3$, $k=2$, $1/2 \geq r_1 \geq r_2 \geq r_3$.

Тогда $z_{12}+z_{13}=r_1, \ \ z_{12}+z_{23}=r_2, \ \  
z_{13}+z_{23}=r_3$.


Отсюда
\[
z_{12}=\frac{r_1+r_2-r_3}{2}, \ \ 
z_{13}=\frac{r_1-r_2+r_3}{2}, \ \
z_{23}=\frac{-r_1+r_2+r_3}{2},
\]
\[
q_{23}=z_{23}/r_2, \ \ 
q_{13}=z_{13}/r_1, \ \
q_{12}=z_{12}/r_1, 
\]
\[
q_{21}=z_{12}/r_2, \ \ 
q_{31}=z_{13}/r_3, \ \
q_{32}=z_{23}/r_3. \ \
\]

Здесь $q_{ij}$ --- вероятность того, что игрок $\mathcal{B}$ добавит ответ-ловушку с номером $j$, если правильный ответ имеет номер $i$.

Игрок $\mathcal{A}$ выбирает ответы равновероятно, его средний выигрыш равен $1/2$.




\section{Надравномерный случай}

Надравномерный случай характеризуется условием $r_1 > \frac{1}{k}$. Докажем, что здесь цена расширенной игры равна $r_1$,
и что у игрока $\mathcal{A}$ есть оптимальная чистая стратегия --- выбирать самый вероятный ответ $O_1$. 
Также найдем оптимальную смешанную стратегию игрока $\mathcal{B}$. Таких стратегий очень много, но трудно
найти конкретную стратегию, которая подходит для общего случая. 

Будем сводить надравномерный случай к подравномерному. Для этого мы введем модифицированные 
(срезанные и масштабированные) вероятности 
\[
r'_i=L \min(r_i,c).
\]

Здесь $c>0$ --- уровень срезки, а 
\[
L=\left( \sum_{i=1}^n  \min(r_i,c) \right)^{-1}
\]
--- нормирующая константа,
обеспечивающая выполнение условия
\[
\sum_{i=1}^n r'_i =1.
\]

 Выберем $c$ как наименьший положительный корень уравнения
\begin{equation}\label{cdef}
 ck= \sum_{i=1}^n  \min(r_i,c)  =: g(c).
 \end{equation}

 
 Такой корень $0<c< 1/k$ обязательно существует, так как левая и правая части уравнения (\ref{cdef}) непрерывны как функции от $c$, 
 равны 0 при $c=0$, $\frac{dg}{dx}|_{x=0+}=n>k$, $g(1/k)<1$.
 
 Тогда
\[
r'_1=Lc=1/k,
\]
и выполнено условие подравномерности для вероятностей $r'_i$.

По аналогии с  (\ref{bayes_linprog}) запишем задачу линейного программирования:

\begin{equation}\label{linprog'}
\left\{ 
\begin{array}{l}
\gamma' = \sum\limits_{s = 1}^{C^{k}_{n}}z'_s \rightarrow \max, \\
\\
\sum\limits_{A_s \ni O_i} z'_s \le r'_i,\ \  i =1,...,n, \ \ |A_s|=k,\\
\\
z'_s \geq 0, \ \ 1 \le s \le C_{n}^{k}.
\end{array}
\right.
\end{equation}

Она имеет решение согласно теореме 2.

\begin{theorem}
Если $r_1 > \frac{1}{k}$, то цена расширенной игры равна $r_1$. При этом оптимальной является чистая стратегия игрока $\mathcal{A}$, при которой  выбирается наиболее вероятный ответ. Оптимальной смешанной стратегией игрока $\mathcal{B}$ является следующая:
если $O_i$ является верным ответом, то множество ответов $A_s$ выбирается  с вероятностью 
$
q'_{i,A_s}=z'_s/r'_i
$,
$O_i \in A_s$.
Здесь $\{z'_s\}_{s=1}^{C_n^k}$ --- решение задачи (\ref{linprog'}).
\end{theorem}

Доказательство

Рассмотрим произвольную чистую стратегию игрока $\mathcal{A}$ и оценим сверху ее средний выигрыш. 

Игрок $\mathcal{A}$ из каждого возникающего в игре множества ответов $A_s$ выбирает один из его элементов.

Пусть 
\[
r_1\ge \ldots \ge r_{k_0} \ge c \ge r_{k_0+1} \ge \ldots \ge r_n.
\]

Из (\ref{cdef}) получаем
\[
ck=ck_0 + r_{k_0+1}+\ldots+r_n,
\]
отсюда
\[
c=\frac{r_{k_0+1}+\ldots+r_n}{k-k_0}.
\]

Следовательно,
\[
k_0=\min \left(t \ge 1: \ \frac{r_{t+1}+\ldots+r_n}{k-t}\ge r_{t+1} \right).
\]

Такое $k_0<k$ всегда существует, так как при $t=k-1$ неравенство выполнено.


Если $i\le k_0$, то $r'_i = 1/k$. Это максимально возможная правая часть в  (\ref{linprog'}).
Поэтому существует смешанная стратегия игрока $\mathcal{B}$, в которой любое выбираемое множество $A_s$ содержит ответы 
$1,\ldots,k_0$ с вероятностью 1. При этом $r_i/r'_i=kr_i$.

Если $i> k_0$, то 
\[
r'_i = \frac{(k-k_0)r_i}{k(r_{k_0+1}+\ldots+r_n)},
\]
\[
r_i/r'_i = \frac{k(r_{k_0+1}+\ldots+r_n)}{k-k_0}.
\]


Оценим сверху условную вероятность того, что $O_i$ является верным ответом, если предложено множество ответов $A_s$.

 
\[
P(T=O_i|A_s) = \frac{ P(T=O_i,A_s)}{P(A_s)} =
\frac{ P(A_s|T=O_i)r_i}{\sum\limits_{j:\, O_j \in A_s} P(A_s|T=O_j)r_j} 
\]
\[
=
\frac{z'_s r_i/r'_i}{\sum\limits_{j:\, O_j \in A_s}  z'_s r_j/r'_j} 
=
\frac{r_i/r'_i}{\sum\limits_{j:\, O_j \in A_s}  r_j/r'_j} 
\]
\[
\le
\frac{kr_1 }{k(r_1+\ldots+r_{k_0})+ \sum\limits_{j:\, O_j \in A_s \cap \{O_{k_0+1},\ldots,O_n\} } \frac{k(r_{k_0+1}+\ldots+r_n)}{k-k_0} } = r_1,
\]
так как $|A_s \cap \{O_{k_0+1},\ldots,O_n\}|=k-k_0$.

Итак, при предлагаемой смешанной стратегии игрока $\mathcal{B}$ средний выигрыш любой чистой стратегии игрока $\mathcal{A}$ не превосходит $r_1$.
Теорема доказана.

\noindent
{\bf Пример 3.} Пусть  $n=3$, $k=2$, $r_1 > 1/2 > r_2 \geq r_3$.

В силу условия нормировки, $r_2+r_3<1/2$.

Согласно теореме 3, $c=r_2+r_3$, 
\[
r_1'=1/2, \ \  r_2'=\frac{r_2}{2(r_2+r_3)}, \ \ r_3'=\frac{r_3}{2(r_2+r_3)}, \ \ r_2'+r_3'=1/2.
\]

Максимум целевой функции достигается на решении системы уравнений
\[
z_{12}'+z_{13}'=1/2,
\]
\[
z_{12}'+z_{23}'=r_2',
\]
\[
z_{13}'+z_{23}'=r_3'.
\]

Отсюда
\[
z_{12}'=r_2', \ \ 
z_{13}'=r_3', \ \
z_{23}'=0,
\]
\[
q_{12}'=\frac{r_2}{r_2+r_3}, \ \ 
q_{13}'=\frac{r_3}{r_2+r_3}, \ \
q_{21}'=q_{31}'=1,  \ \
q_{23}'=q_{32}'=0.
\]

Как и в примере 2, здесь $q_{ij}$ --- вероятность того, что игрок $\mathcal{B}$ добавит ответ-ловушку с номером $j$, если правильный ответ имеет номер $i$.

Игрок $\mathcal{A}$ выбирает наиболее вероятный ответ, его средний выигрыш равен $r_1$.



\section{Заключение}

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

В ходе исследования был выявлен класс индивидуальных задач, для которых существует стратегия игрока $\mathcal{B}$ такая, что информация об априорном распределении вариантов ответов не приносит дополнительного выигрыша игроку $\mathcal{A}$.

В качестве продолжения исследования можно рассмотреть модифицированную формулировку задачи, в которой последовательность платежных матриц образует цепь Маркова. Такая задача относится к классу марковских игр, исследования которых активно проводятся в последние годы. 

Автор благодарит Евгения Прокопенко за предложение сделать исследование в этом направлении и Ивана Смирнова за численную реализацию 
предложенных алгоритмов.


\begin{thebibliography}{99}



\bibitem{Borovkov_MS}  
\textbf{Borovkov\;A.\;A.} Mathematical statistics. New York: Gordon and Breach, 1998. 570 p.

\bibitem{Linprog}
\textbf{Bradley\;S.\;P., Hax\;A.\;C., Magnanti\;T.\;L.} Applied mathematical programming.
Boston: Addison-Wesley Publishing Company, 1977. 716 p.
\url{http://web.mit.edu/15.053/www/AMP.htm}

\bibitem{Markov_game_1} 
\textbf{H\H{o}rner\;J., Rosenberg\;D., Solan\;E., Vieille\;N.} On a Markov game with one-sided information // Operations Research 2010.  Vol. 58,  2010. 
P. 1107--1115.

\bibitem{Matrix_dim_reduction_1} 
\textbf{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 // Information Sciences 2022. Vol. 594. P. 305--321.

\bibitem{Matrix_dim_reduction_2} 
\textbf{Lipton\;R.\;J., Young\;N.\;E.} 
Simple strategies for large zero-sum games with applications to complexity theory //
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing. (Montreal, Quebec, Canada, 5/1994).
New York: ACM, 1994. P. 734--740.

\bibitem{Neumann}
\textbf{Neumann\;J., Morgenstern\;O.} Theory of games and economic behavior. Princeton: University Press 2007. 776 p.

\bibitem{Markov_game_2} 
\textbf{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 // Proceedings of Machine Learning Research 2021. Vol. 134. P. 4259--4299.

\end{thebibliography}

\end{document}

