Войти
Обратная индукция - это процесс рассуждений назад во времени, от конца проблемы или ситуации, для определения последовательности оптимальных действий. Сначала он учитывает, когда в последний раз могло быть принято решение, и выбирает, что делать в любой ситуации в это время. Используя эту информацию, можно затем определить, что делать во время предпоследнего принятия решения. Этот процесс продолжается в обратном направлении до тех пор, пока не будет определено наилучшее действие для каждой возможной ситуации (то есть для каждого возможного информационного набора ) в каждый момент времени. Впервые он был использован Цермело в 1913 году, чтобы доказать, что шахматы имеют чисто оптимальные стратегии.
В математическом методе оптимизации динамического программирования, обратная индукция - один из основных методов решения уравнения Беллмана. В теории игр обратная индукция - это метод, используемый для вычисления идеальных равновесий подигр в последовательных играх. Единственное отличие состоит в том, что оптимизация включает только одного лица, принимающего решения, который выбирает, что делать в каждый момент времени, тогда как теория игр анализирует, как взаимодействуют решения нескольких игроков. То есть, предвидя, что будет делать последний игрок в каждой ситуации, можно определить, что будет делать предпоследний игрок, и так далее. В связанных полях автоматическое планирование и планирование и автоматическое доказательство теорем метод называется обратный поиск или обратная цепочка. В шахматах это называется ретроградный анализ.
Обратная индукция использовалась для решения игр с тех пор, как существовала область теории игр. Джон фон Нейман и Оскар Моргенштерн предложили решать игры двух лиц с нулевой суммой с помощью обратной индукции в своей Теории игр и экономического поведения (1944), книга, которая установила теорию игр как область исследования.
Рассмотрим безработного, который сможет проработать еще десять лет t = 1,2,..., 10. Предположим, что каждый год, в течение которого он остается безработным, ему с равной вероятностью (50/50) могут предлагать «хорошую» работу за 100 долларов или «плохую» за 44 доллара. После того, как он согласится на работу, он останется на ней до конца десяти лет. (Предположим для простоты, что он заботится только о своих денежных заработках и что он одинаково оценивает заработки в разное время, т. Е. ставка дисконтирования равна нулю.)
Если этот человек соглашается на плохую работу ? Чтобы ответить на этот вопрос, мы можем рассуждать в обратном порядке, начиная со времени t = 10.
Можно проверить, продолжая работать в обратном направлении, что плохие предложения должны приниматься только в том случае, если кто-то все еще остается безработным в разы 9. или 10; они должны быть отклонены все время до t = 8. Интуиция подсказывает, что если кто-то ожидает работать на работе в течение длительного времени, это делает более ценным быть разборчивым в том, какую работу принять.
Проблема динамической оптимизации такого типа называется проблемой оптимальной остановки, потому что проблема заключается в том, когда перестать ждать лучшего предложения. Теория поиска - это область микроэкономики, которая применяет проблемы этого типа к таким контекстам, как покупки, поиск работы и брак.
В теории игр обратная индукция - это концепция решения. Это уточнение концепции рациональности, которая чувствительна к индивидуальным наборам информации в расширенном представлении игры. Идея обратной индукции использует последовательную рациональность, определяя оптимальное действие для каждой информации в данном дереве игры.
В «Стратегии: Введение в теорию игр» Джоэла Уотсона процедура обратной индукции определяется как: «Процесс анализа игры от конца до начала. В каждом узле принятия решения исключаются из рассмотрения любые доминирующие действия, учитывая конечные узлы, которые могут быть достигнуты посредством воспроизведения действий, идентифицированных в узлах-преемниках ».
Один из недостатков процедуры обратной индукции заключается в том, что его можно применить только к ограниченным классам игр. Процедура хорошо определена для любой игры с идеальной информацией без какой-либо полезности. Это также хорошо определено и важно для игры с идеальной информацией со связями. Однако это приводит к более чем одному профилю стратегии. Процедура может быть применена к некоторым играм с нетривиальным набором информации, но в целом она ненадежна. Эта процедура лучше всего подходит для решения игр с точной информацией. (Уотсон стр.188)
Процедуру обратной индукции можно продемонстрировать на простом примере.
Предлагаемая игра представляет собой многоступенчатую игру с участием 2 игроков. Игроки планируют пойти в кино. В настоящее время очень популярны 2 фильма: Джокер и Терминатор. Игрок 1 хочет посмотреть Терминатора, а Игрок 2 хочет посмотреть Джокера. Игрок 1 сначала купит билет и расскажет Игроку 2 о своем выборе. Затем Игрок 2 купит свой билет. Как только они оба сделают свой выбор, они сделают выбор, пойти ли в кино или остаться дома. Как и на первом этапе, Игрок 1 выбирает первым. Затем Игрок 2 делает свой выбор, наблюдая за выбором Игрока 1.
В этом примере мы предполагаем, что выплаты добавляются на разных этапах. Игра представляет собой идеальную информационную игру.
Нормальная форма Матрица:
| Игрок 2. Игрок 1 | Джокер | Терминатор |
|---|---|---|
| Джокер | 3, 5 | 0, 0 |
| Терминатор | 1, 1 | 5, 3 |
| Игрок 2. Игрок 1 | Вперед к фильму | Оставайся дома |
|---|---|---|
| К фильму | 6, 6 | 4, -2 |
| Оставайся дома | -2, 4 | -2, -2 |
Расширенная форма Представление:
Терминатор джокера в расширенной форме Шаги для решения этой многоэтапной игры, с расширенной формой для справа:
Назад индукция - это «процесс анализа игры от конца до начала. Как и в случае решения других равновесий Нэша, предполагается рациональность игроков и полное знание. Концепция обратной индукции соответствует этому предположению, что общеизвестно, что каждый игрок будет действовать рационально с каждым узлом принятия решения, когда он выбирает вариант - даже если его рациональность будет означать, что такой узел не будет достигнут.. '
Чтобы найти Идеальное равновесие в подигре с обратной индукцией, игра должна быть записана в развернутой форме, а затем разделена на подигры. Начиная с вспомогательной игры, наиболее удаленной от начального узла или начальной точки, взвешиваются ожидаемые выплаты, перечисленные для этой вспомогательной игры, и рациональный игрок выберет для себя вариант с более высокой выплатой. Выбирается и отмечается вектор наибольшего выигрыша. Найдите идеальное равновесие во вспомогательной игре, постоянно работая в обратном направлении от вспомогательной игры к вспомогательной, пока не достигнете начальной точки. Отмеченный путь векторов - это идеальное равновесие подигры.
Обратная индукция, применяемая к игре Ultimatum
Представьте себе игру между двумя игроками, в которой игрок 1 предлагает разделить доллар с игроком 2. Это известная асимметричная игра которая проводится последовательно, называемая игрой в ультиматум. Первый игрок действует первым, разделяя доллар, как считает нужным. Теперь второй игрок может либо принять ту часть, которую он получил от первого игрока, либо отказаться от разделения. Если игрок 2 принимает разделение, то и игрок 1, и игрок 2 получают выплату в соответствии с этим разделением. Если второй игрок решает отклонить предложение игрока 1, оба игрока ничего не получают. Другими словами, игрок 2 имеет право вето на предложенное игроком 1 распределение, но применение вето отменяет любую награду для обоих игроков. Таким образом, профиль стратегии для этой игры может быть записан в виде пар (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, даже если в итоге они ничего не получают». В то время как обратная индукция предсказывает, что респондент принимает любое предложение, равное или большее нуля, респонденты в действительности не являются рациональными игроками и поэтому, похоже, больше заботятся о «справедливости» предложения, а не о потенциальной денежной прибыли.
См. Также игра в сороконожку.
Рассмотрим динамическую игру, в которой игроки являются действующей фирмой. в отрасли и потенциальным участником этой отрасли. В настоящее время традиционный оператор имеет монополию на отрасль и не хочет терять часть своей доли рынка в пользу новичка. Если новичок решает не вступать, выигрыш для действующего оператора высок (он сохраняет свою монополию), а новичок не теряет и не выигрывает (его выигрыш равен нулю). Если участник входит, действующий участник может «бороться» или «приспосабливаться» к нему. Он будет бороться, снижая цену, выгоняя новичка из бизнеса (и неся издержки выхода - отрицательный результат) и нанося ущерб собственной прибыли. Если он приспособит новичка, он потеряет часть своих продаж, но будет сохраняться высокая цена, и он получит большую прибыль, чем от снижения цены (но ниже прибыли монополии).
Подумайте, будет ли лучший ответ действующего оператора приспосабливаться к вступлению нового участника. Если действующий оператор соглашается, лучший ответ новичка - войти (и получить прибыль). Следовательно, профиль стратегии, в котором новичок входит, и действующий игрок приспосабливается, если новичок входит, является равновесием по Нэшу, совместимым с обратной индукцией. Однако, если действующий участник собирается драться, лучший ответ участника - не входить, а если участник не входит, не имеет значения, что он решает сделать в гипотетическом случае, когда участник действительно входит. Следовательно, профиль стратегии, в котором действующий президент борется, если новичок входит, но не входит, также является равновесием по Нэшу. Однако, если участник отклонится и войдет, лучший ответ действующего президента - приспособиться - угроза боевых действий не вызывает доверия. Таким образом, это второе равновесие по Нэшу может быть устранено обратной индукцией.
Нахождение равновесия по Нэшу в каждом процессе принятия решений (подигре) представляет собой идеальное равновесие подигры. Таким образом, эти стратегические профили, которые изображают идеальное равновесие в подиграх, исключают возможность таких действий, как невероятные угрозы, которые используются для «отпугивания» новичка. Если действующий оператор угрожает начать ценовую войну Ценовая война с участником, он угрожает снизить свои цены с монопольной цены до немного ниже, чем цена участника, что было бы непрактично и невероятно, если бы участник знали, что ценовой войны на самом деле не произойдет, поскольку она приведет к потерям для обеих сторон. В отличие от оптимизации с одним агентом, которая включает в себя равновесия, которые не достижимы или оптимальны, идеальное равновесие во вспомогательной игре учитывает действия другого игрока, таким образом гарантируя, что ни один из игроков не попадет во вспомогательную игру по ошибке. В этом случае обратная индукция, дающая идеальное равновесие в подиграх, гарантирует, что новичок не будет убежден в угрозе действующего президента, зная, что это не лучший ответ в профиле стратегии.
неожиданный парадокс зависания - это парадокс, связанный с обратной индукцией. Предположим, заключенной сказали, что ее повесят где-то с понедельника по пятницу следующей недели. Однако точный день будет неожиданностью (то есть накануне вечером она не будет знать, что на следующий день ее казнят). Заключенная, желая перехитрить своего палача, пытается определить, в какой день будет казнь.
Она считает, что это не может произойти в пятницу, поскольку, если бы это не произошло до конца четверга, она бы знала, что казнь будет в пятницу. Поэтому она может исключить пятницу как возможность. После исключения пятницы она решает, что это не может произойти в четверг, так как, если бы это не произошло в среду, она бы знала, что это должно быть в четверг. Следовательно, она может исключить четверг. Это рассуждение продолжается до тех пор, пока она не исключит все возможности. Она заключает, что на следующей неделе ее не повесят.
К ее удивлению, в среду ее повесили. Она совершила ошибку, предположив, что точно знает, мог ли она рассуждать о неизвестном будущем факторе, который приведет к ее казни.
Здесь заключенный рассуждает путем обратной индукции, но, похоже, приходит к ложному заключению. Обратите внимание, однако, что описание проблемы предполагает, что можно удивить того, кто выполняет обратную индукцию. Математическая теория обратной индукции не делает этого предположения, поэтому парадокс не ставит под сомнение результаты этой теории. Тем не менее, этот парадокс получил существенное обсуждение философов.
Обратная индукция работает, только если оба игрока рациональны, т.е. всегда выбирают действие, которое максимизирует их выигрыш. Однако рациональности недостаточно: каждый игрок также должен верить, что все остальные игроки рациональны. Даже этого недостаточно: каждый игрок должен верить, что все другие игроки знают, что все остальные игроки рациональны. И так до бесконечности. Другими словами, рациональность должна быть общеизвестной.
