ТОП 10:

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



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

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

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

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

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

 

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

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

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

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

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

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

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

6.Если отрезкиa11a12 и a21a22неубывающие: , то стр.A2 доминирует стр-июA1

Если отрезкиa11a12 и a21a22возрастающие: , то стр.A2 строго доминирует стр-июA1

7.Если отрезокa11a21 лежит не ниже отрезкаa12a22, то стр.B2 доминирует стр-июB1

Если отрезокa11a21 лежит выше отрезкаa12a22, не пересекается с ним, то стр.B2 строго доминирует стр-июB1

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

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

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

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

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

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

= .

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

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

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

 

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

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

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

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

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

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

5. Соединяем а11 с а12, а21 с а22.

6. Если отрезки а11а12, а21а22 — неубывающие (имеют неотрицательный наклон), то стр.B1доминирует стр-июB2. Если отрезки а11а12, а21а22 — возрастающие (имеют положительный наклон), то стр.B1строго доминирует стр-июB2.

7. Если отрезки а11а12, а21а22 — невозрастающие (имеют неположительный наклон), то стр.B2до минирует стр-июB1. Если отрезки а11а12, а21а22 — убывающие (имеют отрицательный наклон), то стр.B1 строго доминирует стр-июB2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

Пусть через макс. точку N нижней огибающейа1jа2j, j=1,..., п, порождаемых чистыми стр.миBj,j=1,..., п, иг-каВ, проходят два каких-либо отрезка и , j1j2, j1, j2 {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. Каждую пару точек, изображающих элементы аi1 и аi2, стоящие в i-й строке мат-цыА, соединяем отрезком аi1аi2. Т.о., будут построены m отрезков, представляющих собой графики m линейных функций q [0,1], i=1,..., m. (2. 5)

6. Если все отрезки аi1аi2, i=1,..., m, — неубывающие (имеют неотрицательный наклон), то стр.B1доминирует стр-июB2.Если все отрезки аi1аi2, i=1,..., m, — возрастающие (имеют положительный наклон), то стр.B1строго до минирует стр-июB2.

7. Если все отрезки аi1аi2, i=1,..., m, — невозрастающие (имеют неположительный наклон), то стр.B2 до минирует стр-июB1.Если все отрезки аi1аi2, i=1,..., m, — убывающие (имеют отрицательный наклон), то стр.B1 строго до минирует стр-июB2.

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

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

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

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

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

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

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

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

Т 1

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

 

Т 2

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

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

p0i ,

 

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


 

 

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

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

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

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

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

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

Т Шепли-Сноу

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

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

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







Последнее изменение этой страницы: 2016-09-05; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.232.188.251 (0.013 с.)