d9e5a92d

БЕСКОНЕЧНЫЕ ИГРЫ

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 несет потери L(xlt - ), если использует стратегию хх € Yv Это наказание в действительности влияет только на его собственный вполне смешанный і?Е-выигрыш, оставляя без изменения выигрыш игрока 2.
3) Рассмотрим игру 2x2, в которой обе функции выигрыша взаимно однозначны (как в рассмотренном выше примере 3). Охарактеризуйте те игры, для которых возникает ситуация из пункта 2. Дайте числовой пример.
3. БЕСКОНЕЧНЫЕ ИГРЫ
Если множества чистых стратегий Х( бесконечны, то даже для игры двух лиц с нулевой суммой нельзя утверждать существование цены в смешанных стратегиях. Тем более не гарантируется существование смешанного ХЕ-исхода.
Пример 4. Китайский покер
Каждый из двух игроков выбирает (неотрицательное) целое число. Игрок, который назвал большее число, выигрывает доллар:

Хх Х2 N, их (хХ1 х2)
Вероятностное распределение на Хг = N принимает вид М/==(Мп))л. где 2 рг(п) = 1, рг(п)0 для всех п$Н.
nsN
Обозначая через Mt множество таких распределений, мы получаем игру (Mit М5, иг), где
(М-і Ма) ^ 2 Мі C^i)' Мг (хі) 2 Иі (^-l) * M's (-^a) -
Xi, X,€ N *1, ATjeN
X, Xt X, Xg
Исходная игра является игрой с нулевой суммой без цены sup inf иг = 1 +1 = inf sup uv
Xt x, xt Xi
На самом деле использование смешанных стратегий совсем не увеличивает гарантированный уровень игроков, поэтому и смешанная игра (Ми Мг, Mj) не имеет цены:
sup inf щ = 1 1 = inf sup (26)
Ді Д* M* Ді
Для доказательства этого неравенства фиксируем вероятностное распределение [аг Тогда для любого е 0 найдется целое число Пе, такое, что
+ 00
2 л (п) 8-
п=пк
Рассмотрим далее (чистую) стратегию Хі пв игрока 2й,(Мі, 6,г) = 2 Mi (ft) + 2 Mi (п) (18) + 8==1 + 2e
Пе H/lg
Поскольку e может быть сколь угодно малым положительным числом, получаем
inf (Ml, Мг) = inf 1 (Ml, 1,
Иг Xt
а значит, справедливо левое равенство в (26). Так как наша игра симметрична (см. упр.

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 (*г,


Отметим, что если расстояние между магазинами хотя бы 2/3 (длину улицы мы считаем равной единице), то влияние магазина дешевых товаров прекращается.
Исходная игра не имеет равновесия по Нэшу. Это показано на рис.

1, где приведены множества наилучших ответов для обоих игроков.


Поскольку множество Xf компактно, а н,непрерывные функции, теорема 5 гарантирует существование по крайней мере одного исхода в смешанных стратегиях равновесия по Нэшу.
Равновесием по Нэшу является следующая пара смешанных стратегий (juf, pf)i
= -g- 60 + -g- Sj. + g S_2_ + gf Si,
3 3
Ни одна из двух смешанных стратегий не является вполне смешанной (определение 2 непосредственно обобщается на случай бесконечных игр на основе понятия носителя меры Радона: см., например, Рудин [1966], Колмогоров, Фомин [1972]). Тем не менее пара (pf, pf) обладает типичным свойством вполне смешанного равновесия, а именно:
WjCpj, pf) = Mx(pf, pf) для всех px6^i. ^7) w2(pf, p2) = M2(pf, pf) для всех р2€М2.
Для проверки первого свойства фиксируем чистую стратегию хх игрока 1 и вычислим
йі(бх„ pf) = 4 (!¦*i) + Y (1 (1*i)) = -j Для всех хг?Хх.
Как и в конечном случае, если функция их{-, pf) постоянна на множестве чистых стратегий, то она постоянна также и на множестве смешанных стратегий (поскольку последние являются пределами выпуклых комбинаций чистых стратегий). Фиксируем далее чистую стратегию х2 игрока 2 и вычислим
. 1 (2+ Т\Т~х*3*2х,3 *2 + 6 (^2 з)+ 6 (з Л'2) + 3 ^ х*)’M2(pf. 8*,) =
1 2 если ух2у.
з'з + б (*2 з ) + 6 (*2 з) + з ^ *)
следовательно,
и*(и*. 8*е) = ц2(pf, р2) = ^ для всех х2?Хг, р2€Ма.
Отметим, что pfоптимальная осторожная стратегия игрока 1 в игре с нулевой суммой (Ми М2, щ). В самом деле, ut (pt, р2) = ¦и (р2, Pj) для всех рп р2, а значит, верхнее уравнение в (27) приводит к тому, что пара (pf, pf) является седловой относительно функции и? Следовательно, цена игры в смешанных стратегиях по функции иг равна 1/2 н совпадает с (??-выиг-рышем игрока 1.
Аналогичными рассуждениями можно показать, что (pf, и*) является (единственной) седловой парой в игре (М,, М2, й2), таким образом, смешанный гарантированный выигрыш игрока 2 равен 7/18 и совпадает с его (?і:-выигрышем.
Заметим, наконец, что наш NE-исход доминируем по Парето.
Вычисление смешанных NE-исходов является чрезвычайно трудной задачей даже в случае, когда исходные множества стратегий являются выпуклыми компактными подмножествами евклидовых пространств. Поэтому мы не будем заниматься дальнейшим изучением этого вопроса, а отошлем читателя к работам Партхасаратхи, Рагхаван [1971], Тийс [1981] и указанной в них литературе.
Два наших следующих примераэто игры, в которых множества стратегий игроков одномерны, а функции выигрыша разрывны. В первой из этих игр выигрыши равномерно ограничены, тем не менее не существует равновесия по Нэшу в смешанных стратегиях.

Этот факт указывает на то, что в условиях теоремы Гликсберга нельзя отбросить требование непрерывности функции выигрыша.
Пример 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) Докажите, что если


то смешанное расширение G имеет цену, но ни один игрок не имеет оптимальной стратегии.
Кооперативное поведение игроков
В первой части книги мы изучали сообщество, в котором отсутствовал явный обмен информацией между участниками. Это могло быть следствием физических ограничений, юридических барьеров или же результатом взаимного недоверия. Единственным косвенным способом обмена стратегической информацией (см. процедуру нащупывания по Курно, гл. Ill, разд.

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:-исходом в чистых стратегиях.



Содержание раздела