Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

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

равны между собой,

Более того, существует хотя бы одна ситуация в смешанных стратегиях (Р⁰, Q⁰), для которой выполняется соотношение

Иными словами, любая матричная игра имеет решение в смешанных стратегиях. По­иск этого решения опирается на следующие установленные факты.

 

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

 

Теорема 2. Пусть

и

- оптимальные смешанные стратегии и ν – цена игры,

Оптимальная смешанная стратегия Р⁰ игрока А смешивается только из тех чистых стратегий А_i, i = 1, 2,..., m, то есть отличными от нуля могут быть вероятности p_i

только с теми номерами i = 1,2, ... , m, для которых выполнены равенства

.

Это означает, что смешиваются не все чистые стратегии. Аналогично, в оптимальной смешанной стратегии Q⁰ игрока В отличных от нуля могут быть только те вероятности q_k, для номеров k = 1,2, ... , n, которых выполнены равенства

.

Кроме того, имеют место соотношения

.

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

 

Методы решения матричных игр

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

Для построения решений 2 х n и m х 2 игр существует эффективный метод, осно­ванный на простых геометрических соображениях. Этот метод, называют графическим.

 

X n игры

Пусть

- платежная матрица 2 х n игры.

Согласно теореме о двойном описании игры (теорема 2) нахождение цены игры и оптимального значения р⁰ для игрока А равносильно разрешению уравнения

.

Опишем общую схему, приводящую к искомому результату.

Максимум функции

(*)

проще всего найти, построив ее график. Для этого поступают следующим образом.

Предположим, что игрок А выбрал смешанную стратегию Р = {р, 1 - р}, а игрок В - k-ю чистую стратегию, k = 1, 2, ... , n. Тогда средний выигрыш игрока А в ситуации {Р, k} оказывается равным

(k): .

На плоскости (р, ω) уравнение (k) описывает прямую. Тем самым, каждой чистой стратегия игрока B на этой плоскости соответствует своя прямая.

Поэтому сначала на плоскости (ω, р) последовательно и аккуратно рисуются все
прямые

(k): , k = 1, 2, ... , n

(рис.2). Затем для каждого значения р, 0 £ р £ 1, путем визуального сравнения соответствующих ему значений ω на каждой из построенных прямых определяет­ся и отмечается минимальное из них (рис. 3). В результате описанной процедуры получается ломаная, которая и является графиком функции (*) (выделена жирным на рис. 4). Эта ломаная как бы огибает снизу все семейство построенных прямых,

Рис.2 Рис.3 Рис.4

 

и по этой причине ее принято называть нижней огибающей этого семейства. Верхняя точка построенной нижней огибающей определяет и цену игры – v и оптимальную стратегию игрока А – Р⁰ = {р⁰, 1 - р⁰} (рис. 5).

 

Замечание. Описанная процедура может рассматриваться как некоторый аналог максиминного подхода при отсутствии седловой точки.

 

Опробуем описанную схему решения 2 х n игры на конкретном примере.

 

Пример 5. Рассмотрим игру, заданную 2 x 6 матрицей

Решение.

1-й шаг. Анализ игры на наличие седловой точки.

Нижняя цена игры равна -1, верхняя цена игры равна 1. Седловой точки нет. Решение игры нужно искать в смешанных стратегиях.

2-й шаг. Вычисление средних выигрышей игрока А (проводится при условии, что игрок В выбирает только чистые стратегии).

Из таблицы

p					-1
1 - p	-2	-1

 

легко получаем:

(1): ω = 6p - 2(1 - p),

(2): ω = 4p - (1 - p),

(3): ω = 3p + (1 - p),

(4): ω = p ,

(5): ω = 6p - 2(1 - p),

(6): ω = 4(1 - p),

3-й шаг. Построение нижней огибающей.

Аккуратно строим на координатной плоскости (р, ω) все шесть прямых, уравнения которых полу­чены на 2-м шаге (рис. 6), и находим их нижнюю огибающую.

4-й шаг. Отыскание цены игры и оптимальной смешанной стратегии игрока А.

При аккуратном построении нижней огибающей, нетрудно определить, точкой пересечения каких двух из построенных шести прямых является ее наивысшая точка. В данном случае это прямые (4) и (5), заданные уравнениями ω = р и ω = -р + 5(1 - р) соответственно. Решая систему уравнений

ω = р,

