Задачи теории игр в экономике и в области финансов.

Классификация игр по различным признакам

Теория игр- теоритич основы математич моделей принятия оптим реш-й в конфликт ситуациях рыночн отнош-й.

Конфликт ситуация-это столкновение интересов не менее 2 сторон,каждая из кот для достижения целей имеет возможн действов разл способами в зависимости от действ противоборств сторон.

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

Коалиция -объединение игроков по различным причинам.

Правила игры- система условий с целью формализаций:

а)стратегий игроков

б)объем информ,кот каждый из игроков может получить от действ. др. игрока

в)исход игры в рез-те любой совокупной стратегии игроков.

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

Стратегии-существование определенных возможных действий у каждого из игроков.

Функ выигрыша игрока А→F_A-это степень удовлетвор интересов игрока А.

F_A: X→R, X= . F_A(x)ЄR

Для игрока В-аналогично. F_B-фун-я выигрыша игрока В.

F_B: Y→R, Y= , F_B(y)ЄR.

Игры можно классифицировать по различным признакам:

· по числу «игроков» (сторон)-множественные (≥2) и парные;

· по числу ходов в игре:

многошаговые;

бесконечные;

· математической структуре модели игры:

рекурсивные;

дифференциальные;

· по числу стратегий игры:

конечные;

бесконечные, если хотя бы у одного «игрока» число стратегий бесконечно;

· по взаимоотношениям игроков:

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

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

· по степени информативности «игроков» в игре:

детерминированные, когда условия, в которых принимаются решения, известны полностью;

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

неопределенные, когда известно множество возможных вариантов, но без какой-либо информации об их вероятностях;

· по выигрышу игры:

антагонистические;

игры с ненулевой суммой;

· по характеру получения информации:

статические игры или игры в нормальной форме (игроки получают всю предназначенную им информацию до начала игры и ходят один раз, одновременно и независимо);

динамические игры или игры в позиционной форме (информация поступает игрокам в процессе развития игры);

· по полноте имеющейся у игроков информации:

статические игры с полной информацией

статические игры с неполной информацией);

динамические игры с полной информацией и неполной информацией

Максиминный принцип игры

Рассмотрим матричную т × п - игру с игроками А и В,в кото­рой игрок А обладает т чистыми стратегиями ={А₁,..., А_т}, a игрок В - п чистыми стратегиями ={В₁,..., В_п}. Значения функции выигрыша игрока A обозначим через а_ij,т. е. F_A (i, j) = а_ij, и тогда матрица игры будет иметь вид

Bj A = Ai	B 1	B 2	…	(1) Bn
A 1	a 11	a 12	…	a 1 n
A 2	a 21	a 22	…	a 2 n
…	…	…	…	…
Am	am 1	am 2	…	amn

Перед игроком А стоит задача выбора чистой стратегии из множества , эффективной в определенном смысле, в результате применения которой он получит максимально возможный гарантированный выигрыш. Если игрок А выбрал стратегию А_i (i =1, …, m),, то его выигрышем может быть один из выигрышей

а_{i 1}, а_{i 2}, …, а_in,

расположенных в i -й строке матрицы выигрышей, в зависимости от выбранной игроком В стратегии. Предполагая поведение игрока А крайне осмотрительным, необходимо считать, что игрок В сыграет наилучшим для себя образом и на выбор игроком А стратегии А_i выберет ту стратегию B_j, при которой выигрыш игрока А окажется минимальным. Обозначим минимальный среди выигрышей а_{i 1}, а_{i 2}, …, а_in через α _i:

и назовем его показателем эффективности стратегии А_i. Продолжая действовать разумно, игрок А должен выбрать ту стратегию, которая максимизирует показатель эффективности, т.е. для которой число α _i максимально. Если обозначить это максимальное число через α:

то по формуле

Описанный принцип выбора эффективной стратегии игроком А называется максиминным принципом, а выигрыш α - максимином.

Пусть игрок А выбрал максиминную стратегию а игрок В - какую-то произвольную стратегию B_l, l = 1,..., п. Тогда в создавшейся ситуации ( B_l) выигрыш игрока А в чистых стратегиях будет для которого в силу равенств и будет справедливо неравенство

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

 

