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

В общем случае V * ≠ V * - седловой точки не существует. Оптимальное решение в чистых стратегиях также не существует. Однако, если расширить понятие чистой стратегии введением понятия смешанной стратегии, то удаётся реализовать алгоритм нахождения оптимального решения не вполне определённой игровой задачи. В такой ситуации предлагается использование статистического (вероятностного) подхода к нахождению оптимального решения антагонистической игры. Для каждого игрока, наряду с данным набором возможных для него стратегий, вводится неизвестный вектор вероятностей (относительных частот), с которыми следует применять ту или иную стратегию.

Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом:
P = (p 1 , p 2 ,…, p m),
где p i ≥ 0, p 1 + p 2 +…+ p m = 1. Величина p i называется вероятностью (относительной частотой) применения стратегии A i .

Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид:
Q = (q 1 , q 2 ,…, q n),
где q j ≥ 0, q 1 + q 2 +…+ q n = 1. Величина q j называется вероятностью (относительной частотой) применения стратегии B j . Совокупность (комбинация) чистых стратегий A 1 , A 2 , …A m и B 1, B 2, …B n в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями.

Основной теоремой в теории конечных антагонистических игр является Теорема фон Неймана : каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий .
Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P * и Q * , таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии.
Средний выигрыш игрока A определяется математическим ожиданием:

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

Стратегии P * , Q * называются оптимальными смешанными стратегиями, если M A (P, Q *) ≤ M A (P * , Q *) ≤ M A (P * , Q) (1)
В этом случае M A (P * , Q *) называется ценой игры и обозначается через V (V * ≤ V ≤ V *). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B .

В общем случае подобные задачи успешно решаются этим калькулятором .

Пример .

4	7	2
7	3	2
2	1	8

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

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B 1	B 2	B 3	a = min(A i)
A 1	4	7	2	2
A 2	7	3	2	2
A 3	2	1	8	1
b = max(B i)	7	7	8

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a i) = 2, которая указывает на максимальную чистую стратегию A 1 .
Верхняя цена игры b = min(b j) = 7. Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 ≤ y ≤ 7. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы .
В платежной матрице отсутствуют доминирующие строки и доминирующие столбцы.

3. Находим решение игры в смешанных стратегиях .
Запишем систему уравнений.
Для игрока I
4p 1 +7p 2 +2p 3 = y
7p 1 +3p 2 +p 3 = y
2p 1 +2p 2 +8p 3 = y
p 1 +p 2 +p 3 = 1

Для игрока II
4q 1 +7q 2 +2q 3 = y
7q 1 +3q 2 +2q 3 = y
2q 1 +q 2 +8q 3 = y
q 1 +q 2 +q 3 = 1

Решая эти системы методом Гаусса , находим:

y = 4 1 / 34
p 1 = 29 / 68 (вероятность применения 1-ой стратегии).
p 2 = 4 / 17 (вероятность применения 2-ой стратегии).
p 3 = 23 / 68 (вероятность применения 3-ой стратегии).

Оптимальная смешанная стратегия игрока I: P = (29 / 68 ; 4 / 17 ; 23 / 68)
q 1 = 6 / 17 (вероятность применения 1-ой стратегии).
q 2 = 9 / 34 (вероятность применения 2-ой стратегии).
q 3 = 13 / 34 (вероятность применения 3-ой стратегии).

Оптимальная смешанная стратегия игрока II: Q = (6 / 17 ; 9 / 34 ; 13 / 34)
Цена игры: y = 4 1 / 34

Основная теорема теории антагонистических игр - теорема Дж. фон Неймана

