Лучший ответ - Best response

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

Переписка

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

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

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

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

Динамика

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

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

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

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

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

Сглаженный

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

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

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

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

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

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

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

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

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

• Ellison, G. (1993), "Обучение, местное взаимодействие и координация" (PDF) , Эконометрика , 61 (5): 1047-1071, DOI : 10,2307 / 2951493 , JSTOR  2951493
• Fudenberg, D .; Левин, Дэвид К. (1998), Теория обучения в играх , Кембридж, Массачусетс: MIT Press
• Фуденберг, Дрю ; Тироль, Жан (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, Bibcode : 1950PNAS ... 36. ..48N , DOI : 10.1073 / pnas.36.1.48 , PMC  1063129 , PMID  16588946
• Осборн, MJ; Рубинштейн, Ариэль (1994), курс теории игр , Кембридж, Массачусетс: MIT Press
• Янг, HP (2005 г.), « Стратегическое обучение и его пределы» , Oxford University Press
• Nisan, N .; Roughgarden, T .; Tardos, É .; Вазирани, В.В. (2007), Теория алгоритмических игр (PDF) , Нью-Йорк: Издательство Кембриджского университета