Решение матричной игры путем ее сведения к задачам линейного программирования

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

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

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

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

где X > 0, а р — любое вещественное число, имеют одинаковые равновесные ситуации (либо в чистых, либо в смешанных стратегиях), а цены игр удовлетворяют следующему условию: v_B = Xv_A + р.

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

Будем считать, что цена игры с платежной матрицей А_тХп положительна (и > 0). Если это не так, то согласно аффинному правилу всегда можно подобрать такое число р, прибавление которого ко всем элементам платежной матрицы дает матрицу с положительными элементами и, следовательно, обеспечивает положительное значение цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.

Из определения оптимальной смешанной стратегии следует, что первый игрок, придерживающийся своей оптимальной смешанной стратегии, выиграет не меньше о при любых стратегиях второго игрока (в том числе чистых), а второй игрок, придерживающийся своей оптимальной смешанной стратегии, проиграет не больше о при любых стратегиях первого игрока (в том числе чистых). Из этого следует, что смешанные стратегии х = = (x_v х_т), у = (y_v …, у_п) соответственно первого и второго игроков и цена игры о должны удовлетворять соотношениям.

Разделим все уравнения и неравенства в данных системах на и (это можно сделать, так как по предположению о > 0) и введем обозначения:

Тогда получаем.

Поскольку первый игрок стремится максимизировать цену игры о выбором значений х_[у то обратная величина 1/о должна минимизироваться выбором р_г Таким образом, решение первой задачи сводится к нахождению таких неотрицательных значений р., 2=1,…, т_у при которых.

Поскольку второй игрок стремится найти такие значения у_} и, следовательно, q_y чтобы цена игры и была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений q_jy j = 1, …, п_у при которых

Таким образом, получены двойственные друг другу задачи линейного программирования (ЛП), которые можно решить, например, симплекс-методом.

Решив эти задачи, получим значения р®, i = 1,т_у q®_yj = 1,…, п.

Тогда значение цены игры о определяется из условия.

Оптимальные смешанные стратегии, т. е. х® и г/?, получаются по формулам.

Пример 4.7. Рассмотрим вариант игры «Борьба за рынки». Две конкурирующие компании, А и Б принимают решение о финансировании трех инновационных технических проектов. Каждая из компаний может инвестировать 100 дсн. ед. Компания Б пытается занять рынок, на котором традиционно компания, А лидирует. В случае разработки и развития одних и тех же проектов компания, А получит прибыль, тогда как компания Б понесет убытки. Если инвестиции направляются в разные проекты, компания, А понесет убытки, связанные с перераспределением рынка, а прибыль предприятия Б будет соответствовать убытку предприятия А. Необходимо найти оптимальные стратегии предприятий. Прибыль предприятия, А при разных стратегических ситуациях представлена в таблице:

Решение в MS Excel

Решим задачу с помощью программы MS Excel. В таблицу MS Excel вводятся элементы платежной матрицы игры и с помощью функций МИН () и МАКС () определяются минимальные и максимальные значения по строкам и столбцам соответственно, затем с помощью этих же функций находятся максимин и минимакс (табл. 4.2). Поскольку эти значения не совпадают, седловой точки в игре нет, г. е. в чистых стратегиях она не решается. Значение цены игры должно лежать в диапазоне (-5; 10).

Таблица 4.2

Проверка наличия седловой точки в игре.

Для использования алгоритма решения игры путем ее сведения к задаче линейного программирования применим аффинное правило. С помощью функции МИН () находим минимальное значение элементов платежной матрицы (-20). Модуль этого числа определяется как ABS (MHH (…)). С помощью аффинного преобразования с параметрами X = 1 и р = 20 получим новую платежную матрица (табл. 4.3).

Таблица 4.3

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

Справа от платежной матрицы произвольно указываются искомые переменные р. (на этом этапе могут указываться любые значения). В ячейках под платежной матрицей с помощью функции СУММПРОИЗВ () определяются значения.

