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

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

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

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

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

5. Каждую пару точек, изображающих элементы a_i1 a_i2 i=1,…,m, стоящие в i ой строке матрицы А, соединяем отрезком a_i1 a_i2. Таким образом будут построены m отрезков, представляющих собой графики m линейных функций

H(A_i,Q)=(a_i2-a_i1)q+a_i1, q принадлежит [0.1] i = 1,…,m

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

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

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

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

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

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

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

4. Доминирование смешанных стратегий для игрока a.

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

Пусть имеем игру с матрицей m*n

рассмотрим две произвольные стратегии А:

P’= (p’_I, p’_2,…, p’_m)

P’’=(p’’_I, p’’_2,…, p’’_m)

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

Стратегия Р’’доминирует стратегию P’ если

∑p’_ia_i1≤∑p’’_ia_i1

∑p’_ia_in≤∑p’’_ia_in

Или ∑p’_ia_ij≤∑p’’_ia_ij j=1,2,…n.

Поиск доминирующих стратегий:

выпуклая линейная комбинация чистых стратегий игрока A:

λ₁А₁+ λ₂А₂+…+ λ_kА_k+…+ λ_mА_m

∑ λ_i=1 λ_i≥0

λ_i аналоги вероятностей р_i система ограничений:

λ_k=0

λ₁а_1j+ λ₂a_2j+…+λ_ma_mj≥a_kj

∑ λ_i=1

Стратегия P=(p1= λ₁; p2= λ₂; p_k=0;…;p_m=λ_m )

признаётся доминирующей стратегию A_k

4. Доминирование смешанных стратегий для игрока в.

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

Пусть имеем игру с матрицей m*n

рассмотрим две произвольные стратегии B:

Q’= (q’_I, q’_2,…, q’_m)

Q’’=(q’’_I, q’’_2,…, q’’_m)

Стратегия Q’’доминирует стратегию Q’ если

∑q’_ja_1j≥∑q’’_ja_1j (средний проигрыш второго игрока в ответ на реализацию игроком А своей 1 стратегии )

∑q’_ja_2j≥∑q’’_ja_2j

Или ∑q’_ja_ij≥∑q’’_ja_ij j=1,2,…n.

Доминирующая стратегия приносит игроку В проигрыш не больше, чем другая любая.

Поиск доминирующих стратегий:

выпуклая линейная комбинация чистых стратегий игрока B:

μ₁B₁+ μ₂B₂+…+ μ_kB_k+…+ λ_nB_n

∑ μ_j=1 μ_j ≥0

μ_j аналоги вероятностей q_j система ограничений:

μ_k=0

μ₁а_i1+ μ₂a_i2+…+ μ_na_in≤a_ik

∑ μ_j =1

Стратегия Q=(q1= μ₁; q2= μ₂; q_k=0;…;q_n= μ_n )

признаётся доминирующей стратегию B_k