Лекция 16. Повторяющиеся игры

До сих пор мы рассматривали игры, которые играются "однократно"; игроки получают выигрыши и расходятся. Однако часто приходится многократно играть "одну и ту же игру" с теми же партнерами. Такую ситуацию называют повторяющимися играми, и им посвящено много исследований. Некоторые аспекты мы и рассмотрим.

Главный интерес повторяющихся игр связан с интуицией, что люди иначе ведут себя с теми, с кем ожидают поддерживать долговременные отношения. Если игра играется однократно, то игрок может безнаказанно нарушать лю­бые предварительные договоренности. Вот почему редко равновесия бывают оптимальными. Однако если игра разыгрывается многократно, то некоторые соглашения могут стать равновесиями. Потому что нарушение соглашения в одном раунде может привести к наказанию в последующих раундах. К этому же относятся вопросы репутации. Например, репутация несгибаемого, жест­кого, неисправимого может быть ценным активом в будущей игре.

Повторяющиеся игры. При рассмотрении повторяющихся игр нужно уточнить следующие вещи: длительность игры, наблюдения, стратегии и вы­игрыши.

1. Длительность. Игры могут играться фиксированное конечное количе­ство раз. Или бесконечное. Возможен и более сложный случай, когда время игры рандомизировано.

2. Наблюдения. Возможность наказывать противника за нарушение согла­шения основана на том, что вы знаете, как он играл на предыдущих раундах. Для простоты, мы будем считать, что вся прошлая информация (о ходах, вы­игрышах) доступна.

3. Стратегии. Это уже не просто последовательность ходов в каждом раунде; у вас появляется возможность делать выбор в зависимости от име­ющейся информации. Для того, чтобы сделать это более ясным, рассмотрим двухкруговую игру.

Пусть нам дана какая-нибудь простая игра двух лиц со стратегиями «2 и £1, Было бы ошибкой считать, что стратегические возможности игроков исчерпываются множествами 5^x5^. Главная новость - что при совершении второго хода игрок может учитывать то, что произошло в первом раунде.

Произошедшее в первом раунде (история) задается множеством Б\ х 5г = 5. Поэтому стратегия игрока 1 - это пара (в, /), где в - ход в первом раунде, и / -отображение из Б в 51, возможные его реакции на историю. В нашем примере реакций 24 = 16, поэтому каждый игрок имеет 32 стратегии в двухраундовой игре.

Так что стратегий довольно много. Конечно, тут много лишнего. Напри­мер, зачем игроку реагировать на свою стратегию? Более естественно огра­ничиться отображениями / из $2 в их Уже только 4, так что множество стратегий каждого по существу состоит из 8 элементов.

Аналогично обстоит дело и в общем случае. Если исходная игра была (Л^,       (щ)), то стратегия игрока г на £ + 1-ом шаге - это отображение

. с* _.