Если нижняя V_ и верхняя V цены игры в смешанных стратегиях совпадают, го их общее значение V - V_ - V называется ценой игры в смешанных стратегиях. Из неравенства (1.9.17) следует, что нижняя а и верхняя (3 цены игры в чистых стратегиях и цена игры в смешанных стратегиях V связаны между собой неравенствами а V

Стратегии Р° и Q 0 соответственно игроков А и В, удовлетворяющие равенствам а(Р°) - fi(Q°) = V называются оптимальными смешанными стратегиями соответственно игроков А и В. Если Р° и Q 0 оптимальные стратегии соответственно игроков А и S, то в силу определений (1.9.1) и (1.9.2) будем иметь:

откуда а(Р°) = (3(Q°) = H(P°,Q°) = V.

Определенные таким образом стратегии Р° и Q° называются оптимальными потому, что ни одному из игроков невыгодно отклоняться от своей оптимальной стратегии, если противник придерживается своей оптимальной стратегии.

Множества оптимальных смешанных стратегий соответственно игроков А и В обозначим через (S A)° и (S B)°.

Полным (общим) решением игры в смешанных стратегиях называется трех- элсментное множество {(S,)°, (S B)°, v}. Любая пара оптимальных стратегий

Р° и Q° соответственно игроков А и В и цена игры в смешанных стратегиях V образуют частное решение в смешанных стратегиях.

Основная теорема теории игр, сформулированная и доказанная Дж. фон Нейманом в 1928 году, устанавливает, что в любой конечной матричной игре существует решение в смешанных стратегиях.

Теорема 1.10.1. (Основная теорема матричных Hi p Дж. фон Неймана). Любая матричная игра имеет решение в смешанных стратегиях, т.е. существуют цена игры в смешанных стратегиях V и оптимальные смешанные стратегии Р° и Q° соответственно игроков А и В, т.е.

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

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

Числовая функция f(x) называется выпуклой на выпуклом множестве X конечномерного евклидова пространства, если для любых точек х",х" е X и произвольного числа А, е справедливо неравенство

Джон

фон Нейман (28 .12.1903 - 08 .02 .1957 )

Аналогично определяется вогнутая функция.

Функция f(x) называется вогнутой на выпуклом множестве X , если для любых двух точек х",х" е X и произвольного числа X е справедливо неравенство

Пусть f(x,y) - действительная функция двух векторных аргументов хеХ и у eY, заданная на декартовом произведении Хх У множеств X и У.

Точка (л"°,_у°), л’ 0 е X, у 0 е Y , называется седловой точкой функции f(x,y) на декартовом произведении X х Y, если

Это двойное неравенство эквивалентным образом можно переписать в виде двойного равенства

Если в частности функция / является выигрыш-функцией Н в смешанных стратегиях, а точки х - смешанными стратегиями Р е S A , точки у - смешанными стратегиями QeS B , то из данного определения седловой точки функции f(x,y) получаем определение седловой точки (Р 0 , (2°) выигрыш-функции H(P,Q), а именно, игровая ситуация (P°,Q°) в смешанных стратегиях называется седловой точкой выигрыш-функции H(P,Q), если выполняется неравенство

H(P,Q 0) QeS B , (1.10.2) или эквивалентное неравенству (1.10.2) равенство

Седловая точка выигрыш-функции F в чистых стратегиях (равновесная ситуация), определенная в § 1.5, является частным случаем седловой точки функции Н.

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

Для формулирования критерия (необходимого и достаточного условия) существования седловых точек напомним предварительно определения точных нижней и верхней границ функции.

Число z называется верхней границей числового множества Z, если любой элемент z из Z не превосходит z : z Если существует верхняя граница множества Z, то оно называется ограниченным сверху. У ограниченного сверху множества Z существует бесконечно много верхних границ; наименьшая из них называется точной верхней границей множества Z и обозначается supZ (по- латыни: supremum - наивысшсс).

Аналогично, число z называется нижней границей числового множества Z, если z ограниченным снизу. У офаниченного снизу множества существует бесконечное множество нижних границ, наибольшая из которых называется точной нижней границей множества Z и обозначается inf Z (по- латыни: infimum - наинизшее).

Если z = ф(.т) - числовая функция, определённая на множестве X , то верхняя и нижняя точные границы множества Z = {ф(д)} значений этой функции обозначаются соответственно зирф(х) и inf ф(х).

хеХ хеХ

Теорема 1.10.2 (Критерий существования седловой точки). Для того чтобы функция f(x,y), х е X, yeY, имела седловую точку на декартовом произведении X х Y , необходимо и достаточно, чтобы существовали

и выполнялось их равенство

Доказательство см. в , теорема 9.4, с. 86.

Если функция /(х,у), хе.Х вогнута (выпукла) но переменной х на X при любом фиксированном ye.Y и выпукла (вогнута) по переменной у на Y при любом фиксированном х е X , то она называется вогнуто- выпуклой (выпукло-вогнутой ).

Оказывается, что существование седловых точек является свойством любой непрерывной вогнуто-выпуклой (выпукло-вогнутой) функции.

Теорема 1.10.3. Если множества X с R" - выпуклые компакты, а функция f(x,y) непрерывна по совокупности переменных (x,y) е X xY и вогнуто-выпукла (выпукло-вогнута ) на X х Y , то у неё на декартовом произведении X х У существуют седловые точки.

Доказательство см. в , теорема 9.8, с. 98.

Теперь мы можем доказать теорему Дж. фон Неймана.

Доказательство теоремы 1.10.1.

Симплексы SjCzR"" и S B (zR" являются выпуклыми компактами. Выигрыш-функция H(P,Q ), PsS A , Q е S B , как явствует из ее аналитического выражения (1.8.1), линейна по каждой из переменных PeS i , Q&S B при фиксированной другой, а потому непрерывна и вогнуто - выпукла на декартовом произведении S A xS B . Тогда, по теореме 1.10.3 у функции Н(Р,0) на декартовом произведении S A х S B существует (хотя бы одна) седловая точка по определению (1.10.3) которой maxH(P,Q°) = H(P°,Q°) = mmH(P 0 ,Q),wni но (1.9.2) и

PeS A QeSu

По необходимой части критерия существования седловой точки (теорема 1.10.2), существуют равные величины (см. (1.10.4), (1.10.5))

Но, по теореме 1.9.1, inf H(P,Q) = min H(P,Q) = a(P) и

QeS B QeS„

sup H(P,Q) = max H(P,Q) = |)((9), и потому равенство (1.10.7) перепишется так:

PeS A PeS i

max(x(P) = minB((9). Значит, по определениям (1.9.10) и (1.9.11) нижней и верх-

PeS 4 QeS,

ней цен игры в смешанных стратегиях,

Таким образом, доказано существование цены игры V = V= V в смешанных стратегиях. Используя равенства (1.10.6), будем иметь:

откуда с учетом (1.10.8) получаем цепочку равенств (1.10.1). Таким образом, смешанные стратегии Р° е S., и Q n е S B , образующие седловую точку (Р° ,Q°) е S A x S B выигрыш-функции H(P,Q), являются оптимальными смешанными стратегиями соответственно игроков А и В. Итак, мы доказали существование решения матричной игры в смешанных стратегиях?

В заключение отмстим, что если существует цена игры в чистых стратегиях (у = а = р, см. § 1.4), то из неравенства а V

Пример 1.10.1. Вернемся к игре с матрицей (1.9.19), рассмотренной в примере 1.9.1. Там для показателей эффективности а(Р°) и неэффективности р(0°) смешанных стратегий Р° = (0,4; 0,6) и Q 0 = (0; 0; 0,6; 0,4) соответственно игроков А и В и для нижней К и верхней V цен игры в смешанных стратегиях было установлено равенство а(.Р 0)=Р(?? 0)=К = У = 2,2. Следовательно, ценой рассматриваемой игры является V = 2,2, а стратегии Р" = (0,4; 0,6) и Q 0 = (0; 0; 0,6; 0,4) являются оптимальными во множестве смешанных стратегий соответственно для шроков А и В. Поскольку нижняя цена игры в чистых стратегиях а = 1 меньше верхней цены шры в чистых стратегиях р = 3, данная игра решения в чистых стратегиях нс имеет.

Пример 1.10.2 (Уплата налога). Рассмотрим антагонистическую ситуацию, участниками которой являются, с одной стороны, государственная налоговая инспекция, а с другой стороны, конкретный налогоплательщик с годовым доходом 360 тыс. руб.

В качестве возможных действий государственной налоговой инспекции рассмотрим два способа. Один из них А , состоит в контролировании дохода налогоплательщика и взимании с него:

- налога в размере 13%, если налогоплательщик заявил свой действительный доход в размере 360 тыс. руб.;

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

Налогоплательщик при декларировании своего дохода использует одну из следующих грех стратегий поведения: 5, - заявить о действительном доходе в 360 тыс. руб.; В 2 - заявить доход 150 тыс. руб.; В } - скрыть доход.

Найти оптимальные стратегии действий государственной налоговой инспекции и налогоплательщика.

Решение. Пусть игроком А является государственная налоговая инспекция, а игроком В - налогоплательщик. В описанной ситуации их отношения можно считать антагонистическими, поскольку преследуемые ими цели прогивоположны. У игрока А две чистые стратегии: A t и А-,. Игрок В обладает гремя чистыми стратегиями: В х, В 2 , В,. В качестве выигрышей игрока А будем рассматривать суммы налога с налогоплательщика и возможного штрафа. Рассчитаем выигрыши игрока А.

В игровой ситуации (Л, 5,) выигрыш я и =360000 0,13 = 46800. В ситуации (И,й 2)выи1рыш я 12 = 360000 0,13+ (360000 -150000) 0,1 = 67800. В ситуации (И,5 3)имеем: а, 3 = 360000 0,13+ (360000-0) 0,1 = 82800. В случае, когда игрок А выбрал стратегию А , будем иметь: а, =360000 0,13 = 46800,

а 22 = 150000-0,13 = 19500, а 2} =0 0,13 = 0. Итак, получаем матрицу выигрышей игрока А:



а 2
				46800 Р = 46800~~^^

В последних добавленных к этой матрице столбце и строке проставлены показатели соответственно эффективности а, =46800, а 2=0 стратегий А, А 2 и неэффективности Р, =46800, Р 2 =67800, Р, =82800 стратегий В , В 2 , В } . Седловой точкой является вышрыш а и =46800 (поскольку он наименьший в 1-й строке и наибольший в 1-м столбце). Существует цена шры в чистых стратегиях у = а = р = 46800. Следовательно, цена игры в смешанных стратегиях V = у = 46800. Так как а(Л, ) = а, = 46800 = у = V , то чистая стратегия И, является оптимальной и во множестве чистых стратегий S c 4 , и во множестве смешанных стратегий S A (оптимальность чистой стратегии во множестве смешанных стратегий влечет за собой се оптимальность во множестве чистых стратегий, но не наоборот). Так как Р(^) = Р, =46800 = у = V, то чистая стратегия В х является оптимальной и во множестве чистых стратегий S #, и во множестве смешанных стратегий S B .

Полученный результат экономически интерпретируется следующим образом.

Оптимальное поведение государственной налоговой инспекции состоит в контролировании дохода налогоплательщика и взимании с него: налога в размере 13%, если налогоплательщик заявил свой действительный доход в размере 360 тыс. руб.;

Налога в размере 13% от 360 тыс. руб. и штрафа в размере 10% от нсза- явленной налогоплательщиком суммы, если налогоплательщик заявил в декларации доход меньше 360 тыс. руб., в частности, скрыл свой доход вовсе.

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

Вопросы для самоконтроля знаний

1. Что называется ценой игры в смешанных стратегиях?
2. Какое соотношение имеет место между нижней ценой игры в чистых стратегиях, ценой игры и верхней ценой игры в чистых стратегиях?
3. Какая существует связь между ценами игры в чистых и в смешанных стратегиях?
4. Дайте определение стратегии, оптимальной во множестве смешанных стратегий игрока А.
5. Дайте определение стратегии, оптимальной во множестве смешанных стратегий игрока В.
6. Является ли чистая стратегия, оптимальная во множестве смешанных стратегий, оптимальной и во множестве чистых стратегий?
7. Является ли чистая стратегия, оптимальная во множестве чистых стратегий, оптимальной и во множестве смешанных стратегий?
8. Является ли смешанная не чистая стратегия, оптимальная во множестве смешанных стратегий, оптимальной и во множестве чистых стратегий?
9. Сформулируйте основную теорему теории матричных антагонистических игр.
10. Что называется полным (общим) решением игры в смешанных стратегиях?

И. Какая функция называется выпуклой?

12. Какая функция называется вогнутой?
13. Дайте определение вогнуто-выпуклой функции.
14. Дайте определение седловой точки числовой функции двух векторных аргументов.
15. Дайте определение седловой точки выигрыш-функции в смешанных стратегиях.
16. Сформулируйте критерий существования седловой точки.
17. Сформулируйте достаточные условия существования седловой точки у вогнуто-выпуклой функции двух переменных, непрерывной по совокупности этих переменных.

Задачи для самостоятельного решения

1.10.1 (Рекламирование лекарств). Для игры в из условия задачи 1.9.1 найдите значение цены игры в смешанных стратегиях и покажите оптимальность смешанных стратегий Р° =(1/6, 5/6, 0) и Q° = (0; 0,5; 0,5; 0).
1.10.2. Являются ли оптимальными смешанные стратегии Р"ЦОД; 0,3; 0,1; 0,4) и (У,= (0,4; 0; 0,45; 0,15) для игроков А и В соответственно в условиях задачи 1.9.4? Почему?
1.10.3 (Отгадывание достоинства монеты). Определите, является ли значение среднего выигрыша в условиях задачи 1.8.5 ценой игры.
1.10.4. Найти цену игры, задаваемой следующей платежной матрицей



а 2

1.10.5. Для игры из условия задачи 1.10.4 определите показатель эффективности смешанной стратегии Р° = ( 1/3, 0, 2/3) и показатель неэффективности смешанной стратегии Q =(1/2, 0, 1/2). Чему равен выигрыш игрока В в игровой ситуации (Р° ,(2°)?

Существуют ли другие оптимальные решения для этой игры, кроме полученного в задаче 1.10.4? Приведите пример.

1.10.6. Используя критерий существования седловых точек (теорема 1.10.2),

выяснить их наличие у функции /(х,_у) = ^ - _yj , хе, уе, на декартовом квадрате 2 = х .

Джон фон Нейман (англ. John von Neumann", или Иоганн фон Нейман, нем. Johann von Neumann; при рожде-нии Янош Лайош Нейман, венг. Janos Lajos Neumann) - великий венгеро-американский математик, физик, философ, родился 28 декабря 1903 года в Будапеште в еврейской семье доктора от юриспруденции Макса Неймана, работавшего адвокатом в банке. Мать Маргарет Канн была домохозяйкой. Уже в 6 лет он мог делить в уме восьмизначные числа и разговаривать на древнегреческом, а в восемь хорошо разбирался в математическом анализе.В 1913 г. его отец получил дворянский титул с приставкой фон к фамилии. Джон фон Нейман учился в Берлинском университете (1921-1923), в Цюрихском политехническом институте (1923-1925), окончил Будапештский
университет (1926), который в этом же году присвоил ему степень доктора философии по математике (с элементами экспериментальной физики и химии). Работал в Берлинском университете (1927-1929), в Принстонском университете (США) (1930-1933), в Принстонском институте перспективных исследований (с 1933), в Лос-Аламосской научной лаборатории (1943-1955), член Бюро по проектированию ЭВМ (1945-1955), член комиссиипо атомной энергии США (с 1954). Дж. фон Нейман известен как творец многочисленных основополагающих результатов и научных направлений, как в фундаментальной, так и в прикладной математике. Основные исследования относятся к функциональному анализу, теории топологических групп, теории мер, теории колец операторов(называемых ныне «алгеброй фон Неймана»), теории вероятностей, математическим методам в экономике, вычислительной математике, квантовой механике, математической логике, теории множеств, метеорологии. Внес большой вклад в создание первых ЭВМ и разработку методов их применения. Доказал основную теорему теории игр(1928); совместно с О. Моргенштерном развил теорию игр и показал как она может быть применена в экономике исоциальных науках; вместе они в 1944 г. написали книгу «Теория игр и экономическое поведение», русскийперевод которой появился в издательстве «Паука» в 1970 г. . Им опубликовано 150 научных работ, из которых
посвящены физике. Джон фон Нейман был удостоен высших академических почестей: член Академии точныхнаук (Лима, Перу), Академии деи Линчеи (Рим, Италия), Американской академии искусств и наук, Американскогофилософского общества. Ломбардского института наук и литературы, Нидерландской королевской академии науки искусств. Национальной академии США, являлся почетным доктором многих университетов США и другихстран. Президент Американского математического общества. Награжден премиями М. Бохера (1938), им. А. Эйнштейна (1956), им. Э. Ферми (1957). Скончался фон Нейман 8 февраля 1957 г. в Вашингтоне от костной формырака, который был вызван радиоактивным облучением при испытании атомной бомбы в Тихом океане (, ).

Смешанной стратегией первого игрока называется применение его чистых стратегий
по случайному закону с частотами
причем сумма частот (вероятностей) равна 1:
. Смешанная стратегия первого игрока записывается в виде матрицы:

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

где сумма частот
его стратегий
равна 1:
.

Средняя цена игры V(,) со стратегиями игроков и равна:

(1) V(,) =

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

На основании принципа минимакса определяется решение игры: это пара оптимальных стратегий
, в общем случае смешанных, обладающих свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий решению игры, называется ценой игры и обозначаетсяV.

Так как чистые стратегии являются частным случаем смешанных, то цена игры удовлетворяет неравенству:
.

В 1928 году американский математик Джон Нейман доказал теорему:

Теорема 2 (Неймана ): Каждая конечная игра имеет по крайней мере одно решение, возможно, среди смешанных стратегий.

Для нахождения решения конечных игр без седловой точки требуется ввести еще одно понятие «активной» стратегии:

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

Теорема 3 (об активных стратегиях): если один из игроков придерживается своей оптимальной стратегии, то выигрыш остается неизменным и равным цене игры V , если другой игрок не выходит за пределы своих активных стратегий.

Пример. Позднее мы докажем, что оптимальной стратегией Фионы в игре с пальцами является смешанная стратегия с частотами
. Цена игрыV = –. Так как игра без седловой точки, то обестратегии Эдварда – активные. По теореме 3 при любых частотах стратегий Эдварда цена игры не изменится, если Фиона придерживается своей оптимальной стратегии. Пусть, например, частоты стратегий Эдварда
таковы:
.Средняя цена игры по формуле (1) равна: V.

Теорема 3 имеет большое практическое значение, так как она в некоторых случаях позволяет найти решение игры без седловой точки.

4. Аналитическое решение игры размера 2×2

Рассмотрим игру размера 2×2 с платежной матрицей

Для игры размера 2×2, в которой отсутствует седловая точка, решением игры по теореме Неймана будет пара смешанных стратегий

и
,
,
.

Чтобы их найти, воспользуемся теоремой 3. Если первый игрок придерживается своей оптимальной смешанной стратегии
, то его средний выигрыш будет равен цене игры V при любой активной стратегии второго игрока. Для данной игры размера 2×2 любая чистая стратегия игроков является активной. Если первый игрок использует оптимальную смешанную стратегию
, а второй игрок применит первую активную стратегию, то выигрыш первого игрока равен цене игры:

Если первый игрок использует оптимальную смешанную стратегию
, а второй игрок применит вторую активную стратегию, то выигрыш первого игрока снова будет равен цене игры:

Приравнивая левые части уравнений и учитывая, что =
,

получаем уравнение относительно :

, откуда находим оптимальную стратегию первого игрока:

, =

и цену игры:

Так как цена игры уже найдена, то для определения оптимальной стратегии второго игрока достаточно одного уравнения, которое получаем, если второй игрок применяет оптимальную стратегию, а первый – свою первую активную стратегию:

откуда, учитывая, что
, получаем:

=
,

Найдем по этим формулам решение игры Эдварда и Феоны.

Платежная матрица игры:
, поэтому

,
=
;
; =
,
=;

Оптимальные стратегии игроков:

Игра для Эдварда невыгодная: в среднем за каждую игру он будет проигрывать доллара.

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

Теорема 2. (основная теорема матричных игр, теорема фон Неймана-Нэша). Всякая матричная игра имеет ситуацию равновесия в смешанных стратегиях.

Доказательство

1. Пусть – игра со строго положительной матрицей
, где
. Докажем справедливость теоремы для игры с такой матрицейA .

Рассмотрим задачу линейного программирования следующего вида:

В векторно-матричной форме задача преобразуется к следующему виду:

(6)

где
.

Двойственная к (6) задача имеет следующий вид:

которая имеет следующую векторно-матричную форму:

(6д)

где
.

Так как элементы матрицы A строго положительны, то существует вектор
, для которого
, то есть задача (6) имеет допустимую точку.

С другой стороны, точка y =0 является допустимым решением (6д). Тогда по теореме двойственности существуют и– оптимальные решения задач (6) и (6д) соответственно и значения целевых функций в оптимальных точках совпадают, то есть

. (7)

Рассмотрим векторы:
,
.

Покажем, что ,– оптимальные смешанные стратегии ви цена игры
.

Первоначально докажем, что ,– смешанные стратегии.

Из соотношений (7):
, то есть
. Из допустимости векторовив задачах (6) и (6д) следует, что
,
, то есть пара
– ситуация в смешанных стратегиях.

Докажем, что ,– оптимальные смешанные стратегии.

Вычислим выигрыш первого игрока P1 в ситуации
:

Причем, с одной стороны,
, а с другой –
. Тогда
, а
.

Пусть ,– произвольные смешанные стратегии Р1 и Р2. Тогда выполняются неравенства:

Таким образом, ,
,
, то есть
– ситуация равновесия, а
– цена игрысо строго положительной матрицейA.

2. По лемме о масштабе теорема верна для игры с произвольной матрицей A , т. к. всегда существует матрица
, где
, такая, что элементы матрицы
положительны. Теорема доказана.

Упражнения к § 3.3–3.5

№1. Найти, опираясь на определение ситуации равновесия, ситуацию равновесия в игре со следующей матрицей:

1)
; 2)
.

№2 . Проверить, что
и пара
, где
и
, соответственно цена и ситуация равновесия в игре с матрицей
.

№3 . Методом сведения игры к системе неравенств найти оптимальные стратегии и цену игры, задаваемой матрицей:

№4 . Дана игра с квадратной матрицей
, где
.

С помощью свойства 2 оптимальных смешанных стратегий показать, что оптимальные стратегии игроков равны и вычисляются по формулам:
, а цена игры
.

№5 . Матрица порядка
называется латинским квадратом, если каждая строка и каждый столбец ее содержит все целые числа от 1 доm.

(Например, матрица
– латинский квадрат). Показать, что
.

№6 . Решить графически игру со следующими матрицами:

1)
; 2)
; 3)
;

4)
.

