Решение матричных игр 2 x n и m x 2 графоаналитическим методом
Наибольшее распространение в технических приложениях имеют парные стратегические бескоалиционные конечные некооперативные игры. Модель проблемной ситуации в этом случае имеет вид: < U, V, W1, W2, R1, R2 >, где U - множество стратегий оперирующей стороны (конструктора); V - множество стратегий оппонирующей стороны (технолог и природа); W1 и W2 - показатели качества игроков; R1 и R2 - системы предпочтения игроков. Системы предпочтения игроков, в свою очередь, основываются на двух ведущих принципах рационального поведения: принципе наибольшего гарантированного результата и принципе равновесия. Первый основан на том, что рациональным выбором одного из игроков должен считаться такой, при котором он рассчитывает на самую неблагоприятную для него реакцию со стороны другого игрока. Второй принцип гласит, что рациональным выбором любого игрока считается такая стратегия u$ (или v$), для которой ситуация (u$, v$) обоюдовыгодна, т.е. любое отклонение от данной ситуации игры не является выгодным ни для одного из игроков. По характеру выигрышей игры делятся на: · игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) · игры с ненулевой суммой. Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 (первого игрока) в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2 (второго игрока), столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям). Для матричных игр доказано, что любая из них имеет решение, и оно может быть легко найдено путём сведения игры к задаче линейного программирования. Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков. Первый игрок имеет m стратегий i = 1, 2,..., m, второй имеет n стратегий j = 1, 2,..., n. Каждой паре стратегий (i, j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.
Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i= Каждая стратегия игрока i= Если рассмотреть матрицу A:
то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij. Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i =
т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = iо, при которой этот минимальный выигрыш будет максимальным, т.е. находится
Определение. Число Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается
т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1 стратегию, при которой игрок 1 получит min выигрыш, т.е. находит
Определение. Число Другими словами, применяя свои чистые стратегии игрок 1 может обеспечить себе выигрыш не меньше Определение. Если в игре с матрицей А
Седловая точка – это пара чистых стратегий (iо, jо) соответственно игроков 1 и 2, при которых достигается равенство В общем случае игра 2
(3) Прежде всего необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причём оптимальными стратегиями игроков 1 и 2 соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет чистых стратегий, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями. Пусть Х = (p, 1-p) – оптимальная стратегия игрока 1, где p – можно рассматривать как частоту (вероятность) использования стратегии A1 первым игроком, a (1- p) – частота (вероятность) использования стратегии А2 первым игроком. Так как игрок 2 имеет смешанную оптимальную стратегию, то:
Отсюда следует, что при u ¹ 0 столбцы матрицы А не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Если же коэффициент пропорциональности равен единице, то матрица А принимает вид и игрок 1 имеет чистую оптимальную стратегию (он выбирает с вероятностью 1 ту из строк, элементы которой не меньше соответствующих элементов другой), что противоречит предположению. Следовательно, если u ¹ 0 и игроки имеют только смешанные оптимальные стратегии, то определитель матрицы А отличен от нуля. Из этого следует, что последняя система уравнений имеет единственное решение. Решая её, находим:
Тогда подставив, (6) в (4) можно получить выражение для цены игры:
Аналогичные рассуждения приводят нас к тому, что оптимальная стратегия игрока 2 (второго игрока) Y = (q, 1- q), где q – можно рассматривать как частоту (вероятность) использования стратегии B1 вторым игроком, а (1- q) – частота (вероятность) использования стратегии B2 вторым игроком. Тогда имеем:
Откуда
Поясним графический метод решения матричных игр на примерах.
|
), 2 – свою j-ю стратегию (j= 
), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij< 0, то это значит, что игрок 1 платит второму сумму | аij|). На этом игра заканчивается.
; j = 
(1)
, определённое по формуле (1) называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.
(2)
, определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.
, то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры:
2 определяется матрицей A:
(4)
(5)
(6)
(7)
(8)
(9)