Множество 5дг (т.е. £-я степень 5дг) есть множество всех историй развития игры до момента 1+1. А полная стратегия - это последовательность = (//), где Ь меняется от 1 до Т. Если дан профиль таких стратегий (/•). / Е Л*, то индуктивно определяется последовательность ходов в*, Ь £ {1,.... Т}. где

1 _ Л  Л _ £2(1 \ к+1 _ гк+1( 1 к \

•ъ/ ~~ Л% 1 ь% ~~ .// \,ъЛ" / • • • • 1 ь{     — .//     \,ъЛ" • • • • 1 ,ъ Л" / • • • • 1

т.е. процесс игры.

Как видно, стратегий много и они могут описываться сложно.

4. Выигрыши. Наконец, нужно сказать про выигрыши. Если момент Т окончания игры конечный, то с выигрышем все ясно: это суммарный вы­игрыш ^Л=1 иг(3%)^ ИЛИ Лучше, СреДНИЙ ВЫИГрЫШ (1/Т) ^М=1 иг(3%) ■ ЕСЛИ

случайный момент г, то это ожидаемый средний выигрыш. Наиболее дели­катным является определение выигрыша в случае Т = оо. Здесь обычно поступают одним из двух (или трех) способов.

Первый - образуют средний выигрыш Х^=1 Щ^ю/^ и устремляют Т к бесконечности. Небольшое препятствие состоит в том, что этот предел может не существовать. Тогда берут, например, нижний предел

г

при Т —>• оо.

Второй способ - образовать дисконтированный выигрыш. Для этого фик­сируют некоторый дисконт 6 < 1, и полагают

00

ЩГм) = (1-6)У£&-1щ(з%) (2)

Умножение на 1 — 6 = 1 1        производится для удобства; тогда вы-

игрыш можно рассматривать это как выпуклую смесь щ(з^).

В случае Т = оо получающаяся игра называется суперигрой. Итак, повто­рим, что набор суперстратегий /д- сначала преобразуется в последователь­ность ходов (.%-д-). 1 < £ < Т + 1, а она - в последовательность выигрышей М|(вдг), по которой уже определяется "средний" выигрыш

Повторяющаяся дилемма заключенных. Начнем с Дилеммы заклю­ченных. Удобно ее задать так. Каждый из игроков обращается к Высшему существу с одной из просьб: - дать его компаньону 2 доллара, или - чтобы оно дало ему самому 1 доллар. Таблица выигрышей имеет вид

 

С

Е

С

2,2

0,3

Е

3,0

1,1

Стратегии Е доминирующие и приводят к исходу (1,1), что хуже коопе­ративного исхода (2, 2). Казалось бы, игрокам полезно сговориться и исполь­зовать стратегии С. Однако если игра происходит один раз, и игроки делают ходы независимо и одновременно, каждому выгодно перейти на стратегию Е. Изменится ли ситуация, если они играют многократно?

Пусть сначала игра играется двукратно. Довольно ясно, что равновесная стратегия будет эгоистической. Во втором периоде каждому выгодно исполь­зовать Е, независимо от того, что было в первом. Но тогда и в первом раунде играются стратегии Е. То же заключение сохраняется при любой конечной продолжительности Т.

 

Однако если игра продолжается бесконечно, ситуация кардинально меня­ется. Рассмотрим такую "свирепую" (grim, или триггерную) стратегию пове­дения 1-го игрока: придерживаться С, пока это делает игрок 2; и перейти на Е, как только 2-ой применит Е. Аналогично ведет себя второй игрок. Выигрыши будем определять по формуле (1). При использовании приведен­ных выше стратегий игроки в каждом раунде получают (2,2), поэтому и их средний выигрыш равен (2, 2). Мы утверждаем, что это равновесие.

В самом деле, пусть первый игрок будет применять другую стратегию, а второй остается при старой, свирепой. Если на шаге Т первый игрок впервые применит Э, то последовательность его выигрышей имеет вид

2, 2,2, 3, хт+ъ

где ;/;/ при Ь > Т равны 0 или 1. Среднее значение будет < 1, потому что бесконечный плохой хвост съест все преимущество, полученное на первых Т раундах. Таким образом, отклонение от приведенной выше стратегии пове­дения не дает успеха первому. Аналогично для второго игрока.

Близкий результат дает и стратегия "зуб-за-зуб" - делать то, что ваш ком­паньон делал на предыдущем шаге.

Таким образом, на этом примере мы убедились, что бесконечное разыгры­вание может привести к кооперативному поведению. Конечно, тут важно, что игра не имеет конца.

Дисконт. А что получится, если использовать в суперигре дисконтирован­ную сумму выигрышей (2)? Если применяются указанные стратегии поведе­ния, выигрыши снова равны (2,2). Пусть первый отклоняется, и получается последовательность его выигрышей, как выше. Ее оценка равна

(1 - 6)(2 + 26 + 252 + ... + 25т^ + 35т + [нечто < 1] х 5т+1/(1 - 6)) <

< (1 - 5)[2(1 - 5т)/(1 -6) + 35т + 5т+1/(1 -5)]<2 + 5Т- 25т+1.

Поэтому если 26 > 1, т.е. если 6 > 1/2, то отклонение невыгодно.

Вывод: при дисконте многое зависит от того, близок ли дисконт к 1. Если 6 ~ 1, то возможно кооперативное поведение. Напротив, если дисконт бли­зок к 0, то в каждой партии игрок живет сегодняшним днем, мало думая о последствиях.

В чем же дело? Далее всюду мы будем предполагать, что дисконт равен 1 (т.е. пользоваться критерием среднего выигрыша). Вопрос, который я хочу обсудить - в чем же дело с такой разницей в ответе на Дилемму в случае Т < оо и Т = оо. Что-то здесь неправильно - но где?

Видимо, нужно усомниться в ответе с конечным повторением. Мы видели, что он по­лучен индукцией с конца (фактически это теорема: существует единственное совершенное (к подыграм) равновесие в конечно-повторяющейся Дилемме). А это предполагает очень высокую, если не сказать - чрезмерную, степень рациональности. Мало того, что игро­ки рациональны и что эта рациональность является общим знанием; эта убежденность в рациональности другого должна быть непоколебимой никакими фактами. И очень важно точное знание всеми конца игры.

Если же есть сомнения в длительности игры или рациональности оппонента, выво­ды при конечном (но большом) числе повторений могут приближаться к бесконечно-повторяющимся. Допустим, что мой противник считает, что я буду применять свирепую стратегию: переключиться на Э, как только он применит Э. Хотя это и не лучшая моя стратегия. Тогда ему интереснее будет придерживаться стратегии К почти до самого кон­ца игры. А в моих интересах - не разубеждать его относительно его иллюзии, и тоже играть К.

Так мы видим, что кооперация возможна и при конечном повторении Дилеммы. В реальных экономических играх бывает и то, и другое. Пиндайк и Рубинфельд приводят пример индустрии водомерных приборов, где есть молчаливая кооперация, и пример с авиаперевозками, где ее нет. Объяснение в последнем случае состоит в отсутствии прямых наблюдений стратегий. Поэтому неясно, почему конкурент меняет цены - то ли чтобы подрезать меня, то ли потому, что изменились издержки?

Некоторые общие замечания. Чтобы лучше представлять себе равно­весные выигрыши в супериграх, мы сделаем два простых замечания. Первое - что равновесный (средний) выигрыш не может быть меньше гарантирован­ного уровня, т.е. что

> а».

Действительно, если игрок г использует тупо свою осторожную стратегию, его средний выигрыш > щ при любых стратегиях остальных.

На самом деле, он не меньше Д = тт^ тах^5^). Это видно из следующей леммы:

Лемма. Для любого игрока г и суперстратегий существует супер­стратегия /г, такая что С^(/^,/_г) > Д.

В самом деле, пусть играется £-й раунд. И пусть Л'/_| - предыстория; для определения $ъ мы должны сказать, чему равно Для этого мы по-

ложим б^ = при ] ф г. тем самым определены действия остальных