ω = -p + 5(l - p), ,

получаем

,

(рис.7).

Рис.5 Рис.6 Рис.7

 

Тем самым, цена игры ν и оптимальная стратегия Р⁰ игрока A соответственно равны

, .

 

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

 

Замечание. Решающий матричную игру обычно отождествляет себя с одним из игроков (как правило, это игрок А), считая другого своим противником. Это связано еще и с тем, что в некоторых случаях основное внимание уделяется поиску оптимальных стратегий только игрока А, а стратегии противника могут вообще не интересовать исследователя.

 

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

Как ищется оптимальная смешанная стратегия игрока А, мы уже описали. Покажем теперь, как отыскать оптимальную смешанную стратегию игрока В.

Здесь, в зависимости от формы нижней огибающей, может представиться несколь­ко случаев.

А. Нижняя огибающая имеет ровно одну наивысшую точку (р⁰, ω⁰):

1) Если р⁰ = 0 (оптимальная стратегия игрока А – чистая стратегия А₂), то игро­ку В выгодно применять чистую стратегию, соответствующую номеру прямой, проходящей через точку (0, ω⁰) и имеющей наибольший отрицательный наклон (рис. 8).

Рис.8 Рис.9 Рис.10

 

2) Если p⁰ == 1 (оптимальная стратегия игрока А — чистая стратегия А₁), то опти­мальной для игрока В является чистая стратегия, соответствующая номеру прямой, проходящей через точку (1, ω⁰) и имеющей наименьший положительный наклон (рис. 9).

3) Если 0 < p⁰ < 1, то в наивысшей точке нижней оги­бающей пересекаются, по меньшей мере, две прямые, одна из которых (k-я) имеет положительный наклон, а другая (l-я) — отрицательный (рис. 10), и оптимальная смешан­ная стратегия игрока В получается, если положить

q_k = q, q_l = 1 - q, q_j = 0, j ≠ k, l.

где q – решение уравнения

.

Б. Нижняя огибающая содержит горизонтальный участок, соответствующий чистой стратегии k⁰ игрока B, которая и является оптимальной для него (рис. 11).

Рис. 11

 

Пример 5 (продолжение). Покажем теперь, как найти полное решение игры, то есть еще и оптимальную смешанную стратегию

игрока В.

Для этого поступают так:

1) полагают

(выделяя тем самым из шести чистых стратегий игрока В стратегии В₄ и B₅. которым соответствуют прямые (4) и (5), определяющие наивысшую точку нижней огибающей),

 

2) приравнивают любой из двух средних выигрышей игрока В (игрок А выбирает только чистые стратегии), отвечающих предложенной смешанной стратегии

			q	1 - q
				-1
-2	-1

к цене игры

,

 

3) получают (в обоих случаях), что

.

Полное решение игры имеет следующий вид

, , .

Замечание. Ситуация с наличием лишь двух конкурирующих стратегий игрока А нельзя считать на­думанной. Она возникает сравнительно часто. Например, в случае, если нужно сравнить два образца некоторого изделия (скажем, старого и модернизированного) с целью выяснения возможности замены, это весьма удобно сделать при помощи платежной матрицы 2 х n.

 

M х 2 игры

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

.

Анализ такой игры во многом напоминает рассуждения, описанные для игры 2 х n.

Пусть Q = {q, 1 - q} — произвольная смешанная стратегия игрока В. Если игрок А выбирает i-ю чистую стратегию, i = 1, 2, ... , n, то средний выигрыш игрока В в ситуации {i, Q} будет равным

 

(i): i = 1, 2,..., m. (*)

Зависимость этого выигрыша от переменной q описывается прямой.

Графиком функции

является верхняя огибающая семейства прямых (*), соот­ветствующих чистым стратегиям игрока А (рис. 12).

Рис.12

 

Абсциссой нижней точки полученной ломаной будет значение q⁰, определяющее оптимальную смешанную стра­тегию игрока В, а ординатой ω⁰ – цена игры.

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

Рассмотрим конкретный пример.

Пример 6. 3 х 2 игра задана матрицей

.

 

Решение.

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

Нижняя цена игры равна 0, верхняя цена игры равна 3. Седловой точки нет. Решение игры нужно искать в смешанных стратегиях.

2-й шаг. Вычисление средних выигрышей игрока В (проводится при условии, что игрок А выбирает только чистые стратегии).

