<< Предыдущая

стр. 150
(из 163 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

вую из теорем можно рассматривать как подтверждение того, что концепция Нэша доста-
точно разумна. Отметим, что данный результат относится только к строгому доминирова-
нию. Можно привести пример равновесия Нэша с одной или несколькими слабо домини-
руемыми стратегиями (см. напр. Таблицу 16 на стр. 658).

Равновесие Нэша в смешанных стратегиях
Нетрудно построить примеры игр, в которых равновесие Нэша отсутствует. Следующая
игра представляет пример такой ситуации.


Игра 6. «h…“Ca*o, »
В этой игре первый игрок (проверяемый) поставлен перед выбором — платить или не
платить подоходный налог. Второй — налоговой инспектор, решает, проверять или не
проверять именно этого налогоплательщика. Если инспектор «ловит» недобросовестного
налогоплательщика, то взимает в него штраф и получает поощрение по службе, более чем
компенсирующее его издержки; в случае же проверки «исправного» налогоплательщика,
инспектор, не получая поощрения, тем не менее несет издержки, связанные с проверкой.
Матрица выигрышей представлена в таблице 12.
Oaaeeoa 12
Инспектор
не
проверять
проверять
1 0
нарушать –1 1
Проверяемый
не –1 0
нарушать 0 0
(


Если инспектор уверен, что налогоплательщик выберет не платить налог, то инспектору
выгодно его проверить. С другой стороны, если налогоплательщик уверен, что его прове-
рят, то ему лучше заплатить налог. Аналогичным образом, если инспектор уверен, что
налогоплательщик заплатит налог, то инспектору не выгодно его проверять, а если нало-
гоплательщик уверен, что инспектор не станет его проверять, то он предпочтет не платить
налог. Оптимальные отклики показаны в таблице подчеркиванием соответствующих вы-
игрышей. Очевидно, что ни одна из клеток не может быть равновесием Нэша, поскольку
ни в одной из клеток не подчеркнуты одновременно оба выигрыша.
В подобной игре каждый игрок заинтересован в том, чтобы его партнер не смог угадать,
какую именно стратегию он выбрал. Этого можно достигнуть, внеся в выбор стратегии
элемент неопределенности.
Те стратегии, которые мы рассматривали раньше, принято называть чистыми стратегиями.
Чистые стратегии в статических играх по сути дела совпадают с действиями игроков. Но в
некоторых играх естественно ввести в рассмотрение также смешанные стратегии. Под
смешанной стратегией понимают распределение вероятностей на чистых стратегиях. В ча-
стном случае, когда множество чистых стратегий каждого игрока конечно,
1 ni
Xi = {xi , ..., xi },
(соответствующая игра называется конечной,), смешанная стратегия представляется век-
тором вероятностей соответствующих чистых стратегий:
641
642
µi = (µi , ..., µi ).
1 ni


Обозначим множество смешанных стратегий i-го игрока через ?i:
?i = {µi | µi > 0, k = 1, ... ni; µi + ... + µi = 1}.
k 1 ni


Как мы уже отмечали, стандартное предположение теории игр (как и экономической тео-
рии) состоит в том, что если выигрыш — случайная величина, то игроки предпочитают
действия, которые приносят им наибольший ожидаемый выигрыш. Ожидаемый выигрыш
i-го игрока, соответствующий набору смешанных стратегий всех игроков, (µ1, ..., µm), вы-
числяется по формуле
n1 nm
U(µi, µ–i) = ¤??? ¤ µ1 ???µm ui(x1 , ..., xm ).
ki km ki km

k1=1 km=1

Ожидание рассчитывается в предположении, что игроки выбирают стратегии независимо
(в статистическом смысле).
Смешанные стратегии можно представить как результат рандомизации игроком своих дей-
ствий, то есть как результат их случайного выбора. Например, чтобы выбирать каждую из
двух возможных стратегий с одинаковой вероятностью, игрок может подбрасывать моне-
ту. Эта интерпретация подразумевает, что выбор стратегии зависит от некоторого сигнала,
который сам игрок может наблюдать, а его партнеры — нет.243 Например, игрок может
выбирать стратегию в зависимости от своего настроения, если ему известно распределе-
ние вероятностей его настроений, или от того, с какой ноги он в этот день встал.244


Определение 9.
Набор смешанных стратегий µ* = (µ1, ..., µm) является равновесием Нэша в смешанных
* *

стратегиях, если:

1) стратегия µi каждого игрока является наилучшим для него откликом на ожидаемые им
*

стратегии других игроков µ–i:
e



U(µi , µ–i) = max U(µi, µ–i) ? i = 1, ..., n;
* e e

µi ? ?i

2) ожидания совпадают с фактически выбираемыми стратегиями:
µ–i = µ–i ? i = 1, ..., n.
e *




