Приведение матричной игры к задачам линейного программирования.

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

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

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

· Р*=(р , р ,…, р )

· Q*=(q , q ,…, q )

· V.

Таблица

Платежная матрица игр

	Вероятности использования II-ым игроком своих чистых стратегий
q1		qn
Вероятности использования I-ым игроком своих чистых стратегий	р1	h11		h1n
pm	hm1		hmn

Р* и Q*- вектора, компоненты которых p и q характеризуют вероятности применения чистых стратегий i и j соответственно первым и вторым игроком. Для этих векторов выполняются соотношения:

p +p +... +p =1,

q +q +... +q =1

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

• математическое ожидание его выигрыша не меньше, чем цена игры V в том случае, если второй игрок использует любую из своих стратегий;

• математическое ожидание его выигрыша равно цене игры V, в том случае, если второй игрок использует свою оптимальную смешанную стратегию.

Без ограничения общности можем предположить, что цена игры V>0 (этого можно добиться с помощью преобразования исходной платежной матрицы, сделав все ее элементы h_ij≥0).

Если первый игрок применяет оптимальную смешанную стратегию Р*=(р , р ,…, р ), а второй - любую из своих чистых стратегий j (j=1,..., n), то математическое ожидание выигрыша первого игрока, которое определяется почленным умножением элементов j-го столбца матрицы на соответствующие вероятности р , р ,…, р и сложением полученных результатов:

(j=1,…, n). (2.7.3)

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

h₁₁p₁+h₂₁p₂+…+h_m1p_m≥V

h₁₂p₁+h₂₂p₂+…+h_m2p_m≥V

……

h_1np₁+h_2np₂+…+h_mnp_m≥V (2.7.4)

Для системы неравенств (2.7.4) проведем следующее преобразование: разделим каждое из них на V (заметим, что в соответствии с предположением, сделанным выше, V> 0) и введем новые переменные:

тогда рассматриваемая система примет вид:

h₁₁y₁+h₂₁y₂+…+h_m1y_m≥1

h₁₂y₁+h₂₂y₂+…+h_m2y_m≥1

……

h_1ny₁+h_2ny₂+…+h_mny_m≥1

Разделив равенство:

p_l+p₂+... + p_m=1

на V, получим, что переменные у₁...,у_m удовлетворяют условию:

у₁+у₂+….+y_m=1/V

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

Из сказанного следует, что для первого игрока задача может быть сформулирована следующим образом: определить вектор Y=(у₁,у₂,…,у_m), компоненты которого удовлетворяли бы:

• системе функциональных ограничений:

h₁₁y₁+h₂₁y₂+…+h_m1y_m≥1

h₁₂y₁+h₂₂y₂+…+h_m2y_m≥1

……

h_1ny₁+h_2ny₂+…+h_mny_m≥1

• системе прямых ограничений:

у₁≥0, у₂≥0,...,y_m≥0; (2.7.8)

• а целевая функция Z стремилась бы к минимуму:

Z=y₁+y₂+...+y_m ® min. (2.7.9)

Таким образом, чтобы найти оптимальную смешанную стратегию первого игрока (т.е. определить компоненты p , р , …, р вектора Р*), необходимо решить задачу линейного программирования.

Пример содержательной постановки задач, сводящихся арбитражной схеме.

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

В соответствии с полученной информацией было установлено, что: П₁=V(1)=600 тыс. руб. - прибыль, которую первая фирма стабильно получает на протяжении последнего времени;

П₂=V(2)=700 тыс. руб. - прибыль, которую вторая фирма стабильно получает на протяжении последнего времени;

П₃=V(3)=900 тыс. руб. - прибыль, которую третья фирма стабильно получает на протяжении последнего времени.

На основании проведенных расчетов стало известно, что:

• при объединении первой и второй фирм их совместная прибыль составит П_1,2=V(1, 2)=1300 тыс. руб.,

• при объединении первой и третьей фирм их совместная прибыль составит П_1,3=V(1, 3)=1500 тыс. руб.,

• при объединении второй и третьей фирм их совместная прибыль составит П_2,3=V(2, 3)=2100 тыс. руб.,

• при объединении первой, второй и третьей фирм их совместная прибыль составит П_1,2,3=V(1, 2, 3) = 2700 тыс. руб.

В рассматриваемой задаче:

• игроками являются фирмы, имеющие намерение объединиться;

• количество участников рассматриваемого неантагонистического конфликта равно трем игрокам (n=3);

• V(S)=П(S), так как значение характеристической функции V определяется той возможной прибылью, которую могут получить транспортные фирмы, образуя различные коалиции S;

• область определения характеристической функции состоит из 2³ возможных подмножеств S.

Докажем, что в рассматриваемой нами игре существует «болван»:

• V(2,1)=V(2Èl)=1300, V(2)+V(1)=700+600=1300, следовательно, V(2Èl)=V(2)+V(l);

• V(3, l)=V(3Èl)=1500, V(3)+V(l)=900+600=1500, следовательно, V(3Èl)=V(3)+V(l);

• V(2,3)=V(2È3), V(2)+V(3)=700+900=1600, следовательно, V(2È3)>V(2)+V(3);

• V(2, 3, l)=V(2È3Èl)=2700, V(2È3)+V(1)=2100+600=2700, следовательно, V(2È3È1)=V(2È3)+V(l).

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

«Носителем» игры в данном случае являются 2-ой и 3-ий игроки, так как Т=N\B.

 

Пример содержательной постановки задач, сводящихся кооперативной игре.

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

• у скрипача - 600 руб.;

• у гитариста - 700 руб.;

• у певицы - 900 руб.

Пробуя увеличить свой заработок, эти студенты в течение нескольких месяцев формировали различные группы. Результаты этих экспериментов показали, что, объединившись, они могут увеличить свои средние заработки за вечер:

· совместное выступление скрипача и гитариста приносит им 1500 руб.;

· совместное выступление скрипача и певицы приносит им 1800 руб.;

· совместное выступление гитариста и певицы приносит им 1900 руб.;

· совместное выступление всех троих - скрипача, гитариста и певицы приносит им 3000 руб.

Необходимо определить, выгодно ли им объединять свои усилия и если да, то на каких условиях? Ответить на этот вопрос можно, применяя формализованный аппарат теории кооперативных игр.

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

В нашем примере n=3, следовательно, область определения характеристической функции состоит из 2³ = 8 возможных подмножеств множества I.

Возможными коалициями S в данном случае могут быть:

· одноэлементные коалиции, т.е. коалиции, состоящие из одного игрока-музыканта: S{1}, S{2}, S{2};

· двухэлементные коалиции: S{1,2}, S{1, 3}, S{2, 3};

· трехэлементная коалиция S{ 1,2,3}.

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

• скрипач - 1-ый игрок;

• гитарист - 2-ой игрок;

• певица - 3-ий игрок.

На основе имеющихся данных определим значения характеристической функции игры V:

V(S{1})=600 руб.; V{S{2})=700 руб.; V(S{3})=900 руб.; эти значения характеристической функции определяются соответственно выигрышами первого, второго и третьего игроков, когда каждый из них выступает в одиночку, не кооперируясь ни с кем из своих друзей-музыкантов;

V(S{1, 2})=1500 руб.; V(S{1, 3})=1800 руб.; V(S{2, 3})=1900 руб.; эти значения характеристической функции определяются средним общим заработком за вечер, который могут обеспечить себе студенты, выступая попарно, т.е. образуя соответствующие парные коалиции (скрипач - гитарист S{1, 2}, скрипач - певица S{1,3}, гитарист - певица S{2, 3});

V(S{1, 2, 3})=3000 руб.; это значение характеристической функции определяется средним общим за вечер заработком, который могут обеспечить себе студенты, выступая втроем, т.е. образуя в данном случае максимально большую коалицию I, состоящую из трех игроков (певицы, скрипача и гитариста).

Число подмножеств, на которых определена характеристическая функция V, равно 2ⁿ=2³=8. Это число в рассматриваемом нами примере складывается из трех одноэлементных коалиций, трех двухэлементных коалиций, одной трехэлементной коалиции и пустого множества, при котором V(Æ)=0.

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

Проиллюстрируем выполнение свойства супераддитивности в рассматриваемом нами примере. Прежде всего определим, каким образом формируются непересекающиеся коалиции S и Т. Если часть игроков из I входит в коалицию S, то все другие игроки образуют коалицию Т, так как по определению эта коалиция формируется как I\S. Соответственно, если S представляет собой одноэлементную коалицию, состоящую из первого игрока, то в коалицию Т войдут второй и третий игроки, если же в коалицию S войдут первый и третий игроки, то коалиция Т будет состоять только из второго игрока, и т.д.

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

V(S{1})+V(S{2, 3})<V(SÈT)=V(I), 600+1900=2500<3000,

V(S{2})+V{S{1, 3})<V(SÈT)=V(I), 700+1800=2500<3000,

V(S{3})+F(S{1, 2})<V{SÈT)=V(I), 900+1500=2400<3000.

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

Наличие свойства супераддитивности говорит о целесообразности объединения игроков с точки зрения увеличения выигрыша.

Определим, является ли рассматриваемая нами игра существенной.

600+700+900=2200, V(I) = 3000,

т.е. выполняется неравенство: V(i), значит, рассматриваемая нами игра является существенной, следовательно, ее решение нужно искать среди множества недоминируемых дележей.

Примеры содержательных постановок задач, сводящихся к антагонистическим играм.

Предположим, что предприятие может выпускать четыре вида продукции: A₁, A₂, A₃, А₄, получая при этом прибыль. Ее величина определяется состоянием спроса, который может находиться в одном из трех возможных состояний: В₁ В₂, B_3.

Таблица 2.8.3 Прибыль предприятия при различных состояниях спроса

Виды продукции	Возможные состояния спроса
В1	В2	B3
A1
А2
А3
А4

Элементы матрицы H¢=||h¢_ij|| характеризуют величину прибыли, которую получит предприятие, если будет выпускать i-й вид продукции (i=1,2,3,4) при j-ом состоянии спроса (j=1,2,3,4).

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

Эта задача может быть сведена к антагонистической игре.

В данном случае в качестве первого игрока выступает предприятие, а в качестве второго - природа, которая влияет на состояние спроса.

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

Выступая в качестве первого игрока, предприятие может использовать четыре стратегии:

• первую чистую стратегию, соответствующую выпуску предприятием только продукции А₁

• вторую чистую стратегию, соответствующую выпуску предприятием только продукции А₂

• третью чистую стратегию, соответствующую выпуску предприятием только продукции А₃,

• четвертую чистую стратегию, соответствующую выпуску предприятием только продукции А₄.

Выступая в качестве второго игрока, природа может использовать три возможные стратегии:

• первую чистую стратегию, при которой реализуется состояние спроса B₁

• вторую чистую стратегию, при которой реализуется состояние спроса В₂;

• третью чистую стратегию, при которой реализуется состояние спроса В₃.

Задана платежная матрица Н¢ этой игры:

H¢=

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

Из проведенного анализа следует, что размерность матрицы H¢ можно уменьшить, убрав из нее четвертую строку, в результате платежная матрица может быть сведена к матрице H:

H=

Проверим, имеет ли данная игра седловую точку. Найдем верхнюю и нижнюю цену игры:V_Ù=max_imin_jh_ij=2, V^Ù=min_jmax_ih_ij=4.

Так как нижняя цена игры не равна верхней, то эта антагонистическая игра не имеет седловой точки, следовательно, ее решение нужно искать в смешанных стратегиях.

Сведем рассматриваемый антагонистический конфликт к прямой и двойственной задаче линейного программирования.

Задача второго игрока Задача первого игрока
Целевая функция
F(x)=x1+х2+x3®max	Z(y)=y1+y2+y3®min
Функциональные ограничения
4х1+2х2+2х3≤1 2x1+5х2≤1 2x2+5х3≤1	4y1+y2≥1 2y1+5y2+2y3≥1 2y1+5y2≥1
Прямые ограничения
x1≥0 x2≥0 x3≥0 y1≥0 y2≥0 y3≥0