Свойства оптимальных смешанных стратегий.

Основная теорема теории игр

Лемма

Для любой матричной игры с матрицей А справедлива одна из двух альтернатив:

1) существует такая смешанная стратегия х = (х₁, …, х _m), что

                        (j = 1, 2, …, n);

2) существует такая смешанная стратегия y = (y₁, …, y_n), что

                        (i = 1, 2, …, m).

Основная теорема теории игр (теорема о минимаксе)

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

 и  

существуют и равны между собой.

 

Или другими словами:

Всякая прямоугольная игра имеет цену; игрок в прямоугольной игре всегда имеет оптимальную стратегию.

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

,   

что

При этом  

Теорема 1

Для того чтобы в матричной игре с ценой игры v смешанная стратегия х⁰ первого игрока была оптимальной, необходимо и достаточно для любой смешанной стратегии у второго игрока выполнение неравенства

v £ Е (А, х^о, у).

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

Е (А, х, у^о) £ v.

 

Следствие.

Для того чтобы х⁰ = (х₁⁰, х₂⁰, ..., х _m) была оптимальной смешанной стратегией матричной игры с матрицей А и ценой игры v, необходимо и достаточно выполнение следующих неравенств

(j = 1, 2, …, n)                                   (1)

Аналогично для второго игрока: чтобы у⁰ = (у₁⁰, y₂⁰, ..., y_n⁰) была оптимальной смешанной стратегией второго игрока, необходимо и достаточно выполнение следующих неравенств:

(i = 1, 2, …, m)                                  (2)

Из этого следствия вытекает: чтобы установить, являются ли предполагаемые (х, у) и v решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (1) и (2). С другой стороны, найдя неотрицательные решения неравенств (1) и (2) совместно со следующими уравнениями

= 1, = 1,                                            (3)

получим решение матричной игры.

Итак, решение матричной игры сводится к нахождению неотрицательных решений линейных неравенств (1), (2) и линейных уравнений (3).

 

Теорема 2

Пусть имеется матричная игра с матрицей А, ценой игры v, оптимальными смешанными стратегиями х = (х₁, ..., х _m), у = (у₁, ..., у _n) соответственно первого и второго игроков.

Тогда, если для некоторого i будет

                                 ,

то х _i = 0;

если для некоторого j будет

,

то у _j = 0.

 

Пример

Найти решение матричной игры со следующей матрицей:

А=	1	–1	–1
	–1	–1	3
	–1	2	–1

На основании следствия из теоремы 1 для нахождения решения этой игры следует найти неотрицательные х₁, х₂, х₃, у₁, у₂, у₃, удовлетворяющие следующим соотношениям:

х₁ – х₂ – х₃ ³ v                                     y₁ – y₂ – y₃ £ v

–х₁ – х₂ + 2х₃ ³ v (a)                          – y₁ – y₂ + 3y₃ £ v    (b)

–х₁ + 3х₂ – х₃ ³ v                                   –y₁ + 2y₂ – y₃ £ v

х₁ + х₂ + х₃ = 1                                    y₁ + y₂ + y₃ = 1

Причем системы можно решать вместе или отдельно.

Рассмотрим сначала систему (a). Для ее решения можно сначала заменить все неравенства на равенства и попробовать их решить. Если получатся все неотрицательные значения х₁, х₂, х₃, то получено решение игры. Решая систему уравнений

х₁ – х₂ – х₃ ³ v                                    

–х₁ – х₂ + 2х₃ ³ v                               

–х₁ + 3х₂ – х₃ ³ v                                 

х₁ + х₂ + х₃ = 1  

каким-либо известным способом, получим

х₁ = 6/13,  х₂ = 3/13,  х₃ = 4/13, v = –1/13.

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

Составляя теперь систему уравнений для второго игрока и решая ее, получим

    y₁ = 6/13, y₂ = 4/13, y₃ = 3/13.

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

x = (6/13, 3/13, 4/13),

y = (6/13, 4/13, 3/13),

v = –1/13.

---

Дата добавления: 2021-04-05; просмотров: 234; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!