Перед тем, как решать игру m´n, нужно, прежде всего попытаться ее упростить, избавившись от лишних стратегий.

Дата: 2025-05-01; Просмотры: 1

Оценка:

0.00 из 5.00 — оценок

Скачиваний: 0

Скачать

Часто при нахождении решения матричной игры существенно помогает выявление превосходства одной стратегии над другой.

Определение.

Если для i-й и k-й стратегий первого игрока выполняются соотношения

a_ij ³ a_kj (j = 1, 2, …, n),

причем хотя бы одно из неравенств является строгим, то говорят, что стратегия i превосходит или доминирует стратегию k.

Аналогично для второго игрока: стратегия j доминирует стратегию r, если выполняются неравенства

a_ij ³ a_ir (i = 1, 2, …, m),

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

Использование соотношения доминирования позволяет сократить размерность матрицы выигрышей в матричной игре. Это свойство формулируется в виде следующей теоремы.

Теорема 1.

Пусть Г – матричная игра с матрицей А порядка m´n, и i-я стратегия первого игрока доминирует k-ю стратегию. Пусть А¹ матрица, получаемая из А путем исключения из нее k-й строки, и пусть Г¹ – матричная игра с матрицей А¹.

Тогда цена игры Г¹ совпадает с ценой игры Г, всякая оптимальная смешанная стратегия второго игрока в Г¹ есть также его оптимальная смешанная стратегия в игре Г, если u = (u₁, u₂, …, u_k–1, u_k+1, …, u_m) есть оптимальная смешанная стратегия первого игрока в игре Г¹, то его смешанная стратегия х = (u₁, u₂, …, u_k–1, 0, u_k+1, …, u_m) является оптимальной в игре Г.

Из теоремы следует, что если i-я стратегия первого игрока доминирует k-ю стратегию, то i-я стратегия для первого игрока лучше, чем k-я , т.е. первому игроку не выгодно использовать свою k-ю стратегию и она не должна входить в его оптимальную стратегию. Следовательно, вероятность применения k-й чистой стратегии в оптимальной смешанной стратегии первого игрока должна равняться нулю. Вычеркивая из А эту k-ю строку, получаем матрицу А¹, в которой количество строк на единицу меньше. При этом полагаем x_k = 0, где x_k – k-я компонента х. Игру с матрицей А¹ решать легче, так как в ней меньше строк. Если в матрице А¹ наблюдается доминирование стратегий первого игрока, то далее можно поступать аналогично и таким образом уменьшить размерность матрицы А¹.

Доминирование стратегий для второго игрока также дает дополнительные возможности для сокращения размера матрицы выигрышей.

С этой целью можно использовать следующее свойство.

Теорема 2.

Пусть Г матричная игра с матрицей А. Пусть q-я чистая стратегия второго игрока доминирует r-ю, матрица А¹ получена из А исключением q-го столбца, Г¹ – матричная игра с матрицей А¹. Тогда цена игры Г¹ такая же, как цена игры Г; всякая оптимальная смешанная стратегия первого игрока в Г¹ есть также его оптимальная смешанная стратегия в Г; если w = (w₁, w₂, ..., w_q–1, w_q+1, ..., w _n) есть оптимальная смешанная стратегия второго игрока в Г¹, то у = (w₁, w₂, ..., w_q–1, 0, w_q+1, ..., w _n) есть оптимальная смешанная стратегия второго игрока в Г.

Таким образом, из теоремы 2 следует, что, если q-я чистая стратегия второго игрока доминирует какую-либо его чистую стратегию, то q-й столбец в А можно вычеркнуть, положив y_q = 0, где y_q – q-я компонента оптимальной смешанной стратегии второго игрока. В результате, получаем матрицу А¹ меньшей размерности чем А. Если в А¹ есть доминирование стратегий, то можно поступать с ней аналогично и уменьшить ее размерность.

Пример 1.

Обозначим оптимальные смешанные стратегии первого и второго игроков соответственно через х и у. Очевидно, третья стратегия первого игрока доминирует его первую стратегию, поэтому можно в матрице А вычеркнуть первую строку, положив х₁ = 0. Тогда получим новую матрицу

в которой 4-я стратегия второго игрока доминирует его 2-ю стратегию, и поэтому вычеркиваем четвертый столбец, полагая y₄ = 0, и получаем новую матрицу

В этой матрице уже нет доминирования. Таким образом, исходную игру с матрицей порядка 4´4 с помощью доминирования свели к игре с матрицей порядка 3´3.

Пример 2.

Рассмотрим игру со следующей матрицей:

5 2 1

2 1 3

3 6 4

Третья строка этой матрицы доминирует вторую. Исключение второй строки приводит к матрице

5 2 1

3 6 4

Третий столбец в этой урезанной матрице доминирует второй, и исключение второго столбца дает

5 1

3 4

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

Матричные игры обладают еще одним интересным свойством, которое формулируется в виде следующей теоремы.

Теорема 3.

Пусть дана матричная игра Г с матрицей А = (a_ij) и с ценой игры v. Тогда оптимальные смешанные стратегии игроков матричной игры Г_В с матрицей В = (b_ij) = (da_ij + с), где d > 0 совпадают с оптимальными смешанными стратегиями соответствующих игроков в матричной игре Г, а цена игры Г_В равна v_B = dv + с.

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

Пример.

Рассмотрим матричную игру с матрицей

Если каждый элемент этой матрицы разделить на 100 и затем из полученных элементов вычесть 1, то получим игру с матрицей

которая имеет более простые элементы. Здесь проведено следующее преобразование:

b_ij = 0,01×a_ij – 1, т.е. d = 0,01, c = –1.

В этой игре нет седловой точки в чистых стратегиях. Поэтому для решения игры с матрицей В обозначим через х = (x₁, x₂), у = (y₁, у₂) оптимальные смешанные стратегии соответственно первого и второго игроков, v – цена игры с матрицей A, v_B – цена игры с матрицей В.

Согласно следствию из теоремы 1, х и у должны удовлетворять соотношениям:

x₁ + 5x₂ ³ v_B y₁ + 2y₂ £ v_B

2x₁ ³ v_B 5y₁ £ v_B

x₁ + x₂ = 1 y₁ + y₂ = 1

Предположим, что все эти неравенства являются равенствами. Позже будет показано, что это всегда так, если в матричной игре с матрицей порядка 2´2 нет седловой точки в чистых стратегиях. Тогда получим

x₁ + 5x₂ = v_B y₁ + 2y₂ = v_B

2x₁ = v_B 5y₁ = v_B

x₁ + x₂ = 1 y₁ + y₂ = 1

Решив данную систему, получим:

v_B = 3/5, x₁ = 3/10, x₂ = 7/10, y₁ = 3/25, y₂ = 22/25

Тогда решением матричной игры с матрицей А будет

Замечание.

Отметим, что исключение доминируемых (не строго!) стратегий может привести к потере некоторых решений. Если же исключаются только строго доминируемые стратегии, то множество решений игры не изменится.

Пример 3.

Пусть G = (Х,Y,А), где Х = {1, 2, 3, 4}; Y = {1, 2, 3, 4}, а функция выигрыша А задана следующим образом:

где С > 0.

Решение.

Прежде всего заметим, что по теореме 3 достаточно решить игру G¹ = (Х, Y, А), где А¹ = А . В матричной форме игра G¹ определяется матрицей выигрышей

Элементы четвертой строки этой матрицы “ £ ” соответствующих элементов третьей строки и поэтому третья стратегия игрока 1 доминирует над четвертой. Кроме того, элементы первого столбца матрицы А¹ “ ³ ” соответствующих элементов второго столбца, Следовательно, вторая стратегия игрока 2 доминирует над его первой стратегией.

Далее, из теоремы 1 и 2 следует, что всякое решение игры

G² = (Х \{4}, Y \{1}, А¹)

является решением игры G¹. В матричной форме игру G² можно представить матрицей

.

Очевидно, что элементы второй строки “ ³” полусуммы соответствующих элементов первой и третьей строк. Кроме того, элементы третьего столбца матрицы А² “ ³“ соответствующих элементов второго столбца. Применяя теорему3, получим, что всякое решение игры

G ³ = (Х \ {4,2}, Y \ {1,4}, А²)

является решением игры G ², а следовательно и игры G ¹. Игра G ³ определяется матрицей

.

Матрица А ³ не имеет седловой точки, т.к. не выполнено равенство

= ,

а игра G³ не имеет решения в чистых стратегиях, т.е. оптимальные стратегии игроков являются смешанными. Эти стратегии (в данном случае) легко найти из анализа структуры матрицы А³. Поскольку матрица А³ симметрична, можно предположить, что игроки в оптимальной стратегии используют свои чистые стратегии с равными вероятностями.

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

, либо .

Аналогично, если игрок 2 использует свои чистые стратегии 2 и 3 с равными вероятностями, то математическое ожидание его проигрыша будет равно 3/2. Следовательно, указанные стратегии являются оптимальными в игре G³, а величины 3/2 – значением игры G³. Из предыдущего следует, что эти стратегии оптимальны и в G¹.

Таким образом, стратегия Х = (1/2, 0, 1/2, 0) является оптимальной стратегией игрока 1, стратегия Y = (0, 1/2, 1/2, 0) – оптимальной стратегией игрока 2 в игре G¹, а значение игры G¹ равно 3/2. В силу свойства 4 решением игры G будет тройка (Х, Y, 3С/2).