Нижняя и верхняя цены игры в смешанных стратегиях.

Игру, определяемую матрицей А, имеющей m строк и n столбцов, называют конечной игрой размерности mxn.

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

Величина -гарантированный выигрыш игрока А – нижняя цена игры.

Стратегия_, обеспечивающая получение называется максиминной.

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

Величина называется верхней ценой игры или минимаксом, а соответствующая ему стратегия игрока (столбец) – минимаксной.

Нижняя цена игры всегда не превосходит верхней цены игры.

Если , то число v называется ценой игры. Игра, для которой , называется игрой с седловой точкой.

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

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

Так как функция α (P) по лемме H (P,Q): (P,Q)Î x ,

где P= , Q=() непрерывна на компакте , то она достигает на этом множестве своего максимума, т.е. существует нижняя цена игры в смешанных стратегиях: =max(PÎ α(P)

Аналогичным образом обосновывается существование верхней цены игры в смешанных стратегиях =min(QÎ β(Q)

 

27. Понятие стратегии, оптимальной во множестве смешанных стратегий. Основная теорема матричных игр Дж.Фон Неймана.
1) Смешанная стратегия игрока - это полный набор применения его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Условия применения смешанных стратегий:

• игра без седловой точки;

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

• игра многократно повторяется в сходных условиях;

• при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;

• допускается осреднение результатов игр.

2) Для матричной игры с любой матрицей А величины

равны между собой,

Более того, существует хотя бы одна ситуация в смешанных стратегиях (Р ⁰, Q ⁰), для которой выполняется соотношение

Иными словами, любая матричная игра имеет решение в смешанных стратегиях.

 

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

В определении равновесной ситуации в чистых стратегиях (, учитывая, что( =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.