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

Обратная индукция это процесс рассуждений назад во времени, от конца проблемы или ситуации, чтобы определить последовательность оптимальных действий. Сначала он учитывает, когда в последний раз могло быть принято решение, и выбирает, что делать в любой ситуации в это время. Используя эту информацию, можно затем определить, что делать при предпоследнем принятии решения. Этот процесс продолжается в обратном направлении, пока не будет определено наилучшее действие для каждой возможной ситуации (то есть для каждой возможной ситуации). набор информации ) в любой момент времени. Впервые он был использован Цермело в 1913 году, чтобы доказать, что у шахмат есть чисто оптимальные стратегии.[1][2]

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

Обратная индукция использовалась для решения игр до тех пор, пока существовала теория игр. Джон фон Нейман и Оскар Моргенштерн предложенное решение с нулевой суммой, игры двух лиц методом обратной индукции в их Теория игр и экономического поведения (1944), книга, в которой теория игр стала предметом изучения.[2][6]

Обратная индукция при принятии решений: проблема оптимальной остановки

Рассмотрим безработного, который сможет проработать еще десять лет. т = 1,2, ..., 10. Предположим, что каждый год, в течение которого он остается безработным, ему с равной вероятностью (50/50) могут предлагать «хорошую» работу за 100 долларов или «плохую» за 44 доллара. После того, как он согласится на работу, он останется на ней до конца десяти лет. (Предположим для простоты, что он заботится только о своих денежных доходах и что он одинаково оценивает заработки в разное время, т. Е. учетная ставка равно нулю.)

Следует ли этому человеку соглашаться на плохую работу? Чтобы ответить на этот вопрос, мы можем рассуждать задом наперед т = 10.

  • В момент времени 10 ценность принятия хорошей работы составляет 100 долларов; цена признания плохой работы - 44 доллара; ценность отклонения доступной работы равна нулю. Следовательно, если он все еще остается безработным в последний период, он должен согласиться на любую работу, которую ему предлагают в это время.
  • В момент времени 9 ценность принятия хорошей работы составляет 200 долларов (потому что эта работа продлится два года); ценность признания плохой работы составляет 2 * 44 доллара = 88 долларов. Стоимость отклонения предложения о работе сейчас составляет 0 долларов плюс стоимость ожидания следующего предложения о работе, которая будет составлять либо 44 доллара с вероятностью 50%, либо 100 долларов с вероятностью 50%, для среднего («ожидаемого») значения 0,5 * (100 $ + 44 $) = 72 $. Следовательно, независимо от того, хорошая или плохая работа, доступная в момент 9, лучше принять это предложение, чем ждать лучшего.
  • В момент 8 стоимость получения хорошей работы составляет 300 долларов (на три года); ценность признания плохой работы составляет 3 * 44 доллара = 132 доллара. Стоимость отклонения предложения о работе сейчас составляет 0 долларов плюс стоимость ожидания предложения о работе в момент 9. Поскольку мы уже пришли к выводу, что предложения в момент 9 должны быть приняты, ожидаемая ценность ожидания предложения о работе в момент 9 равно 0,5 * (200 долларов + 88 долларов) = 144 доллара. Следовательно, в момент времени 8 гораздо важнее дождаться следующего предложения, чем принять плохую работу.

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

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

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

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

В «Стратегии: введение в теорию игр» Джоэла Уотсона процедура обратной индукции определяется как: «Процесс анализа игры от конца до начала. На каждом узле принятия решения исключаются из рассмотрения любые доминирующие действия, учитывая конечные узлы, которые могут быть достигнуты посредством воспроизведения действий, идентифицированных в узлах-преемниках ».[8]

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

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

Обратная индукция в теории игр: Многоступенчатая игра

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

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

Нормальная форма Матрица:

Этап 1
Игрок 2

Игрок 1
ДжокерТерминатор
Джокер3, 50, 0
Терминатор1, 15, 3
2 этап
Игрок 2

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

Обширная форма Представление:

Обширная форма игры джокер терминатор

Шаги для решения этой многоэтапной игры с развернутой формой, как показано справа:

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

Обратная индукция в теории игр: игра в ультиматум

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

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

Обратная индукция в игре Ultimatum

