Влияние теории игр на развитие экономической теории. Теория ожидаемой полезности Дж. фон Неймана и О. Моргенштерна. Модель К. Эрроу - Ж. Дебре

Главная / Бизнес

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

, то есть цена игры в смешанных стратегиях не меньше нижней цены игры в чистых стратегиях α и не больше верхней цены игры в чистых стратегиях β.

Полным решением игры в смешанных стратегиях называется совокупность множеств оптимальных стратегий игроков и цены игры. Любая пара оптимальных стратегий и и цена игры образуют частное решение в смешанных стратегиях.

Основная теорема матричных игр фон Неймана . Любая матричная игра имеет решение в смешанных стратегиях, то есть существует цена игры в смешанных стратегиях и оптимальные смешанные стратегии и игроков А и В соответственно.

Критерий оптимальности смешанной стратегии игрока А в терминах, задаваемых цены игры в смешанных стратегиях, выигрыш-функции и множества смешанных стратегий игрока В

Пусть V-цена игры, Н(Р,Q) – выигрыш-функция, S B – множества смешанных стратегий игрока В.

Для того чтобы стратегия Р 0 игрока А была оптимальной, необходимо и достаточно, чтобы выполнялось нер-во Н(Р 0 ,Q) V для любого Q S B , (1)

т.е. выбор игроком А оптимальной стратегии Р 0 гарантирует ему выигрыш Н(Р 0 ,Q), не меньший цены игры V, при любой стратегии Q игрока В .

Док-во:

Необходимость. Пусть Р 0 - опт стратегия игрока А. тогда по т. Фон Неймана показатель эфф-ти α(Р) стратегии Р 0 равен цене игры V: (2)

Рассматривая как пок-ль эф-ти стратегии Р 0 относит множ-ва S B смеш стр-гий игрока В, будем иметь по опр-нию: (3)

Р 0 игрока А выполнется нер-во (1)

Для док-ва оптимальности стратегии Р 0 достаточно показать справедливость равенства: (4)

Т.к. нер-во(1) выполняется для любой стратегии Q S B игрока В, то (5)

Но цена игры V равна нижней цене игры , по опр кот. (6)

Критерий оптимальности смешанной стратегии игрока В в терминах задаваемых цены игры в смешанных стратегиях, выигрыш-функции и множества смешанных стратегий игрока А

Теорема (Критерий оптимальных стратегий.)

Пусть V-цена игры, Н(Р,Q) – выигрыш-функция, S A – множества смешанных стратегий игрока А.

Для того чтобы стратегияQ 0 игрока В была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство

Н(Р 0 ,Q) V для любого Р S A , (1)

т.е. выбор игроком В оптимальной стратегии Q 0 гарантирует ему проигрыш Н(Р, Q 0), не больший цены игры V, при любой стратегии Р игрока А.

Док-во:

Необходимость. Пусть Q 0 - опт стратегия игрока B. тогда по т. Фон Неймана показатель эфф-ти β(Q)стратегии Q 0 равен цене игры V: (2)

Рассматривая как пок-ль эф-ти стратегии Q 0 относит множ-ва S A смеш стр-гий игрока A, будем иметь по опр-нию: (3)

Из равенств (2)-(3)получаем (1)

Достаточность. Пусть для некоторой стр-гии Q 0 игрока B выполнется нер-во (1)

Для док-ва оптимальности стратегии Q 0 достаточно показать справедливость равенства: (4)

Т.к. нер-во(1) выполняется для любой стр-гии Q S B иг-ка В, то (5)

Но цена игры V равна верхней цене игры , по опр кот. (6)

Совокуп (5) и (6) эквивалентна рав-ву (4).

Достаточность доказана. Теорема доказана.

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

В общем случае 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

Введение

Что общего у шахмат, карточных игр, войн, переговоров, рыночной конкуренции, аукционов? Все эти ситуации можно описать c помощью теории игр - раздела прикладной математики, ставшей неотъемлемой частью экономической теории. Всюду, где только имеет место взаимодействие самостоятельных рациональных (или частично рациональных) субъектов, возникает игра. Главный вопрос теории игр заключается в предсказании поведения участников игры: какие ходы сделают шахматисты, чем завершатся войны и переговоры, какие цены сформируются на рынке и т.д. Оказывается, теория игр позволяет сделать достаточно сильные предсказания. Механизмы конкуренции, функционирования рынка, возникновения или краха монополий, способы принятия ими решений в условиях конкурентной борьбы, то есть механизмы игры монополий, действующие в экономической реальности, - все это является предметом анализа теории игр. Уже в момент ее зарождения многие предсказали революцию в экономических науках благодаря использованию нового подхода. Революции, возможно, и не произошло, но тенденции развития экономики показал плодотворность методов теории игр в прикладной сфере. Так, в 1994 году Дж. Харшаньи и Р. Зельтен получили Нобелевскую премию по экономике за работы в области теории игр (приложения их исследований, например - переговоры с односторонними трансакционными затратами, равновесие рынка с продавцом и несколькими потенциальными покупателями). Теория игр имеет не очень длинную историю. Решающий поворот в ее развитии произошел в 1928 году благодаря американцу Дж. фон Нейману. Именно тогда он представил математическое обоснование общей стратегии для игры двух участников в терминах минимизации и максимизации. В моей работе будет рассмотрена как раз та самая основная теорема теории матричных игр - теорема существования решения в смешанных стратегиях Дж. Фон Неймана.