которые будут использоваться в ограничениях задачи ЛИ. Эти значения для произвольно выбранных p_t приведены в табл. 4.3.

В ячейке, обозначенной как «Целевая функция», вводится формула СУММ (…), соответствующая выражению для целевой функции.

В ячейке, обозначенной как «Цена игры», вводится формула для определения цены игры через значение целевой функции:

В ячейках, обозначенных как x_it вводятся формулы для обратного преобразования переменных и нахождения искомых элементов смешанной стратегии первого игрока x_i = u Pj.

Формулировка первой задачи линейного программирования: найти значе;

т т

ни я Р'_У обеспечивающие минимум функции YjPi * пип при условиях ^ a_ijp_i > 1,.

i-1 i=1.

Pi> 0.

Решение задачи линейного программирования осуществляется с помощью модуля «Поиск решения» программы MS Excel (применение этого модуля уже рассматривалось в гл. 2). В поле «Установить целевую ячейку» указывается адрес ячейки, содержащей значение целевой функции; выбирается режим «Равной: минимальному значению». В поле «Изменяя ячейки» указывается массив искомых переменных р_г Нажатием кнопки «Добавить» и выбором массива, соответствующего ограничениям задачи, в поле «Ограничения» устанавливается соответствующее условие. Нажатием кнопки «Параметры» осуществляется переход в диалоговое окно «Параметры поиска решения», в котором выбираются параметры «Линейная модель» и «Неотрицательные значения»; значения остальных параметров остаются без изменений. После закрытия окна «Параметры поиска решения» (кнопкой ОК) нажатием кнопки «Выполнить» в окне «Поиск решения» осуществляется запуск итерационного процесса поиска решения задачи ЛП.

По окончании этого процесса появляется окно «Результаты поиска решения». Если все условия задачи были сформулированы правильно, все данные, формулы и параметры введены корректно, то в окне будет указано «Решение найдено. Все ограничения и условия оптимальности выполнены». В этом случае для сохранения решения нужно нажать ОК. Результаты расчетов представлены в табл. 4.4.

Аналогично решается задача ЛП для второго игрока (табл. 4.5). Обратите внимание, что в данном случае для технического удобства массив искомых переменных расположен в строку (поскольку стратегии второго игрока соответствуют столбцам платежной матрицы), а ячейки с ограничениями — в столбец. Задача решается на максимум и формулируется так: найти значения q_jt

п п

обеспечивающие максимум функции? Я) * ^{тах П}Р^И условиях ^ a_i}q- < 1, q_} > 0.

j-1 ;=i.

Таблица 4.4

Результаты решения задачи ЛП для первого игрока.

Результаты решения задачи ЛП для второго игрока.

Таблица 4.5

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

Результаты показывают, что оптимальной стратегией компании, А является распределение средств, предполагаемых к инвестированию, в пропорции 29, 60 и 11%, т. е. 29, 60 и 11 ден. ед. При этом компания, А получит прибыль не менее 0,5 ден. ед. Минимальное значение прибыли (0,5 ден. ед.) компания, А получит при условии, что компания Б будет придерживаться своей оптимальной стратегии инвестирования проектов, а именно 39, 25, 36%, т. е. инвестировать в проекты 39, 25 и 36 ден. ед. соответственно. Если компания Б будет отклоняться от этой стратегии (придерживаться другой схемы инвестирования), прибыль компании, А будет расти.

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

Таким образом, решение любой матричной игры может быть осуществлено приведением игры к двум задачам линейного программирования. Однако это требует большого объема вычислений, который растет с увеличением числа чистых стратегий игроков. Поэтому в первую очередь следует, по возможности используя метод исключения доминируемых стратегий, уменьшить число чистых стратегий игроков. Исключение слабо доминируемых стратегий может привести к потере некоторых решений. Если же исключаются только сильно доминируемые стратегии, то множество решений игры не изменится. Затем следует во всех случаях проверить наличие седловой точки, т. е. выполнение условия шах min а- = min ma ха…

/ j j i

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

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