Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

Следует ли этому человеку соглашаться на плохую работу? Чтобы ответить на этот вопрос, мы можем рассуждать в обратном порядке, начиная с момента t = 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; они должны быть отклонены все время до t = 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. ^ Rust, Джон (9 сентября 2016). Динамическое программирование . Новый экономический словарь Пэлгрейва: Пэлгрейв Макмиллан. ISBN 978-1-349-95121-5.
  2. ^ Джером Адда и Рассел Купер, « Динамическая экономика: количественные методы и приложения », раздел 3.2.1, стр. 28. MIT Press, 2003.
  3. ↑ Марио Миранда и Пол Факлер, « Прикладная вычислительная экономика и финансы », раздел 7.3.1, стр. 164. MIT Press, 2002.
  4. ^ Дрю Fudenberg и Жан Tirole, "Теория игр", раздел 3.5, стр 92. MIT Press, 1991.
  5. ^ Математика шахмат , веб-страница Джона Маккуорри.
  6. ^ Джон фон Нейман и Оскар Моргенштерн, «Теория игр и экономического поведения», раздел 15.3.1. Издательство Принстонского университета. Издание третье, 1953 г. (издание первое, 1944 г.)
  7. Перейти ↑ Watson, Joel (2002). Стратегия: введение в теорию игр (3-е изд.). Нью-Йорк: WW Norton & Company. п. 63.
  8. Перейти ↑ Watson, Joel (2002). Стратегия: введение в теорию игр (3-е изд.). Нью-Йорк: WW Norton & Company. С. 186–187.
  9. Перейти ↑ Watson, Joel (2002). Стратегия: введение в теорию игр (3-е изд.). Нью-Йорк: WW Norton & Company. п. 188.
  10. ^ http://web.mit.edu/14.12/www/02F_lecture7-9.pdf
  11. ^ Rust, Джон (9 сентября 2016). Динамическое программирование . Новый экономический словарь Пэлгрейва: Пэлгрейв Макмиллан. ISBN 978-1-349-95121-5.
  12. ^ Камински, Марек М. (2017). «Обратная индукция: достоинства и недостатки» . Исследования по логике, грамматике и риторике . 50 (1): 9–24. DOI : 10,1515 / slgr-2017-0016 .
  13. ^ Камерер, Колин Ф. (1997). "Прогресс в теории поведенческих игр" (PDF) . Журнал экономических перспектив . 11 (4): 167–188. DOI : 10,1257 / jep.11.4.167 . ISSN 0895-3309 . JSTOR 2138470 .   
  14. ^ Руст Дж. (2008) Динамическое программирование. В: Palgrave Macmillan (eds) Новый экономический словарь Palgrave. Пэлгрейв Макмиллан, Лондон
  15. ^ Yisrael Aumann (1995-01-01). «Обратная индукция и общепринятое знание рациональности». Игры и экономическое поведение . 8 (1): 6–19. DOI : 10.1016 / S0899-8256 (05) 80015-6 . ISSN 0899-8256 .