Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




Перед тем, как решать игру т × п, нужно, прежде всего, попытаться ее упростить, избавившись от лиш­них стратегий. Введем понятие «доминирования».

Стратегия игрока называется доминирующей стратегией (среди его стратегий) или (слабо) заведомо-оптимальной, если она доминирует любую другую его стратегию либо эквивалентна ей, а сильно доминирующей – если только доминирует любую другую.

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

Первая стратегия “сильно доминирует” вторую (то есть первая стратегия “заведомо лучше”, чем вторая) – когда первая стратегия при любых действиях партнеров лучше второй стратегии.

Если две стратегии доставляют одинаковые выигрыши при любых действиях партнеров, то они эквивалентны для игрока.

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

Поясним сказанное примером. Пусть игра 5×5 за­дана матрицей таблицы 5.

 

Таблица 5

  В1 В2 В3 В4 В5
А1          
А2          
А3          
А4          
А5          

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

Перейдя к стратегиям игрока В замечаем, что в ней некоторые стратегии игрока В доми­нируют над другими: например, В3 над В4 и В5, a В1 - над стратегией В2, поскольку игрок В стремится отдать поменьше. Отбрасывая названные столбцы, получим игру 2×2.

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

Пусть имеется игра т × п без седловой точки с мат­рицей (a,j) (см. таблицу 27.5).

Таблица 6

  В1 В2 Вn
А1 a11 a12 a1n
А2 a12 a22 a2n
Аm am1 am2 amn

 

Допустим, что все выигрыши аij положительны (этого всегда можно добиться, прибавляя ко всем членам матрицы достаточно большое число М; от этого цена игры увеличится на М, а решение S*A, S*B не изменится). Если все аij положительны, то конечно, и цена игры, т. е. средний выигрыш при оптимальной стратегии, тоже положителен: v > 0.

Мы хотим найти решение игры, т. е. две оптималь­ные смешанные стратегии S*A = (p1, р2, …, рт), S*B = (q1, q2,..., qn), дающие каждой стороне максимально возможный для нее средний выигрыш (минимальный проигрыш).

Найдем сначала S*A. Мы знаем, что если один из игроков (в данном случае это А) применяет свою оп­тимальную стратегию, то другой (B) не может улуч­шить свое положение, отступая от своей. Заставим противника (В) отступать от своей оптимальной стра­тегии, пользуясь чистыми стратегиями В1, В2,..., Вп (а мы тем временем упорно держимся стратегии SA). В любом случае наш выигрыш будет не меньше, чем v:

a11 p1 + a21 p2 +…+ am1 pm ≥ v

a12 p1 + a22p2 +…+ am2 pm ≥ v

………………………………..

a1n p1 + a2n p2 +…+ amn pm ≥ v

Разделим полученные неравенства на положительную ве­личину v и введем обозначения

.

Тогда система условий примет вид

a11 х1 + a21 х2 +…+ am1 хm ≥ 1

a12 х1 + a22х2 +…+ am2 хm ≥ 1

………………………………..

a1n х1 + a2n х2 +…+ amn хm ≥ 1

где х1, х2,..., хт - неотрицательные переменные.

В си­лу того, что p1 + р2 + … + pm = 1, переменные x1, х2,..., хт удовлетворяют условию

х1 + х2+ … + хт = 1/v.

Но v есть не что иное, как наш гарантирован­ный выигрыш; естественно, мы хотим сделать его максимальным, а значит, величину 1/v - минимальной.

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

L = х1 + х2+ … + хтmin

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

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

Наиболее простым и наглядным является так называемый метод итераций (иначе - метод Брауна-Робинсон). Идея его в сле­дующем. Разыгрывается «мысленный эксперимент», в котором стороны А и В поочередно применяют друг про­тив друга свои стратегии, стремясь выиграть побольше (проиграть поменьше). Эксперимент состоит из ряда «партий» игры. Начинается он с того, что один из иг­роков (скажем, А) выбирает произвольно одну из своих стратегий Ai. Противник (B) отвечает ему той из своих стратегий Bj, которая хуже всего для А, т. е. обращает его выигрыш при стратегии Ai в минимум. Дальше сно­ва очередь А — он отвечает В той своей стратегией которая дает максимальный выигрыш при стратегии В противника. Дальше — снова очередь противника. Он отвечает нам той своей стратегией Ak, которая является наихудшей не для последней, примененной нами, стра­тегии Ак, а для смешанной стратегии, в которой до сих пор примененные стратегии Аi, Ак встречаются с равными вероятностями. И так далее: на каждом ша­ге итерационного процесса каждый игрок отвечает на очередной ход другого той своей стратегией, которая яв­ляется оптимальной для него относительно смешанной стратегии другого, в которую все примененные до cux пор стратегии входят пропорционально частотам их применения.

