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

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

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

А (х1, y) ³ А (х2, y) (А (х1, y) > А (х2, y)), y Î U.

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

А (х, y1) £ А (х, y2) (А (х, y1) < А (х, y2)), х Î Х.

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

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

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

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

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

Свойство 3. Пусть G = (Х,Y,А) – конечная антагонистическая игра, G¢ = (Х \ х¢,Y,А) – подыгра игры G, а х¢ – чистая стратегия игрока 1 в игре G, доминируемая некоторой стратегией , спектр которой не содержит х¢. Тогда всякое решение (хо, yо, u) игры G¢ является решением игры G.

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

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

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

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

(j = )

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

(i = )

Из последнего свойства вытекает: чтобы установить, является ли предполагаемые (х, y) и u решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (*) и (**). С другой стороны, найдя неотрицательные решения неравенств (*) и (**) совместно со следующими уравнениями

,

получим решение матричной игры.

Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (*) (**) и линейных уравнений (***). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например для матрицы 33 имеем систему из 6 неравенств и 2 уравнений). Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства

= .

Если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок 1 – чистую максиминная, а игрок 2 – чистую минимаксная). В противном случае хотя бы у одного игрока оптимальные стратегии будут смешанные. Для матричных игр небольшого размера эти решения можно найти, применяя свойства 1 – 5.

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

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

где С > 0.

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

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

Далее, из свойства 5 следует, что всякое решение игры G2 = (Х \ {4}, Y \ {1}, А1) является решением игры G1. В матричной форме игру G2 можно представить матрицей

.

Очевидно, что элементы второй строки “ ³” полусуммы соответствующих элементов первой и третьей строк. Кроме того, элементы третьего столбца матрицы А2 “ ³“ соответствующих элементов второго столбца. Применяя свойство 5 получим, что всякое решение игры G3 = (Х \ {4,2}, Y \ {1,4}, А2) является решением игры G2, а следовательно и игры G1. Игра G3 определяется матрицей

.

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

= ,

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

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

,

либо

.

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

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

Вопросы для самоконтроля:

1. По какому алгоритму происходит поиск седловой точки в матричной игре?

2. Всегда ли в матричной игре есть седловые точки?

3. Каким образом можно выбирать свои стратегии случайно?

4. Что такое чистая стратегия игрока?

5. Что такое смешанная стратегия игрока в в матричной игре и как она задается?

6. Что собой представляют содержательно компоненты смешанной стратегии?

7. Как определяется функция выигрыша игрока на смешанных стратегиях?

8. Как задается матричная игра со смешанными стратегиями? Какими свойствами обладают стратегии?

9. Сформулируйте основную теорему теории матричных игр.

10. Приведите критерии оптимальности стратегий игроков.

11. Какова структура множества оптимальных стратегий каждого игрока?

12. Сформулируйте теорему о достижимости максимумов и минимумов функций выигрыша на чистых стратегиях.

13. Какие чистые стратегии входят в качестве компонент седловой точки с положительной вероятностью?

14. Что такое выпуклая комбинация векторов?

15. В каком случае говорят, что один вектор доминирует(строго доминирует) другой?

1. Сформулируйте теорему о доминировании.

Список литературы

Основная:

1. Оуэн Г. Теория игр. Учебное пособие. Санкт-Петербург: ЛКИ, 2008 – 229 с.
2. Мазалов В.В. Математическая теория игр и приложения: Учебное пособие. М.: Лань, 2010
3. Губко М.В., Новиков Д.А Теория игр в управлении организационными процессами [Электронный ресурс]: Учебное пособие. М.: Наука, 2005 – 138 с.
4. Даниловцева Е.Р., Теория игр: основные понятия: текст лекций [Электронный ресурс]. Санкт-Петербург: СПбГУАП, 2003 – 36 с.
5. Коковин С.Г., Лекции по теории игр [Электронный ресурс]. Новосибирск: Типография НГУ, 2010 г. – 91 с.

Дополнительная:

1. Самаров К.Л. Элементы теории игр [Электронный ресурс]. Учебное пособие. Новосибирск: Типография НГУ, 2010 г. – 91 с.
2. Волков Ю.И., Волков А.Ю. Теория игр [Электронный ресурс]. Тюмень, ТГИМЭУП, 2002.
3. Захаров С.Д. Курс теории игр [Электронный ресурс]. Тюмень, ТГИМЭУП, 2002.
4. Данилов В.И. Лекции по теории игр [Электронный ресурс]. КЛ/2002/001. М.: РЭШ, 2002.-192 с.