№ 7 . Найти оптимальные стратегии и цену игры сведением игры к задаче линейного программирования, если матрица имеет вид:

1)
; 2)
, 3)
.

№ 8. К туристу (игрок Р1) подходит незнакомец (игрок Р2) и предлагает сыграть в игру «Орел-решка». Если у туриста «орел», а у незнакомца «решка», то турист получит 30 ден.ед. в местной валюте; если у туриста «решка», а у незнакомца «орел», то всего 10 ден. ед. Если выборы совпадут, то «для справедливости», как говорит незнакомец, турист заплатит ему 20 ден. ед. Действительно ли эта игра «честная»? Станете ли Вы в нее играть (ответьте вначале без обращения к методам теоретико-игрового анализа)? Как будет влиять на Ваше решение количество партий в этой игре? Если Вы принимаете игру, какую стратегию выберете? Рассмотрите два варианта игры: а) выбор стратегий определяется игроками самостоятельно; б) выбор стратегий определяется случайно (по броску монеты). Сделайте выводы.

Из аналитических техник из разных разделов математики, нашедших применение в экономической теории, особое значение приобрела теория игр, разработанная Джоном (Яношем) фон Нейманом (1903-1957), выпускником Будапештского университета (1923). В 1928, будучи тогда приват-доцентом в Берлине, фон Нейман написал статью с изложением случая игры с нулевым эффектом, при которой выигрыш одного игрока слагается исключительно из ставок другого (других), так что общая сумма выгод и потерь равна нулю. Фон Нейман показал, что наилучшая ("минимаксная") стратегия в таких играх заключается в изучении всех возможных вариантов и проработке наихудших возможных результатов, а после - в выборе наименее плохого варианта.

