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

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

ОГЛАВЛЕНИЕ

Следующая >>


Рис. 16.4. Отображения отклика в игре «Инспекция»

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

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

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

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

Заметим, что существование в игре равновесия в чистых стратегиях не исключает суще-
ствования равновесия в невырожденных смешанных стратегиях.
Рассмотрим в Игре 16.2.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

19
Этот результат был доказан Нэшем в статье 1950-го года, цитируемой в сноске 15.
16.2. Статические игры с полной информацией 640

а его отклик имеет вид ?
если ? < (c ? a)/2c
?0,
?
?
?
µ(?) = [0, 1] , если ? = (c ? a)/2c
?
если ? > (c ? a)/2c.
?
?1,
?

Ожидаемый выигрыш 2-го игрока равен

U2 (µ, ?) = ?[µ · c + (1 ? µ) · 0] + (1 ? ?)[µ · b + (1 ? µ) · (b + c)] =
= ?[µ · 2c ? (b + c)] + b + (1 ? µ)c

а его отклик имеет вид ?
?0, если µ < (b + c)/2c
?
?
?
?(µ) = [0, 1] , если µ = (b + c)/2c
?
?
?1, если µ > (b + c)/2c.
?

Графики отображений отклика и точки, соответствующие трем равновесиям изображены
на Рис. 16.5. Как видно, в рассматриваемой игре кроме двух равновесий в чистых стратегиях
имеется одно равновесие в невырожденных смешанных стратегиях. Соответствующие вероят-
ности равны
c?a
b+c
µ= и?=
2c 2c


?
?(µ)
1


µ(?)
c?a
2c



µ
b+c 1
2c


Рис. 16.5. Случай, когда в игре «Выбор компьютера» существует три равновесия, одно из
которых — равновесие в невырожденных смешанных стратегиях


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

Доказательство: Докажем, что отображение отклика, Ri (·), каждого игрока полунепрерывно
сверху и его значение при каждом x?i ? X?i непусто и выпукло. Непустота следует из теоремы
Вейерштрасса (непрерывная функция на компакте достигает максимума).
16.2. Статические игры с полной информацией 641

Докажем выпуклость. Пусть 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 )

Поскольку функция ui (·) достигает максимума в точках z и z , то строгое неравенство здесь
невозможно. Таким образом,
?z + (1 ? ?)z ? Ri (x?i )
Докажем теперь полунепрерывность сверху отображения Ri (·). Рассмотрим последователь-
ность xn сходящуюся к xi и последовательность xn сходящуюся к x?i , причем xn ? Ri (xn ).
?
? ?i ?i
i i
Заметим, что в силу компактности множеств Xj xi ? Xi и x?i ? X?i . Нам нужно доказать,
?
?
что xi ? Ri (? ?i ). По определению отображения отклика
? x

u(xn , xn ) u(xi , xn ) ?xi ? Xi , ?n
?i ?i
i

Из непрерывности функции ui (·) следует, что

u(xi , x?i ) ?xi ? Xi
x? ?
u(?i , x?i )

Тем самым, по введенному выше определению отображения отклика, xi ? Ri (? ?i ).
? x
Опираясь на доказанные только что свойства отображения Ri (·) и на теорему Какутани,
докажем существование равновесия по Нэшу, то есть такого набора стратегий x? ? X , для
которого выполнено
x? ? Ri (x? ) ?i = 1, . . . , n
?i
i

Определим отображение R(·) из X в X следующим образом:

R(x) = R1 (x?1 ) ? · · · ? Rn (x?n )

Отметим, что это отображение удовлетворяет тем же свойствам, что и каждое из отображений
Ri (·), так как является их декартовым произведением.
Отображение R(·) и множество X удовлетворяют свойствам, которые необходимы для
выполнения теоремы Какутани. Таким образом, существует неподвижная точка отображения
R(·):
x? ? R(x? )
Очевидно, что точка x? есть равновесие по Нэшу.

Приложение B
В этом приложении мы формально докажем утверждения о связи между равновесием
Нэша и процедурой последовательного отбрасывания строго доминируемых стратегий.
Сначала определим формально процедуру последовательного отбрасывания строго доми-
нируемых стратегий. Пусть исходная игра задана как

G = I, {Xi }I , {ui }I .

