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

эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью от добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Непрерывная игра» – Новости · газеты · книги · ученый · JSTOR (Март 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

Определить п-пользовательская непрерывная игра ${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,}$ th набор чистых стратегий игрока,

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

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

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

Позволять ${displaystyle {oldsymbol {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} ({oldsymbol {sigma}}) = b_ {1} (sigma _ {- 1}) imes b_ {2} (sigma _ {- 2}) imes cdots imes b_ {n} (sigma _ {-n})}$.

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

Раздельные игры

А отделяемая игра - непрерывная игра, в которой для любого i функция полезности ${displaystyle u_ {i}: mathbf {C} o 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} в mathbf {C}}$, ${displaystyle s_ {i} в C_ {i}}$, ${displaystyle a_ {i ,,, k_ {1} ldots k_ {n}} в mathbb {R}}$, а функции ${displaystyle f_ {i ,,, k}: C_ {i} o mathbb {R}}$ непрерывны.

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

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

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

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

Примеры

Раздельные игры

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

Рассмотрим игру двух игроков с нулевой суммой. Икс и Y, с участием ${displaystyle C_ {X} = C_ {Y} = left [0,1ight]}$. Обозначим элементы ${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) = {egin {case} 1, & {mbox {if}} yin left [0,1 / 2ight) 0 {ext {or}} 1, & {mbox {if}} y = 1/2 0, & {mbox {if}} yin left (1 / 2,1ight] end {cases}}}$

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

${displaystyle b_ {X} (y),}$ и ${displaystyle b_ {Y} (x),}$ не пересекаются, значит, есть

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

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

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

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

${displaystyle {egin {выравнивается} mu _ {X1} geq mu _ {X2} mu _ {X1} ^ {2} leq mu _ {X2} end {выравнивается}} qquad {egin {выравнивается} mu _ {Y1} geq mu _ {Y2} mu _ {Y1} ^ {2} leq mu _ {Y2} конец {выровнено}}}$

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

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

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

${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.

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

Рациональная функция выплаты

Рассмотрим игру двух игроков с нулевой суммой. Икс и Y, с участием ${displaystyle C_ {X} = C_ {Y} = left [0,1ight]}$. Обозначим элементы ${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) = {гидроразрыв {(1 + x) (1 + y) (1-xy)} {(1 + xy) ^ {2}}}.}$

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

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

Ценность игры ${displaystyle 4 / pi}$.

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

Рассмотрим игру двух игроков с нулевой суммой. Икс и Y, с участием ${displaystyle C_ {X} = C_ {Y} = left [0,1ight]}$. Обозначим элементы ${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}} ight) ^ {n} -left ({frac {x} {3}} ight) ^ {n} ight) ight) left (2y ^ {n} -left (left (1- {frac {y} {3}} ight) ^ {n} -left ({frac {y} {3}} ight) ^ {n} ight) ight)}$.

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

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

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

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

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

использованная литература