Теорема о существовании показателей эффективности и неэффективности смешанных стратегий в антагонистической игре.

Для каждой смешаннойстратегии игрока существует ;(4.1)

Для каждой смешаннойстратегии игрока существует . (4.2)

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

Для проведения доказательства введём понятие симплекса

Стандартным n-симплексом называется подмножество пространства действительных чисел, определяемое как

.

Его вершинами являются точки:

,

,

…

.

Сначала покажем, что симплекс является ограниченным замкнутым множеством, т.е. компактом.

Рассмотрим симплекс

в евклидовом пространстве . Так как норма вектора в пространстве определяется следующим образом:

,то для любой точки симплекса справедливо неравенство

,означающее ограниченность симплекса .

Пусть последовательность точек

, ,

сходится к точке при . Так как сходимость в является покоординатной, то означает, что , . Поскольку , то и .

Так как для каждого k, то

.

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

Аналогично и симплекс – компакт в пространстве .

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

,

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

.

Аналогично доказывается и существование (4.2).

Теорема доказана.

13. Теорема о существовании нижней и верхней цен игры в смешанных стратегиях.

Нижней ценой (или максимином)матричной игры в смешанных стратегиях называется величина

Верхней ценой (или минимаксом)матричной игры в смешанных стратегиях называется величина

Докажем существование нижней и верхней цен в смешанных стратегиях, т.е. достижимость максимума в (1) и минимума в (2). Необходимость этого доказательства возникает по причине бесконечности множеств S_Aв (1) и S_Bв (2).

Сначала докажем вспомогательные предложения.

Лемма 1.Соответствие, сопоставляющее каждой смешанной стратегии Р S_Aигрока А показатель ее эффективности α(Р),является числовой функцией, определенной на симплексе S_A,аналитическое выражение которой задается равенством

Аналогично, соответствиеβ(Q),задаваемое формулой

является числовой функцией, определенной на симплексеS_Bи ставящей в соответствие каждой смешанной стратегииQ S_Bигрока В показатель ее неэффективностиβ(Q).

Доказательство. Для каждой смешанной стратегии P S_Aв силу теоремы 1 - для каждой смешанной (в частности, чистой) стратегии Р S_Aигрока А существует (достигается)

для каждой смешанной (в частности, чистой) стратегии Q S_Bигрока В существует (достигается)

существует число которое по определению минимума является единственным. Следовательно, α(Р)- числовая функция векторного аргумента Р, определенная на симплексе S_A.

Аналогичной аргументацией обосновывается, что

является числовой функцией векторного аргумента Q, определенного на симплексе S_B.

Лемма 2.Функцииα(Р) иβ(Q)непрерывны в своих областях определения S_AиS_B.

Оставим без доказательства. Теперь докажем следующую теорему.

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

Аналогичным образом обосновывается существование и верхней цены игры в смешанных стратегиях:

Смешанная стратегия P^О S_A,максимизирующая показатель эффективности α(Р) (существование которой доказано в теореме 2), назовем максиминной смешанной стратегией игрока А. Таким образом, нижняя цена игры есть (см. 1) показатель эффективности максиминной смешанной стратегии P^О:

В частном случае P^О =А_i0 является максиминной чистой стратегией игрока A.

Аналогично, смешанная стратегия Q^О S_B(существование которой доказано в теореме 2), минимизирующая показатель неэффективности β(Q), назовем минимаксной смешанной стратегией игрока В.Показатель неэффективности минимаксной смешанной стратегии Q^Оравен верхней цене игры (см. 2)):

Если Q^О=B_j0, то B_j0является минимаксной чистой стратегией.

14.Теорема о соотношении нижней и верхней цен игры в чистых и смешанных стратегиях.

Теорема.Нижняя цена игрыαи верхняя цена игрыβв чистых стратегиях, нижняя цена игры и верхняя цена игры в смешанных стратегиях удовлетворяют следующим неравенствам:

Доказательство. Начнем доказательство с левого неравенства (1).

По определению

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

Здесь правая часть не зависит от Р и потому это неравенство остается верным и для Р = A_i, i= 1, ..., m:

Так как полученное неравенство справедливо для всехi= 1, ..., m, то оно будет справедливым в частности для того номера i,который максимизирует показатель эффективности α_i:

Итак, первое из неравенств (1) доказано.

Докажем второе неравенство ≤ в (1). Для любых Р S_Aи Q S_Bпо

и

имеем:

Соотношение (2) означает, что в любой ситуации в смешанных стратегиях (Р, Q)выигрыш H(P, Q)игрока A не меньше показателя эффективности α(P)его стратегии Р и не больше показателя неэффективности стратегии Qпротивника В.

Так как (2) справедливо для любых Р S_Aи Q S_B, то из него следует, что

Докажем последнее (правое) из неравенств (1). В силу определения

верхней цены игры в смешанных стратегиях

В частности, это неравенство справедливо и для чистых стратегий Q = B_j,j = 1, ..., п ,игрока В

и, следовательно, неравенство остается в силе и для того номера j,который минимизирует показатель неэффективности β(B_j) стратегии В_j, т.е.

Итак, (1) доказано.

15. Основная теорема матричных игр Джона фон Неймана и седловая точка функции

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

Применение оптимальной стратегии позволяет получить выиг­рыш, равный цене игры: .

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

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

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

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

16.Аналитическое решение игры 2×2 в смешанных стратегиях.

Рассмотрим игру 2х2.

Если такая игра имеет седловую точку, то оптимальное решение – это пара чистых стратегий, соответствующих этой точке. Для игры, в которой отсутствует седловая точка оптимальное решение игры существует и определяется парой смешанных стратегий (x₁^*,x^*₂) и (у₁^*,у₂^*).

(!!!это заменяем на следующее обозначение смешанных стратегий P⁰ =(p₁⁰;p₂⁰) andQ=(q₁⁰;q₂⁰), соответственно дальше меняем сами)

2) Для того, чтобы их найти, воспользуемся теоремой об активных стратегиях.

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

3) Пусть игра задана матрицей

Средний выигрыш первого игрока, если он использует оптимальную смешанную стратегию х^*=(x₁^*,x^*₂), а второй игрок – чистую стратегию, соответ.первому столбцу платежной матрицы, равен цене игры v:

a₁₁x₁^*+a₂₁x^*₂ = v.

Тот же средний выигрыш получает первый игрок, если второй игрок применяет стратегию, соответ.второму столбцу платежной матрицы, т.е. a₁₂x₁^*+a₂₂x^*₂ = v. Учитывая, что x₁^*+ x^*₂=1, получаем систему уравнений для определения оптимальной стратегии первого игрока и цены игры:

a₁₁ x₁^*+a₂₁ x^*₂ = v.

a₁₂ x₁^*+a₂₂ x^*₂ = v

x₁^*+ x^*₂=1

Решая эту систему, получим оптимальную стратегию

x₁^*=

x₂^*=

и цену игры v =

4) Для второго игрока

В=-А^Т=

Применяя теорему об активных стратегиях при отыскании оптимальной смешанной стратегии второго игрока, получаем, что при любой чистой стратегии первого игрока средний проигрыш второго игрока равен v, т.е. a₁₁ у₁^*+ a₁₂ у₂^*=v.

Тогда оптимальная стратегия второго игрока определяется по формулам:

у₁^*=

у₂^*=

v’=-v

17. Геометрический метод нахождения цены игры 2×2 и оптимальных стратегий игрока A.

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

1. Берем горизонтальный отрезок [0,1].

2. В концах отрезка [0,1] проводим к нему 2 перпендикуляра: левый соответ. стратегии А₁ и правый, соотв.стратегии А₂.

