Лекции Хуторецкий

4.3.Равновесия по Нэшу

4.3.1.Определение и основные результаты

Вбольшинстве случаев игрок i не может использовать доминирующую стратегию, ко-

торая принадлежит Ri(x–i) для любого x–i X–i, ввиду отсутствия таких стратегий. Но это и не нужно: если игрок i, имеющий рациональные ожидания, предполагает, что остальные игроки

выберут стратегии,		входящие в набор xe					, то разумным выбором для него является любая
						i
стратегия x*	Ri( xe	). Эта «достаточная рациональность» формализована в следующем опре-
i	i
делении.
Определение.
Набор стратегий и ожиданий игроков (( x* , xe										) | i I) является равновесием по Нэшу, ес-
								i	i
ли xi* Ri( xei	) (стратегия игрока i рациональна) и xei = x*i (ожидания игрока i рациональны)
для всех i I.
В равновесии по Нэшу ( x* , xe					) = ( x* , x*			) = x* для всех i I, поэтому описание равнове-
			i	i		i	i
сия можно упростить, см. следствие 4.5 ниже.
Определение. Графиком точечно-множественного отображения F: A → B называется
множество всех пар (a, b) таких, что a A и b F(a).
Следствие 4.5.(1) Пусть x* = ( x*						| i I) X*. Тогда сформулированные ниже утверждения
					i
попарно эквивалентны:
(а) исход x* соответствует равновесию по Нэшу;
(б) xi* Ri( x*i ) для всех i I;
(в) ui( xi* , x*i ) = max{ui(xi, x*i			) | xi Xi} для всех i I;
(г) для каждого i I пара ( x*			, x* ) принадлежит графику отображения отклика игрока i.
		i		i

Если координаты, входящие в набор ( x*i , xi* ) упорядочить упорядочить так, как они упорядочены в векторе x*, то получим вектор x*. Учитывая утверждения (а) и (г) следствия

4.5, можем считать, что множество всех равновесий по Нэшу совпадает с пересечением гра-

фиков всех откликов.

Определения.

Точка x Rn является граничной точкой множества M Rn, если любая окрестность этой точки имеет непустые пересечения и с множеством M, и с его дополнением.

(1) Доказательство очевидно.

61

Граница множества M Rn — это совокупность всех его граничных точек.

Множество M Rn замкнуто, если оно содержит свою границу.

Множество A Rn называется компактным, если оно замкнуто и ограниченно.

Пусть x0 и x1 ― точки из Rn; множество [x0, x1] = {(1 – )x0 + x1 | [0, 1]} ― это отре-

зок в Rn с концами x0 и x1.

Множество M Rn называется выпуклым, если любой отрезок с концами из M целиком лежит в этом множестве.

Функция f : M → R, определенная на выпуклом множестве M Rn, называется квазивогнутой, если f((1 – )x1 + x2) min{f(x1), f(x2)} для всех [0, 1] и x1, x2 из M.

Теорема 4.1 (о существовании равновесия по Нэшу).(1) Пусть игра записана в нормаль-

ной форме: G = (I, (Xi | i I), (ui | i I)). Если множества Xi являются непустыми, компактными и выпуклыми подмножествами евклидовых пространств (возможно, различных), а каждая функция ui квазивогнута по xi на Xi и непрерывна на множестве всех исходов игры, то в игре

G существует равновесие по Нэшу.

Доказательство теоремы, к сожалению, не является конструктивным, то есть не указы-

вает метод построения равновесий.

4.3.2. Исключение сильно доминируемых стратегий

Определение. Если xi и yi ― стратегии игрока i такие, что ui(xi, x–i) > ui(yi, x–i) для всех x–i A X–i, то будем говорить, что стратегия xi сильно доминирует стратегию yi относи-

тельно множества A.

Мы говорили о том, что рациональный игрок ограничит свой выбор слабо домини-

рующими стратегиями. Отсюда следует, что сильно доминируемая (относительно X–i) стра-

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

нирования относительно множества оставшихся стратегий. Эти игроки могут повторить про-