Представьте себе игру между двумя игроками, в которой игрок 1 предлагает разделить доллар с игроком 2. Это известная асимметричная игра, в которую играют последовательно, называемая ультиматумная игра. Первый игрок действует первым, разделяя доллар, как считает нужным. Теперь второй игрок может либо принять ту часть, которую он получил от первого игрока, либо отказаться от разделения. Если игрок 2 соглашается на разделение, то и игрок 1, и игрок 2 получают выплату в соответствии с этим разделением. Если второй игрок решает отклонить предложение игрока 1, оба игрока ничего не получают. Другими словами, игрок 2 имеет право вето на предложенное игроком 1 распределение, но применение вето отменяет любую награду для обоих игроков.[12] Таким образом, профиль стратегии для этой игры может быть записан в виде пар (x, f (x)) для всех x между 0 и 1, где f (x)) - двузначная функция, выражающая, принято ли x или нет.

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

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

На практике идеальное равновесие в подиграх достигается не всегда. По словам Камерера, американского поведенческого экономиста, игрок 2 «примерно в половине случаев отвергает предложения менее 20 процентов X, даже если в итоге они ничего не получают».[13] В то время как обратная индукция предсказывает, что респондент принимает любое предложение, равное или большее нуля, респонденты в действительности не являются рациональными игроками и поэтому, похоже, больше заботятся о «справедливости» предложения, а не о потенциальной денежной выгоде.

Смотрите также сороконожка.

Обратная индукция в экономике: проблема выхода на рынок

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

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

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

Парадокс обратной индукции: неожиданное повешение

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

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

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

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

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

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

Примечания

  1. ^ Фон Э., Цермело (1913). "Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels" (PDF). www.ethz.ch. Получено 2018-12-31.
  2. ^ а б Математика шахмат, веб-страница Джона Маккуорри.
  3. ^ Джером Адда и Рассел Купер "Динамическая экономика: количественные методы и приложения ", Раздел 3.2.1, стр. 28. MIT Press, 2003.
  4. ^ Марио Миранда и Пол Факлер "Прикладная вычислительная экономика и финансы ", Раздел 7.3.1, стр. 164. MIT Press, 2002.
  5. ^ Дрю Фуденберг и Жан Тироль, «Теория игр», раздел 3.5, стр. 92. MIT Press, 1991.
  6. ^ Джон фон Нейман и Оскар Моргенштерн, «Теория игр и экономическое поведение», раздел 15.3.1. Издательство Принстонского университета. Издание третье, 1953 г. (Первое издание, 1944 г.)
  7. ^ Уотсон, Джоэл (2002). Стратегия: введение в теорию игр (3-е изд.). Нью-Йорк: W.W. Нортон и компания. п. 63.
  8. ^ Уотсон, Джоэл (2002). Стратегия: введение в теорию игр (3-е изд.). Нью-Йорк: W.W. Нортон и компания. п. 186–187.
  9. ^ Уотсон, Джоэл (2002). Стратегия: введение в теорию игр (3-е изд.). Нью-Йорк: W.W. Нортон и компания. п. 188.
  10. ^ http://web.mit.edu/14.12/www/02F_lecture7-9.pdf
  11. ^ Уотсон, Джоэл (2013). Стратегия: введение в теорию игр, 3-е издание. Нью-Йорк, штат Нью-Йорк: Norton & Company. С. 183–203. ISBN  9780393918380.
  12. ^ Камински, Марек М. (2017). «Обратная индукция: достоинства и недостатки». Исследования по логике, грамматике и риторике. 50 (1): 9–24. Дои:10.1515 / slgr-2017-0016.
  13. ^ Камерер, Колин Ф. (1997). «Прогресс в теории поведенческих игр» (PDF). Журнал экономических перспектив. 11 (4): 167–188. Дои:10.1257 / jep.11.4.167. ISSN  0895-3309. JSTOR  2138470.
  14. ^ Руст Дж. (2008) Динамическое программирование. В: Palgrave Macmillan (eds) Новый экономический словарь Palgrave. Пэлгрейв Макмиллан, Лондон
  15. ^ Исраэль Ауманн (1995-01-01). «Обратная индукция и общепринятое знание рациональности». Игры и экономическое поведение. 8 (1): 6–19. Дои:10.1016 / S0899-8256 (05) 80015-6. ISSN  0899-8256.