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

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

Что общего у шахмат, карточных игр, войн, переговоров, рыночной конкуренции, аукционов? Все эти ситуации можно описать 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⁰, B₁), т. е. в ситуации, в которой игрок, А применяет смешанную стратегию P⁰ = (4/6, 2/6), а игрок B — чистую стратегию B₁ = (1,0,0) по формуле равен

Выигрыш игрока, А в ситуации (), т. е. когда игрок применяет смешанную стратегию 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.

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

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