Лучший ответ

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

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

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

Рисунок 2. Соответствие реакций игрока X в игре «Охота на оленя».

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

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

Координационные игры [ править ]

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

Антикоординационные игры [ править ]

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

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

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

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

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

Игры с доминируемыми стратегиями имеют соответствия реакций, которые пересекаются только в одной точке, которая находится либо в левом нижнем, либо в правом верхнем углу в играх 2х2 с симметричными выигрышами. в одиночной игре Например, в дилемме заключенного ход «Сотрудничать» не является оптимальным ни при какой вероятности сотрудничества противника. На рисунке 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, Д) Обе стратегии работают одинаково хорошо, независимо от того, что играет противник.

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

Соответствующие монеты [ править ]

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

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

Динамика [ править ]

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

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

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

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

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

Сглаженный [ править ]

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

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

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

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

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

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

См. также [ править ]

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

Ссылки [ править ]

Эллисон, Г. (1993), «Обучение, местное взаимодействие и координация» (PDF) , Econometrica , 61 (5): 1047–1071, doi : 10.2307/2951493 , JSTOR 2951493
Фуденберг, Д.; Левин, Дэвид К. (1998), Теория обучения в играх , Кембридж, Массачусетс: MIT Press
Фуденберг, Дрю ; Тироль, Жан (1991). Теория игры . Кембридж, Массачусетс: MIT Press . ISBN 9780262061414 . Предварительный просмотр книги.
Гиббонс, Р. (1992), Учебник по теории игр , Harvester-Wheatsheaf, S2CID 10248389
Нэш, Джон Ф. (1950), «Точки равновесия в n играх лиц», Труды Национальной академии наук Соединенных Штатов Америки , 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.
Нисан, Н.; Рафгарден, Т.; Тардос, Э.; Вазирани, В.В. (2007), Алгоритмическая теория игр (PDF) , Нью-Йорк: Издательство Кембриджского университета

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