цедуру исключения сильно доминируемых стратегий. Если игра конечна, то после конечного числа шагов дальнейшее исключение стратегий станет невозможным, причем у каждого иг-

рока останется хотя бы одна не исключенная стратегия. Описанную процедуру исключения сильно доминируемых стратегий для краткости обозначим ИСДС.

(1) Доказательство: Бусыгин В.П., Желободько Е.В., Цыплаков А.А. Микроэкономика: третий уровень. В двух томах. Т. II. Новосибирск: Издательство СО РАН, 2008 (стр. 556 – 557).

62

Теорема 4.2 (инвариантность ИСДС). Для конечной игры в нормальной форме множе-

ство стратегий, не отброшенных в процессе ИСДС, не зависит от того, в каком порядке про-

сматривались игроки и их стратегии.

Доказательство. Исключение одной стратегии одного игрока будем считать шагом

процедуры ИСДС. Предположим, что мы реализовали ее дважды с различными упорядоче-

ниями игроков и исключаемых стратегий (реализации 1 и 2).
Пусть I = 1, m , X j (s)			― множество стратегий игрока i, не исключенных до шага s реа-
		i
лизации j{1, 2}, X j (s) =			X j (s) … X j			(s)	X j	(s) … X j	(s) для i I. Понятно, что для
		i	1	i 1			i 1	m
всех i, j, s справедливо вложение				X j (s)	X j (s 1)			и, следовательно,
				i		i
				j		j			(61)
				X i (s)		X i (s 1) .

Достаточно доказать, что множества стратегий, удаленных в реализациях 1 и 2, совпа-

дают. Предположим, что на шаге s реализации 1 удаляется стратегия yi игрока i, и все страте-

гии, удаленные в реализации 1 до этого шага, исключаются также в реализации 2 (гипотеза индукции). Пусть r ― номер последнего шага реализации 2. Из гипотезы индукции следует,

что	X 2	(r)	X 1	(s) для всех k I, поэтому
	k		k
						X 2k (r) X 1k (s) для всех k I.			(62)
	Допустим, что y X 2					(r 1) . По предположению какая-то стратегия x (1) X 1		(s)	сильно
				i	i	i	i

доминирует yi относительно множества X 1i (s) . Тогда из (62) следует, что xi(1) сильно доми-

нирует yi относительно X 2i (r) . Если xi(1) X i2 (r) , то эта стратегия была удалена на каком-то шаге s1 реализации 2, s1 < r. Значит, в множестве X i2 (s1 ) была стратегия xi(2), сильно доми-

нирующая xi(1) относительно X 2i (s1 ) . Если xi(2) X i2 (r) , то она была удалена на каком-то последующем шаге s2 реализации 2, s1 < s2 < r. Продолжая рассуждение, будем строить по-

следовательность xi(n) такую, что xi(n) X i2 (sn ) , xi(n+1) сильно доминирует xi(n) и, следова-

тельно, yi относительно X 2i (sn ) . Поскольку sn+1 > sn, эта последовательность не может быть бесконечной. Значит, ее последний элемент xi(a) лежит в X i2 (r) . Но xi(a) сильно доминирует yi относительно X 2i (sa ) . Из sa ≤ r и (61) следует, что xi(a) сильно доминирует yi относительно

X 2i (r) , поэтому стратегия yi будет исключена на шаге r реализации 2. #

Теорема 4.3. (связь между ИСДС и равновесиями по Нэшу).(1) Рассматриваем конеч-

ную игру в нормальной форме.

(1) Доказательство: Бусыгин В.П., Желободько Е.В., Цыплаков А.А. Микроэкономика: третий уровень. В двух томах. Т. II. Новосибирск: Издательство СО РАН, 2008 (стр. 547 – 550).

63

(а) Если x* = ( xi* | i I) ― равновесие по Нэшу, то ни одна из стратегий xi* не может быть отброшена в результате применения ИСДС.

(б) Если после завершения ИСДС у каждого игрока остается единственная стратегия xi* ,

то исход x* = ( xi* | i I) является равновесием по Нэшу.

4.4. Равновесия в смешанных стратегиях

Определение. Для игры в нормальной форме G = (I, (Xi | i I), (ui | i I)) стратегии, вхо-

