Игра в сороконожку: Теория и практика

Введение

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

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

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

Если игрок 1 сыграл , то он получает монет, а игрок 2 получает . Если игрок 1 сыграл , то он получает монет, а игрок 2 получает .

Здесь обозначает другого игрока.

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

Стандартные инструменты теории игр предсказывают, что первый игрок поступится принципами в первом раунде, забрав кучу монет себе. В игре в сороконожки чистая стратегия состоит из набора действий (одно для каждой точки выбора в игре, даже если некоторые из этих точек выбора никогда не будут достигнуты), а смешанная стратегия – это распределение вероятностей по возможным чистым стратегиям. Существует несколько чистых равновесий Нэша в игре в сороконожки и бесконечно много смешанных равновесий Нэша. Однако существует только одно совершенное подыгровое равновесие (популярное уточнение концепции равновесия Нэша). В единственном совершенном подыгровом равновесии каждый игрок выбирает поступиться принципами при каждой возможности. Это, конечно, означает дезертирство в первом этапе. Однако в равновесиях Нэша действия, которые были бы предприняты после первоначальных точек выбора (даже если они никогда не достигаются, поскольку первый игрок немедленно дезертирует), могут быть кооперативными. Дезертирство первого игрока является единственным совершенным подыгровым равновесием и требуется любым равновесием Нэша, и это можно установить методом обратной индукции. Предположим, два игрока достигли финального раунда игры; второму игроку будет лучше поступиться принципами и забрать немного большую долю банка. Поскольку мы предполагаем, что второй игрок поступится принципами, первому игроку выгоднее поступиться принципами во втором с конца раунде, получив немного больший выигрыш, чем если бы он позволил второму игроку поступиться принципами в последнем раунде. Но зная это, второй игрок должен поступиться принципами в третьем с конца раунде, получив немного больший выигрыш, чем если бы он позволил первому игроку поступиться принципами во втором с конца раунде. Это рассуждение идет в обратном направлении по дереву игры, пока не придет к выводу, что лучшее действие – это для первого игрока поступиться принципами в первом раунде. Такое же рассуждение можно применить к любому узлу в дереве игры. Для игры, которая заканчивается после четырех раундов, это рассуждение происходит следующим образом. Если бы мы достигли последнего раунда игры, игрок 2 сделал бы лучше, выбрав d вместо r, получив 4 монеты вместо 3. Однако, учитывая, что 2 выберет d, 1 должен выбрать D во втором с конца раунде, получив 3 вместо 2. Учитывая, что 1 выберет D во втором с конца раунде, 2 должен выбрать d в третьем с конца раунде, получив 2 вместо 1. Но учитывая это, игрок 1 должен выбрать D в первом раунде, получив 1 вместо 0. В игре в сороконожки существует большое количество равновесий Нэша, но в каждом из них первый игрок дезертирует в первом раунде, а второй игрок дезертирует в следующем раунде достаточно часто, чтобы удержать первого игрока от продолжения игры. Нахождение в равновесии Нэша не требует, чтобы стратегии были рациональными в каждой точке игры, как в совершенном подыгровом равновесии. Это означает, что стратегии, которые являются кооперативными в никогда не достигаемых более поздних раундах игры, все еще могут находиться в равновесии Нэша. В приведенном выше примере одно равновесие Нэша состоит в том, что оба игрока дезертируют в каждом раунде (даже в более поздних раундах, которые никогда не достигаются). Другое равновесие Нэша – это то, что игрок 1 дезертирует в первом раунде, но продолжает игру в третьем раунде, а игрок 2 дезертирует при любой возможности.

