Решение игр в чистых стратегиях. — КиберПедия 

История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...

Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...

Решение игр в чистых стратегиях.

2017-11-16 1096
Решение игр в чистых стратегиях. 0.00 из 5.00 0 оценок
Заказать работу

Рассмотрим конечную матричную игру двух лиц, представленную матрицей выигрышей (mxn), где число стратегий игрока А совпадает с числом строк i=1,…,m, а число стратегий игрока В совпадает с числом столбцов j=1,…,n.

 

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

Игрок В придерживается минимаксной стратегии.Он своими оптимальными стратегиями стремится уменьшить выигрыш игрока А. Поэтому при каждой j-ой стратегии он определяет величину своего мах проигрыша, а затем выбирает минимальный из них. Математически минимаксную стратегию можно записать в виде

Если выполняется равенство α = β, то игра имеет оптимальное решение в чистых стратегиях и чистая цена игры ν равна

ν = α = β.

В этом случае игра называется игрой с седловой точкой.

Если имеет место неравенство α <β, то игра не имеет решения в чистых стратегиях, а цена игры удовлетворяет неравенству

α < ν < β

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

Задача.

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

  B1 B2 B3 αi
A1        
A2        
βj        

 

Решение.

1) Нижняя цена игры.

, следовательно, максиминная стратегия А2

2) Верхняя цена игры.

, следовательно, максиминная стратегия В1

Имеем, ν = α = β = 4 – чистая цена игры при стратегиях А2 и В1

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

Решение игры: оптимальные чистые стратегии (А2, В1), цена игры ν = 4.

 

Редукция матричной игры.

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

Пусть А=(аij) платежная матрица размерности (mxn). Говорят, что стратегия Ai доминирует (дублирует) стратегию Ak, если справедливы неравенства

aij ≥ akj, где j=1,…,n.

В этом случае из платежной матрицы можно убрать k-ю строку.

Аналогично, стратегия Bj доминирует (дублирует) стратегию Bp, если справедливы неравенства

aij ≤ aip, гдеi=1,…,m.

В этом случае из платежной матрицы можно убрать p-ый столбец.

Редукция не изменяет значения игры (цены игры) в чистых стратегиях.

Задача.

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

 
0,4 0,9 0,5 0,5 0,6
0,6 0,5 0,7 0,8 0,9
0,6 0,3 0,8 0,6 0,7
0,3 0,8 0,5 0,4 0,3
0,1 0,3 0,5 0,4 0,3
0,4 0,8 0,5 0,4 0,5

С позиции коммерческого предприятия (выигрыши игрока А) стратегия доминирует над стратегией , а стратегия доминирует над стратегией . Следовательно, исключаем 5-ю и 6-ю строки матрицы.

 
0,4 0,9 0,5 0,5 0,6
0,6 0,5 0,7 0,8 0,9
0,6 0,3 0,8 0,6 0,7
0,3 0,8 0,5 0,4 0,3

 

С позиций спроса на товары (проигрыши игрока В) стратегия B1 доминирует над стратегиями B3,B4,B5, поэтому эти столбцы исключаем.

 
0,4 0,9
0,6 0,5
0,6 0,3
0,3 0,8

С позиций игрока А стратегия A1 доминирует над стратегией A4, а стратегия A2 доминирует над стратегией A3. Поэтому исключим 3-ю и 4-ю строки и в результате получим сокращенную платежную матрицу

 
0,4 0,9
0,6 0,5

 

Получили платежную матрицу меньшей размерности, которую исследуем по принципу максимина и минимакса.

  αi
0,4 0,9 0,4
0,6 0,5 0,5
βj 0,6 0,9  

 

Имеем, , . Следовательно, игра не имеет решения в чистых стратегиях так как α < β, седловой точки нет, а цена игры заключена в интервале 0,5 < ν < 0,6. Решать эту задачу можно только в смешанных стратегиях.

 

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

Пусть задана исходная платежная матрица А=(aij) размерностиmxn.Аффинное преобразование -это линейное преобразование всех элементов матрицы А по формуле

где k ≠ 0 и b –любые константы.

Решение матричной игры для платежной матрицы А'=(a'ij) совпадает с решением для исходной платежной матрицы. Цену игры ν для исходной платежной матрицы можно найти из цены игры для преобразованной платежной матрицы ν, опираясь на аффинное правило по формуле

Задача. Задана платёжная матрица игры:

A =

Необходимо упростить матрицу игры.

1. Умножим каждый из элементов матрицы A на k = 0.001, получим:

2. К каждому элементу матрицы прибавим b = 5, получим матрицу:

=

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


Поделиться с друзьями:

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...

История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...

Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...

История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.013 с.