Игра без значения
В математической теории игр, в рамках изучения антагонистических игр, существует важное понятие минимаксного значения — математического ожидания выигрыша для одного из участников при условии, что оба противника применяют оптимальные стратегии, основанные на вероятностных распределениях. Однако не каждая игра обладает таким значением. Данная статья представляет пример антагонистической игры без минимаксного значения, предложенный Морисом Сионом и Филипом Вольфом.
Хотя игры с нулевой суммой и конечным набором чистых стратегий всегда имеют минимаксное значение (этот факт доказал Джон фон Нейман), в случае игр с бесконечным числом стратегий это свойство может не выполняться. Приведённый здесь простой пример иллюстрирует такую ситуацию. Существование подобных игр с нулевой суммой представляет теоретический интерес, поскольку многие классические результаты теории игр в этом случае теряют свою применимость.
- Описание игры
Участники, обозначенные как игрок I и игрок II, независимо выбирают числа \(x\) и \(y\) соответственно из интервала от 0 до 1. Функция выигрыша игрока I задаётся следующим образом:
\[ K(x,y)= \begin{cases}
-1 & \text{если } x < y < x + \frac{1}{2}, \\
0 & \text{если } x = y \text{ или } y = x + \frac{1}{2},\\
1 & \text{в остальных случаях}
\end{cases} \]
Таким образом, после выбора чисел игрок II выплачивает игроку I сумму \(K(x,y)\), что соответствует антагонистической игре с нулевой суммой. Если интерпретировать пару \((x,y)\) как точку на единичном квадрате, то график функции показывает зоны выигрыша игрока I. Оба участника могут использовать смешанные стратегии, выбирая числа в соответствии с плотностями вероятности \(f\) и \(g\) соответственно. Игрок I стремится максимизировать значение \(K(x, y)\), в то время как игрок II пытается его минимизировать, причём каждый осведомлён о цели оппонента.
- Анализ значения игры
Сион и Вольф продемонстрировали, что:
\[ \sup_f \inf_g \iint K\,df\,dg = \frac{1}{3} \]
и
\[ \inf_g \sup_f \iint K\,df\,dg = \frac{3}{7} \]
Эти выражения представляют максимальное и минимальное ожидаемые значения выигрыша для игрока I. Супремум и инфимум берутся по всем вероятностным распределениям на единичном интервале (в рамках борелевской сигма-алгебры). Следовательно, игрок I может гарантировать себе выигрыш не менее \(3/7\), если ему известна стратегия противника, а игрок II способен ограничить выигрыш оппонента величиной менее \(1/3\) при аналогичных условиях.
Для достаточно малых \(\varepsilon\), где \(\varepsilon < \frac{1}{2}\left(\frac{3}{7} - \frac{1}{3}\right) \approx 0,0476\), в данной игре отсутствует \(\varepsilon\)-равновесие. Даcгупта и Маскин утверждают, что значения игры достигаются, если игрок I сосредотачивает вес стратегии на множестве \(\left\{0, \frac{1}{2}, 1\right\}\), а игрок II — на множестве \(\left\{\frac{1}{4}, \frac{1}{2}, 1\right\}\).
Исследования показывают, что любая игра с нулевой суммой и полунепрерывной функцией выигрыша имеет минимаксное значение. В данном контексте полунепрерывная сверху (снизу) функция \(K\) определяется так, что множество \(\{P \mid K(P) < c\}\) (или \(\{P \mid K(P) > c\}\)) является открытым для любого вещественного числа \(c\). Функция выигрыша в примере Сиона и Вольфа не обладает полунепрерывностью, но её можно модифицировать, изменив значения \(K(x, x)\) и \(K(x, x + 1/2)\) (в точках разрыва) на \(+1\) или \(-1\), что придаст функции свойство полунепрерывности сверху или снизу и обеспечит наличие значения у игры.
- Обобщения
В последующих работах, таких как исследование Хойера, рассматривается класс игр, в которых единичный квадрат разделён на три области, а функция выигрыша остаётся постоянной в пределах каждой из них.
- Литература
Категория: Некооперативные игры Категория: Математические примеры