Standard game theoretic tools predict that the first player will defect on the first round, taking the pile of coins for himself. In the centipede game, a pure strategy consists of a set of actions (one for each choice point in the game, even though some of these choice points may never be reached) and a mixed strategy is a probability distribution over the possible pure strategies. There are several pure strategy Nash equilibria of the centipede game and infinitely many mixed strategy Nash equilibria. However, there is only one subgame perfect equilibrium (a popular refinement to the Nash equilibrium concept). In the unique subgame perfect equilibrium, each player chooses to defect at every opportunity. This, of course, means defection at the first stage. In the Nash equilibria, however, the actions that would be taken after the initial choice opportunities (even though they are never reached since the first player defects immediately) may be cooperative. Defection by the first player is the unique subgame perfect equilibrium and required by any Nash equilibrium, it can be established by backward induction. Suppose two players reach the final round of the game; the second player will do better by defecting and taking a slightly larger share of the pot. Since we suppose the second player will defect, the first player does better by defecting in the second to last round, taking a slightly higher payoff than she would have received by allowing the second player to defect in the last round. But knowing this, the second player ought to defect in the third to last round, taking a slightly higher payoff than he would have received by allowing the first player to defect in the second to last round. This reasoning proceeds backwards through the game tree until one concludes that the best action is for the first player to defect in the first round. The same reasoning can apply to any node in the game tree. For a game that ends after four rounds, this reasoning proceeds as follows. If we were to reach the last round of the game, Player 2 would do better by choosing d instead of r, receiving 4 coins instead of 3. However, given that 2 will choose d, 1 should choose D in the second to last round, receiving 3 instead of 2. Given that 1 would choose D in the second to last round, 2 should choose d in the third to last round, receiving 2 instead of 1. But given this, Player 1 should choose D in the first round, receiving 1 instead of 0. There are a large number of Nash equilibria in a centipede game, but in each, the first player defects on the first round and the second player defects in the next round frequently enough to dissuade the first player from passing. Being in a Nash equilibrium does not require that strategies be rational at every point in the game as in the subgame perfect equilibrium. This means that strategies that are cooperative in the never reached later rounds of the game could still be in a Nash equilibrium. In the example above, one Nash equilibrium is for both players to defect on each round (even in the later rounds that are never reached). Another Nash equilibrium is for player 1 to defect on the first round, but pass on the third round and for player 2 to defect at any opportunity.

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

Несколько исследований показали, что игра в соответствии с равновесием Нэша (и, аналогично, с совершенным подигровым равновесием) наблюдается редко. Вместо этого участники регулярно демонстрируют частичное сотрудничество, выбирая "R" (или "r") на протяжении нескольких ходов, прежде чем в конечном итоге перейти к выбору "D" (или "d"). Также редко участники сотрудничают на протяжении всей игры. Примеры можно найти в работах McKelvey и Palfrey (1992), Nagel и Tang (1998) или в обзоре Krockow и др. (2016). Исследователи изучали влияние повышения ставок. Как и в других играх, например, в игре с ультиматумом, с увеличением ставок стратегия игроков приближается (но не достигает) равновесия Нэша. Поскольку эмпирические исследования дали результаты, противоречащие традиционному анализу равновесия, было предложено несколько объяснений этого поведения. Для объяснения экспериментальных данных необходимо предположить наличие либо альтруистических игроков, либо игроков с ограниченной рациональностью.

Объяснение, основанное на предпочтениях

Одна из причин, по которой люди могут отклоняться от равновесного поведения, заключается в том, что некоторые из них альтруистичны. Основная идея состоит в том, что в каждой игре существует определенная вероятность сыграть против альтруистичного игрока, и если эта вероятность достаточно высока, то выгоднее дезертировать в последнем раунде, а не в первом. Если достаточное количество людей являются альтруистами, то жертва выгоды от дезертирства в первом раунде оправдывается ради определения, является ли ваш оппонент альтруистом. Маккельви и Палфри (1992) разработали модель, включающую альтруистичных и рациональных игроков, которые в конечном итоге прибегают к смешанной стратегии (то есть играют на нескольких узлах с определенной вероятностью). Для соответствия экспериментальным данным, в модели необходимо, чтобы около 5% игроков были альтруистами. Elmshauser (2022) показал, что модель, включающая альтруистичных игроков и игроков, избегающих неопределенности (вместо рациональных игроков), еще лучше объясняет результаты экспериментов. Некоторые эксперименты пытались выяснить, являются ли игроки, склонные к уступкам, также наиболее альтруистичными в других играх или жизненных ситуациях (см., например, Pulford et al. или Gamba и Regner (2019), которые оценивали социальную ценностную ориентацию). Игроки, чаще уступающие, действительно проявляли большую альтруистичность, но эта разница не была значительной.

Ограниченное объяснение рациональности

