Игра без значения

В математической теории игр, в частности, в непрерывных играх с нулевой суммой, не всякая игра имеет минимаксное значение. Это ожидаемое значение игры для одного из игроков, когда оба игрока придерживаются лучшей стратегии (которая выбирается исходя из плотности вероятности).

Данная статья даёт пример игры с нулевой суммой, которая не имеет минимаксного значение. Пример принадлежит Морису Сиону и Филипу Вольфу^[1].

Известно, что игры с нулевой суммой и конечным набором чистых стратегий имеют минимаксное значение (доказал Джон фон Нейман), но это не обязательно имеет место в случае игр, имеющих бесконечное число стратегий. Здесь приведён простой пример игры, не имеющей значения.

Существование таких игр с нулевой сумой представляет интерес, поскольку многие результаты теории игр становятся в этом случае неприменимы.

Игроки I и II выбирают числа ${\displaystyle x}$ и ${\displaystyle y}$ соответственно между 0 и 1. Выигрыш игрока I составляет $${\displaystyle K(x,y)={\begin{cases}-1&{\text{если }}x<y<x+{\frac {1}{2}},\\0&{\text{если }}x=y{\text{ or }}y=x+{\frac {1}{2}},\\1&{\text{в противном случае}}\end{cases}}}$$ То есть, после того, как выбор осуществлён, игрок II платит ${\displaystyle K(x,y)}$ игроку I (игра с нулевой суммой).

Если пару ${\displaystyle (x,y)}$ рассматривать как точку на единичном квадрате, рисунок показывает выигрыш игрока I. Игрок I может применить смешанную стратегию, выбирая число согласно плотности вероятности ${\displaystyle f}$, а игрок II, аналогично, выбирает смешанную стратегию согласно ${\displaystyle g}$. Игрок I пытается максимизировать выигрыш ${\displaystyle K(x,y)}$, а игрок II пытается минимизировать это значение, и каждый игрок знает цель противника.

Сион и Вольф показали, что $${\displaystyle \sup _{f}\inf _{g}\iint K\,df\,dg={\frac {1}{3}}}$$ и $${\displaystyle \inf _{g}\sup _{f}\iint K\,df\,dg={\frac {3}{7}}.}$$ Это максимальное и минимальное ожидаемое значение игры для игрока I и II.

Супремум и инфимум берутся по плотности вероятности на единичном интервале (фактически, борелевской мере). Таким образом, игрок I может обеспечить выигрыш по меньшей мере 3/7, если знает стратегию игрока II, а игрок II может обеспечить выигрыш меньше 1/3, если знает стратегию игрока I.

Нет никакого эпсилон-равновесия для достаточно малого ${\displaystyle \varepsilon }$, если ${\displaystyle \varepsilon <{\tfrac {1}{2}}\left({\tfrac {3}{7}}-{\tfrac {1}{3}}\right)\simeq 0,0476}$. Дасгупта и Маскин^[2] утверждают, что значения игры достигаются, если игрок I придаёт вес только множеству ${\displaystyle \left\{0,{\tfrac {1}{2}},1\right\}}$, а игрок II придаёт вес только множеству ${\displaystyle \left\{{\tfrac {1}{4}},{\tfrac {1}{2}},1\right\}}$.

Теорема Гликсберга показывает, что любая игра с нулевой суммой и полунепрерывной сверху или снизу функцией выигрыша имеет значение (в данном контексте, полунепрерывная сверху (снизу) функция K — это функция, для которой множество ${\displaystyle \{P\mid K(P)<c\}}$ (соответственно, ${\displaystyle \{P\mid K(P)>c\}}$) является открытым для любого вещественного c).

Функция выигрыша примера Сиона и Вольфа не является полунепрерывной, но может быть сделана таковой путём изменения значения K(x, x) и K(x, x + 1/2) (выигрыш вдоль двух разрывов) либо +1, либо −1, что делает выигрыш полунепрерывным сверху или снизу. Если это сделать, игра будет иметь значение.

Последующая работа Хойера^[3] обсуждает класс игр, в которых единичный квадрат разделён на три области и функция выигрыша постоянна для каждой области.