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

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

Введение

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

1. Теоретическая часть

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

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

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

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

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

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

A₂=(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⁰ и Q⁰ соответственно игроков A и B, т.е:

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

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

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

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

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

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

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

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

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

В определении равновесной ситуации в чистых стратегиях (, учитывая, что F(A_i,B_j) = a_ij, где F - функция выигрыша, неравенство

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

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

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

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

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

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

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

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

Определить выигрыши игрока А в ситуациях (P^0,Q⁰), (P^0, B¹) (P⁰, B²), (P⁰,B³)

Решение:

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

H(P^0,Q⁰) = P⁰ A (Q⁰)² = () ** = *= 8,87

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

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

Задача 2

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

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

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

;

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

;

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

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

p₁₌

q₁₌

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

Заключение

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

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

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

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

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

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

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