С 1930 г. фон Нейман был профессором в Принстонском университете (позже он участвовал в Манхэттенском проекте по созданию атомной бомбы и в создании первой ЭВМ, а также внес вклад в квантовую механику). В 1939 г. в Принстон приехал эмигрировавший из Австрии профессор-экономист Оскар Моргенштерн (1902-1977). Он заочно хорошо знал фон Неймана, в том числе по участию в междисциплинарном Венском коллоквиуме по проблемам экономического равновесия, организованном К. Менгером-младшим, сыном основателя австрийской школы. В сборнике Венского коллоквиума (1937) фон Нейман опубликовал свою первую экономико-математическую статью, в которой доказывал существование траектории, характеризующей динамическое конкурентное равновесие траектории для пропорционально расширяющейся экономики. Фон Нейман представил модель расширяющейся экономики как игру двух участников с нулевой суммой; один из них максимизирует выигрыш - темп роста экономики при ограничениях на предложение, а другой - минимизирует проигрыш процент при ограничениях на прибыль. При некоторых условиях существует седловая точка (решение) такой игры, характеризующаяся равенством значений обеих целевых функций - темпа роста и процента. Это и есть точка равновесия, задающая траекторию сбалансированного роста.

Начавшееся сотрудничество фон Неймана и Моргенштерна завершилось фундаментальным трудом "Теория игр и экономическое поведение" (1944). Во 2-м издании этой книги (1947) была изложена модель выбора между рисковыми перспективами (лотереями) как с одним, так и с несколькими возможными исходами - модель ожидаемой полезности (ОП).