В начале работы, на мой взгляд, необходимо сказать пару слов о её основателе. Фон Нейман Джон - выдающийся американский математик, член национальной АН США и Американской академии искусств и наук. Основные исследования относятся к функциональному анализу, теории типологических групп, теории вероятностей, математическим методам в экономике и вычислительной математике; доказал основную теорему теории игр (1928), совместно с О. Моргенштенром развил теорию игр и показал, как она может быть применена в экономике и социальных науках; вместе они в 1944 написали книгу «Теория игр и экономическое поведение»

Итак, основная теорема матричных игр фон Неймана гласит: любая матричная игра имеет решение в смешанных стратегиях, т.е. существуют цена игры в смешанных стратегиях V и оптимальные смешанные стратегии P 0 и Q 0 соответственно игроков A и B.

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

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

Если говорить о стратегиях, то следует разделять их на чистые и смешанные стратегии. Стратегии (чистые) - возможные действия игроков. Смешанные стратегии - стратегия игрока, состоящая в случайном выборе одной из его чистых стратегий. Таким образом, смешанная стратегия игрока - это дискретная случайная величина, значениями которой являются номера его чистых стратегий. Если говорить о взаимосвязи чистых и смешанных стратегий, то каждую чистую стратегию A i можно рассматривать как смешанную

A 1 =(1,0…,0,0)

A 2 =(0,1,…,0,0)

A m-1 =(0,0,…1,0),

A m =(0,0,…,0,1)

в которой чистая стратегия A i выбирается с вероятностью p i =1, а все остальные чистые стратегии - с вероятностью, равной нулю.

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

управление нейман матричный

Перейдём к цене игры. Прежде всего, стоит отметить, что цена игры бывает нижней и верхней. Начнём с ценой игры в чистых стратегиях. Нижняя цена игры (б) - это выигрыш, не меньший чем б, при использовании игроком А maxmin стратегии

Верхняя цена игры (в) - это максимальный проигрыш игрока B при использовании minimax стратегии.

Если говорить о смешанных стратегиях, то нижняя цены игры обозначается

А верхняя цена игры - величина

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

Итак, ознакомившись с базовыми понятиями, перейдём к самой теореме. Для Любая матричная игра имеет решение в смешанных стратегиях, т.е. существуют цена игры в смешанных стратегиях V и оптимальные смешанные стратегии P 0 и Q 0 соответственно игроков A и B, т.е:

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

Следует отметить, что при л=0 и л=1 неравество 1.2,превращающееся в равенство всегда справделиво. В данном определении x - точка конечномерного евклидова пространства. На множество X налагается условие выпуклости для того, чтобы для любых двух его точек x`, x`` точка при любом также принадлежала множеству X.

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

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

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

Соответственно, функции называется строго вогнутой на выпуклом множестве X если для любых двух точек x`, x``? X и произвольного числа л? справедливо неравенство

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

Итак, перейдём к основной части доказательства. Пусть действительная функция двух векторных аргументов xX и y Y, заданная на декартовом произведении X * Y множеств X и Y. Точка (x 0 , y 0), x 0 , y 0 , называется седловой точкой функции на декартовом произведении X*Y, если

Левое неравенство (1.6) говорит о том, что максимум функции на множестве X достигается в точке, т.е. . Правое неравенство (1.6) означает, что минимум функции на множестве Y достигается в точке, т.е. . Поэтому двойное неравенство (1.6) эквивалентным образом можно переписать в виде двойного равенства:

В определении равновесной ситуации в чистых стратегиях (, учитывая, что F(A i ,B j) = a ij , где F - функция выигрыша, неравенство

можно переписать в виде неравенства

которое соответствует неравенству 1.6, а равенство в виде равенства

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

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

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

Задача 1. Дана платёжная матрица игры 2x3

и смешанные стратегии P 0 = () и Q 0 = (соответственно игроков A и B.

Определить выигрыши игрока А в ситуациях (P 0, Q 0), (P 0, B 1) (P 0 , B 2), (P 0 ,B 3)

Данную задачу решим матричным способом. Воспользуемся матричной формулой.

H(P 0, Q 0) = P 0 A (Q 0) 2 = () ** = *= 8,87

Выигрыш игрока А в ситуации (P 0 , B 1), т.е. в ситуации, в которой игрок А применяет смешанную стратегию P 0 = (4/6, 2/6), а игрок B - чистую стратегию B 1 = (1,0,0) по формуле равен

Выигрыш игрока А в ситуации (), т.е. когда игрок применяет смешанную стратегию P 0 = (4/6, 2/6), а игрок B - чистую стратегию B 2 = (0,1,0) следующий

Выигрыш игрока А в ситуации (), т.е. когда игрок применяет смешанную стратегию P 0 = (4/6, 2/6), а игрок B - чистую стратегию B 2 = (0,0,1) следующий

Игрок А прячет в одной из рук монету. Игрок В пытается угадать руку с монетой. Если В не угадывает, то А получает от В 1 у.е. Если В угадывает руку с монетой и эта рука правая, то он получает от А 1 у.е. Если В находит монету в левой руке, то он получает от А 2 у.е. Определить оптимальные стратегии поведения для каждого игрока и средний выигрыш для А.

Пусть стратегии игроков: А1 - спрятать в правой; В1 - искать в правой; А2 - спрятать в левой; В2 - искать в левой. Игровая матрица для данной ситуации относительно игрока А имеет вид:

Найдём вероятности чистых стратегий в смешанных:

Аналогично с q.

Цена игры равна:

Подставим данные в формулу

Таким образом, игроку А нужно случайно чередовать руки с монетой, но в правой руке прятать в среднем в трех случаях из пяти, а в левой в двух случаях из пяти. В это случае в каждой игре в среднем А получит (-1/5) руб., то есть теряет 20 коп., игра для А не выгодная. Для игрока В выгодно также чередовать руки в которых он ищет монету, но в правой руке искать в 3 случаях из 5, что приведет к среднему выигрышу для него в 20 коп. за игру.

Заключение

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

"Есть в современной математике одна область, она носит безобидное название теории игр, но ей, несомненно, суждено сыграть очень важную роль в человековедении самого ближайшего будущего, - говорил Джон фон Нейман, один из основоположников кибернетики. - Она занимается вопросами оптимального поведения людей при наличии противодействующего противника. Для ученого противник - это природа со всеми ее явлениями; экспериментатор борется со средой; математик - с загадками математического мира; инженер - с сопротивлением материалов".

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

Список использованной литературы

1. Лабскер Л.Г., Бабешко Л.О. «Игровые методы в управлении экономикой и бизнесом»: Учеб. Пособие. - М.; Дело, 2001.

2. Луньков А.Д. «Курс по теории игр»: Учеб. Пособие. - Саратов, 2008

3. Курс лекций Данеева О.В.

Джон фон Нейман

ИССЛЕДОВАНИЕ ЭКОНОМИЧЕСКОГО ПОВЕДЕНИЯ

ВКЛАД ФОН НЕЙМАНА В ТЕОРИЮ ИГР

Теория принятия решений

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

Прежде всего, необходимо заметить, что как математик фон Нейман всегда стремился проверить, как работает то или иное правило на практике, будь то квантовая теория, гидродинамика, метеорология или экономика. В соавторстве с экономистом Оскаром Моргенштерном фон Нейман написал книгу «Теория игр и экономическое поведение». Этот труд описывает систему получения наибольших прибылей при наименьших потерях в условиях, когда друг с другом сталкиваются люди с противоположными интересами. Например, если угостить двух детей одним пирожным и предложить одному из них разрезать его, а другому - выбрать для себя кусок, то первый ребенок,

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

Синтез экономики и математики

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

Изучая историю математической экономики по работам видного экономиста конца XIX века Леона Вальраса, фон Нейман обратил внимание на несовершенство многих моментов в его теории. Он решил, что экономике необходим новый язык, и написал книгу - «Экономическое предсказание». Труд этот имеет несомненную научную ценность, однако очень сложен для чтения и применения на практике или в качестве учебного пособия.

Здесь фон Нейман выступил как первооткрыватель «нового языка», представляя игру как модель экономических взаимоотношений и осуществив, таким образом, синтез экономики и математики.

Скрытые возможности

Основанная в Америке в конце 1945 года корпорация «РЭНД» стала первой в мире организацией, которую назвали «фабрикой мысли». Проект «РЭНД» был запущен с целью обеспечения безопасности государства, поэтому его руководство сразу же заинтересовалась исследованиями фон Неймана и пригласило ученого в качестве консультанта.

В 1950 году Мелвин Дрешер и Мерил Флуд сформулировали «дилемму заключенного», в которой игроки стремятся получить выгоду, сотрудничая друг с другом или предавая друг друга. Как во всей теории игр, предполагается, что игрок («заключенный») максимизирует свой собственный выигрыш, не заботясь о выгоде других. Это открытие заставило людей думать, что теорию игр можно применять гораздо шире - не только в экономике и военном деле, но и в различных сферах общественной деятельности. В теории игр обнаружились скрытые возможности, которые могут быть объяснены с помощью математики.

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

< Противостояние СССР и США в октябре 1962 года, известное как Карибский кризис, было, в частности, проанализировано с помощью «Дилеммы заключенного», что послужило примером применения теории игр в решении военных конфликтов.

Смешанной стратегией первого игрока называется применение его чистых стратегий
по случайному закону с частотами
причем сумма частот (вероятностей) равна 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 любая чистая стратегия игроков является активной. Если первый игрок использует оптимальную смешанную стратегию
, а второй игрок применит первую активную стратегию, то выигрыш первого игрока равен цене игры:

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

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

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

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

, =

и цену игры:

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