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

Игровой квадрат (то есть выигрыш игрока I) для игры без ценности, согласно Sion и Wolfe. Выплата равна 0 вдоль двух диагональных линий

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

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

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

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

Игра

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

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

Ценность игры

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

Ссылки

1. Сион, Морис; Вулф, Филлип (1957), «Об игре без ценности», в Дрешер, М.; Такер, А. В.; Вулф, П. (ред.), Вклад в теорию игр III , Annals of Mathematics Studies 39, Princeton University Press, стр. 299–306, ISBN 9780691079363
2. П. Дасгупта и Э. Маскин (1986). «Существование равновесия в прерывистых экономических играх, I: Теория». Обзор экономических исследований . 53 (1): 1–26. doi :10.2307/2297588. JSTOR  2297588.
3. GA Heuer (2001). «Трехчастные игры разбиения на прямоугольниках». Теоретическая информатика . 259 : 639–661. doi : 10.1016/S0304-3975(00)00404-7 .