Минимаксный принцип игры

Рассмотрим матричную т × п - игру с игроками А и В,в кото­рой игрок А обладает т чистыми стратегиями ={А₁,..., А_т}, a игрок В - п чистыми стратегиями ={В₁,..., В_п}. Значения функции выигрыша игрока A обозначим через а_ij,т. е. F_A (i, j) = а_ij, и тогда матрица игры будет иметь вид

Bj A = Ai	B 1	B 2	…	(1) Bn
A 1	a 11	a 12	…	a 1 n
A 2	a 21	a 22	…	a 2 n
…	…	…	…	…
Am	am 1	am 2	…	amn

 

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

а _{1 j} , а _{2 j} , …, а_mj, (1)

выигрышей, стоящих в j -м столбце матрицы выигрышей, в зависимости от того, какой стратегии будет придерживаться игрок А. Но так как игрок В предполагает, что игрок А играет наилучшим для себя образом, то выигрышем игрока А будет максимальное из чисел (1); обозначим его через β_j:

и назовем показателем неэффективности стратегии В_j. Таким образом, для любой стратегии B_j игрока В наибольший его проигрыш равен β _j. В интересах игрока В - выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел (2) обозначим β:

Отсюда в силу формулы (2) получим для β выражение:

Критерий выбора эффективной стратегии для игрока В называется минимаксным принципом, а выигрыш β называется минимаксом.

Показатель эффективности смешанной стратегии игрока А относительно множества чистых стратегий игрока В. Доказательство теоремы о совпадении показателей эффективности смешанной стратегии игрока А относительно множеств смешанных и чистых стратегий игрока В

Число α (P; )назовем показателем эффективности смешанной стратегии PÎ игрока A относительно множества смешанных стратегий игрока В. Если в этом определении множество смешанных стратегий игрока В заменить на множество его чистых стратегий, то получим определение показателя эффективности смешанной стратегии PÎ игрока А относительно множества чистых стратегий игрока В. Расширение множества чистых стратегий игрока В до множества его смешанных стратегий не изменяет показателей эффективности стратегий игрока А, точнее имеет место следующая теорема: α (P; ) = α (P; )

Так как ﬤ , то {H (P,Q):QÎ } ﬤ{H (P,Q): QÎ } и,

