Применение алгоритмов теории игр в экономических системах (стр. 4 из 8)
Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i =
), определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2 
( 
), т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i -ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = iо, при которой этот минимальный выигрыш будет максимальным, т.е. находится 
. (1)Число α, определённое по формуле (1) называется нижней чистой ценойигры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.
Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается 
,т.е. определяется максимальный выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1 стратегию, при которой игрок 1 получит минимальный выигрыш, т.е. находит
. (2)Число β, определяемое по формуле (2), называется чистой верхней ценойигры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.
Другими словами, применяя свои чистые стратегии игрок 1 может обеспечить себе выигрыш не меньше α, а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем β.
Если в игре с матрицей А
, то говорят, что эта игра имеет седловуюточку в чистых стратегиях и чистую цену игры 
.Седловая точка – это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство
. В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе: 
. (3)Таким образом, исходя из (3), седловой элемент ai0j0является минимальным в iо-й строке и максимальным в jо-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (iо,jо) игроков 1 и 2, образующая седловую точку и седловой элементai0j0, называется решением игры. При этом iо и jо называются оптимальными чистымистратегиями соответственно игроков 1 и 2 [15].
Пример
Рисунок 1.3 – Пример решения матричных игр в чистых стратегиях.
Седловой точкой является пара (iо = 3; jо = 1), при которой g = α = β = 2.
Заметим, что хотя выигрыш в ситуации (3;3) также равен 2 = α = β, она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца [16].
1.6 Игры в смешанных стратегиях
1.6.1 Уменьшение порядка платёжной матрицы
Стратегия K* называется доминируемой стратегией K**, если при любом варианте поведения противодействующего игрока выполняется соотношение Ak* < Ak**, где Ak* и Ak** - значения выигрышей при выборе игроком, соответственно, стратегий K* и K**.
В случае, если выполняется соотношение Ak* = Ak**, стратегия K* называется дублирующей по отношению к стратегии K**.
Например, в матрице (см. таблицу 1).
Таблица 1
Платёжная матрица с доминируемыми и дублирующими стратегиями
| B1 | B2 | B3 | B4 | B5 | B6 | |
| A1 | 1 | 2 | 3 | 4 | 4 | 7 |
| A2 | 7 | 6 | 5 | 4 | 4 | 8 |
| A3 | 1 | 8 | 2 | 3 | 3 | 6 |
| A4 | 8 | 1 | 3 | 2 | 2 | 5 |
Стратегия A1 является доминируемой по отношению к стратегии A2, стратегия B6 является доминируемой по отношению к стратегиям B3, B4 и B5, а стратегия B5 является дублирующей по отношению к стратегии B4. Данные стратегии не будут выбраны игроками, так как являются заведомо проигрышными и удаление этих стратегий из платёжной матрицы не повлияет на определение нижней и верхней цены игры, описанной данной матрицей.
Множество недоминируемых стратегий, полученных после уменьшения размерности платёжной матрицы, называется ещё множеством Парето [17].
1.6.2 Понятие о матричных играх со смешанным расширением
Исследование в матричных играх начинается с нахождения её чистой цены. Если матричная игра имеет решение в чистых стратегиях, то нахождением чистой цены заканчивается исследование игры. Если же в игре нет решения в чистых стратегиях, то можно найти нижнюю и верхнюю цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с определённой вероятностью.
Смешанной стратегией игрока называется полный набор чистых стратегий, применённых в соответствии с установленным распределением вероятностей. Матричная игра, решаемая с использованием смешанных стратегий, называется игрой со смешанным расширением.
Стратегии, применённые с вероятностью, отличной от нуля, называются активными стратегиями.
.При этом условии величина g называется ценой игры.
Кроме того, доказано, что, если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остаётся неизменным и равным цене игры v, независимо от того, каких стратегий придерживается другой игрок, если только он не выходит за пределы своих активных стратегий. Поэтому, для достижения наибольшего гарантированного выигрыша второму игроку также необходимо придерживаться своей оптимальной смешанной стратегии.
Игры, в которых выполняется строгое неравенство, называются не полностью определенными играми без седловой точки.
Пример такой игры, для которой α = -2 < 4 =βприведен на рисунке 1.4.
Рисунок 1.4 - Игра двух участников с нулевой суммой, не имеющая седловую точку
Расширим понятие стратегии за счет смешанных (или случайных) стратегий. Смешанная стратегия представляет собой вероятностную комбинацию чистых стратегий, т.е. ряд чистых стратегий, взятых в случайном порядке с некоторыми вероятностями.
Смешанные стратегии игроков 1 и 2 можно указать с помощью вектора вероятностей:
В теории игр доказано, что любая парная конечная игра с нулевой суммой имеет, по крайней мере, одно решение в смешанных стратегиях. Таким образом, каждая конечная игра имеет цену - g - средний выигрыш, приходящийся на одну партию, удовлетворяющий условию:
Решить игру – найти цену игры и оптимальные стратегии.