дящие в множества Xi называют чистыми стратегиями.

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

можность: выбирать чистую стратегию как значение некоторой случайной величины, для ко-

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

жестве чистых стратегий.

Определение. Смешанная стратегия игрока ― это случайная величина, принимающая

значения из множества его чистых стратегий.
Далее будем рассматривать конечную игру
G = (I, (Xi | i I), (ui | i I)), где I = 1, m , Xi = {aik | k 1, n(i) }.	(63)

Определения и обозначения.

Вероятность, с которой игрок i выбирает чистую стратегию xi Xi обозначим p(xi) и положим pik = p(aik).

Множество смешанных стратегий игрока i имеет вид

n(i)

Mi = {(pi1, …, pin(i)) | pik ≥ 0 для всех k, pik = 1}. (64)

k 1

M = M1 … Mm ― множество исходов игры в смешанных стратегиях.

Каждой чистой стратегии aik игрока i соответствует его вырожденная смешанная стра-

тегия, в которой pik = 1 и pij = 0 для j j. Обозначим эту стратегию eik.

Предположение 15. При многократном повторении игры каждый игрок стремится уве-

личить свой ожидаемый (средний) выигрыш.

Допустим, что выбран исход μ M игры в смешанных стратегиях,

μ = (μi | i 1, m ), μi = (pik | k 1, n(i) ) для всех i. 64

Тогда исход x = (xi | i I) игры в чистых стратегиях, который дает игроку i выигрыш ui(x), мо-

жет быть реализован с вероятностью

m

P(x) = p(xi ) .

i 1

Теперь можем вычислить ожидаемый выигрыш игрока i при исходе μ:

Ui(μ) = ui (x)P(x) .

x X

(65)

(66)

Определение. Смешанным расширением игры (63) называется игра

GM = (I, (Mi | i I), (Ui | i I)),

где Mi и Ui определены формулами (64) и (66) соответственно.

В игре GM чистыми стратегиями игрока являются его смешанные стратегии в игре G, а

выигрыш игрока на любом наборе стратегий равен математическому ожиданию выигрыша при многократном повторении игры G.

Определение. Равновесием в смешанных стратегиях для игры (63) называется равнове-

сие по Нэшу в ее смешанном расширении.

Теорема 4.4 (о существовании равновесия в смешанных стратегиях).(1) Для всякой ко-

нечной игры существует равновесие в смешанных стратегиях.

По утверждению (в) следствия 4.5 (которое справедливо для любой игры в нормальной форме) исход μ* = ( μ*i | i I) является равновесием в смешанных стратегиях тогда и только тогда, когда Ui( μ*i , μ* i ) = max{Ui(μi, μ* i ) | μi Mi} для любого игрока i. Оказывается, в по-

следнем равенстве достаточно максимизировать по множеству чистых (точнее, вырожден-

ных смешанных) стратегий.

Теорема 4.5 (необходимое и достаточное условие равновесия).(2) Исход μ* = ( μ*i | i I)

является равновесием в смешанных стратегиях, если и только если

Ui( μ*i , μ* i ) = max{Ui(eik, μ* i ) | k 1, n(i) } для всех i I.

Следствие 4.6. Если исход x* = (aik(i) | i I) является равновесием в чистых стратегиях,

то соответствующий набор смешанных стратегий μ* = (eik(i) | i I) тоже является равновесием.

Доказательство. Из (66) и утверждения (в) следствия 4.5 получаем:

Ui(μ*) = ui(x*) ≥ ui(aik, x*i ) = Ui(eik, μˆ i ) для всех i I и k 1, n(i) .

(1)Доказательство легко получить, проверив, что смешанное расширение конечной игры удовлетворяет условиям теоремы 4.1.

(2)Доказательство: Воробьев Н.Н. Теория игр для экономистов-кибернетиков. М.: Наука, 1985 (глава 3,

§8.2).

65

Тогда μ* есть равновесие в смешанных стратегиях по теореме 4.5. #

Определение. Пусть μi = (pik | k 1, n(i) ) ― смешанная стратегия игрока i. Чистая стра-