3. На левом перпендикуляре от точки 0 его пересечения с отрезком [0,1] откладываем (как на вертикальной числовой оси) элементы a₁₁ и a₁₂ первой строки матрицы А

4. На правом перпендикуляре от точки 1 его пересечения с отрезком [0,1] (как на вертикальной числовой оси) элементы a₂₁ и a₂₂ второй строки матрицы А

5. Соединяем точки, изображающие элементы с одинаковыми вторыми индексами, т.е. эл-ты, стоящие в одном и том же столбце матрицы А: a₁₁ с a₂₁ и a₁₂ с a_22. В результате получаем отрезки a₁₁a₂₁ и a₁₂a_22.

6. Если отрезки a₁₁a₂₁ и a₁₂a₂₂ не убывающие, то стратегия А₂ доминирует стратегию А₁. Если отрезки a₁₁a₂₁ и a₁₂a₂₂ возрастающие, то стратегия А₂ строго доминирует А_1.

7. Если отрезок a₁₁a₂₁ лежит не ниже отрезка a₁₂a₂₂, то стратегия В₂ доминирует стратегию В₁. Если отрезок a₁₁a₂₁ лежит выше отрезка a₁₂a₂₂ и не пересекается с ним, то стратегия В₂ строго доминирует стратегию В₁

8. Находим нижнюю огибающую отрезков a₁₁a₂₁ и a₁₂a₂₂

9. Находим наивысшие точки нижней огибающей

10. Проектируем их ортогонально на горизонтальный отрезок [0,1]

11. Полученные проекции р⁰ определяют оптимальные стратегии Р⁰=(1-р₀,р₀) игрока А.

12. Ордината наивысшей точки огибающей равна цене игры V

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

14. Нижний из двух верхних концов отрезков a₁₁a₂₁ и a₁₂a₂₂ есть верхняя цена игры в чистых стратегиях

15. Если элемент является нижним на перпендикуляре, где он лежит, и верхним концом отрезка a₁₁a₂₁ или a₁₂a₂₂ , на котором он лежит, то этот эл-т является седловой точкой. В этом случае чистая стратегия игрока В, номер которой совпадает со вторым индексом седловой точки, является оптимальной.

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

18. Геометрический метод нахождения цены игры 2×2 и оптимальных стратегий игрока B.

1. Берем горизонтальный отрезок [0,1].

2.В концах отрезка [0,1] проводим к нему 2 перпендикуляра: левый и правый

3.На левом перпендикуляре вертикальной числовой оси от точки 0 его пересечения с отрезком [0,1] откладываем все элементы матрицы А, за исключением а₂₂

4.На правом перпендикуляре от точки 1 его пересечения с отрезком [0,1] откладываем (как на вертикальной числовой оси) все эл-ты матрицы А, за исключением а₁₁

5.Каждый элемент на левом перпендикуляре соединим отрезком с каждым элементом на правом перпендикуляре, отличающимся от него только одним индексом. В результате получим отрезки a₁₁a₂₁ , a₁₂a₂₂, a₁₁a₁₂ и a₂₁a₂₂

6.Находим нижнюю огибающую отрезов a₁₁a₂₁ и a₁₂a_22.

7. Находим аивысшую точку N нижней огибающей.

8. Находим абсциссу р⁰ наивысшей точки нижней огибающей.

9. Смешанная стратегия Р⁰=(1-р⁰, р⁰) является оптимальной стратегией игрока А.

10. Находим верхнюю огибающую отрезков a₁₁a₁₂ и a₂₁a₂₂.

11. Находим наинизшую точку М верхней огибающей.

12. Находим абсциссу q⁰ наинизшей точки верхней огибающей.

13. Смешанная стратегия Q⁰=(1-q⁰,q⁰) является оптимальной стратегией игрока В.

14. Ордината наивысшей точки нижней огибающей равна ординате наинизшей точки верхней огибающей и представляет собой цену игры V.

