Обратная индукция

Не путать с обратным распространением ошибки .

Обратная индукция — это процесс определения последовательности оптимальных выборов путем рассуждения от конечной точки проблемы или ситуации обратно к ее началу с использованием отдельных событий или действий. Обратная индукция включает в себя изучение конечной точки в серии решений и определение оптимального процесса или действия, необходимого для достижения этой точки. Этот процесс продолжается в обратном направлении до тех пор, пока не будет определено лучшее действие для каждой возможной точки последовательности. Обратная индукция была впервые использована в 1875 году Артуром Кэли , который открыл этот метод при попытке решить проблему секретаря .

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

В теории игр вариант обратной индукции — это метод, используемый для вычисления идеальных равновесий в подыграх в последовательных играх . Разница в том, что в задачах оптимизации участвует один человек, принимающий решения , который выбирает, что делать в каждый момент времени, тогда как задачи теории игр предполагают взаимодействие нескольких игроков . В этой ситуации все еще возможно применить обобщение обратной индукции, поскольку можно определить, что будет делать предпоследний игрок, предсказывая, что будет делать последний игрок в каждой ситуации, и так далее. Этот вариант обратной индукции использовался для решения формальных игр с самого начала теории игр. Джон фон Нейман и Оскар Моргенштерн предложили решать формальные игры с нулевой суммой для двух человек с помощью этого метода в своей «Теории игр и экономического поведения» (1944), книге, которая сделала теорию игр областью исследования.

Пример принятия решения

Задача оптимальной остановки

Рассмотрим человека, оценивающего потенциальные возможности трудоустройства на следующие десять лет, обозначенного как раз $t=1,2,3,...,10$. На каждом $t$, они могут столкнуться с выбором между двумя вариантами работы: «хорошая» работа зарплатой с $\$100$ или «плохая» работа с зарплатой $\$44$. Каждый тип работы имеет равную вероятность быть предложенным. Приняв работу, человек будет сохранять эту конкретную работу в течение всего оставшегося десятилетнего периода.

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

Должен ли рассматриваемый человек соглашаться на «плохую» работу, можно решить, рассуждая в обратном направлении во времени. $t=10$.

• В $t=10$, общий доход от принятия «хорошей» работы равен $\$100$; ценность принятия «плохой» работы $\$44$; общий доход от отказа от доступной работы равен $\$0$. Следовательно, если они все еще остаются безработными в последний период, им следует соглашаться на любую работу, которую им предлагают в это время, для получения большего дохода.
• В $t=9$, общий доход от принятия «хорошей» работы равен $2\times \$100=\$200$ потому что эта работа продлится два года. Общий доход от принятия «плохой» работы составляет $2\times \$44=\$88$. Общий ожидаемый доход от отклонения предложения о работе равен $\$0$ сейчас плюс стоимость следующего предложения о работе, которое либо будет $\$44$ с вероятностью 1/2 или $\$100$ с вероятностью 1/2 для среднего («ожидаемого») значения ${\frac {\$100+\$44}{2}}=\$72$. Поэтому вакансия доступна по адресу $t=9$ следует принять.
• В $t=8$, общий доход от принятия «хорошей» работы равен $3\times \$100=\$300$; Общий заработок от принятия «плохой» работы равен $3\times \$44=\$132$. Общий ожидаемый доход от отклонения предложения о работе равен $\$0$ сейчас плюс общий ожидаемый доход от ожидания предложения о работе в $t=9$. Как было сделано ранее, любое предложение на $t=9$ следует принять, и ожидаемая ценность этого ${\frac {\$200+\$88}{2}}=\$144$. Следовательно, при $t=8$, общий ожидаемый заработок выше, если человек ждет следующего предложения, а не соглашается на «плохую» работу.

