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

Если нижняя 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. Итак, получаем матрицу выигрышей игрока А:

В последних добавленных к этой матрице столбце и строке проставлены показатели соответственно эффективности а, =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. Найти цену игры, задаваемой следующей платежной матрицей

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

Введение

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

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

Биография

Джон Нейман родился в Будапеште, бывшем в те времена городом Австро-Венгерской империи. Он был старшим из трёх сыновей в семье преуспевающего будапештского банкира Макса Неймана и Маргарет Кэнн. Янош, или просто «Янси», был необыкновенно одарённым ребёнком. Уже в 6 лет он мог разделить в уме два восьмизначных числа и беседовать с отцом на древнегреческом. Янош всегда интересовался математикой, природой чисел и логикой окружающего мира. В восемь лет он уже хорошо разбирался в математическом анализе. Говорят, Янош всегда брал с собой две книги в туалет, опасаясь, что окончит чтение одной из них раньше завершения отправления естественных надобностей.

В 1911 году он поступил в Лютеранскую Гимназию.

В 1913 году его отец получил дворянский титул, и Янош вместе с австрийским и венгерским символами знатности - приставками фон (von) к австрийской фамилии и титулом Маргиттаи (Margittai) в венгерском именовании - стал называться Янош фон Нейман или Нейманом Маргиттаи Янош Лайос. Во время преподавания в Берлине и Гамбурге его называли Иоганном фон Нейманом. Позже, после переселения в 1930-х годах в США, его имя на английский манер изменилось на Джон.

Фон Нейман в 23 года получил степень доктора философии по математике (с элементами экспериментальной физики и химии) в университете Будапешта. Одновременно он изучал химическую инженерию в швейцарском Цюрихе (Макс фон Нейман полагал профессию математика недостаточной для того, чтобы обеспечить надёжное будущее сына).

С 1926 по 1930 годы Джон фон Нейман был приват-доцентом в Берлине.

В 1930 году фон Нейман был приглашен на преподавательскую должность в американский Принстонский университет.

В 1937 году фон Нейман стал полноправным гражданином США. В 1938 он был награждён премией имени М. Бохера за свои работы в области анализа.

В 1957 году фон Нейман заболел раком кости, возможно, вызванным радиоактивным облучением при исследовании атомной бомбы в Тихом океане или, может быть, при последующей работе в Лос-Аламосе, штат Нью-Мексико (его коллега, пионер ядерных исследований Энрико Ферми, умер от рака кости в 1954 году). Через несколько месяцев после постановки диагноза фон Нейман умер в тяжёлых мучениях. Рак также поразил его мозг, практически лишив его возможности мыслить. Когда он лежал при смерти в госпитале Вальтера Рида, он шокировал своих друзей и знакомых просьбой поговорить с католическим священником.

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

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

Математическая теория игр берёт своё начало из неоклассической экономики. Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение».

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

Труды Неймана оказали влияние на экономическую науку. Ученый стал одним из создателей теории игр – области математики, которая занимается изучением ситуаций, связанных с принятием оптимальных решений. Приложение теории игр к решению экономических задач оказалось не менее значимым, чем сама теория. Результаты этих исследований были опубликованы в работе Теория игр и экономическое поведение (The Theory of Games and Economic Behavior, совместно с экономистом О.Моргенштерном, 1944). Третья область науки, на которую оказало влияние творчество Неймана, стала теория вычислительных машин и аксиоматическая теория автоматов. Настоящим памятником его достижениям являются сами компьютеры, принципы действия которых были разработаны именно Нейманом (отчасти в совместно с Г.Голдстайном).

Основные положения теории игр

Ознакомимся с основными понятиями теории игр . Математическая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте - игроками. Чтобы описать игру, необходимо сначала выявить ее участников (игроков). Это условие легко выполнимо, когда речь идет об обычных играх типа шахмат и т.п. Иначе обстоит дело с "рыночными играми". Здесь не всегда просто распознать всех игроков, т.е. действующих или потенциальных конкурентов. Практика показывает, что не обязательно идентифицировать всех игроков, надо обнаружить наиболее важных. Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход - это сознательный выбор игроком одного из возможных действий (например, ход в шахматной игре). Случайный ход - это случайно выбранное действие (например, выбор карты из перетасованной колоды). Действия могут быть связаны с ценами, объемами продаж, затратами на научные исследования и разработки и т.д. Периоды, в течение которых игроки делают свои ходы, называются этапами игры. Выбранные на каждом этапе ходы в конечном счете определяют"платежи " (выигрыш или убыток) каждого игрока, которые могут выражаться в материальных ценностях или деньгах. Еще одним понятием данной теории является стратегия игрока. Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации. Обычно в процессе игры при каждом личном ходе игрок делает выбор в зависимости от конкретной ситуации. Однако в принципе возможно, что все решения приняты игроком заранее (в ответ на любую сложившуюся ситуацию). Это означает, что игрок выбрал определённую стратегию, которая может быть задана в виде списка правил или программы. (Так можно осуществить игру с помощью ЭВМ).

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