тегия aik активна в смешанной стратегии μi, если pik > 0.

Следующая теорема показывает, что чистые стратегии, активные в равновесной сме-

шанной стратегии игрока i, в некотором смысле равноценны для него.

Теорема 4.6 (свойство равновесия).(1) Если исход μ* = ( μ*i | i I) является равновесием в смешанных стратегиях, μ*i = (pik | k 1, n(i) ) и pik > 0, то Ui(eik, μ* i ) = Ui( μ*i , μ* i ).

4.5. Антагонистические игры

Определения и обозначения.

Игра с постоянной суммой ― это такая игра, в которой

ui (x) = C

i I

для любого исхода x.

Игра с нулевой суммой ― это игра с постоянной суммой при С = 0.

Игра двух лиц с нулевой суммой называется антагонистической.

Антагонистическую игру будем записывать в виде G = (X, Y, F(x, y)), где X и Y ― мно-

жества стратегий игроков, F(x, y) ― функция выигрыша игрока 1; при этом функция выиг-

рыша игрока 2 равна –F(x, y).

Пусть функция F(x, y) определена на декартовом произведении X×Y произвольных множеств X, Y. Пара (x0, y0) является седловой точкой функции F(x, y) на X×Y, если для всех x X и y Y

F(x, y0) ≤ F(x0, y0) ≤ F(x0, y) для всех x X и y Y,

что эквивалентно условию

max{F(x, y0) | x X} = F(x0, y0) = min{F(x0, y) | y Y}.

Следствие 4.7.(2) Исход (x0, y0) является равновесием по Нэшу в антагонистической игре G = (X, Y, F(x, y)), если и только если (x0, y0) ― седловая точка функции F(x, y) на X×Y.

Теорема 4.7.(3) Если (x0, y0) и (x1, y1) ― седловые точки функции F(x, y) на X×Y, то

F(x0, y0) = F(x1, y1).

(1)Доказательство: там же, глава 3, §10.2.

(2)Доказательство оставляем читателю.

(3)Доказательство: Васин А.А., Морозов В.В. Теория игр и модели математической экономики. М.: МАКС Пресс, 2005 (лемма 1.1).

66

Определения. Пусть x(1) = ( xi(1) | i I) и x(2) = ( xi(2) | i I) ― равновесия по Нэшу.

Равновесия x(1) и x(2) взаимозаменяемы, если исходы ( xi(2) , x(1i) ) и ( xi(1) , x(2i ) ) для любого i I тоже являются равновесиями.

Равновесия x(1) и x(2) эквивалентны, если ui(x(1)) = ui(x(2)) для всех i I.

Переформулируем теорему 4.7, используя последнее определение.

Следствие 4.8.(1) В антагонистической игре все равновесия по Нэшу эквивалентны.

Определения. Пусть G = (X, Y, F(x, y)) ― антагонистическая игра.

Если исход (x0, y0) является равновесием по Нэшу в игре G, то тройку (x0, y0, v), где v =

F(x0, y0), называют решением игры, x0 и y0 ― оптимальными стратегиями игроков, v ― зна-

чением игры.

По теореме 4.7 значение игры не зависит от выбора равновесия.

Определения. Пусть G = (X, Y, F(x, y)) ― антагонистическая игра.

Величину g1(x) = min{F(x, y) | y Y} называют гарантированным результатом (выиг-

рышем) игрока 1 при стратегии x X.

Наибольший гарантированный результат игрока 1 называют нижним значением игры, v = max{g1(x) | x X}.

Стратегию x игрока 1 называют максиминной, если g1(x) = v.

Величину g2(y) = max{F(x, y) | x X} называют гарантированным результатом (проиг-

рышем) игрока 2 при стратегии y Y.

Наименьший гарантированный результат игрока 2 называют верхним значением игры, v = min{g2(y) | y Y}.

Стратегию y игрока 2 называют минимаксной, если g2(y) = v .

Теорема 4.8.(2) Для любой антагонистической игры v ≤ v .

Сформулируем основной результат о равновесиях по Нэшу в антагонистических играх.

Теорема 4.9.(3) Пусть G = (X, Y, F(x, y)) ― антагонистическая игра.