Из таблицы

q	1 - q
	-1
-1

 

получаем:

(1): ω = 3q – (1 - q)

(2): ω = -q + 3(1 - q)

(3): ω = q

3-й шаг. Построение верхней огибающей.

Построим на координатной плоскости (q, ω) все три прямых, а за­тем и их верхнюю огибающую (рис. 13).

Рис. 13

4-й шаг. Отыскание иены игры и оптимальной смешанной стратегии игрока В.

Нижняя точка верхней огибающей является точкой пересечения прямых (1) и (2). Решая систему уравнений

ω = 3q – (1 - q),

ω = -q + 3(1 - q),

получаем

, .

5-й шаг. Отыскание оптимальной смешанной стратегии игрока А.

Полагая

приравниваем средние выигрыши игрока А, соответствующие чистым выигрышам игрока В,

и находим р⁰ = 1/2.

Таким образом, цена игры и оптимальные смешанные стратегии игроков А и В соответственно

.

 

M х n игры

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

 

Правило доминирования

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

Опишем одну из таких возможностей более подробно.

— произвольная m х n-матрица. Будем говорить, что i-я строка матрицы А

a_i1 a_i2 … a_in

не больше j -и строки этой матрицы

a_j1 a_j2 … a_jn ,

если одновременно выполнены следующие n неравенств

При этом говорят также, что j -я строка доминирует i-ю строку, или что стратегия A_j игрока А доминирует стратегию А_i.

Замечание. Игрок А поступит разумно, если будет избегать стратегий, которым в матрице игры отвечают доминируемые строки.

Если в матрице А одна из строк (j -я) доминирует другую строку (i-ю), то число строк в матрице А можно уменьшить путем отбрасывания доминируемой строки (i-й). Далее, будем говорить, что k-й столбец матрицы А

не меньше l-го столбца этой матрицы

если одновременно выполнены следующие m неравенств

При этом говорят также, что 2-й столбец доминирует k-й столбец, или что стратегия В_l игрока В доминирует стратегию В_k.

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

Если в матрице А один из столбцов (l-й) доминирует другой столбец (k-й), то число столбцов в матрице А можно уменьшить путем отбрасывания доминируемого столбца (k-го).

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

 

Пример 7. Рассмотрим игру с матрицей

.

Сравнивая строки матрицы, видим, что 1-я строка совпадает с 4-й строкой, или, что то же, стратегия А₄ дублирует стратегию А₁. Тем самым, одну из этих, строк можно вычеркнуть, не нанося ущерба решению

.

Поэлементна сравнивая 1-ю и 2-ю строки, замечаем, что 1-я строка доминирует 2-ю строку, или, что то же, стратегия А₁ доминирует стратегию А₂. Это вновь позволяет уменьшить число строк матрицы

Замечая, что 4-й столбец полученной матрицы доминирует ее 3-й столбец, приходим к игре с 2 х 3-матрицей

Решая эту 2 х 3 игру графическим методом, находим ее решение – цену игры и оптимальные смешанные стратегии игроков А и В:

.

Возвращаясь к исходной 4 x 4 игре, получаем окончательный ответ:

 

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

 

Аффинное правило

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

Допустимые преобразования матрицы игры и ее цена. Оптимальные стратегии у матричных игр, элементы матриц А и С которых связаны равенствами

с_ik = λа_ik + μ, i = 1, 2, ... , m; k = l, 2, ... , n,

где λ > 0, a μ – произвольно, имеют одинаковые равновесные ситуации (либо в чистых
либо в смешанных стратегиях), а их цены удовлетворяют следующему условию

.

 

Пример 8. Элементы матриц

и

связаны равенством

с_ik = 3а_ik + 5, i= 1, 2; k = 1, 2, 3.

Поэтому цена игры с матрицей С легко вычисляется

(см. пример 7).

 

 

Основные этапы поиска решения матричной игры

 

1-й этап – проверка наличия (или отсутствия) равновесия в чистых стратеги­ях (при наличии равновесной ситуации указываются соответствующие оптимальные стратегии игроков и цена игры).

2-й этап – поиск доминирующих стратегий (в случае успеха этого поиска – отбрасывание доминируемых строк и столбцов в исходной матрице игры).

3-й этап – замена игры на ее смешанное расширение и отыскание оптимальных смешанных стратегий и цены игры.