Игра без ценности - Game without a value

Игровая клетка (то есть выигрыш для игрока I) для игры без значения из-за Сиона и Вулфа. Выплата 0 по двум диагональным линиям.

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

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

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

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

Игра

Игроки I и II выбирают номер, ${\displaystyle x}$ и ${\displaystyle y}$ соответственно, с ${\displaystyle x,y\in [0,1]}$; выигрыш для меня

${\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}}}$

(т.е. игрок II платит ${\displaystyle K(x,y)}$ игроку I; игра с нулевой суммой ). Иногда игрока I называют максимизирующий игрок и игрок II минимизация игрока.

Если ${\displaystyle (x,y)}$ интерпретируется как точка на единичном квадрате, цифра показывает выигрыш для игрока I. Теперь предположим, что игрок I применяет смешанную стратегию: выбирает число из функция плотности вероятности (pdf) ${\displaystyle f}$; игрок II выбирает из ${\displaystyle g}$. Игрок 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}}.}$

Это максимальное и минимальное ожидания ценности игры для игроков I и II соответственно.

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

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

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

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

Обобщения

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

Рекомендации

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