(а) Для существования равновесия по Нэшу в игре G необходимо и достаточно, чтобы вы-

полнялось равенство v = v .

(б) Набор (x0, y0, v) является решением игры G, если и только если v = v = v, x0 ― макси-

минная стратегия игрока 1 и y0 ― минимаксная стратегия игрока 2.

(1).

(2)Доказательство: Васин А.А., Морозов В.В. Теория игр и модели математической экономики. М.: МАКС Пресс, 2005 (лемма 1.2).

(3)Доказательство: там же, теорема 1.1.

67

Следствие 4.9. В антагонистической игре равновесия по Нэшу взаимозаменяемы.

Доказательство. Пусть (x0, y0) и (x1, y1) ― равновесия. Тогда, по теореме 4.9, x0 и x1 яв-

ляются максиминными стратегиями игрока 1, а y0 и y1 ― минимаксными стратегиями игро-

ка 2. Следовательно, по той же теореме, исходы (x0, y1) и (x1, y0) являются равновесиями. #

Если игрок 1 выберет любую максиминную стратегию, а игрок 2 ― любую минимакс-

ную, то возникнет равновесие (по теореме 4.11). По следствию 4.8 выигрыши игроков оди-

наковы во всех равновесиях. Поэтому в антагонистической игре с полной информацией иг-

роки могут независимо выбрать оптимальные стратегии, приводящие к равновесию.

4.6. Матричные игры

Определения и обозначения.

Конечная игра двух лиц называется биматричной игрой.

Множества стратегий игроков 1 и 2 в биматричной игре будем записывать в виде

X1 = {A1, …, Am} и X2 = {B1, …, Bn}.

Биматричную игру будем записывать в виде G = (A, B), где A = (aij) Rm n, B = (bij) Rm n, aij и bij ― выигрыши игроков 1 и 2 соответственно при исходе (Ai, Bj).

Биматричная игра с нулевой суммой (конечная антагонистическая игра) называется

матричной.

Матричную игру будем записывать в виде G = (A), где A = (aij) Rm n, aij ― выигрыш игрока 1 при исходе (Ai, Bj); при этом выигрыш игрока 2 равен –aij.

Теорема 4.10. Смешанное расширение конечной игры с постоянной суммой является игрой с той же постоянной суммой.

