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

 

Если матрица игры А размером 2x2 сим­метрическая, т. е. и не имеет седловой точки, то чис­тые стратегии А₁, В₁ и А₂, В₂ входят в соответствующие оп­тимальные смешанные стратегии и соответственно с вероятностями: .

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

.

 

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

1. Берем горизонтальный отрезок [0, 1], на котором для определенности положено а ₂₂ < а ₁₁ < а ₂₁ < а ₁₂.

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

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

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

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

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

Если отрезки а ₁₁ а ₂₁и а ₁₂ а ₂₂ возрастающие: а ₁₁ а ₂₁­и а ₁₂ а ₂₂ ­_, то стра­тегия А ₂ строго доминирует стратегию А ₁.

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

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

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

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

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

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

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

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

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

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

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

 

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

а ₂₂ < а ₁₁ < а ₂₁ < а ₁₂

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

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

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

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

6. Если отрезки а ₁₁ а ₁₂и а ₂₁ а ₂₂ невозрастающие: а ₁₁ а ₁₂и а ₂₁ а ₂₂ то стратегия В ₂доминирует стратегию В ₁.

Если отрезки а ₁₁ а ₁₂и а ₂₁ а ₂₂ убывающие: а ₁₁ а ₁₂ ¯ и а ₂₁ а ₂₂ ¯, то страте­гия В ₂строго доминирует стратегию В ₁.

7. Если отрезок а ₁₁ а ₁₂лежит не ниже отрезка а ₂₁ а ₂₂ то стратегия А ₁ доминирует стратегию А ₂.

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

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

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

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

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

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

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

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

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

 

10. Геометрический метод нахождения оптимальных смешанных стратегий игрока и цены игры в смешанных стратегиях в игре размерности .

 

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

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

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

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

5. Каждую пару точек, изображающих элементы а _1j и a _2j, j=1,2,..., п, стоящие j-м столбце матрицы A, соединяем отрезком а _1j a _2j. Таким образом, будут построены п отрезков, представляющих собой графики и линейных функций

где Р= (1 — р, р) — смешанная стратегия игрока А.

6. Если все отрезки а _1j a _2j, j=1,2,..., п, неубывающие (имеют неот­рицательный наклон), то стратегия А ₂доминирует стратегию А ₁.

Если все отрезки а _1j a _2j, j=1,2,..., п, возрастающие (имеют поло­жительный наклон), то стратегия А ₂ строго доминирует стратегию А ₁.

7. Если все отрезки а _1j a _2j, j=1,2,..., п, невозрастающие (имеют не­положительный наклон), то страте­гия А ₁доминирует стратегию А ₂.

Если все отрезки а _1j a _2j, j=1,2,..., п, убывающие (имеют отрица­тельный наклон), то стратегия А ₁строго доминирует стратегию А ₂.

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

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

11. Абсцисса р° этой точки является вероятностью выбора игро­ком А чистой стратегии А₂ в оптимальной смешанной стратегии Р° = (1 – р ⁰, р ⁰)

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

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

14. Нижний из верхних концов отрезков а _1j a _2j, j=1,2,..., п, есть верхняя цена игры в чистых стратегиях b.

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

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

На рисунке из п отрезков а _1j a _2j, j=1,2,..., п, указаны три, которые принимают участие в конструировании нижней огибающей, выделенной жирной линией; Н — наивысшая точка этой огибающей; р° — абсцисса точки N, следовательно, Р° = (1 — р°, р°) — оптимальная смешанная стратегия игрока А, цена игры К равна ординате точки N; нижняя цена игры в чистых стратегиях a = a_2j2;верхняя цена игры в чистых стратегиях b = a_2j1; на рисунке видно, что a < V< b.

 

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

 

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

Уравнения отрезков и имеют следующий вид:

Так как эти отрезки пересекаются в точке N, то абсцисса р ⁰ этой точки является решением уравнения

откуда получаем формулу

.

Поскольку цена игры V представляет собой ординату точки N, то для вычисления V достаточно в правую часть одного из ра­венств

подставить вместо р абсциссу р ⁰, выра­женную формулой

.

Подставляя р = р⁰ в правую часть ра­венства , получим

 

12. Теорема о необходимом и достаточном условии оптимальности смешанной стратегии игрока в игре размерности .

 

Пусть через максимальную точку N ниж­ней огибающей отрезков , j = 1,..., п, порождаемых чисты­ми стратегиями B_j, j =1,..., n, игрока В, проходят два каких-либо отрезка u

Для того чтобы смешанная стратегия Q° игрока B, где

была оптимальной, необходимо и достаточно, чтобы отрезки u имели разные наклоны.