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

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

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

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

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

Игра

Игроки I и II выбирают номера. $x$ и $y$ соответственно, от 0 до 1. Выигрыш игроку I равен $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. $K(x,y)$ игроку I (так что игра имеет нулевую сумму ).

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

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

не существует Эпсилон-равновесия для достаточно малых $\varepsilon$ , в частности, если $\varepsilon <{\frac {1}{2}}\left({\frac {3}{7}}-{\frac {1}{3}}\right)\simeq 0.0476$ . Дасгупта и машина ^[2] утверждать, что игровые значения достигаются, если игрок I помещает вес вероятности только в набор $\left\{0,1/2,1\right\}$ а игрок II придаёт вес только $\left\{1/4,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, сделав выигрыш верхним или нижний полунепрерывный соответственно. Если это будет сделано, игра будет иметь ценность.

Обобщения

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

Ссылки

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

[1] Сион, Морис; Вулф, Филипп (1957), «Об игре без ценности», Дрешер, М.; Такер, AW; Вулф, П. (ред.), Вклад в теорию игр III , Анналы математических исследований 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 .

[1]

[2]

[3]