Доказательство. Пусть G = ((I, (Xi | i I), (ui | i I)) ― конечная игра с постоянной сум-

мой, а GM = ((I, (Mi | i I), (Ui | i I)) ― ее смешанное расширение. Множества всех исходов этих игр обозначим X и M соответственно. По условию

ui (x) = C

i I

для любого x X. Зафиксируем μ M, μ = (μi | i I), где μi ― смешанная стратегия игрока i. Те-

перь по формуле (65) определены вероятности P(x) исходов x X. Эти исходы образуют пол-

ную группу попарно несовместных событий, поэтому

		P(x) = 1.
		x X
Тогда, используя (66), получим
Ui (μ) = ui (x)P(x) = P(x) ui (x) = C P(x) = C. #
i I	i I x X	x X	i I	x X

68

Следствие 4.10.(1) Смешанное расширение матричной игры является антагонистиче-

ской игрой.

Теорема 4.11. Для матричной игры равновесия в смешанных стратегиях существуют,

эквивалентны и попарно взаимозаменяемы.

Доказательство. Пусть G = (A) ― матричная игра. По теореме 4.4 она имеет хотя бы одно равновесие в смешанных стратегиях. Множество этих равновесий совпадает с множе-

ством равновесий по Нэшу для смешанного расширения GM игры G. Но GM ― антагонисти-

ческая игра по следствию 4.10. Все ее равновесия эквивалентны по следствию 4.8 и взаимо-

заменяемы по следствию 4.9. #

Определения и обозначения. Пусть G = (A) ― матричная игра, A = (aij) Rm n.

Множества смешанных стратегий игроков 1 и 2 обозначим X и Y,

m	n
X = {(x1, …, xm) | xi = 1, xi ≥ 0 для всех i}, Y = {(y1, …, yn)T | y j = 1, yj ≥ 0 для всех j}.
i 1	j 1

Вероятность исхода (Ai, Bj) при смешанных стратегиях x и y равна xiyj.

По формуле (66) функция выигрыша игрока 1 в игре GM имеет вид

m	n
F(x, y) = aij xi y j .
i 1	j 1

Решением игры G в смешанных стратегиях называется решение игры GM.

Оптимальными смешанными стратегиями игры G называются оптимальные стратегии игры GM.

Значением игры G называется значение игры GM.

По Теореме 4.11 любая матричная игра имеет решение, то есть существует значение игры и у игроков есть оптимальные смешанные стратегии.

По теореме 4.9 набор (x0, y0, v) является решением игры G = (A) в смешанных стратеги-

ях, если и только если

max min		min max		(67)
x X	y Y	F(x, y) = F(x0, y0) = v = y Y x X F(x, y).
Теорема 4.12. Пусть v1		и v2 ― значения матричных игр G1 = (A) и G2 = (B), A = (aij),
B = (bij), причем bij = aij + C для всех i, j. Тогда игры G1 и G2			имеют одинаковые множества

оптимальных смешанных стратегий, причем v2 = v1 + C.

Доказательство. Обозначим M множество исходов в смешанных стратегиях, общее для игр G1 и G2. Пусть μ = (x, y) M, X = (Ai, Bj), Fk(x, y) ― выигрыш игрока 1 в смешанном расширении игры Gk (k{1, 2})Тогда

(1) Доказательство легко получить из определений и теоремы 4.6.

69

F2(x, y) = bi j xi	y j = ai j xi	y j + С xi y j = F1(x, y) + С.	(68)
i j	i j	i j

По следствию 4.7 исход (x*, y*) является равновесием в смешанном расширении игры

Gk тогда и только тогда, когда для любых смешанных стратегий x и y игроков 1 и 2 выполнено неравенство Fk(μ1, μ*2 ) ≤ Fk( μ1* , μ*2 ) ≤ Fk( μ1* , μ2). Но из (68) следует, что для k = 1 и k = 2 эти неравенства эквивалентны. #

Следующая теорема показывает, что внутренние экстремумы в формуле (67) можно вычислять на множествах чистых стратегий. Иначе говоря, при выборе оптимальной страте-

гии игроку достаточно учитывать только чистые стратегии противника.

Теорема 4.13.(1) Для любой игры G = (A), где A = (aij) Rm n, справедливы равенства

m n

m

m n

n

max min aij xi

y j = max min

aij xi

, min max

aij xi

y j = min max aij y j .

x X

y Y

i 1 j 1

x X

j

i 1

y Y x X

i 1 j 1

y Y

i

j 1

Для матричной игры G с матрицей A = (aij) Rm n составим следующую задачу линейно-

го программирования:

m

m

v → max при условиях v – aij xi

≤ 0 для всех j,

xi = 1,

xi ≥ 0 для всех i.

(69)

i 1

i 1

В любом допустимом решении этой задачи x = (xi | i 1, m ) описывает смешанную стра-

тегию игрока 1 и

m

v ≤ min aij xi .

j

i 1

Поэтому в оптимальном решении (v*, x*), x* = ( x*

| i 1, m ), имеем

i

m

v* =

max min

aij xi* .

x X

j

i 1

Из (67) и теоремы 4.13 следует, что v* ― значение игры, а x* ― оптимальная смешанная стратегия игрока 1.

Запишем задачу, двойственную к (69): имеет вид

n	n
w → min при условиях aij y j – v ≥ 0 для всех i,	y j = 1, yj ≥ 0 для всех j.	(70)
j 1	j 1

Пусть оптимальное решение этой задачи имеет вид (w*, y*), y* = ( y*j | j 1, n ). По первой тео-

реме двойственности v* = w*. Рассуждение, аналогичное тому, которое мы провели для зада-

чи (69), показывает, что y* ― оптимальная смешанная стратегия игрока 2.

Сформулируем доказанный результат.

(1) Доказательство: Воробьев Н.Н. Теория игр для экономистов-кибернетиков. М.: Наука, 1985 (теорема

15.1)

70