Лучший ответ

В теории игр, лучший ответ - это стратегия (или стратегии), которая дает наиболее благоприятный исход для игрока, принимая стратегии других игроков как данность (Fudenberg Tirole 1991, p. 29; Гиббонс 1992, стр. 33–49). Концепция наилучшего ответа является центральной в наиболее известном вкладе Джона Нэша, равновесие Нэша, точка, в которой каждый игрок в игре выбирает лучший ответ (или один из лучшие ответы) на стратегии других игроков (Нэш 1950).

• 1 Переписка
  • 1.1 Координационные игры
  • 1.2 Антикоординированные игры
  • 1.3 Игры с доминирующими стратегиями
  • 1.4 Другие (асимметричные по выплатам) игры
  • 1.5 Соответствующие пенни
• 2 Динамика
• 3 Сглаженный
• 4 См. Также
• 5 Ссылки

Рисунок 1. Соответствие реакций для игрока Y в игре Stag Hunt.

Реакции соответствий, также известные как соответствия наилучшего ответа, используются в доказательстве существования смешанной стратегии равновесия по Нэшу (Fudenberg Tirole 1991, раздел 1.3.B; Osborne Rubinstein 1994, раздел 2.2). Соответствия реакции не являются «функциями реакции», поскольку функции должны иметь только одно значение для каждого аргумента, и многие соответствия реакции будут неопределенными, то есть вертикальной линией, для некоторого выбора стратегии противника. Создается соответствие $b\; (\cdot )\; \{\backslash \; displaystyle\; b\; (\backslash \; cdot)\}$для каждого игрока из набора профилей стратегии оппонента в набор стратегий игрока. Итак, для любого заданного набора стратегий оппонента $\sigma \; -\; i\; \{\backslash \; displaystyle\; \backslash \; sigma\; \_\; \{-\; i\}\}$, $bi\; (\sigma \; -\; i)\; \{\backslash \; displaystyle\; b\_\; \{i\}\; (\backslash \; sigma\; \_\; \{-\; i\})\}$представляет лучшие ответы игрока i на $\sigma \; -\; i\; \{\backslash \; displaystyle\; \backslash \; sigma\; \_\; \{-\; i\}\}$.

Рис. 2. Соответствие реакций игрока X в игре Stag Hunt.

Соответствия ответов для всех игр 2x2 нормальной формы могут быть нарисованы с помощью линии для каждого игрока в единичном квадрате стратегии пробел. На рисунках 1–3 показаны графики соответствия наилучшего ответа для игры охота на оленя. Пунктирная линия на рисунке 1 показывает оптимальную вероятность того, что игрок Y играет «оленя» (по оси y), как функцию вероятности того, что игрок X играет оленя (показано по оси абсцисс). На рисунке 2 пунктирная линия показывает оптимальную вероятность того, что игрок X играет «оленя» (показано на оси x), как функцию вероятности того, что игрок Y играет в олень (показано на оси y). Обратите внимание, что на рис. 2 показаны независимые переменные и response на осях, противоположных тем, которые обычно используются, так что их можно наложить на предыдущий график, чтобы показать равновесия Нэша. в точках совпадения лучших ответов двух игроков на рис. 3.

Есть три различных формы соответствия реакций, по одной для каждого из трех типов симметричных игр 2x2: координация игры, игры с дискоординацией и игры с доминирующими стратегиями (тривиальный четвертый случай, когда выплаты всегда равны для обоих ходов, на самом деле не является теоретической проблемой игры). Любая симметричная игра 2x2 с выигрышем примет одну из этих трех форм.

Игры на координацию

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

Антикоординирующие игры

Рис. 3. Соответствие реакций обоих игроков в игре Stag Hunt. Равновесие Нэша, показанное точками, в которых соответствия двух игроков совпадают, т. Е. Перекрестные

