Матричные игры. 
Теория игр для математического решения задач

В этом параграфе будет рассказано о принципе максимина, рациональном представлении матрицы игры, о решении игры при помощи фиктивного разыгрывания.

Начнём непосредственно с матричных игр. Тройка (где x и y — множества, H — функция от двух переменных) называется антагонистической игрой. Процесс разыгрывания конечной антагонистической игры (игра называется конечной, если тройка конечна) состоит в том, что игроки 1 и 2 независимо друг от друга выбирают соответственно некоторые чистые стратегии x и y, в результате чего складывается ситуация (x, y).

Мы знаем, что антагонистическую игру двух участников с нулевой суммой (напомним, что нулевая сумма — это когда выигрыш одного игрока равен проигрышу другого) удобно задавать с помощью, так называемой платёжнойматрицы. Каждый элемент такой матрицы содержит числовое значение выигрыша игрока 1 (или проигрыша игрока 2) в ситуации, когда первый игрок применяет стратегию i, а второй — стратегию j. Классическим примером антагонистической игры является игра с двумя участниками, которые независимо друг от друга загадывают числа. Предполагается, что если сумма оказывается чётной, то выигрыш равный 1, достаётся первому игроку, а если нечётной, то второму. Если предположить, что загадывание нечётного числа — стратегия первого игрока, а загадывание чётного числа — стратегия второго игрока, то платёжная матрица выглядит следующим образом:

Строки матрицы соответствуют стратегиям игрока 1, столбцы — стратегиям игрока 2, а её элементы — результатам (т.е. выигрышам) первого. Если взять элементы матрицы с обратным знаком, то это будут выигрыши второго игрока. Здесь надо отметить, что вопрос о выборе стратегии является основным в теории игр. Для примера проанализируем произвольную игру. При выборе игроком 1 стратегии i, его выигрыш в независимости от игрока 2 составит. Стратегия I произвольно, поэтому главная цель игрока 1 максимизировать величину полученного выигрыша, т. е. получить. Такой принцип получил название принципа максимина. Напомним, что максимин — это выигрыш максимальный из минимальных. Надо также отметить, что принцип максимина обеспечивает игрокам гарантированный «выигрыш» при любых стратегиях противников.

Теорема о принципе максимина.

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

Для игры, заданной матрицей выигрышей можно записать следующее равенство.

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

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

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

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

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

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

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

min a (i=).

j.

т.е определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i=i, при которой этот минимальный выигрыш будет максимальным, т. е. находится.

max min a = a = (1).

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

Игрок 2 при оптимальном своем поведении должен стремиться по возможности за счет своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается.

max a.

i.

т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает свою j=j стратегию, при которой игрок 1 получит min выигрыш, т. е. находит.

min max a=a= (2).

j i.

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

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

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

Пример 3: Провести SP-разбиение матрицы игры (Н).

Решение: вычисляем верхнюю и нижнюю цену игры Исходная игра имеет SP (x1,y1) в чистых стратегиях. Существование SP в чистых стратегиях матричной игры с полной информацией позволяет провести SP-разбиение (Н) исходной игры:

Формирование SPразбиения матричной игры с SP по существу и является рациональным представлением исходной матрицы (Н) игры. Значит, понятие рациональности представления матрицы игры преследует цель сформулировать методы рационального преобразования платёжной матрицы с целью вычисления цены игры v или упрощения построения подыгры-решения.

Далее рассмотрим такое понятие, как решение, при помощи фиктивногоразыгрывания. Есть 2 игрока, которые без теории игр, хотят сделать игру несколько раз, причём каждый из них склонен к статистике и оценивает стратегию своего противника. При каждом разыгрывании противоборствующие стороны стремятся максимизировать свой ожидаемый выигрыш против наблюдаемого вероятностного распределения противника: если игрок 2 использует j-ю стратегию раз, то игрок 1 выберет i-ю стратегию, чтобы максимизировать. Аналогично, если игрок 1 использует i-ю стратегию раз, то игрок 2 выберет j-ю стратегию, чтобы минимизировать. Условно эмпирические распределения сходятся к оптимальным стратегиям. Точнее, пусть — число использований первым игроком i-ой стратегии в течение первых N розыгрышей. Пусть, то тогда является смешанной стратегией. Здесь справедливо утверждение о том, что предел любой сходящейся подпоследовательности является оптимальной стратегией, т. е. если и полученные стратегии игроков 1 и 2, то выполняется равенство. Такой метод полезен в случае игры с большим числом стратегий.

Опишем некоторые свойства решений матричных игр. Пусть G (X, Y, A) — игра двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию, а игрок 2 —, после чего игрок 1 получает выигрыш A=A (x, y) за счёт игрока 2.

Свойство 1: Если чистая стратегия одного из игроков содержится в спектре (спектр — множество чистых стратегий, вероятность которых положительна) некоторой его оптимальной стратегии, то выигрыш этого игрока в ситуации, образованной данной стратегией и любой оптимальной стратегией другого игрока, равен значению конечной антагонистической игры.

Свойство 2: Ни одна доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии.

Свойство 3: Если — конечная антагонистическая игра, а, подыгра игры G причём — чистая стратегия игрока 1 в игре G, доминируемая над некоторой стратегией, спектр которой не содержит. Тогда всякое решение игры является решением игры G.

Свойство 4: Тройка является решением игры, когда является решением игры, где, а — любое вещественное число, к>0.