Заметим, что равновесие Нэша в смешанных стратегиях является обычным равновесием
Нэша в так называемом смешанном расширении игры, т.е. игре, чистые стратегии кото-
рой являются смешанными стратегиями исходной игры.


Найдем равновесие Нэша в смешанных стратегиях в Игре 6.
Обозначим через µ вероятность того, что налогоплательщик не платит подоходный налог,
а через ? — вероятность того, что налоговой инспектор проверяет налогоплательщика.
В этих обозначениях ожидаемый выигрыш налогоплательщика равен

243
Если сигналы , наблюдаемые игроками, статистически зависимы, то это может помочь игрокам скоорди-
нировать свои действия. Это приводит к концепции коррелированного равновесия.
244
Впоследствии мы рассмотрим, как можно достигнуть эффекта рандомизации в рамках байесовского
равновесия.

642
643
U1(µ, ?) = µ [??(–1) + (1 – ?)?1] + (1 – µ) [??0 + (1 – ?)?0] =
= µ (1 – 2 ?),
а ожидаемый выигрыш инспектора равен
U2(µ, ?) = ? [µ?1 + (1 – µ)?(–1)] + (1 – µ) [µ?0 + (1 – µ)?0] =
= ? (2 µ – 1).
Если вероятность проверки мала (? < 1/2), то налогоплательщику выгодно не платить на-
лог, т.е. выбрать µ = 1. Если вероятность проверки велика, то налогоплательщику выгодно
заплатить налог, т.е. выбрать µ = 0. Если же ? = 1/2, то налогоплательщику все равно, пла-
тить налог или нет, он может выбрать любую вероятность µ из интервала [0, 1]. Таким об-
разом, отображение отклика налогоплательщика имеет вид:
если ? < 1/2
? 1,
?
µ(?) = ? [0, 1], если ? = 1/2
? 0, если ? > 1/2 .
?
Рассуждая аналогичным образом, найдем отклик налогового инспектора:
если µ < 1/2
? 0,
? ?
?(µ) = ? [0, 1], если µ = 1/2 ?(µ)
1
? 1, если µ > 1/2 .
?

µ(?)
1
Графики отображений отклика обоих игроков представлены 2
на Рис. 153. По осям на этой диаграмме откладываются ве-
роятности (? и µ соответственно). Они имеют единственную µ
общую точку (1/2, 1/2). Эта точка соответствует равнове- 1 1
сию Нэша в смешанных стратегиях. В этом равновесии, как 2
это всегда бывает в равновесиях с невырожденными сме-
шенными стратегиями (то есть в таких равновесиях, в кото- ?enoiie 153. Ioia?a?aiey
рых ни одна из стратегий не выбирается с вероятностью 1), ioeeeea a ea?a
«Einiaeoey»
каждый игрок рандомизирует стратегии, которые обеспечи-
вают ему одинаковую ожидаемую полезность. Вероятности
использования соответствующих чистых стратегий, выбранные игроком, определяются не
структурой выигрышей данного игрока, а структурой выигрышей его партнера, что может
вызвать известные трудности с интерпретацией данного решения.


В отличие от равновесия в чистых стратегиях, равновесие в смешанных стратегиях в ко-
нечных играх существует всегда,245 что является следствием следующего общего утвер-
ждения.