Теория ожидаемой полезности

Фон Нейман и Моргенштерн, по их собственным словам, "практически определили численную полезность как объект, для которого подсчет математических ожиданий является законным", и представили формальное доказательство того, что принцип максимизации ожидаемой полезности является критерием рациональности принимаемых решений, т.е. может быть выведен из нескольких фундаментальных аксиом. Аксиоматика фон Неймана - Моргенштерна была переформулирована Дж. Маршаком в статье "Рациональное поведение, неопределенные перспективы и измеримая полезность" в журнале (1950) и предложена им в качестве определения рационального поведения в условиях риска.

Категория ожидаемой полезности была особенно интересна для теоретиков-экономистов тем, что возвращала их к вопросу об окончательно, казалось бы, отброшенном кардинализме. Однако разница между кардиналистской трактовкой полезности в маржинализме и в теории игр состояла в том, что в первом случае функция полезности строилась в условиях определенности и определяла иерархию и интенсивность предпочтений, во втором - в условиях риска и определяла допустимые преобразования шкалы измерения. С точки зрения предпочтений теорию фон Неймана - Моргенштерна можно трактовать как ординалистскую, поскольку она обеспечивает лишь порядковое ранжирование лотерей.

Теория ожидаемой полезности стала отправным пунктом для экономической теории информации и методик оценивания риска и принятия решений при неопределенности. Пересмотрев предпосылку модели фон Неймана - Моргенштерна о нейтральном отношении к риску, экономисты из Чикагского университета М. Фридмен и Л. Сэведж в статье "Анализ полезности при выборе среди альтернатив, предполагающих риск" (1948) разделили отношения людей к риску на два типа: предпочтение и неприятие, причем это отношение не жестко персонифицируется, а скорее проявляется у одних и тех же индивидов в разных обстоятельствах. Фридмен и Сэведж проиллюстрировали это положение диаграммой, где индивид отказывается рисковать по мелочи, но готов сыграть в лотерею с большой вероятностью крупного выигрыша. Они также предложили социально-экономическую интерпретацию кривой полезности дохода, несколько раз меняющей выпуклость и вогнутость (рис. 22.1): когда индивид, перемещаясь по оси дохода внутри каждой социальной группы, демонстрирует неприятие риска (выпуклые участки), а при переходе в иную социальную группу склонен рисковать (вогнутый участок).

