Сороконожка игра - Centipede game

Об аркадной игре см. Сороконожка (видеоигра).

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

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

Играть в

В одну из возможных версий игры в сороконожку можно играть следующим образом:

Рассмотрим двух игроков: Алиса и Боб. Алиса ходит первой. В начале игры перед Алисой стоят две стопки монет: одна стопка содержит 4 монеты, а другая - 1 монету. У каждого игрока есть два доступных хода: либо «взять» большую стопку монет и передать меньшую стопку другому игроку, либо «толкнуть» обе стопки через стол другому игроку. Каждый раз, когда стопки монет проходят по столу, количество монет в каждой стопке удваивается. Например, предположим, что Алиса решает «подтолкнуть» стопки на своем первом ходу, передав стопки из 1 и 4 монет Бобу, удваивая их до 2 и 8. Теперь Боб может использовать свой первый ход, чтобы «взять» стопку из 8 монет и отдайте 2 монеты Алисе, или он может «толкнуть» две стопки обратно через стол снова Алисе, снова увеличивая размер стопки до 4 и 16 монет. Игра продолжается в течение фиксированного количества раундов или до тех пор, пока игрок не решит закончить игру, положив в карман кучу монет.

Добавление монет считается внешность, поскольку он не внесен ни одним из игроков.

Формальное определение

Игра сороконожка может быть записана как ${\displaystyle {\mathcal {G}}(N,~m_{0},~m_{1})}$ куда ${\displaystyle N,m_{0},m_{1}\in \mathbb {N} }$ и ${\displaystyle m_{0}>m_{1}}$. Игроки ${\displaystyle I}$ и ${\displaystyle II}$ чередовать, начиная с игрока ${\displaystyle I}$, и может каждый ход делать ход из ${\displaystyle \{\mathrm {take} ,\mathrm {push} \}}$ с максимумом ${\displaystyle N}$ раундов. Игра заканчивается, когда ${\displaystyle \mathrm {take} }$ играется впервые, в противном случае ${\displaystyle N}$ движется, если ${\displaystyle \mathrm {take} }$ никогда не играется.

Предположим, игра заканчивается на раунде ${\displaystyle t\in \{0,\ldots ,N-1\}}$с игроком ${\displaystyle p\in \{I,II\}}$делая последний ход. Тогда исход игры определяется следующим образом:

• Если ${\displaystyle p}$ играл ${\displaystyle \mathrm {take} }$, тогда ${\displaystyle p}$ прибыль ${\displaystyle 2^{t}m_{0}}$ монеты и ${\displaystyle p^{\ast }}$ прибыль ${\displaystyle 2^{t}m_{1}}$.
• Если ${\displaystyle p}$ играл ${\displaystyle \mathrm {push} }$, тогда ${\displaystyle p}$ прибыль ${\displaystyle 2^{t+1}m_{1}}$ монеты и ${\displaystyle p^{\ast }}$ прибыль ${\displaystyle 2^{t+1}m_{0}}$.

Здесь, ${\displaystyle p^{\ast }\in \{I,II\}}$обозначает другого игрока.

Анализ равновесия и обратная индукция

An Обширная форма Представление четырехэтапной игры с сороконожками, которая заканчивается после четырех раундов разделением денег. Передача монет по столу представлена ​​движением р (проходя через ряд решетки, иногда также представленный А для поперек) и положить монеты в карман - это ход D (по решетке). Цифры 1 и 2 в верхней части диаграммы показаны лица, принимающие решения поочередно между двумя игроками, обозначенными здесь как 1 и 2, а числа внизу каждой ветви показывают выигрыш для игроков 1 и 2 соответственно.

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

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

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

Для игры, которая заканчивается после четырех раундов, рассуждение происходит следующим образом. Если бы мы добрались до последнего раунда игры, Player 2 было бы лучше, выбрав d вместо р, получив 4 монеты вместо 3. Однако, учитывая, что 2 выберут d, 1 следует выбрать D в предпоследнем раунде, получив 3 вместо 2. Учитывая, что 1 выбрал бы D в предпоследнем раунде, 2 следует выбрать d в предпоследнем раунде, получив 2 вместо 1. Но, учитывая это, Игрок 1 следует выбрать D в первом раунде, получив 1 вместо 0.

Есть большое количество Равновесия Нэша в игре с сороконожкой, но в каждой из них первый игрок отказывает в первом раунде, а второй игрок выходит из строя в следующем раунде достаточно часто, чтобы отговорить первого игрока от паса. Пребывание в равновесии по Нэшу не требует, чтобы стратегии были рациональными в каждая точка в игре, как и во вспомогательной игре, идеальное равновесие. Это означает, что стратегии, кооперативные в никогда не достигнутых более поздних раундах игры, все еще могут находиться в равновесии по Нэшу. В приведенном выше примере одно равновесие по Нэшу заключается в том, что оба игрока дезертируют в каждом раунде (даже в более поздних раундах, которые никогда не достигаются). Другое равновесие по Нэшу заключается в том, что игрок 1 дезертирует в первом раунде, но проходит в третьем раунде, а игрок 2 отказывается при любой возможности.

эмпирические результаты