Определим последовательность игр {G[t] }t=0,1,2,... , каждая из которых получается из по-
следующей игры отбрасыванием строго доминируемых стратегий. Игры отличаются друг от
друга множествами допустимых стратегий:
[t]
G[t] = I, {Xi }I , {ui }I
16.2. Статические игры с полной информацией 642

Процедура начинается с G[0] = G.
Множество допустимых стратегий i-го игрока на шаге t + 1 рассматриваемой процедуры
берется равным множеству не доминируемых строго стратегий i-го игрока в игре t-го шага.
Множества не доминируемых строго стратегий будем обозначать через N Di (см. определение
строго доминируемых стратегий (Определение 89, с. 631)). Формально
xi ? Xi ?yi ? Xi : ui (yi , x?i ) > ui (xi , x?i ) ?x?i ? X?i
N Di =
Таким образом, можно записать шаг рассматриваемой процедуры следующим образом:
[t+1] [t]
Xi = N Di
[t]
где N Di — множество не доминируемых строго стратегий в игре G[t] .
Приведем теперь доказательства Теорем 151 и 152 (с. 636). Теорема 151 утверждает следу-
ющее:
: Если x? = (x? , . . . , x? ) — равновесие Нэша в некоторой игре, то ни одна из стратегий не
m
1
может быть отброшена в результате применения процедуры последовательного отбрасывания
строго доминируемых стратегий.

Если использовать только что введенные обозначения, то Теорема 151 утверждает, что если
x? — равновесие Нэша в исходной игре G, то на любом шаге t выполнено
[t]
x? ? Xi , ?i ? I, ?t = 1, 2, . . .
i

или
x? ? X [t] , ?t = 1, 2, . . .
Доказательство (Доказательство Теоремы 151): Пусть есть такой шаг ? , что на нем должна
быть отброшена стратегия x? некоторого игрока i ? I . Предполагается, что на предыдущих
i
шагах ни одна из стратегий не была отброшена:
x? ? X [t] , ?t = 1, . . . , ?.
[? ]
По определению строгого доминирования существует другая стратегия игрока i, xi ? Xi ,
которая дает этому игроку в игре G[? ] более высокий выигрыш при любых выборах других
игроков:
[? ]
ui (xi , x?i ) > ui (x? , x?i ) ?x?i ? X?i
i
В том числе, это соотношение должно быть выполнено для x? , поскольку мы предположили,
?i
[? ]
что стратегии x? не были отброшены на предыдущих шагах процедуры (x? ? X?i ). Значит,
?i ?i

ui (xi , x? ) > ui (x? , x? )
?i ?i
i

Однако это неравенство противоречит тому, что x? — равновесие Нэша.

Докажем теперь Теорему 152. Напомним ее формулировку:
: Если в результате последовательного отбрасывания строго доминируемых стратегий у каж-
дого игрока остается единственная стратегия, x? , то x? = (x? , . . . , x? ) — равновесие Нэша в
m
1
i
этой игре.

Данная теорема относится к случаю, когда в процессе отбрасывания строго доминируемых
стратегий начиная с некоторого шага t остается единственный набор стратегий, x? , т. е.
?
[t]
Xi = {x? }, ?i ? I, ?t = 1, . . . , t.
?
i

Теорема утверждает, что x? является единственным равновесием Нэша исходной игры.
16.2. Статические игры с полной информацией 643

Доказательство (Доказательство Теоремы 152): Поскольку, согласно доказанной только что тео-
реме, ни одно из равновесий Нэша не может быть отброшено, нам остается только доказать,
что указанный набор стратегий x? является равновесием Нэша. Предположим, что это не так.
Это означает, что существует стратегия xi некоторого игрока i, такая что
?

ui (x? , x? ) < ui (?i , x? )
x ?i
?i
i

По предположению, стратегия xi была отброшена на некотором шаге ? , поскольку она
?
? . Таким образом, существует некоторая строго доминирующая ее стратегия
не совпадает с xi
[? ]
xi ? Xi , так что
[? ]
ui (xi , x?i ) > ui (?i , x?i ) ?x?i ? X?i
x
В том числе это неравенство выполнено при x?i = x? :
?i

ui (xi , x? ) > ui (?i , x? )
x ?i
?i

Стратегия xi не может совпадать со стратегией x? , поскольку в этом случае вышеприве-
i

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

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

ОГЛАВЛЕНИЕ

Следующая >>