Игра без ценности

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

В этой статье приводится пример игры с нулевой суммой , которая не имеет никакой ценности . Она принадлежит Сиону и Вулфу . ^[1]

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

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

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

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

Сион и Вулф показывают, что но Это максимальные и минимальные ожидания ценности игры для игроков I и 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}}.}$$

И соответственно берут супремум и инфимум по pdf на единичном интервале (фактически меры вероятности Бореля ). Они представляют стратегии игрока I и игрока II (смешанные). Таким образом, игрок I может гарантировать себе выигрыш не менее 3/7, если он знает стратегию игрока II, а игрок II может удерживать выигрыш на уровне 1/3, если он знает стратегию игрока I.${\displaystyle \sup}$${\displaystyle \inf}$

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

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

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

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