2 Упрощение матричных игр icon

2 Упрощение матричных игр




Скачати 123.01 Kb.
Назва2 Упрощение матричных игр
Дата08.09.2012
Розмір123.01 Kb.
ТипРешение

2.6. Упрощение матричных игр

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

Определение 1. Если в платежной матрице игры все элементы строки (столбца) равны соответствующим элементам другой строки (столбца), то соответствующее этим строкам (столбцам) стратегии называются дублирующими.

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

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

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

Пример. Упростить матричную игру, платежная матрица которой имеет вид:


Bj


Ai


B1


B2


B3


B4


B5

A1

5

9

3

4

5

A2

4

7

7

9

10

A3

4

6

3

3

9

A4

4

8

3

4

5

A5

4

7

7

9

10


Из платежной матрицы видно, что стратегия А2 дублирует стратегию А5, потому любую из них можно отбросить (отбросим стратегию А5). Сравнивая почленно стратегии А1 и А4, видим, что каждый элемент строки А4 не больше соответствующего элемента строки А1. Поэтому применение игроком А доминирующей над А4 стратегии А1 всегда обеспечивает выигрыш, не меньший того, который был бы получен при применении стратегии А4. Следовательно, стратегию А4 можно отбросить. Таким образом, имеем упрощенную матричную игру с платежной матрицей вида:








Bj


Ai


B1


B2


B3


B4


B5

A1

5

9

3

4

5

A2

4

7

7

9

10

A3

4

6

3

3

9


Из этой матрицы видно, что в ней некоторые стратегии игрока В доминируют над другими: В3 над В2, В4 и В5. Отбрасывая доминируемые стратегии В2, В4 и В5 получаем игру 3x2, имеющей платежную матрицу, вида:


Bj


Ai


B1


B3

A1

5

3

A2

4

7

A3

4

3


В этой матрице стратегия А3 доминирует как над стратегией А1, так и стратегией А2. Отбрасывая стратегию А3, окончательно получаем игру 2x2 с платежной матрицей



Bj


Ai


B1


B3

A1

5

3

A2

4

7


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

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

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

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

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

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

1) если матрица игры наряду с положительными имеет и отрицательные элементы, то ко всем ее элементам прибавляют такое число, чтобы исключить отрицательные числа в матрице;

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

Пример. Решить матричную игру 2*2 с платежной матрицей вида:


Bj


Ai


B1


B2

A1

0.5

-0.2

A2

0.1

0.3


Умножая все элементы платежной матрицы на 10, а затем прибавляя к ним число 2, получаем игру с платежной матрицей


Bj


Ai


B1


B2

A1

7

0

A2

3

5


Решая эту игру алгебраическим методом, получаем

;

;

.

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


^ 2.7.Решение игр 2xn и mx2

Как уже отмечалось в теореме об активных стратегиях, любая конечная игра mxn имеет решение, в котором число активных стратегий каждого игрока не превосходит , где . Следовательно, у игры 2xn или mx2 всегда имеется решение содержащее не более двух активных стратегий у каждого из игроков . Если эти активнэе стратегии игроков будут найдены, то игры 2xn и mx2 превращается в игру 2x2, методы решения которых рассмотрены выше.

Практически решение игры 2xn осуществляется следующим образом:

1) строится графическое изображение игры;

2) выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы (максимин), которая равна цене игры v;

3) определяется пара стратегий игрока В, пересекающихся в точке оптимума. Эти стратегии и являются активными стратегиями игрока В.

Таким образом, игра 2xn сведена к игре 2x2, которую более точно можно решить алгебраическим методом.

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

Решение игры mx2 осуществляется аналогично. Но в этом случае выделяется не нижняя, а верхняя граница выигрыша, так как находится оптимальная смешанная стратегия игрока В, и на ней находится точка оптимума с наименьшей ординатой (минимакс).

Пример. Найти решение игры, платежная матрица которой имеет вид:


Bj


Ai


B1


B2


B3

A1

2

5

8

A2

7

4

3


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





Рис. 2.


Точка N (максимин) является точкой оптимума. В этой точке пересекаются отрезки, соответствующие активным стратегиям В1 и В2 игрока В. Таким образом, исключая стратегию В3, получаем матричную игру 2x2 с платежной матрицей вида



Bj


Ai


B1


B2

A1

2

5

A2

7

4


Используя алгебраический метод решения этой игры, получаем точное решение

;

;

.

Ответ: ; ;