Несколько исследований показали, что равновесие по Нэшу (а также совершенное равновесие в подиграх) наблюдается редко. Вместо этого субъекты регулярно демонстрируют частичное сотрудничество, играя «R» (или «r») в течение нескольких ходов, прежде чем в конечном итоге выбрать «D» (или «d»). Также редко субъекты сотрудничают на протяжении всей игры. Примеры см. В McKelvey and Palfrey (1992) и Nagel and Tang (1998). Как и во многих других теоретико-игровых экспериментах, ученые исследовали эффект увеличения ставок. Как и в других играх, например, ультиматумная игра, по мере увеличения ставок игра приближается (но не достигает) равновесной игры Нэша.^{[нужна цитата ]}

Пояснения

Поскольку эмпирические исследования дали результаты, несовместимые с традиционным анализом равновесия, было предложено несколько объяснений такого поведения. Розенталь (1981) предположил, что если у кого-то есть основания полагать, что его оппонент отклонится от поведения Нэша, то может быть выгодно не отступать в первом раунде.

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

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

Тем не менее, Parco, Rapoport и Stein (2002) показали, что уровень финансовых стимулов может иметь сильное влияние на результат в игре трех игроков: чем больше стимулы для отклонения, тем больше склонность к обучению поведению в повторяющейся одиночной игре. -играйте в экспериментальный замысел, чтобы приблизиться к равновесию по Нэшу.

Паласиос-Уэрта и Волидж (2009) находят этого эксперта шахматы игроки играют иначе, чем студенты колледжа. С ростом Эло, вероятность продолжения игры снижается; все Гроссмейстеры в эксперименте остановились при первой же возможности. Они приходят к выводу, что шахматисты знакомы с аргументацией обратной индукции и поэтому им нужно меньше учиться, чтобы достичь равновесия. Однако, пытаясь воспроизвести эти результаты, Левитт, Лист и Садофф (2010) находят сильно противоречивые результаты: ноль из шестнадцати гроссмейстеров останавливают игру на первом узле.

Значимость

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

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

Поскольку вознаграждение за некоторое количество сотрудничества в игре «Сороконожка» намного больше, чем немедленное отступничество, «рациональные» решения, данные обратная индукция может показаться парадоксальным. Это, в сочетании с тем фактом, что экспериментальные субъекты регулярно взаимодействуют в игре «Сороконожка», вызвало дискуссию о полезности идеализаций, используемых в решениях обратной индукции, см. Aumann (1995, 1996) и Binmore (1996).

Смотрите также

• Обратная индукция
• Экспериментальная экономика
• Дилемма путешественника
• Неожиданный парадокс зависания

Рекомендации

• Ауманн Р. (1995). «Обратная индукция и общее знание рациональности». Игры и экономическое поведение. 8 (1): 6–19. Дои:10.1016 / S0899-8256 (05) 80015-6.
• ——— (1996). «Ответ Бинмору». Игры и экономическое поведение. 17 (1): 138–146. Дои:10.1006 / игра.1996.0099.
• Бинмор, К. (2005). Естественная справедливость. Нью-Йорк: Издательство Оксфордского университета. ISBN  978-0-19-517811-1.
• ——— (1996). «Замечание об обратной индукции». Игры и экономическое поведение. 17 (1): 135–137. Дои:10.1006 / игра.1996.0098.
• Levitt, S.D .; Лист, Дж. А. и Садофф, С. Е. (2010). «Мат: изучение обратной индукции среди шахматистов» (PDF). Американский экономический обзор. 101 (2): 975–990. Дои:10.1257 / aer.101.2.975.
• Маккелви, Р. и Палфри, Т. (1992). «Экспериментальное исследование игры в сороконожку». Econometrica. 60 (4): 803–836. CiteSeerX  10.1.1.295.2774. Дои:10.2307/2951567. JSTOR  2951567.
• Нагель Р. и Танг Ф. Ф. (1998). «Экспериментальное исследование игры сороконожек в нормальной форме: исследование обучения». Журнал математической психологии. 42 (2–3): 356–384. Дои:10.1006 / jmps.1998.1225.
• Паласиос-Уэрта, И. и Волий, О. (2009). «Полевые многоножки». Американский экономический обзор. 99 (4): 1619–1635. Дои:10.1257 / aer.99.4.1619.
• Parco, J. E .; Рапопорт, А., Стейн, У. Э. (2002). «Влияние финансовых стимулов на подрыв взаимного доверия». Психологическая наука. 13 (3): 292–297. CiteSeerX  10.1.1.612.8407. Дои:10.1111/1467-9280.00454. PMID  12009054.
• Рапопорт, А .; Stein, W. E .; Парко, Дж. Э. и Николас, Т. Э. (2003). «Равновесная игра и адаптивное обучение в игре с участием трех человек». Игры и экономическое поведение. 43 (2): 239–265. Дои:10.1016 / S0899-8256 (03) 00009-5.
• Розенталь, Р. (1981). «Игры с идеальной информацией, хищническим ценообразованием и сетевым магазином». Журнал экономической теории. 25 (1): 92–100. CiteSeerX  10.1.1.482.8534. Дои:10.1016/0022-0531(81)90018-1.

внешняя ссылка

• Статья EconPort об игре «Сороконожка»
• Рациональность и теория игр - Колонка AMS об игре сороконожка
• Онлайн-эксперимент в VeconLab
• Играйте в игру Centipede в своем браузере на gametheorygame.nl