в момент Так вот, пусть .%•; - это наилучший ответ игрока / на 5^. Так

как >      то выигрыш игрока г в раунде I будет не меньше а

поэтому и средний выигрыш по всем временам будет >

С другой стороны, довольно ясно, что (средний) выигрыш (при любых стратегиях, не обязательно равновесных) лежит в выпуклой оболочке вы­игрышей в исходной игре С

Народная теорема. Она утверждает, что любой набор выигрышей (т.е. вектор ждг ^ К^), который лежит в зоне выигрышей игры 6г (т.е. в выпуклой оболочке векторов им {вы), здг £ Бм) и который индивидуально рационален (будем понимать это как х\ > Д) может быть реализован некоторым равно­весием в суперигре.

Результаты такого сорта называются народной теоремой.

Объясним основную идею доказательства народной теоремы. Сначала мы покажем, как реализовать выигрыш вида </.у(-%\у) > Ду- Нужно предъявить равновесные стратегии /і в суперигре. Идея построения таких суперстратегий такова: игроку г нужно применять в^, пока все придерживаются вдг; если же некоторый (один) игрок 2 отклонился, то после этого (до конца) наказывать его. Уточним последнее.

Обозначим через 5!_Дг) такой набор стратегий игроков, отличных от г, ко­торый реализует Ащтіпй_. тахЛ.( щІбі, б-і). Это значит, что для любой стра­тегии в[ Є Бі выполняется в!.^(г)) < Д. Так вот суперстратегия ^ опре­деляется так. Пусть дана предыстория Л'/_|. Если все ходы до момента Ї — 1 включительно были равны вдг, то /;(Л'/_|) = .%•;. Если же не все равны вдг, то нужно взять первый момент г < і. когда было отклонение, и взять некоторо­го игрока 2-, который отклонился (все равно какого, но для определенности с наименьшим номером), и положить для і ф і /і(Хї-і) = -з|(І)- Стратегии $у(Хі-\) определяется произвольно.

Мы утверждаем, что получается суперравновесие. В самом деле, если все придерживаются суперстратегий то выигрыш игрока г равен Пред­положим, что он отклоняется от /і7 а все остальные придерживаются $у Тогда либо произойдет никаких изменений, либо в некотором раунде ї б\ впервые будет отлично от ві (а остальные в*- = в^-). И тогда во всех остальных раун­дах с номерами > Ї участники і (отличные от г) будут делать ходы зіДі). Последовательность выигрышей игрока г имеет вид

