WikiDer > Лучший ответ

Best response

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

Переписка

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

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

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

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

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

Координационные игры

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

Антикоординационные игры

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

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

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

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

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

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

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

В играх 2х2 с асимметрией выигрышей возможен более широкий диапазон форм соответствий реакций. Для каждого игрока существует пять возможных наилучших форм реакции, показанных на рисунке 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. Соответствия реакций игроков в совпадающие пенни игра. Крайнее левое отображение предназначено для координирующего игрока, среднее показывает отображение для дискоординирующего игрока. Единственное равновесие по Нэшу показано на правом графике.

Динамика

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

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

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

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

Теорема: В любой игре с конечным потенциалом динамика наилучшего отклика всегда сходится к равновесию по Нэшу.Nisan et al. 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}$ подразумевает, что игрок с большей вероятностью сделает «ошибки»).

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

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

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

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

Navigation