Розенталь (1981) предположил, что если есть основания полагать, что оппонент отклонится от стратегии Нэша, то может быть выгодно не предавать в первом раунде. Другая возможность связана с ошибками. Если существует значительная вероятность ошибки в действиях, возможно, из-за того, что оппонент не до конца проанализировал ситуацию методом обратной индукции, то сотрудничество в начальных раундах может оказаться выгодным (и рациональным). Маккельви и Палфри (1995) разработали модель квантового равновесия, в которой агенты играют в равновесие Нэша с ошибками, и применили ее к игре «Стоножка». Еще одной моделью, способной объяснить поведение в игре «Стоножка», является модель уровня k, представляющая собой теорию когнитивной иерархии: игрок уровня 0 играет случайным образом, игрок уровня 1 оптимально реагирует на игрока уровня 0, игрок уровня 2 оптимально реагирует на игрока уровня 1 и так далее. Во многих играх исследователи заметили, что большинство игроков были игроками уровня 2 или 3, что согласуется с экспериментальными данными по игре «Стоножка». Гарсия Пола и др. (2020) пришли к выводу, основанному на эксперименте, что большинство игроков руководствуются логикой уровня k или логикой квантового ответа. Однако Парко, Рапопорт и Штайн (2002) показали, что размер финансовых стимулов может существенно влиять на исход игры с тремя участниками: чем выше стимулы к отклонению от стратегии, тем выше вероятность обучения игроков в рамках повторяющегося эксперимента с однократной игрой, направленного на достижение равновесия Нэша. Паласиос Хуерта и Волиж (2009) обнаружили, что опытные шахматисты играют иначе, чем студенты. С ростом рейтинга Эло вероятность продолжения игры снижается; все гроссмейстеры в эксперименте остановились при первой же возможности. Они заключили, что шахматисты знакомы с методом обратной индукции и, следовательно, им требуется меньше обучения для достижения равновесия. Однако, пытаясь воспроизвести эти результаты, Левитт, Лист и Сэдофф (2010) получили резко противоречивые данные: ни один из шестнадцати гроссмейстеров не остановил игру на первом узле. Качественное исследование, проведенное Крокковом и др. с использованием протокола «думай вслух», который требовал от игроков в игре «Стоножка» озвучивать свои рассуждения во время игры, выявило ряд когнитивных искажений, таких как предвзятость к действию или предвзятость к завершению, которые могут приводить к иррациональному выбору в игре.

Rosenthal (1981) suggested that if one has reason to believe his opponent will deviate from Nash behavior, then it may be advantageous to not defect on the first round. Another possibility involves error. If there is a significant possibility of error in action, perhaps because your opponent has not reasoned completely through the backward induction, it may be advantageous (and rational) to cooperate in the initial rounds. The quantal response equilibrium of McKelvey and Palfrey (1995) created a model with agents playing Nash equilibrium with errors and they applied it to the Centipede game. Another modelling able to explain behaviors in the centipede game is the level k model, which is a cognitive hierarchy theory : a L0 player plays randomly, the L1 player best responds to the L0 player, the L2 player best responds to the L1 player and so on. In many games, scholars observed that most of the player were L2 or L3 players, which is consistent with the centipede game experimental data. Garcia Pola et al. (2020) concluded from an experiment that most of the players either play following a Level k logic or a Quantal response logic. However, Parco, Rapoport and Stein (2002) illustrated that the level of financial incentives can have a profound effect on the outcome in a three player game: the larger the incentives are for deviation, the greater propensity for learning behavior in a repeated single play experimental design to move toward the Nash equilibrium. Palacios Huerta and Volij (2009) find that expert chess players play differently from college students. With a rising Elo, the probability of continuing the game declines; all Grandmasters in the experiment stopped at their first chance. They conclude that chess players are familiar with using backward induction reasoning and hence need less learning to reach the equilibrium. However, in an attempt to replicate these findings, Levitt, List, and Sadoff (2010) find strongly contradictory results, with zero of sixteen Grandmasters stopping the game at the first node. Qualitative research by Krockow et al., which employed think aloud protocols that required players in a Centipede game to vocalise their reasoning during the game, indicated a range of decision biases such as action bias or completion bias, which may drive irrational choices in the game.

Значение

Как и в дилемме заключенного, эта игра представляет собой конфликт между личными интересами и взаимной выгодой. Если бы соблюдение правил было гарантировано, оба игрока предпочли бы сотрудничать на протяжении всей игры. Однако личные интересы игрока или недоверие между игроками могут помешать этому и привести к ситуации, в которой обоим будет хуже, чем если бы они сотрудничали, не раздумывая. Хотя дилемма заключенного получила значительное внимание в связи с этим, игра в "Стоножку" осталась относительно менее изученной. Кроме того, Бинмор (2005) утверждает, что некоторые реальные ситуации можно описать с помощью игры в "Стоножку". Он приводит в пример обмен товарами между сторонами, не доверяющими друг другу. Другой пример, который Бинмор (2005) сопоставляет с игрой в "Стоножку", – это поведение гермафродитов морского окуня, которые поочередно обмениваются икрой для оплодотворения. В этих случаях мы наблюдаем широкое распространение сотрудничества. Поскольку выигрыш от некоторого уровня сотрудничества в игре в "Стоножку" значительно превышает выигрыш от немедного отказа от сотрудничества, "рациональные" решения, полученные методом обратной индукции, могут показаться парадоксальными. Это, в сочетании с тем, что участники экспериментов регулярно сотрудничают в игре в "Стоножку", вызвало дискуссии о целесообразности идеализаций, используемых при решении методом обратной индукции, см. Aumann (1995, 1996) и Binmore (1996).