Пример. Найти решение игры, платежная матрица которой имеет вид


Bj


Ai


B1


B2

A1

0

1

A2

4

2

A3

-1

4

A4

1

-3

A5

6

-2

A6



3


Платежная матрица не имеет седловой точки. Для сведения данной игры к игре 2x2 строим ее графическое изображение.





Точка М (минимакс) является точкой оптимума. В этой точке пересекаются отрезки, соответствующие активным стратегиям А2, А6 и А3 игрока А. Таким образом, исключая стратегии А1, А4 и А5 и выбирая из трех активных стратегий две (например, А2 и А3 или А2 и А6), приходим к матричной игре 2x2. Выбор стратегий А3 и А6 исключен, так как в этом случае точка М перестант быть точкой минимакса.

Пусть выбираются стратегии А2 и А3. Тогда игра 2x2 приобретает вид


Bj


Ai


B1


B2

A2

4

2

A3

-1

4


Оптимальные смешанные стратегии данной игры, а, следовательно, и исходной игры определяются следующими вероятностями:

;

;

.

Ответ: ; ;


Другой вариант игры 2x2 получается, если использовать стратегии А2 и А6. В этом случае платежная матрица имеет вид



Bj


Ai


B1


B2

A2

4

2

A6



3


Тогда

;

;

.

Ответ: ; ;


Естественно, что цена игры для обоих вариантов одинакова.

В заключение наметим общую схему решения матричных игр 2xn и mx2:

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

2. Производится упрощение матричной игры путем исключения дублирующих и доминируемых стратегий. Если упрощенная игра имеет размерность не 2x2, то переходим к этапу 3.

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

4. Решается матричная игра 2x2.

Схожі:

2 Упрощение матричных игр iconКонтрольные вопросы по курсу "Исследование операций и теория игр"
Теорема о активных стратегиях. Сведение матричных игр (2 Х n), (m Х 2) к матричной игре (2 Х 2)
2 Упрощение матричных игр iconЛ. Ф. Василевич Решение нечётких матричных игр
Таким образом, возникает нечёткая матричная игра. В данной статье предлагается методика решения таких игр и анализа чувствительности...
2 Упрощение матричных игр iconП. И. Чайковский 4 основные понятия теории игр и их классификация 4 > Предмет и задачи теории игр 4 > Терминология и классификация игр 7 > Примеры игр 12 тесты
Книга содержит большое количество тестов и задач, которые можно использовать для проведения практических занятий, а также для самостоятельного...
2 Упрощение матричных игр iconП. И. Чайковский 3 основные понятия теории игр и их классификация 3 > Предмет и задачи теории игр 3 > Терминология и классификация игр 4 > Примеры игр 6 тесты
Книга содержит большое количество тестов и задач, которые можно использовать для проведения практических занятий, а также для самостоятельного...
2 Упрощение матричных игр icon1. основные понятия теории игр и их классификация предмет и задачи теории игр
Даже идея Руссо об эволюции от «естественной свободы» к «гражданской свободе» формально соответствует с позиций теории игр точке...
2 Упрощение матричных игр icon1. основные понятия теории игр и их классификация предмет и задачи теории игр
Даже идея Руссо об эволюции от «естественной свободы» к «гражданской свободе» формально соответствует с позиций теории игр точке...
2 Упрощение матричных игр iconПриближенный метод решения матричных игр mxn
Разыгрывается эксперимент, в котором игроки а и в поочередно применяют друг против друга свои чистые стратегии. Каждый из игроков...
2 Упрощение матричных игр iconЛекции для экономистов-кибернетиков М.: "Наука".,1985. 271 с. Данилов В. И. Лекции по теории игр: учебное пособие. М.: Российская экономическая школа, 2002. 140 с
Васин А. А., Морозов В. В. Теория игр и модели математической экономики. М.: Макс пресс, 2005 г. 272 с
2 Упрощение матричных игр iconПрактическая работа № Тема: Вычисление пределов функций, интегрирование и дифференцирование, упрощение выражений и разложение на множители в программе
Тема: Вычисление пределов функций, интегрирование и дифференцирование, упрощение выражений и разложение на множители в программе...
2 Упрощение матричных игр iconВ. В. Теория игр и модели математической экономики. М.: Макс пресс, 2005 г. 272 с. Воробьев Н. Н. Теория игр лекции
Васин А. А., Морозов В. В. Теория игр и модели математической экономики. М.: Макс пресс, 2005 г. 272 с
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи