Применение алгоритмов теории игр в экономических системах

       Игру  в развернутой форме называют игрой с полной информацией, если в ней нельзя делать одновременно несколько ходов и если участникам известны выборы, сделанные при предшествующих ходах, включая и случайные ходы. Примером игры с полной информацией являются шахматы. Покер представляет собой игру с неполной информацией, так как игрокам неизвестно, какие карты находятся на руках у противника [12].

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

       Нормальная форма игры двух участников состоит из платежной матрицы, показывающей, какую сумму получает каждый из игроков при любой из возможных стратегий (см. рисунок 1.2).

       Элементами  этой матрицы являются пары чисел, первое из которых определяет величину выигрыша игрока 1, а второе — игрока 2. 

       

       Рисунок 1.2 - Платежная матрица для игры двух участников 

       Игрок 1 выбирает одну из m стратегий A_1, A₂,…,A_m. Игрок 2 выбирает одну из n стратегий B₁, B₂,…,B_n. Пара чисел на пересечении строки и столбца, которые соответствуют стратегиям, избранным игроками, показывает величину выигрыша каждого из них. Если игрок 1 выбирает A_i, а игрок 2 -B_j, то выигрыши игроков 1 и 2 равны соответственно a_ij и b_ij (i=1,..,m; j=1,..,n).

       Платежная матрица имеет размерность m×n, где m — (конечное) число возможных стратегий игрока 1, а n — (конечное) число возможных стратегий игрока 2. Предполагается, что каждому из игроков известны все элементы платежной матрицы [14].

5. Матричные игры. Игры с нулевой суммой. Решение матричных игр в чистых стратегиях

 

       Матричные игры — игры, в которых участвуют два игрока (1 и 2) с противоположными интересами, причём каждый игрок имеет конечное число чистых стратегий.

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

       Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая  абстрактная игра двух игроков.

       Первый  игрок имеет m стратегий i = 1,2,...,m , второй имеет n стратегий j = 1,2,...,n . Каждой паре стратегий (i ,j) поставлено в соответствие число а_ij , выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i -ю стратегию, а 2 – свою j -ю стратегию.

       Каждый  из игроков делает один ход: игрок 1 выбирает свою i -ю стратегию , 2 – свою j -ю стратегию , после чего игрок 1 получает выигрыш а_ij за счёт игрока 2 (если а_ij < 0, то это значит, что игрок 1 платит второму сумму | а_ij | ). На этом игра заканчивается.

       Каждая  стратегия игрока i = ; j = часто называется чистой стратегией.

       Если  рассмотреть матрицу 

       

, 

       то  проведение каждой партии матричной  игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 j -го столбца и получения игроком 1 (за счёт игрока 2) выигрыша а_ij .

       Главным в исследовании игр является понятие  оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i = ), определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2 ( ), т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i -ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = i_о, при которой этот минимальный выигрыш будет максимальным, т.е. находится 

        .     (1) 

       Число α, определённое по формуле (1) называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.

       Игрок 2 при оптимальном своём поведении  должен стремится по возможности  за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается _,т.е. определяется максимальный выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j₁ стратегию, при которой игрок 1 получит минимальный выигрыш, т.е. находит 

        .     (2) 

       Число β, определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.

       Другими словами, применяя свои чистые стратегии  игрок 1 может обеспечить себе выигрыш  не меньше α, а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем β.

       Если  в игре с матрицей А  , то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры .

       Седловая  точка – это пара чистых стратегий (i_о,j_о) соответственно игроков 1 и 2, при которых достигается равенство . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе: 

        .     (3) 

       Таким образом, исходя из (3), седловой элемент  a_i0j0 является минимальным в i_о-й строке и максимальным в j_о-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (i_о,j_о) игроков 1 и 2, образующая седловую точку и седловой элемент a_i0j0, называется решением игры. При этом i_о и j_о называются оптимальными чистыми стратегиями соответственно игроков 1 и 2 [15].

       Пример 

       

       Рисунок 1.3 – Пример решения матричных  игр в чистых стратегиях.

       Седловой  точкой является пара (i_о = 3; j_о = 1), при которой g = α = β = 2.

       Заметим, что хотя выигрыш в ситуации (3;3) также равен 2 = α = β, она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца [16].

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

1. Уменьшение  порядка платёжной  матрицы

 

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

       Стратегия K* называется доминируемой стратегией K**, если при любом варианте поведения противодействующего игрока выполняется соотношение A_k* < A_k**, где A_k* и A_k** - значения выигрышей при выборе игроком, соответственно, стратегий K* и K**.

       В случае, если выполняется соотношение A_k* = A_k**, стратегия K* называется дублирующей по отношению к стратегии K**.

       Например, в матрице (см. таблицу 1). 

       Таблица 1

       Платёжная матрица с доминируемыми и  дублирующими стратегиями

 

       Стратегия A1 является доминируемой по отношению к стратегии A2, стратегия B6 является доминируемой по отношению к стратегиям B3, B4 и B5, а стратегия B5 является дублирующей по отношению к стратегии B4. Данные стратегии не будут выбраны игроками, так как являются заведомо проигрышными и удаление этих стратегий из платёжной матрицы не повлияет на определение нижней и верхней цены игры, описанной данной матрицей.

       Множество недоминируемых стратегий, полученных после уменьшения размерности платёжной  матрицы, называется ещё множеством Парето [17].

2. Понятие о матричных играх  со смешанным расширением

 

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

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

       Стратегии, применённые с вероятностью, отличной от нуля, называются активными стратегиями.

       Доказано,  что для всех игр  со смешанным расширением  существует оптимальная  смешанная стратегия, значение выигрыша при  выборе которой находится в интервале между нижней и верхней ценой игры [9]: .

       При этом условии величина g называется ценой игры.

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

       Игры, в которых выполняется строгое  неравенство, называются не полностью определенными играми без седловой точки.

       Пример  такой игры, для которой α = -2 < 4 = β приведен на рисунке 1.4.