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

Обобщение игр, используемых в теории игр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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})}$, где , , , и функции непрерывны. ${\displaystyle \mathbf {s} \in \mathbf {C} }$ ${\displaystyle s_{i}\in C_{i}}$ ${\displaystyle a_{i\,,\,k_{1}\ldots k_{n}}\in \mathbb {R} }$ ${\displaystyle f_{i\,,\,k}:C_{i}\to \mathbb {R} }$

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

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

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

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

Примеры

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

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

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

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

Соотношения наилучшего ответа в чистой стратегии следующие:

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

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

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

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

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

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

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

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

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

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

${\displaystyle (\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 , где . Обозначим элементы и как и соответственно. Определим функции полезности , где ${\displaystyle C_{X}=C_{Y}=\left[0,1\right]}$ ${\displaystyle C_{X}\,}$ ${\displaystyle C_{Y}\,}$ ${\displaystyle x\,}$ ${\displaystyle y\,}$ ${\displaystyle H(x,y)=u_{x}(x,y)=-u_{y}(x,y)\,}$

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

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

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

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

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

Стоимость игры составляет . ${\displaystyle 4/\pi }$

Требование распределения Кантора

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

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

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

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

• HW Kuhn и AW Tucker, ред. (1950). Вклад в теорию игр: т. II. Annals of Mathematics Studies 28 . Princeton University Press. ISBN  0-691-07935-8 .

Смотрите также

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

Ссылки

1. IL Glicksberg. Дальнейшее обобщение теоремы Какутани о неподвижной точке с применением к точкам равновесия Нэша. Труды Американского математического общества, 3(1):170–174, февраль 1952 г.
2. Н. Стайн, А. Оздаглар и П. А. Паррило. «Разделимые и низкоранговые непрерывные игры». Международный журнал теории игр , 37(4):475–504, декабрь 2008 г. https://arxiv.org/abs/0707.3462
3. Ирвинг Леонард Гликсберг и Оливер Альфред Гросс (1950). «Заметки об играх над квадратом». Кун, Х. У. и Такер, А. В. ред. Вклад в теорию игр: том II. Анналы математических исследований 28 , стр. 173–183. Издательство Принстонского университета.
4. Гросс, О. (1952). «Рациональная характеристика выигрыша распределения Кантора». Технический отчет D-1349, Корпорация RAND.