Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






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

 

Если матричная игра содержит седловую точку, то ее решение находится по принципу минимакса. Если же платежная матрица не имеет седловую точку, то применение минимаксных стратегий каждым из игроков показывает, что игрок I обеспечит себе выигрыш не меньше a, а игрок II обеспечит себе проигрыш не больше b. Так как a < b, то игрок I стремится увеличить выигрыш, а игрок II уменьшить проигрыш. Если информация о действиях противной стороны будет отсутствовать, то игроки будут многократно применять чистые стратегии случайным образом с определенной вероятностью. Такая стратегия в теории игр называется смешанной стратегией. Смешанная стратегия игрока — это полный набор его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Для применения смешанных стратегий должны быть следующие условия:

1) в игре отсутствует седловая точка;

2) игроками используется случайная смесь чистых стратегий с соответствующими вероятностями;

3) игра многократно повторяется в одних и тех же условиях;

4) при каждом из ходов один игрок не информирован о выборе стратегии другим игроком;

5) допускается осреднение результатов игр.

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

Отсюда следует, что каждая конечная игра имеет цену, которую обозначим через g, средний выигрыш, приходящийся на одну партию, удовлетворяющий условию a £ g £ b. Каждый игрок при многократном повторении игры, придерживаясь смешанных стратегий, получает более выгодный для себя результат. Оптимальное решение игры в смешанных стратегиях обладает следующим свойством: каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии, если его противник применяет оптимальную смешанную стратегию, так как это ему невыгодно.

Чистые стратегии игроков в их оптимальных смешанных стратегиях называются активными.

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

Смешанные стратегии игроков S1 и S2 обозначим соответственно A1 , A2 , … Am и B1 , B2 , B3 … Bn , а вероятности их использования через pA = (p1, p2, ..., pm) и qB = (q1, q2, ..., qn), где pi ³ 0, qj ³ 0, при этом .

Тогда смешанная стратегия игрока I — SI, состоящая из стратегий A1, A2, ..., Am, имеет вид:

.

Соответственно для игрока II:

.

Зная матрицу А для игрока I можно определить средний выигрыш (математическое ожидание) :

,

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

.

Игрок II добивается:

.

Обозначим через и векторы, соответствующие оптимальным смешанным стратегиям игроков I и II, при которых выполняется равенство:

.

При этом выполняется условие:

Решить игру — это означает найти цену игры и оптимальные стратегии.

Рассмотрим наиболее простой случай конечной игры 2 ´ 2 без седловой точки с матрицами:

,

С платежной матрицей

.

Требуется найти оптимальные смешанные стратегии игроков , и цену игры g.

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

В игре 2 ´ 2, не имеющей седловой точки, обе стратегии являются активными.

Для игрока I имеем систему уравнений:

 

Для игрока II аналогично:

Если g ¹ 0 и игроки имеют только смешанные оптимальные стратегии, то определитель матрицы не равен нулю, следовательно, эти системы имеют единственное решение.

Решая систему уравнений (10) и (11) находим оптимальные ешения , и g:

 

Пример: Дана платежная матрица:

Найти решение.

Решение. Так как a = 3, b = 5, то a ¹ b, то и матрица игра не имеет седловой точки. Следовательно, решение ищем в смешанных стратегиях. Запишем системы уравнений:

для игрока I:

для игрока II:

Решив эти системы находим:

Следовательно оптимальные стратегии игроков имеют вид:

,

Геометрический метод.

 

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

1. В декартовой системе координат по оси абсцисс откладывается отрезок А1А2, длина которого равна 1 (рис. 2.1.). Левый конец отрезка точка x = 0 соответствует стратегии A1, правый, где х = 1,0 — стратегии А2. Все промежуточные точки этого отрезка соответствуют смешанным стратегиям S1 = (p1, p2).

2. По оси ординат от точки O откладываются выигрыши при стратегии А1.

3. На линии, параллельной оси ординат, от точки 1 откладываются выигрыши при стратегии А2 .

Пусть имеется игра с платежной матрицей:

.

Если игрок II применяет стратегию В1, то выигрыш игрока I при использовании чистых стратегий А1 и А2 составляет соответственно a11 = 0,4 и a21 = 0,6. Соединим эти точки прямой В1В1 .

Если игрок I при стратегии В1 применяет смешанную стратегию , то средний выигрыш, определяемый по формуле математического ожидания g1 = a11p1 + a21p2, изображается ординатой точки N на прямой B1B1. Прямая B1B1 называется стратегией В1. Ордината любой точки отрезка B1B1 равна величине выигрыша игрока I при применении им стратегии A1 и А2 с соответствующими вероятностями p1 и p2.

Аналогично строим отрезок В2В2 , сооветствующий применению игороком II с тратегии В2 .

Ординаты точек отрезка определяют средний стратегий А1 и А2 с соответствующими вероятностями p1 и p2 и равных g2 = a12p1 + a22p2.

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

Игрок II Игрок I
0,4 0,9 0,4
0,6 0,5 0,5
0,6 0,9  

 

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

Рис. 2.1. Геометрический метод решения игры

 

Оптимальная смешанная стратегия и цена игры ровны.

