В теории игр концепция решения — это формальное правило для прогнозирования того, как будет проходить игра. Эти прогнозы называются «решениями» и описывают, какие стратегии будут приняты игроками и, следовательно, результат игры. Наиболее часто используемые концепции решения — это концепции равновесия , наиболее известное из которых — равновесие Нэша .
Многие концепции решений для многих игр приведут к более чем одному решению. Это ставит под сомнение любое из решений, поэтому теоретик игр может применить уточнение , чтобы сузить решения. Каждая последующая концепция решения, представленная ниже, улучшает свою предшественницу, устраняя неправдоподобные равновесия в более богатых играх.
Пусть будет классом всех игр и для каждой игры пусть будет набором профилей стратегий . Концепция решения является элементом прямого произведения , т.е. функцией такой, что для всех
В этой концепции решения предполагается, что игроки рациональны, и поэтому строго доминируемые стратегии исключаются из набора стратегий, которые могут быть реализованы. Стратегия строго доминируется , когда игроку доступна некоторая другая стратегия, которая всегда имеет более высокий выигрыш, независимо от стратегий, которые выбирают другие игроки. (Строго доминируемые стратегии также важны в поиске минимаксного дерева игры .) Например, в дилемме заключенных (один период) (показанной ниже) сотрудничество строго доминируется дефектом для обоих игроков, потому что любой игрок всегда лучше, играя дефект , независимо от того, что делает его противник.
Равновесие Нэша — это профиль стратегии (профиль стратегии определяет стратегию для каждого игрока, например, в приведенной выше игре «Дилемма заключенных» ( сотрудничать , предать ) определяется, что заключенный 1 играет в «сотрудничать» , а заключенный 2 играет в «предать »), в котором каждая стратегия, разыгрываемая каждым агентом (агентом i), является наилучшим ответом на каждую другую стратегию, разыгрываемую всеми остальными противниками (агентами j для каждого j≠i). Стратегия игрока является наилучшим ответом на стратегию другого игрока, если нет другой стратегии, которую можно было бы разыграть и которая дала бы более высокий выигрыш в любой ситуации, в которой разыгрывается стратегия другого игрока.
В некоторых играх существует несколько равновесий Нэша, но не все из них реалистичны. В динамических играх обратная индукция может использоваться для устранения нереалистичных равновесий Нэша. Обратная индукция предполагает, что игроки рациональны и будут принимать наилучшие решения на основе своих будущих ожиданий. Это устраняет невероятные угрозы, которые игрок не стал бы выполнять, если бы его когда-либо призвали это сделать.
Например, рассмотрим динамическую игру с действующей фирмой и потенциальным участником отрасли. Действующий имеет монополию и хочет сохранить свою долю рынка. Если новичок входит, действующий может либо бороться, либо приспосабливаться к новичку. Если действующий приспосабливается, новичок войдет и получит прибыль. Если действующий будет бороться, он снизит свои цены, вытеснит новичка из бизнеса (понеся издержки выхода) и нанесет ущерб своей собственной прибыли.
Лучший ответ для действующего лица, если новичок вступает, — это приспособиться, а лучший ответ для действующего лица, если новичок вступает, — это войти. Это приводит к равновесию Нэша. Однако, если действующее лицо выбирает борьбу, лучший ответ для действующего лица — не вступать. Если новичок не вступает, не имеет значения, что именно выберет действующее лицо. Следовательно, борьба может считаться лучшим ответом для действующего лица, если новичок не вступает, что приводит к другому равновесию Нэша.
Однако это второе равновесие Нэша может быть устранено обратной индукцией, поскольку оно опирается на невероятную угрозу со стороны действующего лица. К тому времени, когда действующее лицо достигнет узла принятия решений, где оно может выбрать борьбу, это будет нерационально, поскольку новичок уже вошел. Таким образом, обратная индукция устраняет это нереалистичное равновесие Нэша.
Смотрите также:
Обобщением обратной индукции является совершенство подигры. Обратная индукция предполагает, что вся будущая игра будет рациональной. В совершенных равновесиях подигры игра в каждой подигре рациональна (в частности, равновесие Нэша). Обратная индукция может использоваться только в завершающих (конечных) играх определенной длины и не может применяться к играм с несовершенной информацией . В этих случаях можно использовать совершенство подигры. Устраненное равновесие Нэша, описанное выше, является несовершенным подигрой, потому что оно не является равновесием Нэша подигры, которая начинается в узле, достигнутом после того, как вошел участник.
Иногда подигровое совершенство не накладывает достаточно большого ограничения на необоснованные результаты. Например, поскольку подигры не могут прорезать информационные множества , игра с несовершенной информацией может иметь только одну подигру — себя — и, следовательно, подигровое совершенство не может быть использовано для устранения любых равновесий Нэша. Идеальное байесовское равновесие (PBE) — это спецификация стратегий и убеждений игроков о том, какой узел в информационном множестве был достигнут в ходе игры. Убеждение об узле решения — это вероятность того, что конкретный игрок думает, что этот узел находится или будет находиться в игре (на пути равновесия ). В частности, интуиция PBE заключается в том, что он определяет стратегии игроков, которые являются рациональными, учитывая указанные им убеждения игроков, а указанные им убеждения согласуются со стратегиями, которые он определяет.
В байесовской игре стратегия определяет, что игрок играет на каждом информационном наборе, контролируемом этим игроком. Требование, чтобы убеждения соответствовали стратегиям, не является чем-то определенным в совершенстве подигры. Следовательно, PBE является условием согласованности убеждений игроков. Так же, как в равновесии Нэша ни одна стратегия игрока не является строго доминируемой, в PBE ни для одного информационного набора ни одна стратегия игрока не является строго доминируемой, начиная с этого информационного набора. То есть для каждого убеждения, которого игрок может придерживаться на этом информационном наборе, нет стратегии, которая дает больший ожидаемый выигрыш для этого игрока. В отличие от приведенных выше концепций решения, ни одна стратегия игрока не является строго доминируемой, начиная с любого информационного набора, даже если он находится вне равновесного пути. Таким образом, в PBE игроки не могут угрожать игрой в стратегии, которые строго доминируются, начиная с любого информационного набора вне равновесного пути.
Байесовский в названии этой концепции решения намекает на тот факт, что игроки обновляют свои убеждения в соответствии с теоремой Байеса . Они вычисляют вероятности, учитывая то, что уже произошло в игре.
Прямая индукция так называется, потому что так же, как обратная индукция предполагает, что будущая игра будет рациональной, прямая индукция предполагает, что прошлая игра была рациональной. Когда игрок не знает, к какому типу относится другой игрок (т. е. имеется несовершенная и асимметричная информация), этот игрок может сформировать убеждение о том, к какому типу относится этот игрок, наблюдая за прошлыми действиями этого игрока. Следовательно, убеждение, сформированное этим игроком о вероятности того, что противник будет определенного типа, основано на прошлой игре этого противника, который был рациональным. Игрок может выбрать сигнализировать о своем типе посредством своих действий.
Kohlberg и Mertens (1986) ввели концепцию решения Stable balance, уточнение, которое удовлетворяет прямой индукции. Был найден контрпример, где такое стабильное равновесие не удовлетворяло обратной индукции. Чтобы решить эту проблему, Жан-Франсуа Мертенс ввел то, что теоретики игр теперь называют концепцией стабильного равновесия Мертенса , вероятно, первую концепцию решения, удовлетворяющую как прямой, так и обратной индукции.
Прямая индукция дает уникальное решение для игры со сжиганием денег .
