Т об аналит решении игры 2x2 без седл. Точки в смеш стр-ях и её следствия Для симметир и двоякосимметр мат-цы.

Т: Пусть мат-ца А размером 2x2 не имеет седл. точки. Тогда каждый из иг-ов А и В обладает единственной опт.смеш. стратегией соответственно , где , (1), , (2), а цена игры в смеш.стр-яхV определяется формулой: (3)

Док-во. Так как мат-ца не имеет седл. точки, то нижняя цена игры в чистыхстр-яхa меньше верхней цены игры в чистых стр-яхb: решения игры в чистых стр-ях не существует и надо искать решение игры в смеш.стр-ях.

В этом случае выполняется условие (*).Пусть , — оптим смешанные стр-иииг-ов А и В и V — цена игры. Тогда по определению опт.стр-ий . Т.к. мат-ца А не имеет седл. точек, то в силу Т о сущ-ииседл. точки в терминах пассивных стр-ий, пассивных стр-ий в игре не существует. Поэтому стр-ии В₁ и В₂ активны. Тогда , j= 1,2. Записывая ле­вые части этих рав-тв по формуле и присоединяя к ним условие получим систему трех ли­нейных алгебраических уравнений:

Найдем решение системы по ф-лам крамера и имеет единственное решение, т.к. определитель системы ≠0 (). Определитель этой системы:

, , . Тогда: , , . Откуда и получаем требуемые ф-лы (1) и (3). Док-ва формул (2) аналогичные.

 

38. Геометрический метод нахождения цены игры 2 2 и опт. стр-ий иг-ка А

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

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

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

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

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

Прямые на графике:

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

Если отрезки a ₁₁ a ₁₂ и a ₂₁ a ₂₂возрастающие: , то стр. A ₂ строго доминирует стр-ию A ₁

7. Если отрезок a ₁₁ a ₂₁ лежит не ниже отрезка a ₁₂ a ₂₂, то стр. B ₂ доминирует стр-ию B ₁

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

8. Пок-льэфф-тисмеш.стр-ииР=(1-р,p)

- это ф-ия от р, являющаяся нижней огибающей ф-ии Н(Р, В₁) и Н(Р, В₂) (отрезков a ₁₁ a ₂₁ и a ₁₂ a ₂₂ соответственно).

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

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

11. Полученные проекции определяют опт.стр-ии иг-ка А.

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

= _.

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

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

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

 

39. Геометрический метод нахождения цены игры 2´2 и опт.стр-ийиг-ка В.

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

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

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

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

Замечание к пунктам 1, 3, 4. Масштабы на правом и левом перпендикулярах одинаковые, но не обязательно совпадают с масштабом горизонтального отрезка [0,1].

5. Соединяем а ₁₁ с а ₁₂, а ₂₁ с а ₂₂.

6. Если отрезки а ₁₁ а ₁₂, а ₂₁ а ₂₂ — неубывающие (имеют неотрицательный наклон), то стр. B ₁доминирует стр-ию B ₂. Если отрезки а ₁₁ а ₁₂, а ₂₁ а ₂₂ — возрастающие (имеют положительный наклон), то стр. B ₁строго доминирует стр-ию B ₂.

7. Если отрезки а ₁₁ а ₁₂, а ₂₁ а ₂₂ — невозрастающие (имеют неположительный наклон), то стр. B ₂до минирует стр-ию B ₁. Если отрезки а ₁₁ а ₁₂, а ₂₁ а ₂₂ — убывающие (имеют отрицательный наклон), то стр. B ₁ строго доминирует стр-ию B ₂.

8. Если отрезок лежит не ниже отрезка , то стр. доминирует стр-ию . Если отрезок — выше отрезка , то стр. строго доминирует стр-ию .

9. Находим (выделяем) верхнюю огибающую отрезков а ₁₁ а ₁₂, а ₂₁ а ₂₂.

10. Наверхней огибающей находим минимальную точку.

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

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

