Непрерывная игра

Непрерывная игра — математическое понятие, используемое в теории игр , обобщающее идею обычной игры, такой как крестики-нолики (крестики-нолики) или шашки (шашки). Другими словами, это расширяет понятие дискретной игры, в которой игроки выбирают из конечного набора чистых стратегий. Концепции непрерывных игр позволяют играм включать более общие наборы чистых стратегий, которые могут быть несчетно бесконечными .

В общем, игра с несчетным множеством стратегий не обязательно будет иметь равновесное решение по Нэшу . Однако если наборы стратегий должны быть компактными , а функции полезности непрерывными , то равновесие по Нэшу будет гарантировано; это обобщение Гликсбергом теоремы Какутани о неподвижной точке . По этой причине класс непрерывных игр обычно определяется и изучается как подмножество более широкого класса бесконечных игр (т.е. игр с бесконечными множествами стратегий), в которых множества стратегий компактны, а функции полезности непрерывны.

Формальное определение

Определите n игроков. непрерывную игру для $G=(P,\mathbf {C} ,\mathbf {U} )$ где

$P={1,2,3,\ldots ,n}$ это набор $n\,$ игроки,

$\mathbf {C} =(C_{1},C_{2},\ldots ,C_{n})$ где каждый $C_{i}\,$ — компакт в метрическом пространстве , соответствующий $i\,$ набор чистых стратегий игрока,

$\mathbf {U} =(u_{1},u_{2},\ldots ,u_{n})$ где $u_{i}:\mathbf {C} \to \mathbb {R}$ функция полезности игрока $i\,$

Мы определяем $\Delta _{i}\,$ быть набором борелевских вероятностных мер на $C_{i}\,$, что дает нам пространство смешанных стратегий игрока i .

Определите профиль стратегии ${\boldsymbol {\sigma }}=(\sigma _{1},\sigma _{2},\ldots ,\sigma _{n})$ где $\sigma _{i}\in \Delta _{i}\,$

Позволять ${\boldsymbol {\sigma }}_{-i}$ быть стратегическим профилем всех игроков, кроме игрока $i$. Как и в дискретных играх, мы можем определить ответа наилучшее соответствие для игрока. $i\,$, $b_{i}\$. $b_{i}\,$ — это отношение множества всех распределений вероятностей по профилям игроков противника к множеству игроков $i$стратегии, такие, что каждый элемент

$b_{i}(\sigma _{-i})\,$

это лучший ответ на $\sigma _{-i}$. Определять

$\mathbf {b} ({\boldsymbol {\sigma }})=b_{1}(\sigma _{-1})\times b_{2}(\sigma _{-2})\times \cdots \times b_{n}(\sigma _{-n})$.

Профиль стратегии ${\boldsymbol {\sigma }}*$ является равновесием по Нэшу тогда и только тогда, когда ${\boldsymbol {\sigma }}*\in \mathbf {b} ({\boldsymbol {\sigma }}*)$Существование равновесия Нэша для любой непрерывной игры с непрерывными функциями полезности можно доказать, используя Ирвинга Гликсберга обобщение теоремы Какутани о неподвижной точке . В общем, решения может не быть, если мы допустим пространства стратегий, $C_{i}\,$которые не являются компактными, или если мы допускаем ненепрерывные функции полезности.

Разделимые игры

Сепарабельная игра — это непрерывная игра, в которой для любого i функция полезности $u_{i}:\mathbf {C} \to \mathbb {R}$ можно выразить в виде суммы произведений:

$u_{i}(\mathbf {s} )=\sum _{k_{1}=1}^{m_{1}}\ldots \sum _{k_{n}=1}^{m_{n}}a_{i\,,\,k_{1}\ldots k_{n}}f_{1}(s_{1})\ldots f_{n}(s_{n})$, где $\mathbf {s} \in \mathbf {C}$, $s_{i}\in C_{i}$, $a_{i\,,\,k_{1}\ldots k_{n}}\in \mathbb {R}$, а функции $f_{i\,,\,k}:C_{i}\to \mathbb {R}$ являются непрерывными.

Полиномиальная игра – это сепарабельная игра, в которой каждый $C_{i}\,$ представляет собой компактный интервал на $\mathbb {R} \,$ и каждая функция полезности может быть записана как многомерный полином.

В общем, смешанные равновесия Нэша в разделимых играх легче вычислить, чем в несепарабельных играх, как это следует из следующей теоремы:

Для любой сепарабельной игры существует хотя бы одно равновесие Нэша, при котором игрок i смешивает не более $m_{i}+1\,$ чистые стратегии.

В то время как равновесная стратегия для несепарабельной игры может потребовать несчетной бесконечной поддержки , сепарабельная игра гарантированно будет иметь по крайней мере одно равновесие Нэша со смешанными стратегиями с конечным носителем.

Примеры

Разделимые игры

Полиномиальная игра

Рассмотрим игру для двух игроков с нулевой суммой между игроками X и Y , где $C_{X}=C_{Y}=\left[0,1\right]$. Обозначим элементы $C_{X}\,$ и $C_{Y}\,$ как $x\,$ и $y\,$ соответственно. Определите функции полезности $H(x,y)=u_{x}(x,y)=-u_{y}(x,y)\,$ где

$H(x,y)=(x-y)^{2}\,$.

