Теория Риска. Стратегические игры Выполнил Ланге В.А. группа 245

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

Игра - упрощенная формализованная модель реальной кон­фликтной ситуации ( т.е. определены варианты действия сторон; исход игры при данном варианте действия; объем информации каждой стороны о поведении всех других сторон) Платежная матрица (матрица эффективности, матрица игры) включает все значения выигрышей (в конечной игре). Количество игроков. Если в игре участвуют две стороны, то ее называют игрой двух лиц.. Количество стратегий игры (конечные и бесконечные) Взаимоотношения сторон --- кооперативные (коалиции определены) --- коалиционные и бескоалиционные Характер выигрышей --- игра с нулевой суммой выигрышей (класс антагонистических игр). При этом выигрыш одного игрока при этом равен проигрышу другого. Например, в экономических задачах общий капитал всех игроков перераспределяется между игроками, но не меняется --- игра с ненулевой суммой (как правило, нужно вносить взнос за участие). Так, торговые взаимоотношения стран приводят всех участников к выигрышу.

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

Количество ходов (многошаговые и одношаговые) Информированность сторон --- с полной информацией (игрок на каждом ходу игры знает все ранее примененные другими игроками на предыдущих ходах стратегии) --- не с полной информацией (игроку известны не все стратегии предыдущих ходов других игроков известны) Степень неполноты информации --- стратегические: полная неопределенность (имеется возможность получения информации на основе статистического эксперимента, при котором вычисляется или оценивается распределение вероятно­стей состояний (стратегий)) --- статистические игры: в условиях частичной неопределенности. С теорией статистических игр тесно связана теория принятия экономических решений.

Оценка игры Рассмотрим матричную игру, представленную матрицей выигрышей тхn, где число строк i = l,m, а число столбцов j = 1,n. Подход игрока 1 Подход игрока 2 В этом случае игра называется игрой с седловой точкой.

В данном случае решением игры являются: чистая стратегия игрока 1; чистая стратегия игрока 2; седловой элемент. Смешанная стратегия игрока - это полный набор его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Условия применения: игра без седловой точки; игроки используют случайную смесь чистых стратегий с заданными вероятностями; игра многократно повторяется в сходных условиях; при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком; допускается осреднение результатов игр. Оптимальные чистые стратегии – это чистые стратегии, образующие седловую точку.

Математическое ожидание эффекта (средний выигрыш) в матричной игре Применяя смешанные стратегии, игроки 1 игрок (увеличить свой средний выигрыш) 2 игрок (уменьшить свой проигрыш) Цена игры - средний выигрыш игрока 1 при использовании обоими игроками смешанных стратегий. Тогда, решением матричной игры будет: 1) - оптимальная смешанная стратегия игрока 1 ; 2) - оптимальная смешанная стратегия игрока 2 ; 3) - цена игры

Теорема (основная теорема матричных игр) Для матричной игры с любой матрицей А величины существуют и равны между собой: α = β = При выборе оптимальных стратегий игроку 1 всегда будет гарантирован средний выигрыш, не меньший чем цена игры, при любой фиксированной стратегии игрока 2 (и, наоборот, для игрока 2). Активными стратегиями игроков 1 и 2 называют стратегии, входящие в состав оптимальных смешанных стратегий соответствующих игроков с вероятностями, отличными от нуля. Значит, в состав оптимальных смешанных стратегий игроков могут входить не все априори заданные их стратегии.

2.3. Решение задач в смешанных стратегиях (частный случай) Рассмотрим метод нахождения оптимальных смешанных стратегий для матричных игр начнем с простейшей игры, описываемой матрицей 2x2 (при отсутствии седловой точки можно получить две оптимальные смешанные стратегии)

откуда получаем оптимальные

и цена игры

Графический способ решения задач По оси абсцисс откладывается отрезок единичной длины. По оси ординат откладываются выигрыши при стратегии А 1. На линии, параллельной оси ординат, в точке 1 откладываются выигрыши при стратегии А 2 Концы отрезков обозначаются для a 11 - b 11, a 12 - b 21, а 22 - Ь 22, a 21 – b 12 и проводятся две прямые линии b 11 b 12 и b 21 b 22. Определяется ордината точки пересечения с. Она равна Абсцисса точки с равна р 2 (р 1 = 1 - р 2 ).

Выбрать оптимальный режим работы новой системы ЭВМ, состоящей из двух ЭВМ типов А 1 и А 2. Известны выигрыши от внедрения каждого типа ЭВМ в зависимости от внешних условий, если сравнить со старой системой. Максимальный выигрыш соответствует наибольшему значению критерия эффекта от замены вычислительной техники старого поколения на ЭВМ А 1 и А 2. Запишем условия в принятых обозначениях Определим нижнюю и верхнюю цены игры:

Получаем игру без седловой точки, так как Для этой стратегии гарантированный выигрыш равен (40%) по сравнению со старой системой.

Алгоритм решения: По оси абсцисс отложим отрезок единичной длины. По оси ординат отложим выигрыши при стратегии А 1. На вертикали в точке 1 отложим выигрыши при стратегии А 2. Проводим прямую b 11 b 12, соединяющую точки а 11, а 21. Проводим прямую b 21 b 22, соединяющую точки а 12, а 22. Определяем ординату точки пересечения с линий b 11 b 12 и b 21 b 22. Она равна Определим абсциссу точки пересечения с. Она равна р 2, а Р 1 = 1 - Р 2 Выпишем решение и представим оптимальную стратегию игры: Таким образом, если неизвестны условия решения задач заказчика, на работу ЭВМ А 1 должно приходиться 37,5% времени, а на работу ЭВМ А ,5%. При этом выигрыш составит 55% по сравнению с предыдущей системой ЭВМ.

Мажорирование (доминирование) стратегий Мажорирование представляет отношение между стратегиями, наличие которого во многих практических случаях дает возможность сократить размеры исходной платежной матрицы игры Рассуждая с позиции игрока 2, обнаруживаем преимущество его третьей стратегии перед второй, поскольку при первой стратегии игрока 1 выигрыш игрока 2 равен -3 (вторая стратегия) и 1 (третья стратегия), а при второй стратегии игрока 1 выигрыш игрока 2 равен -2 (вторая стратегия) и -0,5 (третья стратегия). при наличии третьей стратегии игрок 2, если он стремится играть оптимально, никогда не будет использовать свою вторую стратегию, поэтому ее можно исключить из игры, т.е. в исходной платежной матрице можно вычеркнуть 2-й столбец:

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

Мажорирование можно распространить и на смешанные стратегии. Если элементы одной строки не все меньше (или равны) соответствующих элементов других строк, но все меньше (или равны) некоторых выпуклых линейных комбинаций соответствующих элементов других строк, то эту стратегию можно исключить, заменив ее смешанной стратегией с соответствующими частотами использования чистых стратегий. Частоты использования стратегии 1 и 2 0,25 и 0,75 Третья стратегия игрока 1 мажорируется линейной выпуклой комбинацией первой и второй чистых стратегий, взятых с частотами 0,25 и 0,75 соответственно. третью стратегию игрока 1 можно исключить, используя вместо нее указанную выше смешанную стратегию

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