13. Верхний из нижних концов отрезков а ₁₁ а ₁₂, а ₂₁ а ₂₂ есть нижняя цена игры в чистых стр-ях α.

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

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

40. Геометрический метод нахождения цены игры 2´n и опт.стр-ийиг-ка А.

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

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

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

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

Масштабы на левом и правом перпендикулярах должны быть одинаковыми, не обязательно совпадающими с масштабом горизонтального отрезка [0,1].

5. Каждую пару точек, изображающих элементы а _{1 j} и а _{2 j}, стоящие в j -м столбце мат-цы А, соединяем отрезком а _{1 j}а _{2 j}. Т.о., будут построены n отрезков, представляющих собой графики n линейных функций p [0,1], j =1,..., п. (1. 1)

6. Если все отрезки а _{1 j}а _{2 j}, j =1,..., п, — неубывающие (имеют неотрицательный наклон), то стр. А ₂доминирует стр-ию А ₁.

Если все отрезки а _{1 j}а _{2 j}, j =1,..., п, возрастающие (имеют положительный наклон): а _{1 j}а _{2 j}, j =1,..., п, то стр. А ₂строго до минирует стр-ию A ₁.

7. Если все отрезки а _{1 j}а _{2 j}, j =1,..., п, невозрастающие (имеют неположительный наклон), то стр. А ₂ до минирует стр-ию A ₁.

Если все отрезки а _{1 j}а _{2 j}, j =1,..., п, убывающие (имеют отрицательный наклон), то стр. A ₁ строго до минирует стр-ию А ₂.

8. Если отрезок лежит не ниже отрезка , j ₁≠ j ₂, j ₁, j ₂ {1, …, n },то стр. доминирует стр-ию .Если отрезок лежит выше отрезка , j ₁≠ j ₂, j ₁, j ₂ {1, …, n }, то стр. строго доминирует стр-ию .

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

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

11. Абсцисса p ⁰ этой точки (удовлетворяющая рав-тву (2)) является вероятностью выбора игроком А чистой стр-ии А ₂ в опт.смеш.стр-ии P ⁰=(1 -p ⁰, p ⁰ ).

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

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

14. Нижний из верхних концов отрезков а _{1 j}а _{2 j}, j =1,..., п, есть верхняя цена игры в чистых стр-ях β.

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

41. Т об аналитическом методе нахождения цены игры 2´n и опт.стр-ийиг-ка А.

Если через макс. точку N нижней огибающей отрезков а _{1 j}а _{2 j}, j =1,..., п, порождаемых чистыми стр.ми B_j, j =1,..., п, иг-ка В, проходят два каких-либо отрезка и , j ₁≠ j ₂, j ₁, j ₂ {1, …, n }, то абсцисса точки N (1. 2) и, следовательно, (1. 3) а цена игры (1. 4)

42. Т об аналитическом методе нахождения цены игры 2´n и опт.стр-ийиг-ка В.

Пусть через макс. точку N нижней огибающей а _{1 j}а _{2 j}, j =1,..., п, порождаемых чистыми стр.ми B_j, j =1,..., п, иг-ка В, проходят два каких-либо отрезка и , j ₁≠ j ₂, j ₁, j ₂ {1, …, n }. Для того чтобы смеш. стр. иг-ка B, где (1.10), (1.11), (1.12) была опт.⇔чтобы отрезки и имели разные наклоны.

Док-во. Цена игры Т.к. цена игры V представляет собой ординату точки M, то для вычисления V достаточно в правую часть одного из рав-тв или подставить . Подставляя в правую часть рав-ва , получим Необходимость. Пусть смеш. стр. иг-ка В, в которой вероятности , j =1,..., n, определяются ф-лами (1.10), (1.11) и (1.12), является опт..

Нам надо доказать, что отрезки и имеютразные наклоны. Предположим противное: эти отрезки имеют одинаковые наклоны.

Так как уравнениями отрезков и являются соответственно уравнения (1.8) и (1.9), то угловые коэффициенты этих отрезков соответственно равны (1.13), (1.14)

Т.к. (по предположению) отрезки и имеют одинаковые наклоны, то и либо оба положительны, либо оба отрицательны, либо оба равны нулю.

+следствие

43. Геометрический метод нахождения цены игры m´2 и опт. стр-ийиг-ка В

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

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

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

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

5. Каждую пару точек, изображающих элементы а_{i 1} и а_{i 2}, стоящие в i -й строке мат-цы А, соединяем отрезком а_{i 1} а_{i 2}. Т.о., будут построены m отрезков, представляющих собой графики m линейных функций q [0,1], i =1,..., m. (2. 5)

6. Если все отрезки а_{i 1} а_{i 2}, i =1,..., m, — неубывающие (имеют неотрицательный наклон), то стр. B ₁доминирует стр-ию B ₂.Если все отрезки а_{i 1} а_{i 2}, i =1,..., m, — возрастающие (имеют положительный наклон), то стр. B ₁строго до минирует стр-ию B ₂.

7. Если все отрезки а_{i 1} а_{i 2}, i =1,..., m, — невозрастающие (имеют неположительный наклон), то стр. B ₂ до минирует стр-ию B ₁.Если все отрезки а_{i 1} а_{i 2}, i =1,..., m, — убывающие (имеют отрицательный наклон), то стр. B ₁ строго до минирует стр-ию B ₂.

8. Если отрезок лежит не ниже отрезка , i ₁≠ i ₂, i ₁, i ₂ {1, …, m },то стр. доминирует стр-ию .Если отрезок лежит выше отрезка , i ₁≠ i ₂, i ₁, i ₂ {1, …, m }, то стр. строго доминирует стр-ию .Находим (выделяем) верхнюю огибающую (2.1) семейства отрезков (2.4), которая в общем случае будет представлять собой выпуклую вниз ломаную, а, в частности, может быть и отрезком.

9. Наверхней огибающей находим минимальную (низшую) точку (или точки).

10. Абсцисса q ⁰ этой точки (удовлетворяющая рав-тву (2.2)) является вероятностью выбора игроком B чистой стр-ии B ₂ в опт.смеш.стр-ии Q ⁰=(1 -q ⁰, q ⁰ ).

11. Ордината низшей точки верхней огибающей является ценой игры V (см.(2.3)).

12. Верхний из нижних концов отрезков а_{i 1} а_{i 2}, есть нижняя цена игры в чистых стр-ях α.

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

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

44. Т об аналитическом методе нахождения цены игры и опт.стр-ийиг-ка В. (надо А)

Т 1

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

 

Т 2

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

Для того чтобы смешанная страт-я Р⁰=(р⁰₁, р⁰_m) игрока А, где:

p⁰_i ,

 

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

 

 

45.Принцип решения игры методом Шепли-Сноу. Т Шепли-Сноу о крайних опт.стр-ях

Крайняя точка — это такая точка Р выпуклого мн-ва S, которой нельзя подобрать такой интервал, который бы содержал эту точку Р и сам содержался бы в S. Мн-тво крайних точек мн-ва S обозначают . Например, мн-тво крайних точек выпуклого многогранника есть мн-тво его вершин, поэтому крайние точки выпуклого многогранника называют также угловыми.

Мн-тво опт. стр-ийиг-ка А (B) является выпуклым многогранником (политопом), содержащимся в симплексе ()всех смеш.стр-ийиг-ка (B).

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

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

Отметим, что метод Шепли-Сноу — точный метод решения.

Т Шепли-Сноу

Пусть и - крайние опт.стр-ии соответственно иг-ов А и B в игре с ценой игры , т.е. и . Тогда номеров строк мат-цы , номеров столбцов мат-цы , Крайняя опт. стр. удовлетворяет системе уравнений:

, а крайняя опт.стр. удовлетворяет системе уравнений

. При этом, если , то мат-ца системы для и транспонированная мат-ца системы для невырождены, т.е. их определители не равны нулю.