следовательно £ (P; ) = (QÎ minH(P,Q) ≤ (): (QÎ minH (P,Q) = α (P; )
(для 23 вопроса не min, amax; и )

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

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

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

 

 

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

Теорема. Для того, чтобы стратегия Q^o игрока В была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство H(P,Q^o)≤V для любого РϵS_B, т.е. выбор игроком В одной из своих оптимальных стратегий Q^o гарантирует ему проигрыш, не большей цены игры V, при любой стратегии Р игрока А.

Доказательство. Пусть Q^o – оптимальная стратегия игрока В. Тогда по основной теореме матричных игр фон Неймана показатель эффективности β(Q^o) стратегии Q^o равен цене игры V: V= β(Q^o). Рассматривая β(Q^o) как показатель эффективности β(Q^o, S_A) стратегии Q^o относительно множества SA смешанных стратегий игрока А, будем иметь по определению β(Q^o, S_A)=maxH(P,Q^o).

Следовательно, V= β(Q^o)= β(Q^o, S_A)=maxH(P,Q^o), откуда получаем неравенство H(P,Q^o)≤V. Но V= V^¾=min β(Q)≤ β(Q^o). Получаем β(Q^o)=V, которое в силу теоремы фон Неймана означает, что стратегия Q^o являеься оптимальной.

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

Теорема. Пусть V- цена игра, H(P⁰,Q) – функция выигрыша, S^C_B={B₁,…,B_n} – множество чистых стратегий игрока В.

Для того чтобы стратегия Р⁰ игрока А была оптимальной, необходимо и достаточно, чтобы Н(Р⁰,B_j)≥V, j=1,…,n.

Доказательство. Достаточно установить эквивалентность неравенств H(P⁰, Q)≥V и Н(Р⁰,B_j)≥V. Докажем эквивалентность. Пусть справедливо неравенство H(P⁰, Q)≥V. Так как это неравенство имеет место для любой стратегии QϵS_B игрока В, то оно, в частности, будет справедливым и для его чистых стратегий B_jϵ S^C_B, j=1,…,n, т.е. неравенство Н(Р⁰,B_j)≥V имеет место. Таким образом импликация H(P⁰, Q)≥V на Н(Р⁰,B_j)≥V доказана.

Теперь пусть имеет место неравенство Н(Р⁰,B_j)≥V, j=1,…,n. Тогда по формуле с учетом того, что =1, получим, , QϵS_B, т.е. доказано неравенство H(P⁰, Q)≥V. Таким образом, справедлива импликация

Н(Р0,Bj)≥V на H(P⁰, Q)≥V и, следовательно, эквивалентность H(P⁰, Q)≥V и Н(Р⁰,B_j)≥V.

 

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

Теорема. Пусть V- цена игра, H(P,Q⁰) – функция выигрыша, S^C_A={A₁,…,A_n} – множество чистых стратегий игрока A. Для того чтобы стратегия Q⁰ игрока В была оптимальной, необходимо и достаточно, чтобы Н(A_i,Q⁰⁾≤V, i=1,…,n.

Доказательство. Достаточно установить эквивалентность неравенств H(P,Q^o)≤V и Н(A_i,Q⁰⁾≤V. Докажем эквивалентность. Пусть справедливо неравенство H(P,Q^o)≤V. Так как это неравенство имеет место для любой стратегии PϵS_A игрока A, то оно, в частности, будет справедливым и для его чистых стратегий A_iϵ S^C_A, i=1,…,n, т.е. неравенство H(P,Q^o)≤V имеет место. Таким образом импликация H(P,Q^o)≤V на Н(A_i,Q⁰⁾≤V доказана.

Теперь пусть имеет место неравенство Н(A_i,Q⁰⁾≤V, i=1,…,n. Тогда по формуле с учетом того, что =1, получим, , PϵS_A, т.е. доказано неравенство H(P,Q^o)≤V. Таким образом, справедлива импликация

Н(A_i,Q⁰⁾≤V на H(P,Q^o)≤V и, следовательно, эквивалентность H(P,Q^o)≤V и Н(A_i,Q⁰⁾≤V.

 

32. Доказательство теоремы о геометрической интерпретации множества стратегий игрока , оптимальных во множестве смешанных стратегий.

Следствие. Множество S^O_A оптимальных стратегий игрока А является выпуклым многогранником (политопом), содержащимся в симплексе S_A всех смешанных стратегий игрока А.

Доказательство. Для каждой оптимальной стратегии Р0=(р⁰₁,…,р⁰_m) игрока А справедливо неравенство Н(Р⁰,B_j)≥V, j=1,…,n, которое можно переписать следующим образом: , j=1,…,n. Множество точек Р⁰=(р⁰₁,…,р⁰_m) m-мерного пространства R^m, координаты p⁰_i, i=1,…,m, которых удовлетворяет этому неравенству для фиксированного jϵ{1,…,n}, является замкнутым полупростанством, а множество точек Р⁰=(р⁰₁,…,p⁰_m), координаты p⁰_i, i=1,…,m, которых удовлетворяют этому неравенству для всех j=1,…,n, является пересечением конечного числа n замкнутых полупростанств и называется выпуклым замкнутым полиэдром. Так как к тому же множество оптимальных оптимальных стратегий игрока А S^O_A ограничено, поскольку оно является подмножеством симплекса всех его смешанных стратегий S_A, то S^O_A является выпуклым многогранником.

 

 

33. Доказательство теоремы о геометрической интерпретации множества стратегий игрока , оптимальных во множестве смешанных стратегий.

Следствие. Множество S^O_В оптимальных стратегий игрока В является выпуклым многогранником (политопом), содержащимся в симплексе S_В всех смешанных стратегий игрока В.

Доказательство. Для каждой оптимальной стратегии Q⁰=(q⁰₁,…,q⁰_m) игрока А справедливо неравенство Н(A_i,Q⁰)≤V, i=1,…,m, которое можно переписать следующим образом: , j=1,…,m. Множество точек Q⁰=(q⁰₁,…,q⁰_m) m-мерного пространства R^m, координаты q⁰_i, i=1,…,m, которых удовлетворяет этому неравенству для фиксированного jϵ{1,…,n}, является замкнутым полупростанством, а множество точек Q⁰=(q⁰₁,…,q⁰_m), координаты q⁰_i, i=1,…,m, которых удовлетворяют этому неравенству для всех j=1,…,n, является пересечением конечного числа n замкнутых полупростанств и называется выпуклым замкнутым полиэдром. Так как к тому же множество оптимальных оптимальных стратегий игрока B S^O_B ограничено, поскольку оно является подмножеством симплекса всех его смешанных стратегий S_B, то S^O_B является выпуклым многогранником.

 

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

Теорема. Для того чтобы V было ценой игры, а Р⁰ и Q⁰ – оптимальными стратегиями соответственно игроков А и В, другими словами, для того, чтобы {P⁰,Q⁰,V} было решеннием игры, необходимо и достаточно выполнение двойного неравенства H(P,Q⁰)≤V≤H(P⁰,Q) для любых PϵS_A и QϵS_B.

Доказательство. Необходимость. Пусть V – цена игры и P⁰, Q⁰ – оптимальные стратегии. Тогда неравенства H(P,Q^o)≤V и H(P⁰, Q)≥V справедливы и их можно записать в неравенство H(P,Q⁰)≤V≤H(P⁰,Q).

Достаточность. Пусть для некоторого числа V и некоторых стратегий Р⁰ игрока А и Q⁰ игрока В выполняется двойное неравенство (P,Q⁰)≤V≤H(P⁰,Q). Так как это неравенство верно для любых PϵS_A и QϵS_B, то в частности оно будет справедливо и для Р= P⁰, Q= Q⁰: H(P⁰,Q⁰)≤V≤H(P⁰,Q⁰), т.е. V=H(P⁰,Q⁰).

Тогда получим: H(P,Q⁰)≤ H(P⁰,Q⁰)≤H(P⁰,Q), PϵS_A и QϵS_B. max(PϵS_A)H(P,Q⁰)≤ H(P⁰,Q⁰)≤min(QϵS_B)H(P⁰,Q) или β(Q^o)≤ H(P⁰,Q⁰)≤α(Р⁰). Отсюда по определению верхней и нижней цен игры получим: V^¾=min(QϵS_B)β(Q)≤ β(Q^o)≤ H(P⁰,Q⁰)≤α(Р⁰)≤ max(PϵS_A) α(Р)=V_¾.

Из H(P⁰,Q⁰)≤V≤H(P⁰,Q⁰) и V^¾=min(QϵS_B)β(Q)≤ β(Q^o)≤ H(P⁰,Q⁰)≤α(Р⁰)≤ max(PϵS_A) α(Р)=V_¾. следует, что V – цена игры, а также справедливость равенства V= α(Р⁰)= β(Q^o)= H(P⁰,Q⁰), которое по определению оптимальных стратегий, означает, что P⁰,Q⁰ – оптимальные стратегии соответственно игроков А и В.

 

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

Теорема. Для того, чтобы V была ценой игры, а P⁰,Q⁰ – оптимальными стратегиями соответственно игроков А и В, необходимо и достаточно выполнение двойного неравенства Н(A_i,Q⁰)≤V≤ Н(Р⁰,B_j), i=1,…,m, j=1,…,n.

Доказательство. Достаточно доказать эквивалентность неравенств H(P,Q⁰)≤V≤H(P⁰,Q) и Н(A_i,Q⁰)≤V≤ Н(Р⁰,B_j).

Пусть справедливо неравенство H(P,Q⁰)≤V≤H(P⁰,Q). Так как оно имеет место для любых стратегий PϵS_A и QϵS_B, то, в частности, оно справедливо и для любых чистых стратегий P=A_i, i=1,…,m, и Q=B_j, j=1,…,n, т.е. справедливо двойное неравенство Н(A_i,Q⁰)≤V≤ Н(Р⁰,B_j).

Докажем обратное. Пусть имеет равенство Н(A_i,Q⁰)≤V≤ Н(Р⁰,B_j). Тогда из него, допустив получим: = =1, получим: , PϵS_A и QϵS_B, т.е. справедливо неравенство H(P,Q⁰)≤V≤H(P⁰,Q).

 

 

36. Доказательство в терминах седловых точек выигрыш-функции критерия того, что число - цена игры в смешанных стратегиях, а P^O и Q^O - стратегии, оптимальные во множестве смешанных стратегий соответственно игроков А и B.

Для того чтобы V было ценой игры, а Р° и Q^o — оптимальными стратегиями соответственно игроков А и В, необходимо и достаточно, чтобы (Р°, Q°) была седловой точкой выигрыш-функции Н(Р, Q) и Н(Р°, Q°) = V.

Множество номеров i ∈ {1,2,…,m}, для которых p_i> 0, называется спектром смешанной стратегии Р={р₁,р₂,…, р_m) и обозначается supp Р.

Таким образом,

suppР = {i∈{1,2,..., m):р_i>0}

Чистая стратегия A_i- называется пассивной или активной относительно смешанной оптимальной стратегии Р° = (р₁^O,р₂^O,..., р_m^O)в зависимости от того, i не ∈supp Р° или i∈supp Р°, т.е. в зависимости от того, p_i⁰ = 0 или р_i⁰> 0.

 

Следствие 1

 

1. Если k-я строка матрицы игры доминируется некоторой другой строкой, то существует оптимальная смешанная стратегия игрока А, относительно которой чистая стратегия А_k является пассивной, т.е. входит в эту смешанную стратегию с нулевой вероятностью.

2. Если к-я строка матрицы игры строго доминируется некоторой другой строкой, то относительно любой оптимальной смешанной стратегии игрока A_k-я чистая стратегия А_k является пассивной, т.е. входит в любую смешанную стратегию с нулевой вероятностью.

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

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

Следствие 1

1. Если k-я строка матрицы игры доминируется некоторой другой строкой, то существует оптимальная смешанная стратегия игрока А, относительно которой чистая стратегия А_k является пассивной, т.е. входит в эту смешанную стратегию с нулевой вероятностью.

2. Если к-я строка матрицы игры строго доминируется некоторой другой строкой, то относительно любой оптимальной смешанной стратегии игрока A_k-я чистая стратегия А_k является пассивной, т.е. входит в любую смешанную стратегию с нулевой вероятностью.

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

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

Доказательство.

Необходимость. Пусть i, k Î{1, 2}, i k, – номера чистых стратегий игрока А, а j, l Î{1, 2} ,j l, – номера чистых стратегий игрока В. Пусть – седловая точка. Тогда A_i – оптимальная стратегия игрока А.

Так как чистую оп­тимальную стратегию A_i можно рассматривать как смешанную оптимальную стратегию, в которую чистая стратегия A_i входит достоверно, т. е. с вероятностью, равной 1, а чистая стратегия A_k – cнулевой вероятностью, то стратегия А_k является пассивной, и необходимость доказана.

Отметим, что из того, что – седловая точка, аналогичным образом следует, что B_l — пассивная стратегия игрока В.

Достаточность. Пусть одна из чистых стратегий, напри­мер, стратегия А_k игрока А является пассивной. Тогда найдется оптимальная смешанная стратегия Р⁰ игрока А, в которую чистая стратегия А_k входит с нулевой вероятностью и, следовательно, чистая стратегия А_k входит с вероятностью, равной единице. Это означает, что Р⁰ = A_i, т. е. A_i – оптимальная стратегия.

Пусть Q⁰ – некоторая оптимальная стратегия игрока В, в кото­рую чистые стратегии В_j и В_l входят соответственно с вероятностями q⁰ и 1 – q⁰. Так как q⁰+( 1 – q⁰) = 1, то хотя бы одно из чисел q⁰ и 1 – q⁰ положительно.

Если q⁰ = 1и, следовательно, 1 – q⁰ = 0, то чистая стратегия В_j является активной и тогда, по теореме об активных страте­гиях

(1)

где V- цена игры.

В то же время стратегия B_j является оптималь­ной, так как в случае q⁰ = 1, имеет место равенство B_j = Q⁰, a Q⁰ – оптимальная стратегия. Из равенства с учетом оптималь­ности стратегий А_i и B_j следует, что – седловая точка.

Если q⁰ = 0 и, следовательно, 1 – q⁰ = 1, то чистая стратегия В_j является активной оптимальной стратегией и тогда из равенства

(2)

которое имеет место в силу теоремы об активных стратеги­ях, следует, что — седловая точка.

Наконец, рассмотрим случай q⁰ > 0 и 1 – q⁰ > 0. В этом случае стратегии B_j и B_l активны и тогда по теореме об активных стратегиях имеют место оба равенства .

Могут представиться две возможности:

(3)

и

(4)

1) Рассмотрим возможность .

В силу (1) и (2) для показателя эффективности стратегии А_i будем иметь

Из неравенства (3) и равенства (1) следует, что

Из (5) и (6) получаем двойное равенство

которое означает, что A_i и B_j - оптимальные стратегии. Следовательно, – седловая точка матрицы А.

2) Рассмотрим возможность .

Если , то это нера­венство вместе с неравенством будет означать, что i-я строка матрицы А строго доминируется k-й строкой и потому i-ю строчку нужно отбросить как заведомо не выгодную, что противоречит оптимальности стратегии А_i. Значит, . Но так как по (2) и (1) , то элемент наименьший в i-й строке (на самом деле равный ) и наибольший в l-м столбце, т. е. — седловая точка матрицы А.

4. Доказательство теоремы о признаке (достаточном условии) существования седловой точки матрицы игры размерности .

 

Для того чтобы у матрицы А размером 2x2 существовала седловая точка, достаточно, чтобы сумма эле­ментов главной диагонали матрицы А равнялась сумме элемен­тов ее побочной диагонали:

Доказательство.

Из равенства

Возможны случаи:

или

В случае (1) из получаем неравенство , ко­торое вместе с неравенством (1) означает, что второй столбец матрицы А доминируется ее первым столбцом. Тогда существует оптимальная смешанная стратегия игрока В, в которую чистая стратегия В ₂ входит с нулевой вероятностью (другими словами, в данном случае стратегия В ₁является оптимальной). Следовательно, стратегия В ₂пассивна, и потому в силу критерия седловой точки матрицы игры размерности в терминах пассивных стратегий у матрицы А существует седловая точка.

Если же имеет место случай (2), то из вытекает неравенство , которое вместе с (2) означает строгую юминируемость первого столбца матрицы А ее вторым столб­цом. А потому В ₁является пассивной и, следовательно, у матрицы А существует седловая точка.

 

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

 

Так как матрица А не имеет седловой точки, то нижняя цена игры в чистых стратегиях а меньше верх­ней цены игры в чистых стратегиях Поэтому решения игры в чистых стратегиях не существует и надо искать решение игры в смешанных стратегиях.

В этом случае в соответствии со следствием выполняется условие

.

Пусть — оптимальная смешанная стратегия игрока A (которая всегда существует по основной теореме матричных игр фон Неймана) и V – цена игры.

Так как матрица А не имеет седловых точек, то пассивных стратегий в игре не существует. Поэтому стратегии В ₁и В ₂активны. Тогда Записывая ле­вые части этих равенств по формуле и присоединяя к ним нормировочное условие получим систему трех ли­нейных алгебраических уравнений

с тремя неизвестными Определитель этой системы

в силу выполнимости условия . Поэтому система имеет единственное решение, которое можно найти по формулам Крамера. Для этого вычислим определители

Тогда по формулам Крамера

получаем требуемые формулы

и

 

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

 

Так как матрица А не имеет седловой точки, то нижняя цена игры в чистых стратегиях а меньше верх­ней цены игры в чистых стратегиях Поэтому решения игры в чистых стратегиях не существует и надо искать решение игры в смешанных стратегиях.

В этом случае в соответствии со следствием выполняется условие

.