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

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

		Число показываемых пальцев
		2	3	4
Называемое число	4	1	2	3
	5	4	5	6
	6	7	8	9
	7	10	11	12
	8	13	14	15
	4	16	17	18
	5	19	20	21
	7	22	23	24
	8	25	26	27
	6	28	25	30

2. Составить матрицу игры полковника Блотто для случаев, представленных в таблице, и найти состояние равновесия (если оно существует).

		Значение n
		5	6	7
Значение m	2	1	2	3
	3	4	5	6
	4	7	8	9
	2	10	11	12
	3	13	14	15
	4	15	17	18
	2	19	20	21
	3	22	23	24
	4	25	26	26
	2	28	25	30

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

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

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

Таким образом, если игрок 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₀) называетсяценой игрыи обозначается через.

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

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

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

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

min x,u	max y,w
x^TAw,                  (3.2.1)	Ayu, ,                  (3.2.2)
x0m	y0n

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

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

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

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

,

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

,

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

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

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

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

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

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

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

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

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

min (1x1+ 1x2)	max (1y1+1y2)
5x1+3x21 1x1+4x21	5y1+1y21 3y1+4y21
x1,x20	y1,y20

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

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

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

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

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