5.4.2. Метод последовательных приближений

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

Табл.5.4.2-1. Метод последовательных приближений для игры 3×3.

N	i(N)	l1(N)	l2(N)	l3(N)	v1(N)	j(N)	u1(N)	u2(N)	u3(N)	v2(N)	v1(N)- v2(N)

При методе последовательных приближений все расчеты заносят­ся в таблицу. Для случая игры 3x3 эта таблица составляется следующим образом (табл.5.4.2-1). В первую колонку вносится номер партии, во вторую — номер i(N) чистой стратегии игрока А в N-й партии, в третью — общий платеж l₁(N) игроку А после N партий, если игрок В применяет все время стратегию с₁. Аналогично определяют l₂(N) и l₃(N); v₁(N) – наименьший средний выигрыш игрока А после N партий; j(N) – номер чистой стратегии игрока В в N-й партии; u₁(N) – общий платеж игроку А после N партий, если игрок А все время применяет стратегию k₁.

Аналогично определяются стратегии u₂(N) и u₃(N); v₂(N) – наибольший средний выигрыш игрока А после N партий.

.

Игрок А в первой партии выбирает стратегию k₁. Правило выбора стратегий j(N) и i(N) на каждом шаге может быть записано следующим образом:

j(N) выбирается так, чтобы оно было наимень­шим целым, при котором

,

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

i (N) выбирается наименьшим целым числом, при котором

.

т. е. перед очередным шагом игрок А делает возможный перебор стратегий и ходит так, чтобы на данном шаге получить максималь­ный платеж. Здесь вместо (N) стоит (N-1), так как вначале хо­дит игрок А, потом игрок В, и первые перед N-м ходом имеют N-1 партий, а вторые – N партий для анализа; u_j(N) вычисляют по формуле

Цена игры приближенно определяется по формуле

,

где

[ Кузин 15к]

5.4.3. Решение матричных игр методами линейного программирования

Теория игр находится в тесной связи с линейным программированием, так как любую конечную иг­ру двух лиц с нулевой суммой можно представить в виде задачи линейного программи­рования и наоборот. Дж. Данциг [2] отмечает, что когда в 1947 году создатель теории игр Дж. фон Нейман впервые ознакомился с симплекс-методом, он сразу установил эту взаимосвязь и обратил особое внимание на концепцию двойственности в линейном про­граммировании. Этот раздел иллюстрирует решение матричных игр методами линейного программирования.

Оптимальные значения вероятностей x_i, i = 1, 2, ..., m, игрока А могут быть определе­ны путем решения следующей максиминной задачи.

,

Чтобы сформулировать эту задачу в виде задачи линейного программирования, положим

Отсюда вытекает, что

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

Максимизировать z = v

при ограничениях

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

Оптимальные стратегии у₁,у₂,…, y_n игрока В определяются путем решения задачи

,

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

Максимизировать w = v

при ограничениях

Две полученные задачи оптимизируют одну и ту же (не ограниченную в знаке) переменную v, которая является ценой игры. Причиной этого является то, что задача игрока В является двойственной к задаче игрока А. Это означает, что оптимальное решение одной из задач автоматически определяет оптимальное решение другой.

Пример 5.4.3-1.

Рассмотрим пример решения матричной игры методом линейного программирования. Вернемся к примеру игры двух участников с нулевой суммой, платежная матрица которой приведена на рис.5.3.1-2:

.

Эта игра не имеет седловой точки, поэтому решение игры следует искать в смешанных стратегиях. Значение цены игры должно находится между -2 (минимум строк) и 4 (максимум столбцов).

Задача линейного программирования для игрока А.

Максимизировать z = v

при ограничениях

Из системы ограничений можно исключить переменную x₂ и перейти к задаче с двумя оптимизируемыми переменными z и v.

Максимизировать z = v

при ограничениях

На рис.5.4.3-1 приведен графический способ решения задачи линейного программирования. Цифрами обозначены графики линейных функций, представляющих собой границы областей, в пределах которых выполняются соответствующие ограничения-неравенства. Стрелками показаны направления внутрь областей.

v

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

Задача линейного программирования для игрока А.

Максимизировать z = v

при ограничениях

Для решения сформулированной задачи линейного программирования воспользуемся системой компьютерной математики Mathcad. Встроенная функция Minimize реализует достаточно универсальный алгоритм оптимизации не требующий вычисления производных. На рис.5.4.3-2 приведено решение поставленной задачи с соответствующим описанием ее постановки.

Оптимальным решением, полученным с помощью программы, является смешанная стратегия y₁ = 0,412, y₂= 0,588, y₃ = 0. Ей соответствует цена игры v = 1,294, т.е. решения полученные игроком А и игроком В дают одинаковую цену игры, что соответствует теореме о минимаксе. Кроме того известно, что в игре 2×n каждый из участников может располагать не более чем двумя активными стратегиями. Равенство нулю вероятности y₃ означает, что третья стратегия не является активной и участнику В не следует использовать ее в данной игре. Последний результат подтверждается и графическим решением задачи линейного программирования для игрока А: точка максимума целевой функции не принадлежит прямой (3), соответствующей третей чистой стратегии игрока В.

27