— 1 раз], ? в момент    и       5!_Дг)) < А в моменты > Ї.

Поэтому и средний выигрыш < Д.

Поясним теперь, как получать другие вектора выигрышей. Любой дру­гой вектор представляет выпуклую смесь выигрышей вида у/ у («у), т.е. ждг = ^2к^и^{3м,к)- Если А^ - рациональные числа с периодом Р, то нужно вы­брать периодическую (с периодом Р) траекторию в которой « у./,, встреча­ется нужное число раз. После этого суперстратегия /дг строится аналогично: если предыстория совпадает с траекторией в', то = в*. Если в первый

раз кто отклонился, то его наказывать без конца.

В общем случае нужно приближать А^ рациональными числами и брать все большие периоды. □

Комментарии к народной теореме.

1. За счет перехода к супериграм удается ликвидировать главный минус равновесий Нэша - их общую неэффективность.

2. Зато в суперигре получается "очень много" суперравновесий, и не очень понятно, которое из них реально осуществится. Тут снова возникают вопросы с фокальными точ­ками.

3. Народные теоремы установлены не только для критерия среднего выигрыша. Они известны для критерия перегона (overtaking) (Рубинштейн, 1979), для дисконтированного критерия (Васин, 1977; Фуденберг и Маскин, 1986). Конечно, в последнем случае дисконт S должен быть близок к 1.

4. "Совершенная" народная, теорема, или кто охраняет охранников. Идея, лежащая в основе устойчивость суперравновесий, заключается в наказании уклонистов. Но вполне может оказаться (не в Дилемме), что наказывать накладно и не выгодно. Иначе говоря, рассматриваемое суперравновесие может быть несовершенным (возможная причина раз­вала цивилизаций?!). Например, свирепая стратегия несовершенна в семейном споре. А можно ли найти совершенное? Оказывается, что ДА. Аккуратное доказательство требует возни, но идея ясна - нужно наказывать тех, кто уклоняется от наказания, и т.д.

Поясняющий пример - перекрывающиеся поколения, мать-дочь. "Хорошее" поведение - кормить мать, если она кормила свою. И не кормить, если та не кормила. Это равнове­сие, но не совершенное. А совершенное будет, если наказывать нон-конформистов. Игрок считается конформистом, если она кормит свою мать тогда и только тогда, когда та тоже конформистка.

Похожая ситуация рассматривалась в конце лекции 13 про зарплату.

До сих пор предполагалось, что игра идет молча, что игроки не имеют воз­можностей сообщаться друг с другом, если это явно не предусмотрено в стра­тегиях. Что произойдет, если они могут поговорить перед игрой, обменяться легким трепом (cheap talk)? Есть два способа сделать это. Первый - ввести возможности переговоров явно в стратегии, перейти к новой игре, которую нужно анализировать старыми способами. Другой - изменить понятие ре­шения, учитывая возможности переговоров в каком-то обобщенном смысле. Именно этот второй способ мы здесь в основном и обсудим.

Доигровые переговоры. Будем предполагать, что игроки перед игрой могут встретиться на полчасика и обсудить предстоящую игру. В частно­сти, они могут договариваться о стратегиях, которые они будут применять, но это договоренности не являются обязывающими соглашениями. Тогда, чтобы договоренности были правдоподобными (credible), они должны быть равновесиями Нэша. Так что, казалось бы, легкий треп может помочь реали­зации некоторого равновесия, но не может дать новых решений.

Однако это не совсем так. Во время легкого трепа можно договориться о контингентных действиях, т.е. действиях, зависящих от значений некото­рых совместно наблюдаемых случайных величин (событий). Поясним это на примере игры "Перекресток"

 

м

в

м

2,2

0,3

в

3,0

-1,-1

У каждого игрока есть две стратегии, миролюбивая и воинственная. Здесь есть два чистых равновесия (М,в) и (В,м), и одно смешанное равновесие, когда с равными шансами используются мир и война (выигрыши тогда равны

(1.1) ). Игроки могут договориться о следующем: мы бросаем монету, и если выпадет орел, то играть (М,в), а если решка - то (В,м). Средний выигрыш для каждого будет по 1.5. Это хуже кооперативного (и недостижимого) исхода

(2.2) , но лучше исхода смешанного равновесия (1,1). Множество исходов, которые могут быть получены на этом пути, изображены на картинке.

 

Здесь ( | н ( ■> - исходы чистых равновесий, а - исход смешанного равновесия, р - смесь чисто равновесных исходов, с - исход коррелированного равновесия.