Теорема 3.
Предположим, что в игре G = ?I, {Xi}i?I , {ui}i?I ? у любого игрока множество стратегий
Xi непусто, компактно и выпукло, а функция выигрыша ui(?) вогнута по xi и непрерывна.
Тогда в игре G существует равновесие Нэша (в чистых стратегиях).



245
Этот результат был доказан Нэшем в статье 1950-го года, цитируемой в сноске 241.

643
644
Существование равновесия Нэша в смешанных стратегиях в играх с конечным числом
чистых стратегий является следствием того, что равновесие в смешанных стратегиях яв-
ляется равновесием в чистых стратегиях в смешанном расширении игры.


Следствие (Теорема Нэша).
Равновесие Нэша в смешанных стратегиях существует в любой конечной игре.


Заметим, что существование в игре равновесия в чистых стратегиях не исключает сущест-
вования равновесия в невырожденных смешанных стратегиях.
Рассмотрим в Игре 1 «Выбор компьютера» случай, когда выгоды от совместимости значи-
тельны, т.е. a < c и b < c. В этом варианте игры два равновесия в чистых стратегиях: (IBM,
IBM) и (Mac, Mac). Обозначим µ и ? вероятности выбора компьютера IBM PC первым и
вторым игроком соответственно. Ожидаемый выигрыш 1-го игрока равен
U1(µ, ?) = µ [??(a + c) + (1 – ?)?a] + (1 – µ) [??0 + (1 – ?)?c] =
= µ [??2c – (c – a)] + (1 – ?) c,
а его отклик имеет вид
если ? < (c – a)/2c
? 0,
?
µ(?) = ? [0, 1], если ? = (c – a)/2c
? 1, если ? > (c – a)/2c .
?
Ожидаемый выигрыш 2-го игрока равен
U2(µ, ?) = ? [µ?c + (1 – µ)?0] + (1 – ?) [µ?b + (1 – µ)?(b + c)] =
= ? [µ?2c – (b + c)] + b + (1 – µ) c,
а его отклик имеет вид
если µ < (b + c)/2c
? 0,
?
?(µ) = ? [0, 1], если µ = (b + c)/2c
? 1, если µ > (b + c)/2c .
?
Графики отображений отклика и точки, соответствующие трем равновесиям изображены
на Рис.154. Как видно, в рассматриваемой игре кроме двух равновесий в чистых стратеги-
ях имеется одно равновесие в невырожденных смешанных стратегиях. Соответствующие
вероятности равны
b+c c–a
µ = 2c и ? = 2c .




644
645
?
?(µ)
1


µ(?)
c–a
2c

µ
b+c 1
2c

?enoiie 154. Neo?ae, eiaaa a ea?a «Auai? eiiiu?oa?a» nouanoaoao o?e
?aaiiaaney, iaii ec eioi?uo – ?aaiiaanea a iaau?i?aaiiuo niaoaiiuo
no?aoaaeyo


Приложение A


Теорема.
Предположим, что в игре G = ?I, {Xi}i?I , {ui0}i?I ? у любого игрока множество стратегий
Xi непусто, компактно и выпукло, а функция выигрыша ui(?) вогнута по xi и непрерывна.
Тогда существует равновесие Нэша.


Доказательство.
Докажем, что отображение отклика, Ri(?), каждого игрока полунепрерывно сверху и его
значение при каждом x–i ? X–i непусто и выпукло. Непустота следует из теоремы Вейер-
штрасса (непрерывная функция на компакте достигает максимума).
Докажем выпуклость. Пусть z?, z?? ? Ri(x–i). Очевидно, что u(z?, x –i) = u(z??, x –i). Из во-
гнутости по xi функции ui(?) следует, что при ? ? [0, 1]
u(?z? + (1–?)z??, x –i) > ?u(z?, x –i) + (1–?)u(z??, x –i) =
= u(z?, x –i) = u(z??, x –i).

<< Предыдущая

стр. 150
(из 163 стр.)

ОГЛАВЛЕНИЕ

Следующая >>