Гарантированный средний выигрыш составляет 0,57.

 

3.6. Метод линейного программирования.

 

Антагонистическую игру m ´ n (где m > 3, n > 3) с конечными значениями m и n можно свести к паре двойственных задач линейного программирования.

Рассмотрим игру m ´ n, заданную платежной матрицей:

.

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

Пример. С учетом вариантов конъюнктуры В1, В2, В3, В4, В5 сложившейся на рынке и поведения покупателей в микрорайоне города коммерческое предприятие разработало шесть технологий продажи товаров А1, А2, А3, А4, А5, А6. Найти оптимальное решение. Возможные варианты среднедневного товарооборота в млн.руб. приведены в таблице:

  В1 В2 В3 В4 В5
А1 0,4 0,9 0,5 0,5 0,6
А2 0,6 0,5 0,7 0,8 0,9
А3 0,6 0,3 0,8 0,6 0,7
А4 0,3 0,8 0,5 0,4 0,3
А5 0,1 0,3 0,5 0,4 0,3
А6 0,4 0,8 0,5 0,4 0,5

 

Стратегия А1 доминирует над стратегией А6, а стратегия А4 доминирует над стратегией А5, следовательно исключаем 5 и 6 строки матрицы

  В1 В2 В3 В4 В5
А1 0,4 0,9 0,5 0,5 0,6
А2 0,6 0,5 0,7 0,8 0,9
А3 0,6 0,3 0,8 0,6 0,7
А4 0,3 0,8 0,5 0,4 0,3

 

С позиций проигрышей строки В стратегии В3, В4 и В5 доминируют над стратегией В1, поэтому эти столбцы исключаем из таблицы:

  В1 В2
А1 0,4 0,9
А2 0,6 0,5
А3 0,6 0,3
А4 0,3 0,8

 

С позиций игрока А стратегия А1 доминирует над стратегией А4, а стратегия А2 доминирует над стратегией А3, следовательно исключаем 3 и 4 строки матрицы:

  В1 В2
А1 0,4 0,9
А2 0,6 0,5

 

Допустим, что все элементы (выигрыши) платежной матрицы положительны (aij ³ 0) (если это не так, то можно ко всем элементам прибавлять достаточно большое число M, сделав их положительными. При этом цена игры увеличится на M, а решение задачи и не изменится). Если все aij ³ 0, то g > 0. Пусть платежная матрица не содержит седловой точки, т.е. игра решается в смешанных стратегиях:

.

Применение игроком I оптимальной смешанной стратегии гарантирует ему средний выигрыш, не меньше цены игры g, независимо от поведения игрока II. Игрок II, применяя оптимальную смешанную стратегию гарантирует для себя минимальный проигрыш (не больше g).

Если игрок II применяет свою чистую стратегию Bj, а игрок I — свою оптимальную стратегию , то средний выигрыш игрока I равен:

Если игрок I применяет чистую стратегию Аi, а игрок II – свою оптимальную смешанную стратегии , то средний выигрыш игрока II составит

Учитывая, что gj не может быть меньше g для игрока I, а и не может быть больше g для игрока II, двойственную задачу линейного программирования можно записать следующим образом:

1) для игрока I:

2) для игрока II:

Смысл этих систем уравнений заключается в следующем: игрок I стремится увеличить цену игры (g ® max), он действует так, чтобы его средний выигрыш при использовании его стратегий с вероятностями pi для любой j-й стратегии игрока II был не меньше величины g, которую он стремится увеличить. Игрок II стремится уменьшить свой проигрыш (g ® min), т.е. он действует так, чтобы его средний проигрыш при использовании его стратегий с вероятностями qj при любой i-й стратегии игрока I не превышал величину g, которую он стремится уменьшить.

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

Разделив левую и правую части неравенств на цену игры g > 0, получим:

Введем обозначения:

Тогда выражения примут следующий вид:

Из равенств и следует, что переменные xi и yj должны удовлетворяют условиям:

Учитывая, что игрок I стремится максимизировать g, а игрок II стремится минимизировать g, переменные xi и yj должны быть выбраны так, чтобы целевая функция достигала минимума, а целевая функция достигала максимума.

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

Решая их, находим xi, yj, цену игры g и оптимальные стратегии и .

или

Задача. Найти решение игры конфликтной ситуации с платежной матрицей:

Решение. Математические модели пары двойственных задач линейного программирования можно записать так:

Найти минимум функции F(Х) = x1 + x2 + x3 при ограничениях:

Найти максимум функции Ф(Y) = y1 + y2 + y3 при ограничениях:

Симплексный метод позволяет найти решение этой системы неравенств таблица 2.4.

Тогда цена игры а вероятность применения стратегий игрока II будет:

Таким образом оптимальная система стратегии игрока II.

Таблица 2.4.

Базисные переменные
-1 -1 -1  
 
 
 
 
 
 
     

 

Поскольку решение этой системы неравенств симплексным методом дает также и решение табл. 2.4. двойственной задачи.

то находим также и вероятность применения стратегий игрока I:

,

таким образом, оптимальная смешанная стратегия игрока I:

.

 

Последнее изменение этой страницы: 2016-08-11

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...