Для каждой формализованной игры вводятся правила, т.е. система условий, определяющая: 1) варианты действий игроков; 2) объём информации каждого игрока о поведении партнёров; 3) выигрыш, к которому приводит каждая совокупность действий. Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулём, выигрыш - единицей, а ничью - ½. Игра называется игрой с нулевой суммой, или антагонистической, если выигрыш одного из игроков равен проигрышу другого, т. е. для полного задания игры достаточно указать величину одного из них. Если обозначить а - выигрыш одного из игроков, b - выигрыш другого, то для игры с нулевой суммой b = -а, поэтому достаточно рассматривать, например а. Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной - в противном случае. Для того чтобы решить игру, или найти решение игры , следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получать максимальный выигрыш , когда второй придерживается своей стратегии. В то же время второй игрок должен иметь минимальный проигрыш , если первый придерживается своей стратегии. Такие стратегии называются оптимальными . Оптимальные стратегии должны также удовлетворять условию устойчивости , т. е. любому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре. Если игра повторяется достаточно много раз, то игроков может интересовать не выигрыш и проигрыш в каждой конкретной партии, а средний выигрыш (проигрыш) во всех партиях.

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

Типы игр

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

Симметричные и несимметричные

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

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

С нулевой суммой и с ненулевой суммой

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

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

Ещё игрой с отличной от нуля суммой является торговля , где каждый участник извлекает выгоду. Сюда также относятся шашки и шахматы; в двух последних игрок может превратить свою рядовую фигуру в более сильную, получив преимущество. Во всех этих случаях сумма игры увеличивается. Широко известным примером, где она уменьшается, является война .

Параллельные и последовательные

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

С полной или неполной информацией

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

Примеры игр с полной информацией: шахматы, шашки и другие. Известно, что фон Нейман считал свою теорию неприложимой к шахматам. Потому что теоретически, для каждой позиции в шахматной игре у каждого из игроков не только существует одна наилучшая стратегия, но она в принципе может быть просчитана обоими. Здесь нет места гаданию о том, каков будет ход противника, и нет места обману и блефу.

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

Игры с бесконечным числом шагов

Игры в реальном мире или изучаемые в экономике игры, как правило, длятся конечное число ходов. Математика не так ограничена, и в частности, в теории множеств рассматриваются игры, способные продолжаться бесконечно долго. Причём победитель и его выигрыш не определены до окончания всех ходов.

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

Дискретные и непрерывные игры

Большинство изучаемых игр дискретны : в них конечное число игроков, ходов, событий, исходов и т. п. Однако эти составляющие могут быть расширены на множество вещественных чисел. Игры, включающие такие элементы, часто называются дифференциальными. Они связаны с какой-то вещественной шкалой (обычно - шкалой времени), хотя происходящие в них события могут быть дискретными по природе. Дифференциальные игры находят своё применение в технике и технологиях, физике.

Метаигры

Это такие игры, результатом которых является набор правил для другой игры (называемой целевой или игрой-объектом ). Цель метаигр - увеличить полезность выдаваемого набора правил.

Пример ы: Однажды Винни Пух с Пятачком пошли вместе охотиться на Слонопотама. Вырыли яму-ловушку, а в качестве приманки положили на дно горшок с медом. Ночью, однако, медвежонок почувствовал, что ему чего-то очень не хватает. Уговорив себя, что он только оближет немного меда , он пошел к яме и... съел всю приманку. Естественно, Слонопотам не явился к ловушке. В терминах теории игр, Винни Пух выбрал стратегию предать свою команду ради собственной выгоды и этим лишил всех игроков коллективного блага.

Классическая задача в теории иг р

Рассмотрим классическую задачу в теории игр.

Фундаментальная проблема в теории игр

Рассмотрим фундаментальную проблему в теории игр под названием Дилемма заключенного.

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

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

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

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

Классическая дилемма заключённого

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

Классическая формулировка дилеммы заключённого такова:

Двое преступников, А и Б, попались примерно в одно и то же время на сходных преступлениях. Есть основания полагать, что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок лишения свободы (10 лет)(20 лет). Если оба молчат, их деяние проходит по более лёгкой статье, и они приговариваются к 6 месяцам(1 год). Если оба свидетельствуют против друг друга, они получают минимальный срок (по 2 года)(5 лет). Каждый заключённый выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно , что сделает другой. Что произойдёт?

Игру можно представить в виде следующей таблицы:

Дилемма появляется, если предположить, что оба заботятся только о минимизации собственного срока заключения.

Представим рассуждения одного из заключённых. Если партнёр молчит, то лучше его предать и выйти на свободу (иначе - полгода тюрьмы). Если партнёр свидетельствует, то лучше тоже свидетельствовать против него, чтобы получить 2 года (иначе - 10 лет). Стратегия «свидетельствовать» строго доминирует над стратегией «молчать». Аналогично другой заключённый приходит к тому же выводу.

