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

Игрок 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].

1.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_{i 0 j 0} является минимальным в i_о -й строке и максимальным в j_о -м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (i_о ,j_о ) игроков 1 и 2, образующая седловую точку и седловой элементa_{i 0 j 0} , называется решением игры . При этом i_о и j_о называются оптимальными чистыми стратегиями соответственно игроков 1 и 2 [15].

Пример

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

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

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

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

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

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

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

В случае, если выполняется соотношение A_{k *} = A_{k **} , стратегия 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].