v1?M1v1 = vm(U1).
Если ?х принадлежит множеству Л4Х, то вполне смешанный WE-выигрыш игрока 1 совпадает с его гарантированным выигрышем, ?х осторожная смешанная стратегия игрока 1, а рх, вообще говоря, нет.
2) Предположим, что ?х не есть смешанная стратегия (что в силу утверждения 1 эквивалентно ?х ?т (t/x)). Тогда множество Ух отрицательных компонент ?х не пусто.
Скажем, что Хх х Xz матрица Lx есть матрица Ух-потерь, если
?хх € Уі. ^^2) і/г € Xі (Л-іі f/г) ^ ^?хх€^і\Уі, ?^а€^2 М*і. *2) = О-
Покажите, что для любой достаточно малой ненулевой матрицы Ух-потерь L1 игра (Хх, Хг, Ul L1, U2) имеет единственное вполне смешанное равновесие. Соответствующий вектор выигрышей (іх, ?2) удовлетворяет условиям
1), то правое равенство также справедливо.
Сложность приведенного выше примера связана с некомпактностью множеств чистых стратегий, а также множеств смешанных стратегий. Когда те и другие множества компактны, непрерывность (исходной) функции выигрыша гарантирует существование равновесия по Нэшу в смешанных стратегиях.
Определение 4. Пусть G (X., up, і ? N) исходная игра [ N лиц в нормальной форме, для которой
для всех і € N.
Х{компактное подмножество некоторого' евклидова пространства Rp щнепрерывная функция на Хд,
Смешанная стратегия ц,- игрока і является вероятностной мерой Радона на X,-; это положительный непрерывный линейный функционал, заданный на множестве непрерывных действительных функций, определенных на X,-, наделенном топологией равномерной сходимости. Значение этого функционала на функции, тождественно равной единице, есть единица. Обозначим через М{ множество всех смешанных стратегий игрока і.
Смешанное расширение игры Gэто игра Gm (М,, up i g N)i
ut(x) = 5 u{(x)dy.(x),
где da (x) = 60 dpi(Xi) произведение вероятностных w им мер juf, i?N.
Теорема 5 (Гликсберг [1952]). В условиях определения 3 смешанное расширение Gm игры G имеет по крайней мере одно равновесие по Нэшу.
Доказательство. В силу стандартного результата из функционального анализа (см. например, Данфорд, Шварц [1957], Колмогоров, Фомин [1972]) имеем:
Множество Mt -слабо компактно в пространстве, сопряженном к пространству непрерывных функций на Х{, наделенному топологией равномерной сходимости. Функция и{ линейна относительно переменной р,- и непрерывна на Мд, при условии, что последнее множество наделено произведением -слабых топологий.
Таким образом, теорема Гликсберга следует из теоремы Нэша (теорема 2, гл. III).
Пример 5. Игра размещение магазинов
На одной улице должно быть размещено два магазина спорттоваров. Владельца магазина дешевых товаров назовем игроком 1, а дорогихигроком 2. Если магазины расположены близко друг от друга, то покупатели зачастую предпочитают приобрести дешевый товар. Спрос неэластичен.
Игрок 1 стремится разместить свой магазин как можно ближе к магазину игрока 2, а тот старается по возможности увеличить расстояние между магазинами.
Бояее точно, мы предполагаем, что функции выигрыша имеют следующий вид:Хж = Х, = [0, 1],
u1(xlf хг) 1 X2\t
\xtха, если IX}X,
и2 (*г,
1, где приведены множества наилучших ответов для обоих игроков.
Этот факт указывает на то, что в условиях теоремы Гликсберга нельзя отбросить требование непрерывности функции выигрыша.
Пример 6. Игра двух лиц в единичном квадрате, не имеющая цены в смешанных стратегиях (Сайон, Вулф [1957])
Положим Хх = Х2 = [0, 1] и
1, если х1х2х1 + ±-,
О, если х% = х2 или х2 = х, -- \
+ 1, если х2 хг или xt + ~ х2.
Утверждается, что смешанное расширение этой игры двух лиц с нулевой суммой не имеет цены. Более точно, выполнено
sup inf и, = -1- inf sup и..
Hi Hi Hi Hi
Докажем правое равенство от противного, предположив, что существует стратегия р,2, для которой*1
Подставляя последовательно в (28) ^=1, ^ = 0, получаем!
где а = [і2(о, у) , ? = р2(^у, і). Далее применяем (28) при *і Т8 и предполагаем, что е стремится к нулю:
(31)
М{0})+М{1})!**({т})+а т*
Суммируя (30) и (31), получаем
С другой стороны, [а2это вероятностное распределение, следовательно,
Суммируя (33) и (30), имеем
Суммируя (34) и (32), получаем противоречие с (29), Следова
тельно, мы доказали, что
inf sup tii j- *
Взяв смешанную стратегию
Р* = у б+ у 61_ + у 6і
4 2
получаем, что она гарантирует игроку 2 проигрыш не больше 3/7.
Упражнение 10 Докажите, что
sup inf! = -i-.
Hi ' Hi d
Указание: осторожная стратегия игрока 1 равна
р?=у бо + у 6j_+y б4.
2
В нашем последнем примере множеством стратегий будет действительная полуось, а функция выигрыша будет разрывна и неограниченна. Тем не менее докажем, что существует вполне смешанный NE-исход.
Пример 7. Игра „аукцион"
Доллар распределяется между п участниками, которые тайно делают ставки. Обозначим эти ставки через xt, ..., хп. Пусть наибольшая ставка принадлежит игроку і0: ш(л;) = {/„}, Где w(x)множество всех игроков, предложивших наивысшую Ставку, а именно
W (X) = {І ? У I х( sup хЛ.
leN
Правило аукциона состоит в том, что игрок і0 выигрывает доллар и должен уплатить вторую из назначенных цен, в то время как каждый из остальных игроков платит то, что он объявил: игрок і, і Ф /0, должен уплатить свою ставку xt.
Если наивысшую ставку предложили одновременно несколько игроков, то для того чтобы определить, кому достанется доллар, эти игроки бросают жребий. Получается следующая игра в нормальной форме:
Эта игра является вариантом игры „война на истощение" (задача 5 гл. Ill), в которой предмет конкуренции имеет одинаковую ценность для всех игроков, а число игроков произвольно.
Анализ исходной игры в нормальной форме (35) аналогичен исследованию игры „война на истощение. Игра (35) имеет п существенно различных /?Е-исходов в чистых стратегиях; все они оптимальны по Парето.
В каждом из таких исходов один игрок делает ставку больше единицы в то время, как остальные не ставят ничего.
Любое равновесие приводит к резкой несимметрии между игроками: для того чтобы сделать равновесие правдоподобным исходом игры, один из игроков должен выступить в качестве лидера, заявив окружающим, что он будет делать ставку больше единицы. Игроки знают о симметричности игры, поэтому вполне возможно, что никто из них не сделает подобного заявления.
В этом случае не может реализоваться исход, в котором какой-либо из игроков является лидером.
Совсем другая картина наблюдается при использовании смешанных стратегий. Здесь уже каждый игрок должен сохранять в тайне чистую стратегию, которая является реализацией смешанной стратегии.
Отсюда вытекает симметричность и вполне смешанность равновесия по Нэшу.
Для того, чтобы доказать это утверждение, мы введем вероятностное распределение ?* на [0, +00). такое, что для всех і€ N
не зависит от х g X,-
Вероятностное распределение ?* выбирается с непрерывной функцией плотности /:
?* (Л) = § f(t)dt для любого измеримого множества Ас[0, -f оо).
А
Обозначим через F функцию распределения:
F(x) = lf(t)dt.
0
Если каждый игрок / из N\{i\ использует смешанную стратегию ?*, то случайная переменная
sup х,
і е N \{і}
имеет функцию распределения Fn_1 с соответствующей плотностью fa~{n\)Fn~1f. Следовательно, мы можем вычислить
X + 00
Щ(6Ж, цТ) = 5(1-0/ (0 dt X I /„ (0 dt = о . *
- (П_ 1) J (1 t)Fn~a (t) f (t) dtx (1 Fn~1(x)).
о
В силу непрерывности / приведенное выше выражение дифференцируемо по х и условие (36) приводит к
О = = (n l)Fn~2(x) f (х) -{-Fn~l (х)-1.
Поэтому G~Fn~l является решением дифференциального уравнения G' (x)-fG(x) = l, и, принимая во внимание, что F(0) = 0, окончательно получаем
1
F(x) = [lе"*]-1 для всех х^О.
Следовательно, в симметричном вполне смешанном NE-исходе каждый игрок использует одну и ту же функцию плотности!
f . 1 е~х
/ (*) „ ! ‘ п-2
Заметим, что для любого сколь угодно большого числа % Вероятность того, что игрок сделает ставку выше X не равна
Кулю (а есть в точности 1(1е_д)п"1) . Отсюда следует, что ваш NE-исход доминируем по Парето. Тем не менее математическое ожидание а наибольшей ставки является конечным:
Заметим, наконец, что, как показывают простые вычисления, /?Е-выигрыш для каждого игрока в точности равен нулю.
Задача 6. Модифицированный китайский покер, имеющий цену
Каждый из двух игроков выбирает натуральное число. Если эти два числа ие равны, то выигрыш равен нулю. Если выбранные числа совпадают хг хг = р, то выигрыш игрока 1 равен ар, где а2 1 ... ^ ар 1 ... неубывающая последовательность
положительных чисел. Таким образом, игрок 2 сталкивается со следующей дилеммой.
Чем больше число, которое он выберет, тем меньше вероятность того, что игрок 1 его угадает, но тем более опасным становится угадывание данного числа. Исходная игра двух лиц с нулевой суммой такова:
G = (Xj, X2, щ),
Ее смешанное расширение может быть определено следующим образом:
S ?(р) = 1 и ?(р) 0 для всех р к р=і I
+ QB
(Их* И.) = 2 арЦі (р) ілг (р)
р=і
(ut может принимать значение -foo).
Возможно и другое определение:
Mt= Mt= /?€Л1 sup[a_-v (/?)] + oo1 , l I pe N f
при этом значения функции щ всегда конечны. При ответе на следующие вопросы можно использовать любой из этих двух вариантов определения смешанного расширения.
1) Докажите, что если
+ OS?± + ржі ар
то смешанное расширение игры G имеет цену, каждый игрок обладает единственной оптимальной стратегией ?, причем стратегия ? вполне смешанная.
2) Докажите, что если
3) являлось совместное наблюдение тактических ходов.
Теперь же мы хотим создать поведенческие модели кооперативного сообщества, в котором имеется явный обмен информацией. Структурная неэффективность некооперативных равновесных исходов (присущая большинству примеров игр с ненулевой суммой, рассмотренных в первой части книги) теперь будет интерпретироваться как побудительный мотив к кооперации.
Попытаемся определить ее основные черты.
После этапа переговоров об условиях кооперации, который может включать взаимное выяснение функций выигрыша, торг и различные психологические маневры, игроки приходят к кооперативному соглашению. Соглашения могут быть обязательными (когда несколько игроков подписывают контракт об использовании определенных стратегий и выполнение этого контракта обеспечивается некоторым контролирующим органом, которому подчиняются все игроки) или необязательными (когда такого органа не существует, и поэтому соглашение во многом напоминает международные договоры, которые действуют до тех пор, пока не выгодно их нарушать).
Наш подход состоит в изучении разумных исходов переговоров. При этом не делается никакой попытки дать описание самого процесса переговоров. При рассмотрении необязательных соглашений возникает целый ряд вопросов стабильности, которые могут быть исследованы наилучшим образом при фиксации некоторых информационных предположений (гл.
V и VI). С другой стороны, изучение обязательных соглашений связано с нормативным определением справедливости, которая рассматривается как некая сила, поддерживающая кооперацию.
Обязательные соглашения не будут здесь рассматриваться (см. введение).
Необязательные соглашения определяют исход и, следовательно, конкретную стратегию для каждого игрока. Поскольку мы хотим, чтобы для каждого игрока была сохранена полная суверенность стратегического выбора, то предполагается, что никакого игрока и никакую коалицию игроков нельзя заставить использовать стратегии, рекомендованные соглашением.
Таким образом, имеется единственный способ предотвратить возможное невыполнение соглашения отдельными участниками или коалицией участников. Нужно сделать так, чтобы отклонение от соглашения было невыгодно отклоняющимся игрокам.
Это и есть свойство стабильности.
Стабильность является не таким уж простым понятием, как это может показаться на первый взгляд. В самом деле, отклонение некоторых игроков, нарушающих рассматриваемое соглашение, может заставить остальных игроков (которые первоначально не собирались нарушать соглашение) изменить свои стратегии. Эти индуцированные изменения трудно предсказуемы независимо от того, предполагаем ли мы, что первоначальное нарушение соглашения убьет дух кооперации и вынудит игроков придерживаться некооперативного поведения.
В самом деле, единственным бесспорным выводом первой части книги является то, что большинство игр в нормальной форме обладает несколькими различными некооперативными равновесными исходами (см. гл. Ill и IV).
В соответствии с этим необязательные соглашения будут состоять из договоренности об исходе, а также из сценария реагирования каждого игрока і на отступление какой-либо коалиции, не содержащей і. Этот сценарий объявляется заранее. В следующей главе в качестве таких сценариев будут рассмотрены угрозы, которые могут предусматривать различную реакцию на каждое возможное отклонение от соглашения.
На протяжении данной главы мы будем рассматривать очень простой сценарий реагирования, а именно полное отсутствие реакции.
Верность соглашению требует придерживаться условленной стратегии независимо от того, какие стратегии используют остальные игроки. Выше уже было сказано о том, что следует использовать соглашения, которые не выгодно нарушать.
Такие соглашения как бы автоматически, обеспечивают свое выполнение, и в этом смысле мы называем их стабильными.
Основным примером стабильного соглашения является соглашение, базирующееся на равновесии по Нэшу. Его стабильность обеспечивается взаимным незнанием окончательных стратегических выборов.
Мы обобщим концепцию равновесия по Нэшу в двух направлениях. Если игроки-нарушители могут образовывать коалицию, то выполнение соглашения подвергается опасности со стороны потенциальных отклонений любой коалиции. Это приводит к концепции сильного равновесия (разд.
1). Если игроки могут использовать случайный механизм, реализующий коррелированные рандомизированные стратегии и посылающий каждому игроку изолированно сигнал о том, какой стратегии ему придерживаться, то возникает новое понятие стабильного соглашения. Назовем его равновесием в совместных смешанных стратегиях (разд.
2).
I. СИЛЬНОЕ РАВНОВЕСИЕ
Пример 1. Пиратские корабли
Два корабля уходят в один и тот же день на остров сокровищ. Каждый из п пиратов должен принять решение, на каком корабле ему плыть: на корабле А или на корабле В. Если t число пиратов, решивших плыть на корабле А, то путешествие на корабле А затянется на а(() дней, а путешествие на корабле В, на котором (п /) пиратов, продлится Ь(пt) дней.
Каждый игрок стремится минимизировать длительность его собственного путешествия. Данная ситуация описывается следующей игрой:
где t = 2 х,,
І 6 N '
ut (лг) =
Хг = {0, 1} itN а(і), если хг = 1, Ь(пt), если х{ = О,
Х[ = 1 означает, что игрок і плывет на корабле А.
Предположим, что функции а и b строго монотонно возрастают на {0, ..., п] и выполнены условия a(0)6(ft), 6(0) а(/г).
Некооперативным равновесием (МЕ-исходом) в данной игре является любой исход х*, для которого число t* = 2 xt
UN
удовлетворяет следующим условиям:
a(t*)^b(n нет желания переключаться со страте
гии 1 на стратегию О и
b(п1): нет желания переключаться со стратегии 0 на стратегию 1.
Предполагая для простоты, что a{t)^b(nt -f 1) для всех і, получаем, что существует единственное целое число t*, удовлетворяющее двум приведенным выше неравенствам, а именно
f*== sup {t\a(t)^b(n t + 1)} = inf {11 b (n 0 ^ a (/ + 1).
Следовательно, исход x* есть равновесие по Нэшу тогда и
только тогда, когда 2 xf = t*.
le N
Если игроки не могут обмениваться информацией перед выбором стратегии (они должны забронировать место на одном из двух кораблей заранее), то они не смогут скоординировать свои выборы так, чтобы достигнуть равновесия по Нэшу в чистых стратегиях. По-видимому, они будут использовать симметричное вполне смешанное равновесие, которое в действительности доминируемо по Парето любым Л/?-исходом в чистых стратегиях.
Упражнение 1
Докажите существование единственного вполне смешанного /??-исхода, в котором каждый пират выбирает стратегию 1 с одной и той же вероятностью р. Докажите, что этот исход, как правило, доминируем по Парето любым Ni:-исходом в чистых стратегиях.