Анализ матричных игр двух игроков с нулевой суммой в смешанных стратегиях.

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

Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

Таким образом, если игрок 1 имеет m чистых стратегий 1,2, ..., m, то его смешанная стратегия x – это набор чисел x =(x ₁, ..., x_m) ^T, удовлетворяющих соотношениям x_i ³0, i =1,2,3,…, m, = 1. Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y – это набор чисел y =(y ₁, ..., y_n), y_j ³ 0, (j = 1,2,3,…, n), = 1.

Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая–либо i –я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i– я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей и равен

Е (А, х, y)=á x, Ay ñ= = x^TAy.

Первый игрок стремится за счёт изменения своих смешанных стратегий х максимально увеличить свой средний выигрыш Е (А, х, y), а второй – за счёт своих смешанных стратегий стремится сделать Е (А, х, y) минимальным. Верхняя и нижняя границы игры будут иметь соответственно вид Е (А, х, y), Е (А, х, y).

Подобно играм, имеющим седловые точки в чистых стратегиях, вводится понятие равновесия в игре

Определениие. Под состоянием равновесия в игре будем понимать пару смешанных стратегий (x ₀, y ₀), для которых Е (А, х, y ₀)£ Е (А, х ₀, y ₀)£ Е (А, х ₀, y), т.е. отклонение любого (только одного) из игроков от этой стратегии приводит к ухудшению (неулучшению) его критерия.

Величина Е (А, х ₀, y ₀) называется ценой игры и обозначается через q.

Как и для игр с чистыми стратегиями, возникает вопрос о существовании состояния равновесия в играх со смешанными стратегиями. На него отвечает следующая основная теорема матричных игр:

Теорема (о минимаксе). Для матричной игры с любой матрицей А величины Е (А, х, y) и Е (А, х, y) существуют и равны между собой.

Таким образом, можно записать:

Не все матричные игры имеют ситуацию равновесия в чистых стратегиях. Однако всякая матричная игра имеет ситуацию равновесия в смешанных стратегиях. Задача линейного программирования эквивалентна в определенном смысле матричной игре. Рассмотрим антагонистическую игру с матрицей A, размерностью (m ´ n). Выпишем симметричные двойственные задачи линейного программирования с этой матрицей следующего вида

min á x, u ñ	max á y, w ñ
x^TA ³ w, (3.2.1)	Ay £ u,, (3.2.2)
x ³ 0 m	y ³ 0 n

где u – вектор, все компоненты которого равны 1, размерность соответствует размерности вектора x, аналогично вектор w, размерность которого соответствует размерности ветора y. Справедлива следующая теорема.

Теорема. Пусть матрица положительна (все элементы положительны), тогда:

1. Задачи (3.2.1), (3.2.2) имееют решения, при этом

2. значение игры v равно

,

для того, чтобы стратегии были равновесными, необходимо и достаточно, чтобы

,

где – оптимальные решения соответственно задач (3.2.1), (3.2.2)

 

Пусть матрица A ¢ произвольная матрица размерностью (m ´ n), тогда существует константа b >0 такая, что матрица A = A ¢+ B, B ={ b_ij }, b_ij = b, i =1,2,3,…, m, j =1,2,3,…, n, сторого положительная и для нее существует состояние равновесия x ^*, y ^*. Можно показать, что состояние равновесия x ^*, y ^* также является состоянием равновесия и в игре с матрицей A ¢, значение игры в ней равно 1/ q – b.

Алгоритм поиска состояния равновесия

1. По матрице A ¢ строится строго положительная матрица A = A ¢+ B, B ={ b_ij }, b_ij = b, i =1,2,3,…, m, j =1,2,3,…, n,

2. Строятся двойственные задачи (3.2.1), (3.2.2) и находятся их оптимальные решения , а также число q.

3. Находится равновесное состояние , вычисляется значение игры 1/ q – b.

Рассмотрим эту связь на примере антагонистической игры с матрицей A ¢, имеющей вид:

A ¢= . Положим b =1, матрица A примет вид A ¢= .

Поставим матрице A в соответствие следующие двойственные задачи:

min (1 x 1+ 1 x 2)	max (1 y 1+1 y 2)
5 x 1+3 x 2³1 1 x 1+4 x 2³1	5 y 1+1 y 2£1 3 y 1+4 y 2£1
x 1, x 2³0	y 1, y 2³0

В этих задачах w =(1,1) ^T u =(1,1) ^T.

Решением этих задач является:

x ₁ =1/17, x ₂ =4/17;

y₁ =3/17, y₂ =2/17; значение функционала q =5/17.

x ₁^* =1/5, x ₂^* =4/5, y₁^* =3/5, y₂^* =2/5, значение игры v =1/ q – b =17/5–1=12/5.

 

Самостоятельная работа №6

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

1. A = ,	2. A = ,	3. A = ,	4. A = ,
5. A = ,.	6. A = ,	7. A = ,	8. A = ,
9. A = ,	10. A = ,	11. A = ,	12. A = ,
13. A = ,	14. A = ,	15. A =	16. A = ,
17. A = ,	18. A =	19. A =	20. A = ,
21. A = ,	22. A = ,	23. A = ,	24. A = ,
25. A = ,.	26. A = ,	27. A = ,	28. A = ,
29. A = ,	30. A = ,	31. A = ,	32. A = ,