Лучший ответ

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

Переписка [ править ]

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

Соответствия реакций , также известные как соответствия наилучшего отклика, используются в доказательстве существования смешанной стратегии равновесия по Нэшу ( Fudenberg & Tirole 1991 , раздел 1.3.B; Osborne & Rubinstein 1994 , раздел 2.2). Соответствия реакции не являются «функциями реакции», поскольку функции должны иметь только одно значение для каждого аргумента, и многие соответствия реакции будут неопределенными, то есть вертикальной линией при выборе стратегии оппонента. Создается соответствие для каждого игрока из набора профилей стратегии оппонента в набор стратегий игрока. Таким образом, для любого набора стратегий противника , представляет собой игрок I ${\ Displaystyle б (\ cdot)}$ ${\ displaystyle \ sigma _ {- i}}$ ${\ displaystyle b_ {я} (\ sigma _ {- 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 CS1 maint: обескураженный параметр ( ссылка )
Фуденберг, Дрю ; Тироль, Жан (1991). Теория игр . Кембридж, Массачусетс: MIT Press . ISBN 9780262061414. Предварительный просмотр книги.
Гиббонс, Р. (1992) , Учебник по теории игр , Harvester-Wheatsheaf, S2CID 10248389
Нэш, Джон Ф. (1950), «Равновесные точки в п многих лиц игры», Труды Национальной академии наук Соединенных Штатов Америки , 36 (1): 48-49, DOI : 10.1073 / pnas.36.1. 48 , PMC 1063129 , PMID 16588946 CS1 maint: обескураженный параметр ( ссылка )
Осборн, MJ; Рубинштейн, Ариэль (1994), курс теории игр , Кембридж, Массачусетс: MIT Press CS1 maint: обескураженный параметр ( ссылка )
Янг, HP (2005 г.), « Стратегическое обучение и его ограничения» , Oxford University Press
Nisan, N .; Roughgarden, T .; Tardos, É .; Вазирани, В.В. (2007), Теория алгоритмических игр (PDF) , Нью-Йорк: Издательство Кембриджского университета

vтеТемы по теории игр
Определения	Игра с перегрузкой Кооперативная игра Решительность Эскалация обязательств Игра в расширенной форме Победа первого и второго игрока Сложность игры Язык описания игры Графическая игра Иерархия убеждений Информационный набор Игра в нормальной форме Предпочтение Последовательная игра Одновременная игра Выбор одновременного действия Решенная игра Лаконичная игра
Концепции равновесия	равновесие по Нэшу Совершенство подигры Устойчивое равновесие по Мертенсу Байесовское равновесие по Нэшу Идеальное байесовское равновесие Дрожащая рука Правильное равновесие Эпсилон-равновесие Коррелированное равновесие Последовательное равновесие Квази-совершенное равновесие Эволюционно устойчивая стратегия Доминирование риска Основной Значение Шепли Парето эффективность Равновесие Гиббса Равновесие с квантовым откликом Самоподтверждающееся равновесие Сильное равновесие по Нэшу Марковское идеальное равновесие
Стратегии	Доминирующие стратегии Чистая стратегия Смешанная стратегия Аргумент кражи стратегии Око за око Мрачный спусковой крючок Сговор Обратная индукция Прямая индукция Марковская стратегия Затенение ставки
Классы игр	Симметричная игра Идеальная информация Повторная игра Сигнальная игра Скрининговая игра Дешевый разговор Игра с нулевой суммой Конструкция механизма Проблема торга Стохастическая игра Средняя игра n -пользовательская игра Большая игра Пуассона Нетранзитивная игра Глобальная игра Строго определенная игра Возможная игра
Игры	Идти Шахматы Бесконечные шахматы Шашки Крестики-нолики Дилемма заключенного Игра по обмену подарками Необязательная дилемма заключенного Дилемма путешественника Координационная игра Курица Сороконожка игра Сигнальная игра Льюиса Дилемма волонтера Долларовый аукцион Битва полов Охота на оленя Соответствующие пенни Ультиматум игра Камень ножницы Бумага Пиратская игра Диктаторская игра Игра в общественные блага Блотто игра Война на истощение Проблема с баром Эль Фарол Справедливое деление Ярмарка нарезки торта Игра Курно Тупик Дилемма закусочной Угадайте 2/3 среднего Покер куна Игра Нэша в торг Индукционные пазлы Доверительная игра Игра принцесс и монстров Проблема рандеву
Теоремы	Теорема невозможности Эрроу Теорема согласия Ауманна Народная теорема Теорема о минимаксе Теорема Нэша Теорема очищения Принцип откровения Теорема Цермело
Ключевые цифры	Альберт В. Такер Амос Тверски Антуан Огюстен Курно Ариэль Рубинштейн Клод Шеннон Даниэль Канеман Дэвид К. Левин Дэвид М. Крепс Дональд Б. Гиллис Дрю Фуденберг Эрик Маскин Гарольд В. Кун Герберт Саймон Эрве Мулен Жан Тироль Жан-Франсуа Мертенс Дженнифер Тур Чейес Джон Харсани Джон Мейнард Смит Джон Нэш Джон фон Нейман Кеннет Эрроу Кеннет Бинмор Леонид Гурвич Ллойд Шепли Мелвин Дрешер Меррилл М. Флуд Ольга Бондарева Оскар Моргенштерн Пол Милгром Пейтон Янг Райнхард Зельтен Роберт Аксельрод Роберт Ауманн Роберт Б. Уилсон Роджер Майерсон Сэмюэл Боулз Сюзанна Скотчмер Томас Шеллинг Уильям Викри
Разнообразный	All-pay аукцион Альфа – бета обрезка Парадокс бертрана Ограниченная рациональность Комбинаторная теория игр Анализ конфронтации Совместное соревнование Эволюционная теория игр Преимущество первого хода в шахматах Игровая механика Глоссарий теории игр Список теоретиков игр Список игр по теории игр Безвыигрышная ситуация Решение шахмат Топологическая игра Трагедия общественного достояния Тирания маленьких решений