Основная теорема теории матричных игр – теорема существования решения в смешанных стратегиях Дж. Фон Неймана

Федеральное государственное образовательное бюджетное

учреждение высшего профессионального образования

 

«Финансовый университет

при Правительстве Российской Федерации»

(Финансовый Университет)

Кафедра «Моделирование экономических и информационных систем»

Теоретико-практическая работа

по дисциплине «Теория игр»

на тему:

«Основная теорема теории матричных игр – теорема существования решения в смешанных стратегиях Дж. Фон Неймана.»

 

 

Выполнила:

КЭФ 2-7

Кочиева Элла

Научный руководитель:

 профессор Лабскер Лев Григорьевич

 

Москва

2014

Содержание

 

 

Введение

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

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

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

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

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

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

A1=(1,0…,0,0) 
A2=(0,1,…,0,0) 
………….. 
Am-1=(0,0,…1,0), 
Am=(0,0,…,0,1)

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

 

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

 

 

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

 

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

 

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

 

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

 

 

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

)

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

  (1.2)

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

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

  (1.3)

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

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

  (1.4)

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

  (1.5)

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

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

 

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

 

В определении равновесной ситуации в чистых стратегиях (, учитывая, что F(Ai,Bj) = aij, где F – функция выигрыша, неравенство 
  можно переписать в виде неравенства

 

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

 

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

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

 

Практическая часть

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

Задача 1.

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

Bj Ai	B1	B2	B3
A1	6	12	0
A2	1	6	8

 

 

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

Определить выигрыши игрока А в ситуациях (P0 ,Q0) , (P0, B1) (P0, B2), (P0,B3)

Решение:

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

 

H(P0 ,Q0) = P0 A (Q0)2 = () ** = *= 8,87

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

 

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

 

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

 

 

Задача 2.

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

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

	B1	B2
A1	-1	1
A2	1	-2

 

 

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

 ;

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

 ;

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

 

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

p1=

q1=

 

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

 

Заключение

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

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

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

 

 

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

1. Лабскер Л.Г., Бабешко Л.О. «Игровые методы в управлении экономикой и бизнесом»: Учеб. Пособие. – М.; Дело, 2001.
2. Луньков А.Д. «Курс по теории игр»: Учеб. Пособие. – Саратов, 2008
3. Курс лекций Данеева О.В.

 

 

 

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