Соотношения наилучшего ответа в чистой стратегии таковы:

$b_{X}(y)={\begin{cases}1,&{\mbox{if }}y\in \left[0,1/2\right)\\0{\text{ or }}1,&{\mbox{if }}y=1/2\\0,&{\mbox{if }}y\in \left(1/2,1\right]\end{cases}}$

$b_{Y}(x)=x\,$

$b_{X}(y)\,$ и $b_{Y}(x)\,$ не пересекаются, поэтому чистой стратегии равновесия Нэша не существует.Однако должно существовать равновесие смешанной стратегии. Чтобы найти его, выразите ожидаемое значение: $v=\mathbb {E} [H(x,y)]$ как линейная комбинация первого и второго моментов вероятностных распределений X и Y :

$v=\mu _{X2}-2\mu _{X1}\mu _{Y1}+\mu _{Y2}\,$

(где $\mu _{XN}=\mathbb {E} [x^{N}]$ и аналогично для Y ).

Ограничения на $\mu _{X1}\,$ и $\mu _{X2}$ (с аналогичными ограничениями для y ,) задаются Хаусдорфом как:

${\begin{aligned}\mu _{X1}\geq \mu _{X2}\\\mu _{X1}^{2}\leq \mu _{X2}\end{aligned}}\qquad {\begin{aligned}\mu _{Y1}\geq \mu _{Y2}\\\mu _{Y1}^{2}\leq \mu _{Y2}\end{aligned}}$

Каждая пара ограничений определяет компактное выпуклое подмножество на плоскости. С $v\,$ линейно, любые экстремумы относительно первых двух моментов игрока будут лежать на границе этого подмножества. Равновесная стратегия игрока i будет лежать на

$\mu _{i1}=\mu _{i2}{\text{ or }}\mu _{i1}^{2}=\mu _{i2}$

Обратите внимание, что первое уравнение допускает только смеси 0 и 1, тогда как второе уравнение допускает только чистые стратегии. Более того, если лучший ответ в определенный момент игроку i лежит на $\mu _{i1}=\mu _{i2}\,$, оно будет лежать на всей строке, так что лучшим ответом будут и 0, и 1. $b_{Y}(\mu _{X1},\mu _{X2})\,$ просто дает чистую стратегию $y=\mu _{X1}\,$, так $b_{Y}\,$ никогда не даст одновременно 0 и 1.Однако $b_{x}\,$ дает как 0, так и 1, когда y = 1/2.Равновесие по Нэшу существует, когда:

$(\mu _{X1}*,\mu _{X2}*,\mu _{Y1}*,\mu _{Y2}*)=(1/2,1/2,1/2,1/4)\,$

Это определяет одно уникальное равновесие, в котором Игрок X играет случайную смесь 0 в течение 1/2 времени и 1 в остальных 1/2 времени. Игрок Y играет по чистой стратегии 1/2. Стоимость игры 1/4.

Неразделимые игры

функция

Рассмотрим игру для двух игроков с нулевой суммой между игроками X и Y , где $C_{X}=C_{Y}=\left[0,1\right]$. Обозначим элементы $C_{X}\,$ и $C_{Y}\,$ как $x\,$ и $y\,$ соответственно. Определите функции полезности $H(x,y)=u_{x}(x,y)=-u_{y}(x,y)\,$ где

$H(x,y)={\frac {(1+x)(1+y)(1-xy)}{(1+xy)^{2}}}.$

В этой игре нет равновесия по Нэшу в чистой стратегии. Это можно показать что существует уникальное равновесие Нэша смешанной стратегии со следующей парой кумулятивных функций распределения :

$G^{*}(y)={\frac {4}{\pi }}\arctan {\sqrt {x}}\qquad G^{*}(y)={\frac {4}{\pi }}\arctan {\sqrt {y}}.$

Или, что то же самое, следующая пара функций плотности вероятности :

$f^{*}(x)={\frac {2}{\pi {\sqrt {x}}(1+x)}}\qquad g^{*}(y)={\frac {2}{\pi {\sqrt {y}}(1+y)}}.$

Ценность игры в том, $4/\pi$.

дистрибутив

Рассмотрим игру для двух игроков с нулевой суммой между игроками X и Y , где $C_{X}=C_{Y}=\left[0,1\right]$. Обозначим элементы $C_{X}\,$ и $C_{Y}\,$ как $x\,$ и $y\,$ соответственно. Определите функции полезности $H(x,y)=u_{x}(x,y)=-u_{y}(x,y)\,$ где

$H(x,y)=\sum _{n=0}^{\infty }{\frac {1}{2^{n}}}\left(2x^{n}-\left(\left(1-{\frac {x}{3}}\right)^{n}-\left({\frac {x}{3}}\right)^{n}\right)\right)\left(2y^{n}-\left(\left(1-{\frac {y}{3}}\right)^{n}-\left({\frac {y}{3}}\right)^{n}\right)\right)$.

Эта игра имеет уникальное равновесие смешанной стратегии, где каждый игрок играет смешанную стратегию с сингулярной функцией Кантора в качестве кумулятивной функции распределения .

Дальнейшее чтение

• Х.В. Кун и А.В. Такер, ред. (1950). Вклад в теорию игр: Том. II. Анналы математических исследований 28 . Издательство Принстонского университета. ISBN   0-691-07935-8 .

См. также

• График непрерывный