Продолжая работать в обратном направлении, можно убедиться, что «плохое» предложение следует принимать только в том случае, если человек по-прежнему безработный. $t=9$ или $t=10$; плохое предложение должно быть отклонено в любой момент вплоть до $t=8$. Если интуитивно обобщить этот пример, то он соответствует принципу: если кто-то рассчитывает работать на работе в течение длительного времени, ее стоит выбирать осторожно.

Задача динамической оптимизации такого типа называется задачей оптимальной остановки , поскольку речь идет о том, когда следует прекратить ждать лучшего предложения. Теория поиска — это область микроэкономики, которая применяет модели этого типа к таким вопросам, как покупки, поиск работы и брак.

Теория игр

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

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

Эту идею обратной индукции в теории игр можно продемонстрировать на простом примере.

Многоэтапная игра

Рассмотрим многоэтапную игру, в которой участвуют два игрока, планирующие пойти в кино. Игрок 1 хочет посмотреть «Терминатора», а игрок 2 хочет посмотреть «Джокера». Игрок 1 первым купит билет и расскажет Игроку 2 о своем выборе. Затем Игрок 2 купит свой билет. Как только они оба увидят выбор, на втором этапе они решают, пойти ли в кино или остаться дома. Как и на первом этапе, сначала делает выбор Игрок 1, затем Игрок 2 делает свой выбор, наблюдая за выбором Игрока 1.

В этом примере выплаты суммируются на разных этапах. Игра представляет собой идеальную информационную игру. Матрицы нормальной формы для этих игр:

Этап 1

Игрок 2 Игрок 1	Джокер	Терминатор
Джокер	3, 5	0, 0
Терминатор	1, 1	5, 3

Этап 2

Игрок 2 Игрок 1	Перейти в фильм	Оставайся дома
Перейти в фильм	6, 6	4, -2
Оставайся дома	-2, 4	-2, -2

Расширенная форма для игры Джокер-Терминатор

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

1. Анализ начинается с конечных узлов.
2. Игрок 2 будет наблюдать за 8 подиграми из последних узлов, чтобы выбрать «пойти в кино» или «остаться дома».
   • Игрок 2 должен сделать всего 8 возможных сравнений, выбрав в каждом из них вариант с наибольшим выигрышем.
   • Например, учитывая первую вспомогательную игру, выигрыш Игрока 2, равный 11, за «пойти в кино» выше, чем его выигрыш, равный 7, за «оставаться дома». Поэтому игрок 2 выберет «пойти в кино».
   • Метод продолжается для каждой подигры.
3. После того как оптимальные решения Игрока 2 определены (жирные зеленые линии на развернутой диаграмме), начинается анализ решений Игрока 1 в ее четырех подиграх.
   • Процесс аналогичен шагу 2: сравниваются выигрыши Игрока 1, чтобы предугадать его выбор.
   • Подигры, которые не были бы выбраны Игроком 2 на предыдущем шаге, больше не рассматриваются, поскольку они исключаются предположением о рациональной игре.
   • Например, в первой подигре выбор «пойти в кино» предлагает выигрыш 9, поскольку дерево решений заканчивается на награде (9, 11), учитывая ранее установленный выбор Игрока 2. Между тем, «остаться дома» предлагает выигрыш 1, поскольку он заканчивается на (1, 9), поэтому Игрок 1 выберет «пойти в кино».
4. Процесс повторяется для каждого игрока, пока не будет достигнут начальный узел.
   • Например, Игрок 2 выберет «Джокера» для первой подигры в следующей итерации, потому что выигрыш 11, заканчивающийся на (9, 11), больше, чем выигрыш «Терминатора» с выигрышем 6 в (6, 6).
   • Игрок 1 в начальном узле выберет «Терминатора», потому что он предлагает более высокий выигрыш 11 в (11, 9), чем Джокер, который имеет награду 9 в (9, 11).
