В теории игр ход , действие или игра — это любой из вариантов, который игрок может выбрать в обстановке, где оптимальный результат зависит не только от его собственных действий, но и от действий других. [1] Дисциплина в основном касается действий игрока в игре, влияющих на поведение или действия других игроков. Некоторые примеры «игр» включают шахматы, бридж, покер, монополию, дипломатию или морской бой. [2]
Термин стратегия обычно используется для обозначения полного алгоритма игры, сообщающего игроку, что делать в каждой возможной ситуации. Стратегия игрока определяет действие, которое игрок предпримет на любом этапе игры. Однако идею стратегии часто путают или объединяют с идеей хода или действия из-за соответствия между ходами и чистыми стратегиями в большинстве игр : для любого хода X «всегда играй ход X » является примером допустимой стратегии, и в результате каждый ход также можно считать стратегией. Другие авторы рассматривают стратегии как нечто иное, нежели действия, и, следовательно, отличное.
Полезно думать о «стратегии» как о списке направлений, а о «ходе» как об отдельном повороте в списке направлений. Эта стратегия основана на выигрыше или результате каждого действия. Цель каждого агента — рассмотреть свой выигрыш на основе действия конкурента. Например, конкурент A может предположить, что конкурент B выходит на рынок. Отсюда конкурент A сравнивает выигрыши, которые он получает, войдя и не войдя. Следующий шаг — предположить, что конкурент B не входит, а затем рассмотреть, какой выигрыш лучше, основываясь на том, решит ли конкурент A войти или не войти. Этот метод может определить доминирующие стратегии, где игрок может определить действие, которое он может предпринять независимо от того, что делает конкурент, чтобы попытаться максимизировать выигрыш.
Профиль стратегии (иногда называемый комбинацией стратегий ) — это набор стратегий для всех игроков, который полностью определяет все действия в игре. Профиль стратегии должен включать одну и только одну стратегию для каждого игрока.
Набор стратегий игрока определяет, какие стратегии ему доступны для игры.
Игрок имеет конечный набор стратегий, если у него есть несколько доступных ему дискретных стратегий. Например, игра « камень, ножницы, бумага» включает в себя один ход каждого игрока, и ход каждого игрока делается без знания хода другого, а не в качестве ответа, поэтому у каждого игрока есть конечный набор стратегий {камень, ножницы, бумага}.
В противном случае набор стратегий бесконечен. Например, игра по разрезанию торта имеет ограниченный континуум стратегий в наборе стратегий {Отрезать где-то между нулем процентов и 100 процентов торта}.
В динамической игре , играх, которые разыгрываются в течение ряда времени, набор стратегий состоит из возможных правил, которые игрок может дать роботу или агенту о том, как играть в игру. Например, в игре ультиматум набор стратегий для второго игрока будет состоять из всех возможных правил, какие предложения принять, а какие отклонить.
В байесовской игре или играх, в которых игроки имеют неполную информацию друг о друге, набор стратегий аналогичен набору в динамической игре. Он состоит из правил того, какие действия следует предпринять для любой возможной частной информации.
В прикладной теории игр определение наборов стратегий является важной частью искусства создания игры одновременно решаемой и осмысленной. Теоретик игр может использовать знание общей проблемы, то есть трения между двумя или более игроками, чтобы ограничить стратегические пространства и облегчить решение.
Например, строго говоря, в игре Ultimatum у игрока могут быть такие стратегии, как: Отклонить предложения ($1, $3, $5, ..., $19), принять предложения ($0, $2, $4, ..., $20) . Включение всех таких стратегий делает пространство стратегий очень большим и довольно сложной проблемой. Теоретик игр вместо этого мог бы полагать, что он может ограничить набор стратегий следующим образом: {Отклонить любое предложение ≤ x , принять любое предложение > x ; для x в диапазоне ($0, $1, $2, ..., $20)}.
Чистая стратегия дает полное определение того, как игрок будет играть в игру. Чистую стратегию можно рассматривать как отдельный конкретный план, зависящий от наблюдений, которые игрок делает в ходе игры. В частности, она определяет ход, который сделает игрок в любой ситуации, с которой он может столкнуться. Набор стратегий игрока — это набор чистых стратегий, доступных этому игроку.
Смешанная стратегия — это назначение вероятности каждой чистой стратегии. Привлечение смешанной стратегии часто происходит потому, что игра не допускает рационального описания при указании чистой стратегии для игры. Это позволяет игроку случайным образом выбирать чистую стратегию. (См. следующий раздел для иллюстрации.) Поскольку вероятности непрерывны, игроку доступно бесконечно много смешанных стратегий. Поскольку вероятности назначаются стратегиям для конкретного игрока при обсуждении выплат определенных сценариев, выплату следует называть «ожидаемой выплатой».
Конечно, можно рассматривать чистую стратегию как вырожденный случай смешанной стратегии, в котором эта конкретная чистая стратегия выбирается с вероятностью 1 , а каждая другая стратегия — с вероятностью 0 .
Полностью смешанная стратегия — это смешанная стратегия, в которой игрок назначает строго положительную вероятность каждой чистой стратегии. (Полностью смешанные стратегии важны для уточнения равновесия, такого как идеальное равновесие дрожащей руки .)
В футбольном пенальти игрок должен выбрать, бить ли в правую или левую сторону ворот, и одновременно вратарь должен решить, в какую сторону его заблокировать. Кроме того, у игрока есть направление, в котором он лучше всего бьет, это влево, если он правша. Матрица для футбольного матча иллюстрирует эту ситуацию, упрощенную форму игры, изученную Кьяппори, Левиттом и Гроузклоузом (2002). [3] Она предполагает, что если вратарь угадает правильно, удар будет заблокирован, что устанавливается на базовый выигрыш 0 для обоих игроков. Если вратарь угадает неправильно, удар с большей вероятностью попадет в ворота, если он будет слева (выигрыши +2 для игрока и -2 для вратаря), чем если он будет справа (меньший выигрыш +1 для игрока и -1 для вратаря).
В этой игре нет равновесия чистой стратегии, поскольку один из игроков будет отклоняться от любого профиля стратегий — например, (Влево, Влево) не является равновесием, поскольку игрок, играющий с мячом, отклонится вправо и увеличит свой выигрыш с 0 до 1.
Равновесие смешанной стратегии бьющего определяется тем фактом, что они будут отклоняться от рандомизации, если только их выигрыши от удара слева и справа не будут точно равны. Если вратарь наклоняется влево с вероятностью g, ожидаемый выигрыш бьющего от удара слева равен g(0) + (1-g)(2), а от удара справа равен g(1) + (1-g)(0). Приравнивая эти значения, получаем g = 2/3. Аналогично, вратарь готов рандомизировать только в том случае, если бьющий выбирает вероятность смешанной стратегии k, такую, что выигрыш наклона влево равен k(0) + (1-k)(-1) равен выигрышу наклона вправо равен k(-2) + (1-k)(0), поэтому k = 1/3. Таким образом, равновесие смешанной стратегии равно (Prob(Kick Left) = 1/3, Prob(Lean Left) = 2/3).
В равновесии игрок бьет в свою лучшую сторону только в 1/3 случаев. Это потому, что вратарь больше защищает эту сторону. Также в равновесии игроку безразлично, в какую сторону он бьет, но для того, чтобы это было равновесие, он должен выбрать вероятность ровно 1/3.
Chiappori, Levitt и Groseclose пытаются измерить, насколько важно для игрока, который бьет, бить в свою любимую сторону, добавлять центральные удары и т. д., и посмотреть, как на самом деле ведут себя профессиональные игроки. Они обнаруживают, что они действительно рандомизируются, и что игроки, которые бьют, бьют в свою любимую сторону в 45% случаев, а вратари наклоняются в эту сторону в 57% случаев. Их статья хорошо известна как пример того, как люди в реальной жизни используют смешанные стратегии.
В своей знаменитой статье Джон Форбс Нэш доказал, что для каждой конечной игры существует равновесие . Равновесия Нэша можно разделить на два типа. Равновесия Нэша чистой стратегии — это равновесия Нэша, в которых все игроки играют в чистые стратегии. Равновесия Нэша смешанной стратегии — это равновесия, в которых по крайней мере один игрок играет в смешанную стратегию. Хотя Нэш доказал, что каждая конечная игра имеет равновесие Нэша, не все имеют равновесия Нэша чистой стратегии. Пример игры, в которой нет равновесия Нэша в чистых стратегиях, см. в Matching pennies . Однако во многих играх есть равновесия Нэша чистой стратегии (например, игра «Координация» , дилемма заключенного , охота на оленя ). Кроме того, в играх могут быть как равновесия чистой стратегии, так и равновесия смешанной стратегии. Простым примером является игра «Чистая координация», в которой в дополнение к чистым стратегиям (A, A) и (B, B) существует смешанное равновесие, в котором оба игрока играют в любую стратегию с вероятностью 1/2.
В 1980-х годах концепция смешанных стратегий подверглась резкой критике за то, что она «интуитивно проблематична», поскольку они являются слабыми равновесиями Нэша, и игроку безразлично, следовать ли вероятности своей равновесной стратегии или отклоняться к какой-то другой вероятности. [4] [5] Специалист по теории игр Ариэль Рубинштейн описывает альтернативные способы понимания этой концепции. Первый, предложенный Харсани (1973), [6] называется очищением и предполагает, что интерпретация смешанных стратегий просто отражает наше отсутствие знаний об информации игроков и процессе принятия решений. По-видимому, случайные выборы затем рассматриваются как последствия неопределенных, не имеющих отношения к выигрышу экзогенных факторов. [5] Вторая интерпретация предполагает, что игроки в игре представляют большую популяцию агентов. Каждый из агентов выбирает чистую стратегию, а выигрыш зависит от доли агентов, выбирающих каждую стратегию. Таким образом, смешанная стратегия представляет собой распределение чистых стратегий, выбранных каждой популяцией. Однако это не дает никаких оправданий для случая, когда игроки являются отдельными агентами.
Позднее Ауманн и Бранденбургер (1995), [7] переосмыслили равновесие Нэша как равновесие в убеждениях , а не в действиях. Например, в игре «камень, ножницы, бумага » равновесие в убеждениях заставило бы каждого игрока верить, что другой с равной вероятностью будет играть каждую стратегию. Однако эта интерпретация ослабляет описательную силу равновесия Нэша, поскольку в таком равновесии каждый игрок может фактически играть чистую стратегию «Камень» в каждой игре игры, даже если со временем вероятности будут такими же, как у смешанной стратегии.
В то время как смешанная стратегия назначает распределение вероятностей по чистым стратегиям, стратегия поведения назначает в каждом информационном наборе распределение вероятностей по набору возможных действий. Хотя эти две концепции очень тесно связаны в контексте игр в нормальной форме, они имеют совершенно разные последствия для игр в расширенной форме. Грубо говоря, смешанная стратегия случайным образом выбирает детерминированный путь по дереву игры , в то время как стратегия поведения может рассматриваться как стохастический путь. Связь между смешанной и поведенческой стратегиями является предметом теоремы Куна , поведенческого взгляда на традиционные гипотезы теории игр. Результат устанавливает, что в любой конечной игре в расширенной форме с идеальным отзывом для любого игрока и любой смешанной стратегии существует стратегия поведения, которая, вопреки всем профилям стратегий (других игроков), вызывает такое же распределение по конечным узлам, как и смешанная стратегия. Обратное также верно.
Известный пример того, почему для эквивалентности требуется идеальное воспоминание, приведен Пиччоне и Рубинштейном (1997) [ необходима полная цитата ] в их игре «Рассеянный водитель» .
Эквивалентность исхода объединяет смешанную и поведенческую стратегию Игрока i по отношению к чистой стратегии противника Игрока i. Эквивалентность исхода определяется как ситуация, в которой для любой смешанной и поведенческой стратегии, которую выбирает Игрок i, в ответ на любую чистую стратегию, которую играет противник Игрока I, распределение результатов смешанной и поведенческой стратегии должно быть равным. Эту эквивалентность можно описать следующей формулой: (Q^(U(i), S(-i)))(z) = (Q^(β(i), S(-i)))(z), где U(i) описывает смешанную стратегию Игрока i, β(i) описывает поведенческую стратегию Игрока i, а S(-i) является стратегией противника. [8]
Идеальное припоминание определяется как способность каждого игрока в игре помнить и вспоминать все прошлые действия в игре. Идеальное припоминание требуется для эквивалентности, поскольку в конечных играх с несовершенным припоминанием будут существовать смешанные стратегии Игрока I, в которых нет эквивалентной стратегии поведения. Это полностью описано в игре « Рассеянный водитель» , сформулированной Пиччоне и Рубинштейном. Короче говоря, эта игра основана на принятии решений водителем с несовершенным припоминанием, которому нужно съехать с шоссе на втором съезде, чтобы добраться до дома, но он не помнит, на каком перекрестке он находится, когда добирается до него. Рисунок [2] описывает эту игру.
Без идеальной информации (т. е. несовершенной информации) игроки делают выбор в каждом узле принятия решений, не зная о решениях, которые ему предшествовали. Поэтому смешанная стратегия игрока может привести к результатам, которые не может дать его поведенческая стратегия, и наоборот. Это продемонстрировано в игре «Рассеянный водитель» . При идеальной памяти и информации у водителя есть единственная чистая стратегия, которая есть [продолжить, выйти], поскольку водитель знает, на каком перекрестке (или узле принятия решений) он находится, когда прибывает к нему. С другой стороны, если рассматривать только стадию оптимального планирования, максимальный выигрыш достигается при продолжении на обоих перекрестках, максимизируясь при p=2/3 (ссылка). Эта простая игра для одного игрока демонстрирует важность идеальной памяти для эквивалентности результатов и ее влияние на игры в нормальной и расширенной форме. [9]