С точки зрения группы (этих двух заключённых) лучше всего сотрудничать друг с другом, хранить молчание и получить по полгода, так как это уменьшит суммарный срок заключения. Любое другое решение будет менее выгодным.

Обобщённая форма

1. 
   В игре - два игрока и банкир. Каждый игрок держит 2 карты: на одной написано «сотрудничать», на другой - «предать» (это стандартная терминология игры). Каждый игрок кладёт одну карту перед банкиром лицом вниз (то есть никто не знает чужого решения, хотя знание чужого решения не влияет на анализ доминирования). Банкир открывает карты и выдаёт выигрыш.
2. 
   Если оба выбрали «сотрудничать», оба получают C . Если один выбрал «предать», другой «сотрудничать» - первый получает D , второй с . Если оба выбрали «предать» - оба получают d .
3. 
   Значения переменных C, D, c, d могут быть любого знака (в примере выше все меньше либо равны 0). Обязательно должно соблюдаться неравенство D > C > d > c, чтобы игра представляла собой «Дилемму заключённого» (ДЗ).
4. 
   Если игра повторяется, то есть играется больше 1 раза подряд, общий выигрыш от сотрудничества должен быть больше суммарного выигрыша в ситуации, когда один предаёт, а другой - нет, то есть 2C > D + c.

Похожая, но другая игра

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

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

В этой игре обман всегда будет наилучшим решением, означая также, что рациональные игроки никогда не будут играть в неё, и что рынок обмена закрытыми сумками будет отсутствовать.

Проблемы практического применения в управлении

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

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

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

Экспериментально доказано, что при расширении игры до десяти и более этапов игроки уже не в состоянии пользоваться соответствующими алгоритмами и продолжать игру с равновесными стратегиями.

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

Если нижняя и верхняя цены игры в смешанных стратегиях совпадают, то их общее значение 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).

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

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

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

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

Игра – это формализованная модель реальной ситуации, описывающая действия двух или нескольких участников, выполняемые по определенным правилам. Примерами игр являются шахматы, футбол, карточные игры. Игра заканчивается выигрышем (победой) одного из игроков. Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух. Далее будем рассматривать только парные игры.

Игра называется игрой с нулевой суммой или антагонистической, если выигрыш одного из игроков равен проигрышу другого. В игре с нулевой суммой сумма выигрышей игроков всегда равна нулю.

Развитие игры во времени состоит из ряда последовательных этапов – «ходов» игроков. Ход игрока – это выбор одного из предусмотренных правилами игры действия игрока. Ходы делятся на случайные и личные. Случайный ход – это случайно выбранное действие, например, случайно выбранное число компьютером. Личный ход– это сознательный выбор игроком одного из возможных действий, например, выбор клетки в игре «крестики – нолики». Многие карточные игры относятся к играм смешанного типа, которые содержат как случайные, так и личные ходы, в отличие от шахмат, где все ходы – личные.

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

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

Если игра повторяется многократно, то в качестве цены игры определяется средний выигрыш (математическое ожидание) первого игрока за одну игру.

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

Рассмотрим парную антагонистическую конечную игру, в которой первый игрок имеет m стратегий, а второй игрок имеет n стратегий. Такая игра называется игрой размерности m×n. Пусть X = – множество стратегий первого игрока, Y =
– множество стратегий второго игрока. В результате выбора игроками любой пары стратегий иоднозначно определяется выигрышпервого игрока или проигрыш
второго игрока. Предположим, что значенияизвестны для любой пары стратегийи. МатрицаA = (),i = 1, 2, …, m; j = 1, 2, …, n, называется платежной матрицей или матрицей игры. Таким образом, любую конечную игру можно рассматривать как тройку объектов
, гдеA – платежная матрица вида:

Пример1. Составим платежную матрицу для следующей игры: У Ани 2 карты – белая и черная с цифрой 1 на каждой. У Бори тоже 2 карты, черная с цифрой 1, а белая с цифрой 0. Цвет и цифры обозначены только на одной стороне, так что их можно скрыть от противника. Аня и Боря одновременно открывают одну из своих карт. Если цвета совпадают, то выигрывает Аня сумму (в рублях), равную разности показанных цифр. Если же карты разного цвета, то эту сумму получает Боря.

Решение. Если оба показывают белые карты, то Аня выигрывает 1 – 0 =1 рубль. Если обе карты черные, то выигрыш Ани равен 1– 1 =0.

Если у Ани белая карта, а у Бориса черная, то проигрыш Ани равен нулю. В противоположном случае она проигрывает 1 – 0 =1 рубль. Получаем платежную таблицу:

Пример 2. Составим платежную матрицу для игры «Выбрасывание пальцев»: Эдвард и Фиона одновременно показывают друг другу один или два пальца. Если общее число показанных пальцев четное, то именно такую сумму в долларах выигрывает Эдвард. Если же было показано 3 пальца, то Фиона выигрывает 3 доллара.

Очевидно, у каждого из игроков имеется 2 стратегии – показать 1 или 2 пальца. Платежная таблица (выигрышей Эдварда) имеет вид: