<< Предыдушая Следующая >>

Последовательное отбрасывание строго доминируемых стратегий



К сожалению, довольно часто бывает, что по крайней мере у одного из игроков нет строго доминирующей стратегии или даже просто доминирующей стратегии. Иногда в таких играх исход можно предсказать однозначно, если дополнительно к рациональности предположить, что каждый игрок знает цели партнеров и способен достаточно глубоко «просчитать» их умозаключения.
Рассмотрим в Игре 1 случай, когда а< с< Ъ. Пусть, к примеру, а = 1, с = 2, 6 = 3.
Если 2-й игрок выберет IBM, то 1-му игроку тоже выгодно выбрать IBM. Если же 2-й игрок выберет Макинтош, то 1-му игроку будет выгодно выбрать Макинтош. Эти оптимальные решения выделены в Таблице 5 подчеркиванием соответствующих выигрышей. Здесь оптимальное для 1-го игрока решение будет зависеть от того, какое решение примет 2-й игрок.
В этом и ему подобных случаях нельзя рассматривать мотивацию одного игрока, не рассматривая мотивацию других игроков. Игрок, у которого нет доминирующей стратегии, должен делать какие-то предположения о том, какие стратегии могут
Таблица 5
Игрок 2 IBM Mac
IBM
Игрок 1
Мае 2
3 со 0
0 5
2

выбрать другие игроки. Не специфицируя механизма формирования ожиданий, мы можем исходить из того, что все такие механизмы не противоречат рациональности игроков. Наиболее очевидное требование можно сформулировать следующим образом:
«Рациональный игрок не станет выбирать строго доминируемую стратегию».
Определение 6.
Стратегия yte Л', игрока г называется строго доминируемой, если существует стратегия х,е Л",, которая ее строго доминирует, т.е.
Щ{Уг, Х-г) < иг(Хг, X-i) •< Л ••
Проанализируем ситуацию, в которой структура игры (множества стратегий и функции выигрышей), а также то, что все игроки рациональны, известно каждому игроку. Более того, мы рассмотрим ситуацию, в которой все это общеизвестно, то есть не только каждый игрок знает это, но он знает, что все другие игроки знают это, и так далее до бесконечности.
В этом случае игрок должен не только сам исходить из того, что ни один из игроков не выберет доминируемую стратегию, но и учитывать, что другие игроки исходят из того, что ни один из игроков не выберет доминируемую стратегию. Эту цепочку предположений следует продолжить до бесконечности.
На этой основе строится метод получения решения игры путем отбрасывания строго доминируемых стратегий. Если в результате последовательности шагов, состоящих в вычеркивании строго доминируемых стратегий получился «остаток», в котором у каждого игрока только одна стратегия, то при сделанных нами предположениях о рациональности представляется естественным, что игроки должны выбрать именно эти не отброшенные стратегии.
Можно отметить, что в данном случае предполагается не только рациональность игроков, но и их способность провести соответствующие рассуждения, ведь цепочка рассуждений может быть достаточно длинной (я знаю, что он знает, что я знаю...).
Таблица б А
В 1
II 3
2 0
3 1
2 4
1 6
2 2
4 III 7
0 2
1 8
3 (Таблица 6) стратегия минирует стратегию стратегию III следует (игрок выбирающий станет выбирать эту
В Таблице 6 и таблицах на Рис. 3 показан пример процесса отбрасывания строго доминируемых стратегий. В исходной игре 3x3
I строго до- III, поэтому вычеркнуть строки, не стратегию).
Отбрасываемая стратегия обведена двойной волнистой рамкой. Остается игра 2x3 (Рис. 3 а) ), в которой стратегия А строго доминирует стратегию С. Стратегию С вычеркиваем (поскольку игрок, выбирающий столбцы, прогнозируя действия игрока, выбирающего строки, не станет ее выбирать). В получившейся игре 2x2 (Рис. 3 6)) стратегия I строго доминирует стратегию II. В получившейся после отбрасывания стратегии II игре (Рис. 3 в) ) у игрока, выбирающего строки, осталась только одна стратегия. Для игрока, выбирающего столбцы, стратегия А строго лучше стратегии В, поэтому стратегия В вычеркивается. Остается игра (Рис. 3 г) ), в которой каждый игрок имеет только по одной стратегии: (I, А). На основании этого можно сделать вывод, что в исходной игре 3x3 должен реализоваться исход (I, А). а)
б)
В 1 3
2 0
3 II 4
1 6
2 А В С 3
2 0
3 1
2 4
1 6
2 2
4 А В г) А 3 0 1 3 2 3 1 2 Рисунок 3. Если общеизвестно, что игроки рациональны, и после последовательного вычеркивания строго доминируемых стратегий у каждого игрока останется единственная стратегия (как в приведенной выше игре), то, как и в случае существования строго доминирующих стратегий у каждого игрока, исход игры может быть предсказан однозначно.
Даже если рассматриваемая процедура даст неоднозначный результат, то по крайней мере можно быть уверенным, что решение должно принадлежать полученному «остатку». Ситуации, когда в игре существует равновесие в доминирующих стратегиях, достаточно редки. И далеко не во всех играх можно найти решение, отбрасывая строго доминируемые стратегии. Соответствующий пример игры представлен в Таблице 7.
Таблица 7
Второй игрок выберет стратегию
В
Я. А, если предполагает, что первый вы-
X - ^ 1 берет стратегию Z; в то же время
— _ = стратегия В для него предпочтитель-
у ^ - " нее в случае, если первый выберет У.
— — Естественно предположить, что
z 1 " 3 _ отсУтствии У всех игроков доми-
-= 1— нирующих стратегий, выбор каждого
игрока зависит от ожиданий того, какими будут выборы других. Далее мы рассмотрим концепцию решения, основанную на этой идее.
Равновесие по Нэшу
Кроме ситуаций, рассмотренных в предыдущем разделе, бывают ситуации, которые естественно моделировать, исходя из следующих предположений:

игроки при принятии решений ориентируются на предполагаемые действия партнеров;
ожидания являются равновесными (совпадают с фактически выбранными партнерами действиями).
Если считать, что все игроки рациональны, так что каждый выбирает стратегию, дающую ему наибольший выигрыш при данных ожиданиях, то эти предположения приводят к концепции решения, называемой равновесием Нэша. В равновесии у каждого игрока нет оснований пересматривать свои ожидания.
Формально равновесие Нэша определяется следующим образом.
Определение 7.
Набор стратегий х е X является равновесием Нэша, если:
стратегия х* каждого игрока является наилучшим для него откликом на ожидаемые им стратегии других игроков х%:
щ(х\, x-i) = max xU) Vi = 1,..., п;
X, Е _Y,
ожидания совпадают с фактически выбираемыми стратегиями:
x-i = x*_i Vi = 1, ..., п.
Заметим, что при использовании равновесия Нэша для моделирования игровых ситуаций вопросы о том, знают ли игроки цели партнеров, знают ли они о рациональности партнеров, умеют ли их просчитывать, и т.д., отходят на второй план. Способ
формирования ожиданий выносится за рамки анализа; здесь важно только то, что ожидания являются равновесными.
Но если при анализе равновесия Нэша не важно, знает ли игрок цели других игроков, то может возникнуть сомнение в правомерности рассмотрения концепции Нэша в контексте игр с полной информацией. Все дело в том, что термин «полная информация» в теории игр имеет довольно узкое значение. Он фактически подразумевает только полноту сведений о типах партнеров (термин «тип игрока», разъясняется в параграфе, посвященном байесовским играм).
Как легко видеть, приведенное определение равновесия Нэша эквивалентно следующему свойству, которое обычно и используется в качестве определения:
Набор стратегий ж* е X является равновесием Нэша, если стратегия ж* каждого игрока является наилучшим для него откликом на стратегии других игроков х*_ ~.
щ{хг, ж*) = max щ(хг, ж*) Vг = 1, ..., п.
I, Ё Л',
Это свойство можно также записать в терминах так называемых функций (отображений) отклика.
Определение 8.
Отображение отклика г-ro игрока,
x_i i-> xt,
сопоставляет каждому набору стратегий других игроков, жч е Л" ,, множество стратегий г-го игрока, каждая из которых является наилучшим откликом на жч. Другими словами,
Щ(Уi, x-i) = max ut(xt, x_t) Vж_i e X_t, Vy, e Rt(x_t).
X, E _Y,
Введение отображений отклика позволяет записать определение равновесия Нэша более компактно: набор стратегий ж* е Л" является равновесием Нэша, если
< />'.(*'.! Vi = 1, ..., п. Если отклик каждого игрока однозначен (является функцией), то множество равновесий Нэша совпадает с множеством решений системы уравнений:
= V г = 1, ..., п.
В Таблице 7 отображения отклика игроков изображены подчеркиванием выигрышей, соответствующих оптимальным действиям. Равновесие Нэша в данной игре — клетка (В, У), поскольку выигрыши обоих игроков в ней подчеркнуты.
Проиллюстрируем использование функций отклика на примере игры, в которой игроки имеют континуум стратегий.
Игра 5. Международная торговля»
Две страны одновременно выбирают уровень таможенных пошлин, Объем торговли между странами, ж, зависит от установленных пошлин как
Ж = 1 - Tj - Т2.
Цель каждой страны — максимизировать доходы:
и, = т,ж —> max.

Рисунок 4 Равновесие Нэша в игре «Международная торговля»
Ф
Максимизируем выигрыш 1-й страны,
X^l-X!-!^,
по Xj считая фиксированным уровень пошлины, установленный 2-й страной. Условие первого порядка имеет вид
1-2Х!-Х2 = 0.
Поскольку максимизируемая функция строго вогнута, то условие первого порядка соответствует глобальному максимуму.
Условие первого порядка для задачи максимизации выигрыша 2-й страны находится аналогично:
l-x!-2x2 = 0.
Решив систему из двух линейных уравнений, найдем равновесие Нэша:
< = < = 1/3.
Оптимальный отклик 1-й страны на уровень таможенной пошлины, установленной 2-й страной описывается функцией
/ , 1 — х2
XllX2) ~~ 2
Аналогично, функция отклика 2-й страны имеет вид
X2(Xl) = 2~L"
Чтобы найти равновесие Нэша, требуется решить систему уравнений
г х1«)=<,
jx2(x;)=x;.
Графически поиск равновесия Нэша показан не Рис. 4. Точки, лежащие на кривых оптимального отклика Х^Хг) и Х^Х^, характеризуются тем, что в них касательные к кривым безразличия игроков параллельны соответствующей оси координат. Напомним, что кривой безразличия называют множество точек, в которых полезность рассматриваемого индивидуума одна и та же (щ(х) = const). Равновесие находится как точка пересечения кривых отклика.
Преимущество использования концепции равновесия Нэша состоит в том, что можно найти решение и в тех играх, в которых отбрасывание доминируемых стратегий не позволяет этого сделать. Однако сама концепция может показаться более спорной, поскольку опирается на сильные предположения о поведении игроков.
Связь между введенными концепциями решений описывается следующими утверждениями.

j Теорема 1.
j Если х = (х\, хт) — равновесие Нэша в некоторой иг- j ре, то ни одна из составляющих его стратегий не мо- j жет быть отброшена в результате применения процеду- ! ры последовательного отбрасывания строго доминируе- j мых стратегий.
Обратная теорема верна в случае единственности. ! Теорема 2.
j Если в результате последовательного отбрасывания ! строго доминируемых стратегий у каждого игрока оста- j ется единственная стратегия, xit то х* = (х\, ..., хт) — | равновесие Нэша в этой игре.
Доказательства этих двух утверждений даны в Приложении В (стр. 18). Нам важно здесь, что концепция Нэша не входит в противоречие с идеями рациональности, заложенной в процедуре отбрасывания строго доминируемых стратегий.
По-видимому, естественно считать, что разумно определенное равновесие, не может быть отброшено при последовательном отбрасывании строго доминируемых стратегий. Первую из теорем можно рассматривать как подтверждение того, что концепция Нэша достаточно разумна. Отметим, что данный результат относится только к строгому доминированию. Можно привести пример равновесия Нэша с одной или несколькими слабо доминируемыми стратегиями (см. напр. Таблицу 12 на стр. 27).
<< Предыдушая Следующая >>
= Перейти к содержанию учебника =
Информация, релевантная "Последовательное отбрасывание строго доминируемых стратегий"
  1. 1.5. Рационализуемые стратегии
    Мы обсуждали исключение строго доминируемых стратегий, исходя из того, что рациональный игрок никогда не выбрал бы такую стратегию, вне зависимости от того, как играют его оппоненты. Однако «общее знание» структуры игры и того, что игроки рациональны, позволяет исключить больше, нежели просто последовательно удалить строго доминируемые стратегии, причем здесь опять же важную роль играет «общее
  2. 16.2.3 Последовательное отбрасывание строго доминируемых стратегий
    К сожалению, довольно часто бывает, что по крайней мере у одного из игроков нет строго доминирующей стратегии или даже просто доминирующей стратегии. Иногда в таких играх исход можно предсказать однозначно, если дополнительно к рациональности предположить, что каждый игрок знает цели партнеров и способен достаточно глубоко "просчитать" их умозаключения. Таблица 16.5. Игрок 1 IBM Mac IBM Игрок 2
  3. 1.3. Доминируемые стратегии
    Посмотрим внимательно на приведенную выше игру (рис.7). Независимо от того, как играет игрок 1, R дает игроку 2 строго больший выигрыш, нежели М. В этом смысле стратегия М строго доминируема, поэтому ясно, что рациональный игрок 2 не должен играть М. Далее, если игрок 1 знает (т.к. он сам рационален и знает, что другой рационален...), что 2 не будет играть М, то для него и будет лучше, чем т или
  4. 16.2.4 Равновесие по Нэшу
    Кроме ситуаций, рассмотренных в предыдущем разделе, бывают ситуации , которые естественно моделировать, исходя из следующих предположений: игроки при принятии решений ориентируются на предполагаемые действия партнеров; ожидания являются равновесными (совпадают с фактически выбранными партнерами действиями). Если считать, что все игроки рациональны, так что каждый выбирает стратегию, дающую ему
  5. ИГРЫ С СОВЕРШЕННОЙ ИНФОРМАЦИЕЙ
    Грубо говоря, в этих играх очередной игрок знает (обладает совершенной информацией) все ходы, которые были предприняты ранее. Здесь полностью отсутствует элемент одновременности. Формально все информационные множества имеют только один узел. Игра 1 является примером такой игры; игра Штакельберга из главы 8 и ценовая игра с краткосрочным связыванием из главы 6 тоже. Любопытно в этих играх то, что
  6. РАВНОВЕСИЕ НЭША
    В этом разделе мы будем пользоваться только представлением в нормальной форме. Для того чтобы принять оптимальное решение» игрок должен в общем предвидеть поведение своего оппонента. Основным и бесспорным основанием для такого предположения является то, что оппоненту не следует во время игры пользоваться доминируемыми стратегиями. Если один ход дает игроку выплату ниже, чем другой, то, что бы
  7. 1.10. Равновесие «дрожащей руки»
    Мы уже обсуждали ранее слабо доминируемые стратегии и сейчас вновь обратимся к ним. Рассмотрим игру, изображенную на рис. 28. L R U ( (2,2) (0,-2) \ D \ (-2,0) (0,0) ) Рис. 28. Легко видеть, что в этой игре два р.Н. в чистых стратегиях (U, L) и (D, R) , причем второе равновесие характерно тем, что оба игрока выбирают свои слабо доминируемые стратегии. Мы остановимся сейчас на
  8. 4.2. Последовательное равновесие
    Важным, тесно связанным с ССБР понятием равновесия, которое в то же время усиливает понятие слабого совершенного Байесова равновесия за счет введения дополнительного условия согласованности представлений, является понятие последовательного равновесия (Wilson, Kreps, 1982). В противоположность совершенному Байесову равновесию, в понятии последовательного равновесия эта согласованность вводится не
  9. СОДЕРЖАНИЕ
    ЭЛЕМЕНТЫ ТЕОРИИ НЕКООПЕРАТИВНЫХ ИГР 5 Введение 5 Статические игры с полной информацией 5 Нормальная форма игры 6 Концепция доминирования 8 Последовательное отбрасывание строго доминируемых стратегий 11 Равновесие по Нэшу 12 Равновесие Нэша в смешанных стратегиях 15 Приложение А 18 Приложение В 18 Задачи 20 Динамические игры с совершенной информацией 22 Задачи 30 Динамические игры с
  10. 1.12. Задачи
    1. Какие стратегии в следующей игре, представленной в нормальной форме, выживают после последовательного исключения строго доминируемых стратегий? Найдите все равновесия по Нэшу. L С R Г / (2Д) (1,1) (4,2) м (3,4) (1,2) (2,3) в V (1,3) (0,2) (3,0) 2. Игроки I и II торгуются по поводу того, как поделить один доллар. Оба игрока одновременно называют доли, которые они бы хотели иметь, 5*1 и , где
  11. 16.2.5 Равновесие Нэша в смешанных стратегиях
    Нетрудно построить примеры игр, в которых равновесие Нэша отсутствует. Следующая игра представляет пример такой ситуации. Игра б. "Инспекция" В этой игре первый игрок (проверяемый) поставлен перед выбором - платить или не платить подоходный налог. Второй - налоговой инспектор, решает, проверять или не проверять именно этого налогоплательщика. Если инспектор "ловит" недобросовестного
Портал "ЭКОНОМИСТЪ" © 2014
info@economuch.com
Рейтинг@Mail.ru