Игры, такие как игра в цыпленка и игра в ястреб-голубь, в которых игроки набирают больше всего очков, когда выбирают противоположные стратегии, т. е. дискоординированные, называются антикоординированными играми. У них есть соответствия реакций (рис.4), которые пересекаются в направлении, противоположном координационным играм, с тремя равновесиями Нэша, по одному в каждом из верхнего левого и нижнего правого углов, где один игрок выбирает одну стратегию, другой игрок выбирает противоположную стратегию. Третье равновесие по Нэшу - это смешанная стратегия, лежащая по диагонали от нижнего левого до верхнего правого углов. Если игроки не знают, какой из них какой, то смешанная стратегия Нэша является эволюционно устойчивой стратегией (ESS), поскольку игра ограничивается диагональной линией от нижнего левого угла до верхнего правого угла. В противном случае говорят, что существует некоррелированная асимметрия, а угловые равновесия Нэша являются ESS.

Рис. 4. Соответствие реакций обоих игроков в игре «Ястреб-голубь». Равновесия по Нэшу показаны точками, в которых соответствия двух игроков совпадают, т.е. пересекаются

Игры с доминирующими стратегиями

Рисунок 5. Соответствие реакций для игры с доминирующей стратегией.

Игры с доминирующими У стратегий есть соответствия реакций, которые пересекаются только в одной точке, которая будет либо в нижнем левом, либо в правом верхнем углу в играх с симметричной выплатой 2x2. Например, в одиночной игре дилемма заключенного, ход «Сотрудничать» не является оптимальным для любой вероятности сотрудничества оппонента. На рис. 5 показано соответствие реакций для такой игры, где размерности - «вероятностная игра в сотрудничестве», а равновесие по Нэшу находится в нижнем левом углу, где ни один из игроков не играет в кооперацию. Если бы размеры были определены как «Дефект вероятностной игры», тогда кривые наилучшего ответа обоих игроков были бы равны 1 для всех вероятностей стратегии оппонента, а соответствия реакций пересекались бы (и формировали равновесие по Нэшу) в верхнем правом углу.

Другие (асимметричные игры)

В играх 2x2 с асимметрией выплат возможен более широкий диапазон форм соответствий реакций. Для каждого игрока существует пять возможных наилучших форм реакции, показанных на рисунке 6. Слева направо: стратегия доминирования (всегда игра 2), стратегия доминирования (всегда игра 1), рост (стратегия игры 2, если вероятность того, что другой игрок количество игр 2 выше порога), падающее (стратегия игры 1, если вероятность того, что другой игрок играет 2 выше порога) и безразличие (обе стратегии играют одинаково хорошо при любых условиях).

Рисунок 6. Пять возможных соответствий реакций для игрока в игре 2x2. Предполагается, что оси показывают вероятность того, что игрок использует свою стратегию 1. Слева направо: A) Всегда играйте 2, стратегия 1 - это B) Всегда играйте 1, стратегия 2 преобладает, C) Стратегия 1 лучше всего, когда противник играет свою стратегию 1, и стратегию 2 лучше всего, когда противник играет свою 2, D) Стратегия 1 лучше всего, когда противник играет свою стратегию 2, и 2 лучше, когда играет противник его 1, E) Обе стратегии работают одинаково хорошо, независимо от того, что играет противник.

Хотя существует только четыре возможных типа симметричных игр 2x2 с выплатами (из которых один является тривиальным), пять различных кривых наилучшего ответа для каждого игрока позволяют большее количество видов асимметричной игры с выплатами. Многие из них на самом деле не отличаются друг от друга. Измерения можно переопределить (обменять названиями стратегий 1 и 2) для создания симметричных игр, которые логически идентичны.

Сопоставление пенни

Одной из хорошо известных игр с асимметрией выплат является игра сопоставление пенни. В этой игре один игрок, играющий по ряду, изображенный на графике в измерении y, выигрывает, если игроки координируют свои действия (оба выбирают орла или оба выбирают решку), в то время как другой игрок, игрок столбца, показанный на оси x, выигрывает, если игроки рассогласовать. Соответствие реакций игрока Y - это игра на координацию, а у игрока X - игра на рассогласование. Единственное равновесие по Нэшу - это комбинация смешанных стратегий, где оба игрока независимо выбирают орел и решку с вероятностью 0,5 каждый.

Рис. 7. Соответствия реакций игроков в игре сопоставление пенсов. Крайнее левое отображение предназначено для координирующего игрока, среднее показывает отображение для дискоординирующего игрока. Единственное равновесие по Нэшу показано на правом графике.

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

