Теория игр (стр. 2 из 5)

Пример 1

Седловой точкой является пара (i_о = 3; j_о = 1), при которой u =

= = 2.

Заметим, что хотя выигрыш в ситуации (3;3) также равен 2 =

= , она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.

Пример 2

Из анализа матрицы выигрышей видно, что

, т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию i = 2, то игрок 2, выбрав свою минимаксную j = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию i = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию j = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д.

Смешанное расширение матричной игры.

Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивается исследование игры. Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с определённой вероятностью.

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

Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия x– это набор чисел x = (x₁, ..., x_m) удовлетворяющих соотношениям

x_i³ 0 (i= 1,m),

= 1.

Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y – это набор чисел

y = (y₁, ..., y_n), y_j³ 0, (j = 1,n),

= 1.

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

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

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

E (A, x, y) =

= x A y^T

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

Е (А, х, y).

Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть

Е (А, х, y).

Подобно играм, имеющим седловые точкив чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиямиигроков 1 и 2 называются такие наборы х^о, у^о соответственно, которые удовлетворяют равенству

Е (А, х, y) = Е (А, х, y) = Е (А, х^о, у^о).

Величина Е (А, х^о ,у^о) называется при этом ценой игры и обозначается через u.

Имеется и другое определение оптимальных смешанных стратегий: х^о, у^о называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку:

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

Оптимальные смешанные стратегии и цена игры называются решением матричной игры.

Основная теорема матричных игр имеет вид :

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

Е (А, х, y) и Е (А, х, y)

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

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

Обозначим через G (Х,Y,А) игру двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию х Î Х, игрок 2 – y ÎU, после чего игрок 1 получает выигрыш А = А (х, y) за счёт игрока 2.

Определение. Стратегия х¹ игрока 1 доминирует (строго доминирует) над стратегией х², если

А (х¹, y)³ А (х², y)(А (х¹, y) > А (х², y)), y ÎU.

Стратегия y¹ игрока 2 доминирует (строго доминирует) над стратегией y², если

А (х, y¹)£ А (х, y²)(А (х, y¹) < А (х, y²)), х Î Х.

При этом стратегии х²и y² называются доминируемыми (строго доминируемыми).

Спектром смешанной стратегии игрока в конечной антагонистической игре называется множество всех его чистых стратегий, вероятность которых согласно этой стратегии положительна.

Свойство 1. Если чистая стратегия одного из игроков содержится в спектре некоторой его оптимальной стратегии, то выигрыш этого игрока в ситуации, образованной данной чистой стратегией и любой оптимальной стратегией другого игрока, равен значению конечной антагонистической игры.

Свойство 2. Ни одна строго доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии.

Игра G¢ = (Х¢,Y¢,А¢) называется подыгрой игры G (Х,Y,А), если Х¢Ì Х, U¢ÌU, а матрица А¢ является подматрицей матрицы А. Матрица А¢ при этом строится следующим образом. В матрице А остаются строки и столбцы, соответствующие стратегиям Х¢ и U¢, а остальные “вычеркиваются”. Всё то что “останется” после этого в матрице А и будет матрицей А¢.

Свойство 3. Пусть G = (Х,Y,А) – конечная антагонистическая игра, G¢ = (Х &bsol; х¢,Y,А) – подыгра игры G, а х¢ – чистая стратегия игрока 1 в игре G, доминируемая некоторой стратегией

, спектр которой не содержит х¢. Тогда всякое решение (х^о, y^о, u) игры G¢ является решением игры G.

Свойство 4. Пусть G = (Х,Y,А) – конечная антагонистическая игра, G¢ = (Х,Y &bsol; y¢,А) – подыгра игры G, а y¢– чистая стратегия игрока 2 в игре G, доминируемая некоторой стратегией

, спектр которой не содержит y¢.Тогда всякое решение игры G¢является решением G.

Свойство 5. Если для чистой стратегии х¢ игрока 1 выполнены условия свойства 3, а для чистой стратегии y¢ игрока 2 выполнены условия свойства 4, то всякое решение игры G¢ = (Х &bsol;х¢,Y &bsol; y¢,А) является решением игры G = (Х,Y,А).

Свойство 6. Тройка (х^о, y^о, u) является решением игры G = (Х,Y,А) тогда и только тогда, когда (х^о, y^о, кu +а) является решением игры G(Х,Y,кА+а), где а – любое вещественное число, к > 0.

Свойство 7. Для того, чтобы х^о = (

) была оптимальной смешаннойстратегией матричной игры с матрицей А и ценой игры u, необходимо и достаточно выполнение следующих неравенств

(j =

)