5. Чтобы определить идеальное равновесие подигры , необходимо определить маршрут, который выбирает оптимальную подигру в каждом наборе информации.
   • В этом примере Игрок 1 выбирает «Терминатора», а Игрок 2 также выбирает «Терминатора». Затем они оба выбирают «пойти в кино».
   • Идеальное равновесие в подыгре приводит к выигрышу (11,9).

Ограничения

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

Более того, даже в играх, которые формально допускают обратную индукцию в теории, она не может точно предсказать эмпирический ход игры на практике. Это можно продемонстрировать на втором примере.

Ультиматум игра

См. Также: Игра «Мороконожка».

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

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

Игра «Ультиматум» является теоретической иллюстрацией полезности обратной индукции при рассмотрении бесконечных игр, но теоретически предсказанные результаты игры «Ультиматум» не соответствуют эмпирическим наблюдениям. Экспериментальные данные показали, что предлагающий игрок, Игрок 1, очень редко предлагает 0 долларов, а отвечающий, Игрок 2, иногда отклоняет предложения, превышающие 0 долларов. То, что игрок 2 считает приемлемым, зависит от контекста. Давление или присутствие других игроков и внешние последствия могут означать, что формальная модель игры не обязательно может предсказать, что выберет реальный человек. По мнению Колина Камерера , американского экономиста-бихевиориста, игрок 2 «отклоняет предложения менее 20 процентов X примерно в половине случаев, даже если в итоге они остаются ни с чем».

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

Экономика

Проблема принятия решения о входе

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

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

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

Неожиданный парадокс зависания

Основная статья: Неожиданный парадокс зависания

Неожиданный парадокс зависания — это парадокс, связанный с обратной индукцией. Заключенный, описанный в парадоксе, использует обратную индукцию, чтобы прийти к ложному выводу. Описание проблемы предполагает, что можно удивить того, кто выполняет обратную индукцию. Математическая теория обратной индукции не делает такого предположения, поэтому парадокс не ставит под сомнение результаты этой теории.

Общие знания о рациональности

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

Ограниченная обратная индукция

Ограниченная обратная индукция — это отклонение от полностью рациональной обратной индукции. Он включает в себя выполнение обычного процесса обратной индукции без совершенного предвидения. Теоретически это происходит, когда один или несколько игроков имеют ограниченное предвидение и не могут выполнить обратную индукцию через все конечные узлы. Ограниченная обратная индукция играет гораздо большую роль в более длительных играх, поскольку эффекты ограниченной обратной индукции более сильны в более поздние периоды игр.

Четырехэтапная последовательная игра с предвидением.

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

Существуют три основные гипотезы этого явления:

1. Наличие социальных факторов (например, справедливости)
2. Наличие несоциальных факторов (например, ограниченная обратная индукция)
3. Культурные различия

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

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

Ограниченная обратная индукция также была протестирована в рамках варианта гоночной игры. В игре игроки будут последовательно выбирать целые числа внутри диапазона и суммировать свой выбор, пока не будет достигнуто целевое число. Попадание в цель приносит игроку приз; другой проигрывает. В ходе серии игр был введен небольшой приз. Затем большинство игроков выполнили ограниченную обратную индукцию, поскольку они решили получить небольшой приз, а не первоначальный приз. Лишь небольшая часть игроков на старте рассматривала оба приза.

Большинство тестов обратной индукции основаны на экспериментах, в которых участники лишь в небольшой степени заинтересованы в том, чтобы выполнять задание хорошо, если вообще это делают. Однако нарушения обратной индукции также часто встречаются в ситуациях с высокими ставками. Масштабный анализ американского телевизионного игрового шоу «Цена правильная» , например, свидетельствует об ограниченности предвидения. В каждом эпизоде ​​участники играют в Showcase Showdown — последовательную игру с точной информацией, для которой оптимальную стратегию можно найти с помощью обратной индукции. Частые и систематические отклонения от оптимального поведения позволяют предположить, что значительная часть участников не может должным образом выполнить обратную индукцию и близоруко рассматривает только следующий этап игры.

См. также

• Минимакс