Непрерывная игра
Эта статья нуждается в дополнительных ссылок для проверки . ( март 2009 г. ) |
Непрерывная игра — математическое понятие, используемое в теории игр , обобщающее идею обычной игры, такой как крестики-нолики (крестики-нолики) или шашки (шашки). Другими словами, это расширяет понятие дискретной игры, в которой игроки выбирают из конечного набора чистых стратегий. Концепции непрерывных игр позволяют играм включать более общие наборы чистых стратегий, которые могут быть несчетно бесконечными .
В общем, игра с несчетным множеством стратегий не обязательно будет иметь равновесное решение по Нэшу . Однако если наборы стратегий должны быть компактными , а функции полезности непрерывными , то равновесие по Нэшу будет гарантировано; это обобщение Гликсбергом теоремы Какутани о неподвижной точке . По этой причине класс непрерывных игр обычно определяется и изучается как подмножество более широкого класса бесконечных игр (т.е. игр с бесконечными множествами стратегий), в которых множества стратегий компактны, а функции полезности непрерывны.
Формальное определение [ править ]
Определите n игроков. непрерывную игру для где
- это набор игроки,
- где каждый — компакт в метрическом пространстве , соответствующий , набор чистых стратегий игрока
- где функция полезности игрока
- Мы определяем быть набором борелевских вероятностных мер на , что дает нам пространство смешанных стратегий игрока i .
- Определите профиль стратегии где
Позволять быть стратегическим профилем всех игроков, кроме игрока . Как и в дискретных играх, мы можем определить наилучшее соответствие ответа для игрока. , . — это отношение множества всех распределений вероятностей по профилям игроков противника к множеству игроков стратегии, такие, что каждый элемент
это лучший ответ на . Определять
- .
Профиль стратегии является равновесием по Нэшу тогда и только тогда, когда Существование равновесия Нэша для любой непрерывной игры с непрерывными функциями полезности можно доказать, используя Ирвинга Гликсберга обобщение теоремы Какутани о неподвижной точке . [1] В общем, решения может не быть, если мы допустим пространства стратегий, которые не являются компактными, или если мы допускаем ненепрерывные функции полезности.
Разделимые игры [ править ]
Сепарабельная игра — это непрерывная игра, в которой для любого i функция полезности можно выразить в виде суммы произведений:
- , где , , , а функции являются непрерывными.
Полиномиальная игра — это сепарабельная игра, в которой каждый представляет собой компактный интервал на и каждая функция полезности может быть записана как многомерный полином.
В общем, смешанные равновесия Нэша в разделимых играх легче вычислить, чем в несепарабельных играх, как это следует из следующей теоремы:
- Для любой сепарабельной игры существует хотя бы одно равновесие Нэша, при котором игрок i смешивает не более чистые стратегии. [2]
В то время как равновесная стратегия для несепарабельной игры может потребовать несчетной бесконечной поддержки , сепарабельная игра гарантированно будет иметь по крайней мере одно равновесие Нэша со смешанными стратегиями с конечным носителем.
Примеры [ править ]
Разделимые игры [ править ]
Полиномиальная игра [ править ]
Рассмотрим игру для двух игроков с нулевой суммой между игроками X и Y , причем . Обозначим элементы и как и соответственно. Определите функции полезности где
- .
Соотношения наилучшего ответа в чистой стратегии таковы:
и не пересекаются, поэтому не существует чистой стратегии равновесия Нэша. Однако должно быть равновесие смешанной стратегии. Чтобы найти его, выразите ожидаемое значение: как линейная комбинация первого и второго моментов вероятностных распределений X и Y :
(где и аналогично для Y ).
Ограничения на и (с аналогичными ограничениями для y ,) определяются Хаусдорфом как:
Каждая пара ограничений определяет компактное выпуклое подмножество на плоскости. С линейно, любые экстремумы относительно первых двух моментов игрока будут лежать на границе этого подмножества. Равновесная стратегия игрока i будет лежать на
Обратите внимание, что первое уравнение допускает только смеси 0 и 1, тогда как второе уравнение допускает только чистые стратегии. Более того, если лучший ответ в определенный момент игроку i лежит на , оно будет лежать на всей строке, так что лучшим ответом будут и 0, и 1. просто дает чистую стратегию , так никогда не даст одновременно 0 и 1. Однако дает как 0, так и 1, когда y = 1/2. Равновесие по Нэшу существует, когда:
Это определяет одно уникальное равновесие, в котором Игрок X играет случайную смесь 0 в течение 1/2 времени и 1 в остальных 1/2 времени. Игрок Y играет по чистой стратегии 1/2. Стоимость игры 1/4.
Неразделимые игры [ править ]
Рациональная выигрыша функция
Рассмотрим игру для двух игроков с нулевой суммой между игроками X и Y , причем . Обозначим элементы и как и соответственно. Определите функции полезности где
В этой игре нет равновесия по Нэшу в чистой стратегии. Это можно показать [3] что существует уникальное равновесие Нэша смешанной стратегии со следующей парой кумулятивных функций распределения :
Или, что то же самое, следующая пара функций плотности вероятности :
Ценность игры в том, .
Cantor Требуется дистрибутив
Рассмотрим игру для двух игроков с нулевой суммой между игроками X и Y , причем . Обозначим элементы и как и соответственно. Определите функции полезности где
- .
Эта игра имеет уникальное равновесие смешанной стратегии, где каждый игрок играет смешанную стратегию с сингулярной функцией Кантора в качестве кумулятивной функции распределения . [4]
Дальнейшее чтение [ править ]
- Х.В. Кун и А.В. Такер, ред. (1950). Вклад в теорию игр: Том. II. Анналы математических исследований 28 . Издательство Принстонского университета. ISBN 0-691-07935-8 .
См. также [ править ]
Ссылки [ править ]
- ^ И. Л. Гликсберг. Дальнейшее обобщение теоремы Какутани о неподвижной точке с применением к точкам равновесия Нэша. Труды Американского математического общества, 3 (1): 170–174, февраль 1952 г.
- ^ Н. Штайн, А. Оздаглар и П. А. Паррило. «Сепарабельные и непрерывные игры низкого ранга». Международный журнал теории игр , 37(4):475–504, декабрь 2008 г. https://arxiv.org/abs/0707.3462.
- ^ Ирвинг Леонард Гликсберг и Оливер Альфред Гросс (1950). «Записки об играх на площади». Кун, HW и Такер, AW, ред. Вклад в теорию игр: Том II. Анналы математических исследований 28 , стр. 173–183. Издательство Принстонского университета.
- ^ Гросс, О. (1952). «Рациональная характеристика распределения Кантора». Технический Отчет D-1349, Корпорация РЭНД.