Стратегия (теория игр)
В теории игр ход от , действие или игра — это любой из вариантов, который игрок может выбрать в ситуации, когда оптимальный результат зависит не только от его собственных действий , но и действий других. [1] Дисциплина в основном касается действий игрока в игре, влияющих на поведение или действия других игроков. Некоторые примеры «игр» включают шахматы, бридж, покер, монополию, дипломатию или линкор. [2]
Термин «стратегия» обычно используется для обозначения полного алгоритма игры, сообщающего игроку, что делать в каждой возможной ситуации. Стратегия игрока определяет действия, которые он предпримет на любом этапе игры. Однако идею стратегии часто путают или смешивают с идеей хода или действия из-за соответствия между ходами и чистыми стратегиями в большинстве игр : для любого хода X фраза «всегда играть ход X » является примером допустимого варианта. стратегии, и в результате каждый ход также можно считать стратегией. Другие авторы рассматривают стратегии как вещи, отличные от действий, и, следовательно, отличные от действий.
Полезно рассматривать «стратегию» как список направлений, а «ход» — как отдельный поворот в самом списке направлений. Эта стратегия основана на выигрыше или результате каждого действия. Цель каждого агента — рассчитать свой выигрыш на основе действий конкурентов. Например, конкурент А может предположить, что на рынок выйдет конкурент Б. После этого конкурент А сравнивает выигрыши, которые он получает, вступая и не вступая в игру. Следующий шаг — предположить, что конкурент Б не участвует, а затем рассмотреть, какой выигрыш лучше, исходя из того, решит ли конкурент А участвовать или не участвовать. Этот метод позволяет определить доминирующие стратегии, при которых игрок может определить действие, которое он может предпринять независимо от того, что делает конкурент, чтобы попытаться максимизировать выигрыш.
Профиль стратегии (иногда называемый комбинацией стратегий ) — это набор стратегий для всех игроков, который полностью определяет все действия в игре. Профиль стратегии должен включать одну и только одну стратегию для каждого игрока.
Набор стратегий
[ редактировать ]игрока Набор стратегий определяет, какие стратегии ему доступны.
Игрок имеет конечный набор стратегий, если ему доступно несколько дискретных стратегий. Например, игра « камень-ножницы-бумага» включает в себя один ход каждого игрока — и каждый игрок делает ход без знания другого игрока, а не в качестве ответа — поэтому у каждого игрока есть конечный набор стратегий {камень-ножницы-бумага}.
В противном случае набор стратегий бесконечен. Например, игра по разрезанию торта имеет ограниченный континуум стратегий в наборе стратегий {Разрезать где-нибудь между 0 и 100 процентами торта}.
В динамических играх , играх, которые проводятся в течение определенного периода времени, набор стратегий состоит из возможных правил, которые игрок может дать роботу или агенту о том, как играть в игру. Например, в игре «Ультиматум» стратегия, установленная для второго игрока, будет состоять из всех возможных правил, предложения которых следует принять, а какие — отклонить.
В байесовской игре или играх, в которых игроки имеют неполную информацию друг о друге, набор стратегий аналогичен таковому в динамической игре. Он состоит из правил, определяющих, какие действия следует предпринять в отношении любой возможной конфиденциальной информации.
Выбор набора стратегий
[ редактировать ]В прикладной теории игр определение наборов стратегий является важной частью искусства сделать игру одновременно разрешимой и значимой. Теоретик игр может использовать знание общей проблемы, то есть трений между двумя или более игроками, чтобы ограничить пространство стратегии и облегчить решение.
Например, строго говоря, в игре «Ультиматум» у игрока могут быть такие стратегии: отклонять предложения на сумму (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, 0 | +2, -2 |
| Удар вправо | +1, -1 | 0, 0 | |
| Расплата за футбольный матч (кикер, вратарь) | |||
В этой игре нет чисто стратегического равновесия, потому что тот или иной игрок будет отклоняться от любого профиля стратегий - например, (Влево, Влево) не является равновесием, потому что бьющий игрок отклонится вправо и увеличит свой выигрыш с 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. Таким образом, равновесие смешанной стратегии равно (Вероятность(Удар влево) = 1/3, Вероятность(Наклон влево) = 2/3).
В равновесии бьющий игрок наносит удар в лучшую сторону только в 1/3 случаев. Это потому, что вратарь больше защищает эту сторону. Кроме того, в равновесии игроку, выполняющему удар, безразлично, в какую сторону он нанесет удар, но для достижения равновесия он должен выбрать ровно 1/3 вероятности.
Чиаппори, Левитт и Гросеклоуз пытаются оценить, насколько важно для игрока, выполняющего удар, наносить удары в пользу своей любимой стороны, добавлять удары по центру и т. д., и смотреть, как на самом деле ведут себя профессиональные игроки. Они обнаружили, что они рандомизированы, и что бьющие игроки бьют в свою любимую сторону в 45% случаев, а вратари наклоняются в эту сторону в 57% случаев. Их статья известна как пример того, как люди в реальной жизни используют смешанные стратегии.
Значение
[ редактировать ]В своей знаменитой статье Джон Форбс Нэш существует равновесие доказал, что в каждой конечной игре . Равновесия Нэша можно разделить на два типа. Равновесие по Нэшу в чистой стратегии — это равновесие по Нэшу, при котором все игроки используют чистые стратегии. Смешанная стратегия Равновесие Нэша — это равновесие, при котором хотя бы один игрок придерживается смешанной стратегии. Хотя Нэш доказал, что каждая конечная игра имеет равновесие Нэша, не все из них имеют равновесие Нэша в чистой стратегии. Пример игры, в которой нет равновесия Нэша в чистых стратегиях, см. в разделе « Сопоставление монет» . Однако во многих играх есть чистая стратегия равновесия Нэша (например, координационная игра , дилемма узника , охота на оленя ). Кроме того, игры могут иметь равновесие как в чистой стратегии, так и в смешанной стратегии. Простым примером является игра чистой координации, где в дополнение к чистым стратегиям (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]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Бен Полак Теория игр: Стенограмма лекции 1 ECON 159, 5 сентября 2007 г., Открытые Йельские курсы .
- ^ Ауманн, Р. (22 марта 2017 г.). Теория игр. В: Пэлгрейв Макмиллан . Лондон: Пэлгрейв Макмиллан. ISBN 978-1-349-95121-5 .
- ^ Кьяппори, Пенсильвания-А.; Левитт, С.; Гросеклоуз, Т. (2002). «Тестирование равновесия смешанной стратегии, когда игроки разнородны: случай пенальти в футболе» (PDF) . Американский экономический обзор . 92 (4): 1138. CiteSeerX 10.1.1.178.1646 . дои : 10.1257/00028280260344678 .
- ^ Ауманн, Р. (1985). «Чего пытается достичь теория игр?» (PDF) . Ин Эрроу, К.; Хонкапохья, С. (ред.). Границы экономики . Оксфорд: Бэзил Блэквелл. стр. 909–924.
- ^ Jump up to: а б Рубинштейн, А. (1991). «Комментарии к интерпретации теории игр». Эконометрика . 59 (4): 909–924. дои : 10.2307/2938166 . JSTOR 2938166 .
- ^ Харсаньи, Джон (1973). «Игры со случайно нарушенными выигрышами: новое обоснование точек равновесия смешанной стратегии». Межд. Дж. Теория игр . 2 : 1–23. дои : 10.1007/BF01737554 . S2CID 154484458 .
- ^ Ауманн, Роберт ; Бранденбургер, Адам (1995). «Эпистемические условия равновесия Нэша». Эконометрика . 63 (5): 1161–1180. CiteSeerX 10.1.1.122.5816 . дои : 10.2307/2171725 . JSTOR 2171725 .
- ^ Симодзи, Макото (01 мая 2012 г.). «Результат-эквивалентность самоподтверждающегося равновесия и равновесия Нэша» . Игры и экономическое поведение . 75 (1): 441–447. дои : 10.1016/j.geb.2011.09.010 . ISSN 0899-8256 .
- ^ Как, Субхаш (2017). «Редукс проблемы рассеянного водителя». arXiv : 1702.05778 [ cs.AI ].
| Базы данных органов управления : Национальные |
|---|