15. Т.о. найдено геометрическими средствами решение игры {P⁰,Q⁰,V}

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

17. Нижний из концов верхней огибающей (лежащий на перпендикулярах) есть верхняя цена игры в чистых стратегиях

19.Геометрический метод нахождения цены игры 2×n и оптимальных стратегий игрока A.

20. Геометрический метод нахождения цены игры m×2 и оптимальных стратегий игрока B.

(!!! Помним про обозначения вероятностей чистых стратегий через p,q)

Решение игр размера 2xn или nx2 допускает наглядную геометрическую интерпретацию. Такие игры можно решать графически.

1)Дадим геометрическую интерпретацию игры

На плоскости XY по оси абсцисс отложим единичный отрезок A₁A₂ (рисунок 5.1). Каждой точке отрезка поставим в соответствие некоторую смешанную стратегию U = (u₁, u₂). Причем расстояние от некоторой промежуточной точки U до правого конца этого отрезка – это вероятность u₁ выбора стратегии A₁, расстояние до левого конца - вероятность u₂ выбора стратегии A₂. Точка А₁ соответствует чистой стратегии А₁, точка А₂ – чистой стратегии А₂.

В точках А₁ и А₂ восстановим перпендикуляры и будем откладывать на них выигрыши игроков. На первом перпендикуляре (совпадающем с осью OY) покажем выигрыш игрока А при использовании стратегии А₁, на втором – при использовании стратегии A₂. Если игрок А применяет стратегию A₁, то его выигрыш при стратегии B₁ игрока B равен 2, а при стратегии B₂ он равен 5. Числам 2 и 5 на оси OY соответствуют точки B₁ и B₂. Аналогично на втором перпендикуляре найдем точки B^'₁ и B^'₂ (выигрыши 6 и 4).

Соединяя между собой точки B₁ и B^'₁, B₂ и B^'₂, получим две прямые, расстояние от которых до оси OX определяет средний выигрыш при любом сочетании соответствующих стратегий.

Например, расстояние от любой точки отрезка B₁B^'₁ до оси OX определяет средний выигрыш игрока A при любом сочетании стратегий A₁ и A₂ (с вероятностями u₁ и u₂) и стратегии B₁ игрока B.

Рисунок 5.1 – Геометрическая интерпретация игры примера 5.3 (нахождение оптимальной стратегии игрока А)

Ординаты точек, принадлежащих ломаной B₁MB^'₂ определяют минимальный выигрыш игрока A при использовании им любых смешанных стратегий. Эта минимальная величина является наибольшей в точке М, следовательно, этой точке соответствует оптимальная стратегия U^* = ( , ), а ее ордината равна цене игры v.

Координаты точки M найдем, как координаты точки пересечения прямых B₁B^'₁ и B₂B^'₂.

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

Составим уравнения прямых для нашей задачи.

Прямая B₁B^'₁:

= или y = 4x + 2.

Прямая B₂B^'₂:

= или y = -x + 5.

Получим систему:

y = 4x + 2, y = -x + 5.

Решим ее:

4x + 2 = -x + 5, 5x = 3, x = 3/5, y = -3/5 + 5 = 22/5.

Таким образом, U^* = (2/5, 3/5), v = 22/5.

Аналогично решается задача по нахождению оптимальной стратегии игрока B. Разница состоит в том, что находится точка, сводящая к минимуму средний проигрыш, поэтому на рисунке 5.2 рассматривается ломаная A₂MA^'₁.

Рисунок 5.2 – Геометрическая интерпретация игры примера 5.3 (нахождение оптимальной стратегии игрока B)

Найдем координаты точки М.

Прямая A₁A^'₁:

= , откуда y = 3x + 2.

Прямая A₂A^'₂:

= , откуда y = -2x + 6,

3x + 2 = -2x + 6, 5x = 4, x = 4/5.

Таким образом, = 1/5, = 4/5.