Вместо того чтобы вычислять каждый раз средний выигрыш, можно пользоваться просто «накоп­ленным» за предыдущие ходы выигрышем и выбирать ту свою стратегию, при которой этот накопленный вы­игрыш максимален (минимален). Доказано, что такой метод сходится: при увеличении числа «партий» сред­ний выигрыш на одну партию будет стремиться к цене игры, а частоты применения стратегий — к их вероят­ностям в оптимальных смешанных стратегиях игроков.

Рассмотрим применение итерационного метода на конкретном примере. Продемонстрируем его на примере игры 3×3 предыдущего параграфа (табли­ца 4). Чтобы не иметь дела с отрицательными чис­лами, прибавим к элементам матрицы таблицы 4 число 5 (см. таблицу 7); при этом цена игры увели­чится на 5, а решение. S*A, S *В не изменится.

 

 

Таблица 7

  В1 В2 В3
А1      
А2      
А3      

 

Начнем с произвольно выбранной стратегии игрока А,— например, со стратегии А3. В таблице 8 приведе­ны первые 15 шагов итерационного процесса по методу Брауна — Робинсон. В первом столбце дан номер пар­тии (пары выборов) k, во втором — номер i выбранной в данной партии стратегии игрока А. В последующих трех столбцах — «накопленный выигрыш» за первые k партий при тех стратегиях, которые применяли игроки в предыдущих пар­тиях и при стратегиях В1, В2, Вз игрока В в данной партии (получается при­бавлением элементов соот­ветствующей строки к то­му, что было строкой вы­ше). Из этих накопленных выигрышей в таблице 8 подчеркнут минимальный (если их несколько, подчеркиваются все). Под­черкнутое число определяет ответный выбор иг­рока В в данной партии — он выбирает ту страте­гию, которая соответствует подчеркнутому числу (если их несколько, берется любая). Таким образом определя­ется номер j оптимальной (в данной партии) стратегии В (ставится в следующем столбце).

 

Таблица 8

к i B1 B2 В3 j A1 А2 А3 v*
                      4,5
                  4,5   6,75
                  3,67   4,84
                  2,75 5,50 4,13
                  4,00 6,60 5,30
                  4,84 5,50 5,17
                  4,43 5,14 4,79
                  5,00 5,61 5,30
                  4,45 5,11 4,78
                  4,90 5,30 5,10
                  4,64 5,09 4,87
                  5,00 5,41 5,20
                  4,61 5,07 4,84
                  4,93 5,21 5,07
                  4,74 5,06 4,90

 

В последующих трех столбцах дается накопленный выигрыш за k партий соответственно при стратегиях A1, А2, А3 игрока А (получается прибавлением элементов столбца Bj к тому, что было строкой выше). В последних трех столбцах таблицы 8 даны: — нижняя оценка цены игры, равная минимальному накопленному выигрышу, деленному на число партий k; — верхняя оценка цены игры, равная максимальному накопленному выигрышу, деленному на k; v* — сред­нее арифметическое между ними (оно служит лучшей, чем нижняя и верхняя, приближенной оценкой цены игры).

График, построенный по результатам последнего столбца и представленный на рисунке 10 показывает, что величина v* незначительно колеблется около цены игры v = 5 (цена исходной игры была 0, но мы прибавили к элементам матрицы по 5).

 

 

Рисунок 10. График зависимости v* от номера итерации

 

Подсчитаем по таблице 8 частоты стратегий игроков. Получим:

р1 = 4/15 = 0,266, р2 = 7/15 = 0,468; р3 = 4/15 = 0,266,

q1 = 2/15 = 0,133, q2 = 8/15 = 0,534, q3 = 5/15 = 0,333,

что не так уж сильно отличается от вероятностей, вычисленных аналитически.

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

Замечание: в теории игр счи­тается, что каждому игроку известны все возможные стратегии противника, неизвестно лишь то, какой именно из них он воспользуется в данной партии игры. В реальном конфликте это обычно не так: перечень возможных стратегий противника как раз неизвестен, и наилучшим решением в конфликтной ситуации неред­ко будет именно выйти за пределы известных против­нику стратегий, «ошарашить» его чем-то совершенно новым, непредвиденным!

 

 


 

 

Тема 2. Математический аппарат оценки рисков и их последствий
Занятие 7. Принятие решения в условиях неопределенности
Учебные вопросы 4. Задачи теории статистических решений 5. Основные критерии статистических решений 6. Примеры практического применения теории игр

 

 




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


Дата добавления: 2014-11-29; Просмотров: 1898; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.041 сек.