Аудит /
Институциональная экономика /
Информационные технологии в экономике /
История экономики /
Логистика /
Макроэкономика /
Международная экономика /
Микроэкономика /
Мировая экономика /
Операционный анализ /
Оптимизация /
Страхование /
Управленческий учет /
Экономика /
Экономика и управление народным хозяйством (по отраслям) /
Экономическая теория /
Экономический анализ
Главная
Экономика
Экономика
| С. Л. Печерский, А. А. Беляева. Теория игр для экономистов, 2001 | |
2.5. Повторяющиеся игры |
|
|
Рассмотрим следующий вариант Дилеммы Заключенного (рис.20). Будем считать, что игра повторяется дважды, причем игроки узнают исход первого розыгрыша до того, как начинается второй. Считаем пока, что нет дисконта и, поэтому выигрыши есть просто сумма выигрышей в первом и втором разыгрывании, т.е. мы имеем дело с двухпериодной или двухшаговой Дилеммой Заключенного. L 2 R2 и ( (1Д) (5,0) \ Кг \ (0,5) (4,4) ) Рис. 20. Следуя той логике СПРН, которая у нас была ранее, посмотрим, что происходит на втором шаге игры. Ясно, что исход игры второго шага будет р.Н., т.е. (L\,L2) Х А это значит, что игра на первом шаге сводится к тому, что к каждому элементу исходной матрицы нужно добавить выигрыши второго шага, т. е. (1,1). Таким образом, матрица становится ((2,2) (6,1) \ V (1,6) (5,5) J а в ней р.Н. единственно - (L\,L2) , значит СПРН в этой двухшаговой Дилемме Заключенного - это (L\, Ь2) на первом шаге и (L\,L2) Чна втором. Теперь отвлечемся на время от двукратного повторения игры. Пусть G = (Ai,..., Ап; и\,..., ип) - статическая игра с полной информацией, в которой игроки одновременно выбирают ходы ai из своих пространств стратегий Ai и соответствующие выигрыши есть щ(а\,..., ап) . Будем называть G лбазовой игрой. Определение 2.5.1. Конечной повторяющейся игрой G(T) базовой игры G называется игра, в которой G разыгрывается Т раз и перед началом каждого очередного розыгрыша игрокам известны исходы всех предыдущих розыгрышей, т. е. известны стратегии, избранные игроками, и полученные выигрыши. Выигрыши в игре G(T) определяются как сумма (или дисконтированная сумма) выигрышей на каждом шаге. Рассмотренная выше ситуация на самом деле характерна и для общего случая. Предложение 2.5.1. Если базовая игра G имеет единственное равновесие по Нэшу, то для любого конечного Т повторяющаяся игра G(T) имеет единственное СПРН: на каждом шаге играется р.Н. Рассмотрим теперь ситуацию, когда базовая игра G имеет несколько равновесий (Gibbons): L2 м2 i?2 Li ((1,1) (5,0) (0,0) Mi (0,5) (4,4) (0,0) Ri V (0,0) (0,0) (3,3) Здесь 2 равновесия по Нэшу в чистых стратегиях и (i?i,i?2). Предположим, что эта игра повторяется дважды, причем исход первой игры известен до того, как разыгрывается вторая. Для нас важно, что может существовать СПРН, в котором на первом шаге играется (М^Мг). Это тот самый нюанс, который важен для нас, поскольку он, так сказать, разделяет дух того, что происходит в случае бесконечного разыгрывания игры G. Как и раньше, предполагаем (поскольку речь идет о СПРН), что игроки считают, что исход второго розыгрыша - это р.Н. базовой игры. Вообще говоря, можно предположить, что игроки могут ожидать, что различным исходам 1-го этапа будут соответствовать разные исходы 2-го этапа. Предположим, например, что игроки ожидают, что (i?i, R2) будет исходом, если первый исход был (М^Мг), но {Е\Д2), если один из 8 оставшихся был исходом 1-го этапа. В этом случае игра на 1-м шаге сводится к игре, Е2 М2 R2 Ех / (2,2) (6,1) (1,1) \ Мг (1,6) (7,7) (1,1) Ri V (М) (1.1) (4,4) У Здесь (3,3) добавлено к выигрышам, соответствующим (МЬМ2) и (1,1) - к 8 остальным элементам исходной матрицы. В этой игре уже 3 р.Н.: (Li,L2), (Mi,M2), (i?i,i?2). Эти три р.Н. соответствуют СПРН в первоначальной повторяющейся игре. Обозначим ((w, х)(у, z)), - исходы в повторяющейся игре (w, х) - на 1-м шаге, (у, z) - на 2-м. Равновесие (Li,L2) соответствует лсовершенному иод-игровому исходу ((Li, L2), (Li, L2)) в повторяющейся игре. Аналогично р.Н. (i?i,i?2) соответствует лсовершенному под-игровому исходу ((i?i, i?2), (Li, L2)) в повторяющейся игре. Эти два исхода просто лнаследуют р.Н. базовой игры. Но третий исход - качественно другой: (Mi,M2) - соответствует лсовершенному под-игровому (СП) исходу ((Mi, М2), (i?i, i?2)) в повторяющейся игре, т.к. лпредвидимый исход 2-го шага - это (i?i,i?2) вслед за (Mi,M2). Иными словами, кооперацию можно достичь на 1-м шаге СП- исхода повторяющейся игры. А это уже дает пример более общей природы: если G - статическая игра с полной информацией и множественными р.Н., то может существовать СП исход в игре G(T) , в которой на любом шаге t < Т исход шага t - не является р.Н. Основной вывод здесь такой: угрозы или обещания, которым можно верить в будущем, могут влиять на текущее поведение. Второй вывод, однако, состоит в том, что лпод- игровое совершенство может не воплощать достаточно сильные определения лправдоподобия. Говоря, например, о СП исходе ((Mi, М2), (i?i, i?2)), мы предполагали, что игроки предвидят, что (i?i, i?2) будет исходом на втором шаге, если исход первого шага был (Mi,M2), a (Li,L2) - исходом второго шага игры, если любой другой из 8 оставшихся исходов возникает на первом шаге. Однако игра (Li, L2) на втором шаге может показаться достаточно глупой, если (i?i,i?2) с выигры-шем (3,3) также возможно в равновесии на втором шаге игры. Далее можно рассуждать следующим образом. Если (Mi,M2) не стало исходом первого шага, так как предполо жительно будет играться на втором шаге, то каждый игрок может считать, что лчто прошло, то прошло, и предпочтительная для обоих игроков ситуация (i?i,i?2) должна разыгрываться на 2-м шаге. Но если (i?i,i?2) будет исходом 2-го шага после любого исхода розыгрыша, то пропадают стимулы играть (МЬМ2) на 1-м шаге: розыгрыш 1-го шага сводится просто к добавлению к каждому исходу (3, 3). А тогда Li есть лучший ответ игрока i на Mj игрока j . Прежде чем перейти к бесконечным повторяющимся играм, вернемся к нашему определению и введем коэффициент дисконтирования. Считаем, что игроки дисконтируют будущие выигрыши с общим дисконтом S . Иногда бывает удобно рассматривать не просто суммарный выигрыш т t=1 а нормировать его для того, чтобы рассматривать среднюю полезность за период, т.е. t=1 средний дисконтированный выигрыш (за период). Он показывает, сколько нужно платить игроку i в каждом периоде, чтобы он получил тот же суммарный выигрыш. Если Дилемма Заключенного разыгрывается один раз, то нужно лсознаваться. Если разыгрывается конечное число раз, то лиод-игровое совершенство требует в последний раз лсознаться, а обратная индукция говорит, что единственное СПРН - это лсознаваться всегда. Если игра разыгрывается бесконечное число раз, то лсознаться остается СПРН. Более того - это единственное равновесие такое, что игра на каждом шаге не меняется в зависимости от того, что игралось на предыдущих шагах. Но если горизонт бесконечен и 5 > 1/2 , то, как мы увидим ниже, следующий набор стратегий оказывается тоже СПРН: лмолчать (кооперироваться) на 1-м шаге и продолжать лмолчать (кооперироваться) до тех пор, пока никто не предал. Если только кто-то предал, то далее предавать всегда. Пример. L м R и ( (о,о) (3,4) (6,0) м (4,3) (0,0) (0,0) D V (0,6) (0,0) (5,5) Считаем, что эта игра разыгрывается дважды и что выигрыши - дисконтированная сумма выигрышей. Если эта игра разыгрывается один раз, то здесь 3 равновесия: (М, L), (U, М) и jM^j , jM^j с выигры-шами (4,3), (3,4) и соответственно. Здесь запись у С/, jM^j означает, что с вероятностью | играется л С/ и с вероятностью | - играется М. Эффективный набор выигрышей (5, 5) не достижим. Однако в двухшаговой игре с 5 > 7/9 следующий набор стратегий является СПРН: Играть (D, R) на первом шаге. Если исход первого шага (D, R) , то играть (М, L) во втором шаге; если исход первого шага - не (Д Д), то играть ((3/7?/, 4/7М), (3/7L, 4/7М)) на втором шаге. По построению эти стратегии используют р.Н. на 2-м шаге. Отклонение этой стратегии на 1-м шаге увеличивает текущий выигрыш на 1 и уменьшает следующие выигрыши игроков 1 и 2 соответственно с 4 или 3, до 12/7. Поэтому игрок 1 не будет отклоняться, если 1 < ^4 - y^j 5 или 5 > 7/16, а второй не будет отклоняться, если 1 < I 3 - 4г 15 или 5 > 7/9. Итак, как мы отмечали, имеет место следующее уточнение: если в базовой игре G есть несколько равновесий по Нэшу, то может существовать СПРН в повторяющейся игре G(T) такое, что для любого t < Т исход шага t не является равновесием по Нэшу. В бесконечно повторяющихся играх справедлив более сильный результат: даже если в базовой игре G есть единственное равновесие по Нэшу, то может существовать СПРН бесконечно повторяющейся игры, в которой никакой лпо-шаговый исход не будет равновесием по Нэшу. Итак, рассмотрим вариант Дилеммы Заключенного, повторяющейся бесконечно, причем для любого t исходы t - 1 предыдущего шага игры известны до начала разыгрывания шага t: L2 R2 Li MM) (5,0) \ Кг \ (0,5) (4,4) У Разумеется, в бесконечном случае уже без дисконтирующего множителя не обойтись. Определение 2.5.2. Если 8 - коэффициент дисконтирования, то приведенная стоимость бесконечной последовательности выигрышей tt\, тг2, ... есть оо t=1 Мы покажем, что в нашем варианте Дилеммы Заключенного лкооперация (Ri,R2) на каждом шаге может быть СПРН бесконечно повторяющейся игры (хотя единственный равновесный исход в базовой игре - это (L\, Е2)). А именно, если игроки кооперируются сегодня, то они кооперируются и завтра, и т.д., а в противном случае они играют лплохое равновесие. Предположим, что игрок г начинает игру, кооперируясь, и продолжает так только и если только оба игрока кооперировались на любом предыдущем шаге. Формально его стратегия описывается следующим образом: Играть Ri на 1-м шаге. На шаге t, если все предыдущие tЧ1 исхода были (R\, R2) , играть RI; в противном случае играть Li . Это так называемая триггерная стратегия (стратегия переключения). Если игроки придерживаются этой стратегии, то в бесконечно повторяющейся игре равновесным исходом будет (R\, R2) на каждом шаге . Мы вначале покажем, что если S достаточно близко к 1, то это есть равновесие по Нэшу в бесконечно повторяющейся игре для обоих игроков, придерживающихся этой стратегии. А затем покажем, что это СПРН. Чтобы показать, что это есть равновесие по Нэшу в бесконечно повторяющейся игре, предположим, что г-й игрок использует триггерную стратегию, и покажем, что если S достаточно близко к 1, то для j-го игрока лучшим ответом будет тоже применять такую стратегию. Так как игрок i будет играть Li всегда, как только на каком-то шаге исход отличается от (Ri,R2), то лучшим ответом j-го будет тоже играть LJ всегда после нарушения (Ri,R2). Т.е. осталось определить лучший ответ j-го игрока на 1-м шаге и на всех шагах таких, что все предыдущие были (RI, R2) ж Игра Lj даст 5 на этом шаге, но переключит на лнекооперативное поведение игрока i (а значит и j) навсегда. Следовательно, на любом будущем шаге выигрыш будет 1; так как 1 + 5 +52+ ХХХ+ХХХ = 1/(1 - 5) , то приведенная стоимость последовательности выигрышей есть 5 + 5 + 52 + -- - = 5 + уз^ . С другой стороны, ответ Rj дает выигрыши 4 и аналогич-ный выбор между LJ и RJ на следующем шаге. Пусть V - приведенная стоимость выигрыша j -го игрока, если он играет оптимально. Если игра Rj оптимальна, то V = 4 + 5V . Следовательно, " = тЬ- Если Lj оптимальна, то V = 5 + у^ > следовательно, Rj оптимальна в том и только в том случае, если 4 ^ г 5 с ^ 1 > 5 Н или о > 1-5 ~ 1-5 ~ 4 Пусть теперь G - игра с полной информацией, в которой игроки одновременно выбирают ходы. Если дана базовая игра G, то G(оо, 5) - это бесконечно повторяющаяся игра, в которой G повторяется всегда и у игроков общий коэффициент дисконтирования 5 . Для любого t исходы предыдущих tЧ1 шагов наблюдаются до начала шага t. Выигрыш каждого игрока - приведенная стоимость его выигрышей. Как хорошо известно, в любой игре стратегия - полный план действия. В статической игре с полной информацией - это просто ходы. В динамике, разумеется, все сложнее. Скажем, в двухшаговой Дилемме Заключенного стратегию можно записать как пятерку (v, w, х, у, z): v - на 1-м шаге; w - ходить w , если исход был (L\, Ь2) ; х - ходить х , если - (L\, R2) ; у - ходить у , если - (Ri, L2) ; z - ходить z , если - (Ri, R2) ж Это можно представить себе, как набор команд агентам: 1-й ходит на первом шаге, 2-й - на втором и т. д. В повторяющейся игре G(T) или G(00, 5) история игры до шага t - это лзапись ходов игроков до шага t. В конечно повторяющейся игре G(T) или бесконечно повторяющейся игре G(00, 5) стратегия игрока описывает действие игрока, которые он предпринимает на каждом шаге, для любой возможной истории. (В этом смысле история соответствует информационному множеству: каждая история приводит к вполне определенному информационному множеству (одноточечному), а каждому информационному множеству (одноточечному) соответствует вполне определенный путь (история), который приводит именно к этому информационному множеству.) Для конечно повторяющейся игры G(T) под-игра, начинающаяся на шаге t-\-1, - это конечно повторяющаяся игра, в которой G разыгрывается Т - t раз и которая обозначается G(T - t) . В G(oo,S) каждая под-игра, начиная с шага t + 1, идентична G(oo,S). Игр, начинающихся с ?+1, столько же, сколько историй. Разумеется, каждая под-игра осмысленна вместе с предысторией. Таким образом, здесь, как и ранее, равновесие по Нэшу является СПРН, если соответствующие стратегии игроков образуют равновесие по Нэшу в любой под-игре. СПРН является уточнением равновесия по Нэшу в том смысле, что стратегии игроков должны, во-первых, образовывать равновесие по Нэшу, а кроме того, лвыдерживать дополнительный тест - в под-играх. Вернемся к Дилемме Заключенного и к триггерной стратегии, рассмотренной выше. Здесь все под-игры можно разбить на 2 группы: под-игры, в которых все исходы предыдущих шагов были (i?i,i?2), и под-игры, в которых хотя бы один из предыдущих исходов был не (i?i, R2). Если игроки используют триггерную стратегию во всей игре, то 1) стратегии игроков в под-игре первой группы тоже оказываются триггерными стратегиями, которые формируют равновесие по Нэшу во всей игре; 2) стратегии игроков в под- игре второй группы просто лнавечно повторяют лпошаговое равновесие {Ь\Д2) , которое также является равновесием во всей игре. Поэтому равновесие по Нэшу в триггерных стратегиях является СПРН. 5 4 1 1 4 5 Рис. 21. Набор выигрышей ..., хп) называется достижимым в базовой игре G, если он является выпуклой комбинацией выигрышей в ситуациях в чистых стратегиях игры G . На рис. 21 изображено множество достижимых выигрышей в Дилемме Заключенного - это параллелограмм. Средний выигрыш (за период) бесконечной последовательности выигрышей 7Ti, 7Г2,7Гз,... при данном коэффициенте дисконтирования S есть оо (1-5)^-4 t=1 Преимущество среднего выигрыша по сравнению с приведенной стоимостью в том, что средний выигрыш непо-средственно можно сравнивать с пошаговыми выигрышами. В рассмотренном нами варианте Дилеммы Заключенного оба игрока могут получать выигрыш 4 в каждом периоде. Такая последовательность выигрышей дает средний выигрыш 4, а приведенную стоимость 4/(1 - S) . С другой стороны, средний выигрыш - это просто приведенная стоимость с некоторым множителем; максимизация среднего выигрыша эквивалентна максимизации приведенной стоимости. Мы можем сформулировать теперь знаменитую теорему, которая носит название народной (фольклорной) - Folk Theorem, которая столь хорошо известна специалистам, что ее авторство считается лнародным, хотя, по-видимому, первым ее для СПРН доказал Джеймс Фридман. Теорема 2.5.1. (Friedman, 1971). Пусть G конечная, статическая игра с полной информацией. Пусть (е\,..., еп), выигрыши в состоянии равновесия по Нэшу, и пусть (х\,... ,хп) - любой достижимый вектор выигрышей в G . Если Xi > е{ для любого i и 8 достаточно близко к 1, то существует СПРН в игре G(oo,S), дающее (х\,... ,хп) в качестве среднего выигрыша. Доказательство этой теоремы можно найти, например, в учебнике Gibbons (1992). На рис. 19 множество возможных СПРН заштриховано. Пример. Сговор Курно-дуополистов. Вспомним статическую дуополию по Курно. Спрос на рынке P(Q) = а - Q , где Q = qi + q2 , Q < а, у фирм постоянные предельные затраты с, и нет фиксированных затрат. В единственном равновесии по Нэшу каждая фирма производит qc = (а - с)/3 . Поскольку суммарный объем в равновесии 2 (а - с)/3 превышает монопольный объем qm = (а - с)/2, обеим фирмам было бы лучше, если бы каждый производил половину монопольного выпуска qi = qmj2 . Рассмотрим бесконечно повторяющуюся игру, в которой базовая игра - это рассматриваемая дуополия по Курно, причем у обеих фирм общий коэффициент дисконтирования Ь . Мы сейчас вычислим значение Ь , для которых в совершенном лпод-игровом равновесии по Нэшу этой бесконечно повторяющейся игры играется (обеими фирмами) следующая стратегия: Производить половину монопольного объема, qmj2 , в первом периоде. В периоде t играть qmj2 , если обе фирмы про- изводили qmj2 в каждом из предыдущих t - 1 периодов; в противном случае производить qc. Прибыль фирмы, когда обе фирмы производят qmj2 , есть (а - с)2/8 , которую мы обозначим через 7гт/2 . Прибыль фирмы, когда обе производят qc, есть (а - с)2/9 , которую мы обозначим 7ГС. Далее, если фирма i собирается производить qmj2 в этом периоде, то объем, максимизирующий прибыль фирмы j , решает задачу 1 яз к J 2 max(a - q3 - -qm - c)qy Решением этой задачи является qj = 3^ag ^ с соответствующей прибылью тт^ = ж Таким образом, ситуации, в которых фирмы играют триггерную стратегию, приведенную выше, являются равновесием по Нэшу, если 1 1 5 Km > Kd + -7ГС. _9_ 17 ' Подставляя тгт , тгс, тг^ , получаем S > |
|
| << Предыдушая | Следующая >> |
| = К содержанию = | |
Похожие документы: "2.5. Повторяющиеся игры" |
|
|