• В модели большой популяции игроки выбирают свое следующее действие вероятностно, исходя из того, какие стратегии лучше всего подходят для всего населения.
• В пространственной модели игроки выбирают (в следующем round) действие, которое является лучшим ответом для всех своих соседей (Ellison 1993).

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

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

Теорема: в любом конечном потенциале в игре, динамика наилучшего отклика всегда сходится к равновесию по Нэшу. (Nisan et al. 2007, Раздел 19.3.2)

Рисунок 8. Соответствие BR (черный) и сглаженные функции BR (цвета)

Вместо соответствий наилучшего отклика в некоторых моделях используется сглаживание функции наилучшего отклика . Эти функции похожи на соответствие наилучшего отклика, за исключением того, что функция не "перескакивает" с одной чистой стратегии на другую. Разница проиллюстрирована на рисунке 8, где черный цвет представляет собой соответствие наилучшего отклика, а каждый другой цвет представляет различные сглаженные функции наилучшего отклика. В стандартных соотношениях наилучшего отклика даже малейшая выгода от одного действия приведет к тому, что индивидуум выполнит это действие с вероятностью 1. В сглаженном наилучшем ответе, поскольку разница между двумя действиями уменьшается, индивидуальная игра приближается к 50:50.

Есть много функций, которые представляют сглаженные функции наилучшего отклика. Проиллюстрированные здесь функции представляют собой несколько вариаций следующей функции:

$e\; E\; (1)\; /\; \gamma \; e\; E\; (1)\; /\; \gamma \; +\; e\; E\; (2)\; /\; \gamma \; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{e\; ^\; \{E\; (1)\; /\; \backslash \; gamma\}\}\; \{e\; ^\; \{E\; (1)\; /\; \backslash \; gamma\}\; +\; e\; ^\; \{E\; (2)\; /\; \backslash \; gamma\}\}\}\}$

где $E\; (x)\; \{\backslash \; displaystyle\; E\; (x)\}$представляет ожидаемую отдачу от действия $x\; \{\backslash \; displaystyle\; x\}$, а $\gamma \; \{\backslash \; displaystyle\; \backslash \; gamma\}$- параметр который определяет степень отклонения функции от истинного наилучшего отклика (большее значение $\gamma \; \{\backslash \; displaystyle\; \backslash \; gamma\}$означает, что игрок с большей вероятностью сделает «ошибки»).

Использование сглаженного наилучшего отклика дает несколько преимуществ, как теоретических, так и эмпирических. Во-первых, это согласуется с психологическими экспериментами; когда люди примерно безразличны между двумя действиями, кажется, что они выбирают более или менее случайно. Во-вторых, игра отдельных лиц определяется однозначно во всех случаях, поскольку это соответствие, которое также является функцией. Наконец, использование сглаженного наилучшего отклика с некоторыми правилами обучения (как в Фиктивная игра ) может привести к тому, что игроки научатся играть смешанную стратегию равновесие Нэша (Фуденберг Levine 1998).

• Решенная игра

• Эллисон, Г. (1993), «Обучение, локальное взаимодействие и координация» (PDF), Econometrica, 61 (5): 1047–1071, doi : 10.2307 / 2951493, JSTOR 2951493
• Fudenberg, D. ; Левин, Дэвид К. (1998), Теория обучения в играх, Кембридж, Массачусетс: MIT Press
• Fudenberg, Drew ; Тироль, Жан (1991). Теория игр. Кембридж, Массачусетс: MIT Press. ISBN 9780262061414.Предварительный просмотр книги.
• Гиббонс, Р. (1992), Учебник по теории игр, Harvester-Wheatsheaf, S2CID 10248389
• Нэш, Джон Ф. (1950), «Точки равновесия в играх с n людьми», Proceedings of the National Academy of Sciences of the United States of America, 36 (1): 48 –49, doi : 10.1073 / pnas.36.1.48, PMC 1063129, PMID 16588946
• Осборн, MJ; Рубинштейн, Ариэль (1994), курс теории игр, Cambridge MA: MIT Press
• Young, H.P. (2005), Стратегическое обучение и его пределы, Oxford University Press
• Nisan, N.; Roughgarden, T.; Tardos, É.; Вазирани, В. (2007), Теория алгоритмических игр (PDF), Нью-Йорк: Cambridge University Press