Введение

Что общего у шахмат, карточных игр, войн, переговоров, рыночной конкуренции, аукционов? Все эти ситуации можно описать 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 года, известное как Карибский кризис, было, в частности, проанализировано с помощью «Дилеммы заключенного», что послужило примером применения теории игр в решении военных конфликтов.

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

Если нижняя 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 г. в Вашингтоне от костной формырака, который был вызван радиоактивным облучением при испытании атомной бомбы в Тихом океане (, ).

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

Теорема 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 ден. ед. Действительно ли эта игра «честная»? Станете ли Вы в нее играть (ответьте вначале без обращения к методам теоретико-игрового анализа)? Как будет влиять на Ваше решение количество партий в этой игре? Если Вы принимаете игру, какую стратегию выберете? Рассмотрите два варианта игры: а) выбор стратегий определяется игроками самостоятельно; б) выбор стратегий определяется случайно (по броску монеты). Сделайте выводы.