Рис. 22.1.

Равновесие Наша и модель Эрроу - Дебре. В 1950 г. молодой математик из Принстонского университета Джон Нэш защитил диссертацию "Некооперативные игры", в которой развил теорему фон Неймана о минимаксе, включив в нее ситуации игр с ненулевой суммой. Он показал, что для любой игры с любым количеством игроков всегда есть по крайне мере одна стратегия, которая гарантирует, что игрокам будет гораздо хуже, если они выберут что-нибудь другое. Перейдя в 1951 г. в Массачусетский технологический институт, Нэш опубликовал четыре статьи, которые легли в основу новой интерпретации конкурентного равновесия, которое выгодно сохранять игрокам, так как любое изменение только ухудшит их положение.

Открытие Нэша дало импульс изощренной математической модели общего экономического равновесия, которую предложили профессор Стэнфордского университета Кеннет Эрроу (р. 1921) и приехавший из Парижа Жерар Дебре (1921-2004) в статье "Существование равновесия в конкурентной экономике" в журнале (1954). Эрроу и Дебре начали сотрудничать благодаря участию обоих в комиссии Коулза и опирались на инструментарий теории выпуклых множеств - раздела теории игр. Они пришли к выводу, что одновременное существование равновесия на нескольких рынках в условиях совершенной конкуренции требует наличия форвардных рынков - то есть рынков, на которых можно заплатить сегодня за товар (услугу), который будет получен завтра, или получить сегодня товар в обмен на обещание заплатить за него завтра. Позднее Ж. Дебре обобщил модель в монографии "Теория ценности: аксиоматический анализ экономического равновесия" (1960).