Теоретико-игровые методы принятия решений (Еремеев А. П.) (545581), страница 4

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

Текст из файла (страница 4)

В полученной матрице снова проведём удаление, так как . Получим упрощенную игру G(22), представленную табл. 3.8.

Таблица 3.9

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

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

3.3.2.Метод Лагранжа

Метод Лагранжа относится к точным методам решения матричных игр G(mm), т.е. имеющим квадратные матрицы (или приведенные к такому виду после упрощения).

Допустим, что игрок A использует смешанную стратегию S_A = (p₁, …, p_m), а игрок B отвечает своей чистой стратегией B_i (i = 1, 2, …, m). Цена игры в таком случае равна . Если же игрок B также будет применять смешанную стратегию S_B = (q₁, …, q_m), то итоговая цена игры будет равна

. (3.1)

Для нахождения оптимального решения необходимо максимизировать значение V при ограничениях .

Составим функцию Лагранжа L = V + ₁(p₁ + … + p_m – 1) + ₂(q₁ + … + q_m – 1) и приравняем к нулю частные производные по всем аргументам: .

В результате получим следующую систему из (2m + 2) уравнений с (2m + 2) неизвестными:

Решение этой системы и даёт смешанные стратегии для обоих игроков.

Нетрудно заметить, что исходная система уравнений включает две независимые подсистемы (для p_i, i = 1, …, m, ₁ и q_j, j = 1, …, m, ₂ соответственно), состоящие из (m + 1) уравнений с (m + 1) неизвестными, решение которых и даст искомые вероятности p_i и q_j, а также после подстановки этих вероятностей в формулу (3.1) цену игры V.

В качестве примера рассмотрим игру G(22), представленную в общем виде табл. 3.9.

Таблица 3.10

V₁ = a₁₁p₁ + a₂₁p₂, V₂ = a₁₂p₁ + a₂₂p₂,

V = V₁q₁ + V₂q₂ = (a₁₁p₁ + a₂₁p₂)q₁ + (a₁₂p₁ + a₂₂p₂)q₂.

L = V + ₁(p₁ + p₂ – 1) + ₂(q₁ + q₂ – 1).

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

Решив данную систему получим следующие значения вероятностей:

.

Подставив полученные значения в выражение для V, получим цену игры.

Например, для игры G(22), представленной табл. 3.8, получим:

p₁ = 0,6; p₂ = 0,4; q₁ = 0,8; q₃ = 0,2; V = 3,6.

Можно также найти решение в общем виде для игры G(33) и т.д.

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

Рассмотрим игру игры G(33) в общем виде, представленную табл. 3.10.

Таблица 3.11

Для нахождения решения в смешанных стратегиях необходимо решить следующую систему уравнений:

Эту систему можно представить следующим образом:

.

Решением в общем виде представляется системой

Более конкретно:

Обозначив

k = – a₁₁a₂₂ + a₁₁a₃₂ + a₁₁a₂₃ – a₁₁a₃₃ + a₂₁a₁₂ – a₂₁a₃₂ –

– a₂₁a₁₃ + a₂₁a₃₃ – a₃₁a₁₂ + a₃₁a₂₂ + a₃₁a₁₃ – a₃₁a₂₃ –

– a₁₂a₂₃ + a₁₂a₃₃ + a₂₂a₁₃ – a₂₂a₃₃ – a₃₂a₁₃ + a₃₂a₂₃,

получим итоговое решение:

p₁ = (– a₂₁a₃₂ + a₂₁a₃₃ + a₃₁a₂₂ – a₃₁a₂₃ – a₂₂a₃₃ + a₃₂a₂₃) / k

p₂ = ( a₁₁a₃₂ – a₁₁a₃₃ – a₃₁a₁₂ + a₃₁a₁₃ + a₁₂a₃₃ – a₃₂a₁₃) / k

p₃ = (– a₁₁a₂₂ + a₁₁a₂₃ + a₂₁a₁₂ – a₂₁a₁₃ – a₁₂a₂₃ + a₂₂a₁₃) / k

q₁ = (– a₁₂a₂₃ + a₁₂a₃₃ + a₂₂a₁₃ – a₂₂a₃₃ – a₃₂a₁₃ + a₃₂a₂₃) / k

q₂ = ( a₁₁a₂₃ – a₁₁a₃₃ – a₂₁a₁₃ + a₂₁a₃₃ + a₃₁a₁₃ – a₃₁a₂₃) / k

q₃ = (– a₁₁a₂₂ + a₁₁a₃₂ + a₂₁a₁₂ – a₂₁a₃₂ – a₃₁a₁₂ + a₃₁a₂₂) / k

V = – |A| / |A1|,

где А — исходная матрица игры.

Данный подход легко применим для произвольной игры G(mm): строится матрица A1, далее, используя определители, записываются выражения для p_i и q_j, множитель знака для них будет равен (–1)^{m + i + 1}.

3.3.3.Метод линейного программирования

Данный метод также относится к точным методам решения матричных игр и применим к игре G(mn) при условии, что все элементы матрицы игры a_ij, i = 1, …, m, j = 1, …, n, положительны (этого легко добиться прибавлением ко всем элементам матрицы положительной константы, большей, чем модуль наименьшего отрицательного элемента или нуля, если отрицательных элементов нет).

Рассмотрим ситуацию, когда игрок A применяет свою оптимальную смешанную стратегию, а игрок B последовательно отвечает своими чистыми стратегиями B₁, …, B_n. Поскольку оптимальные стратегии обладают свойством устойчивости, то справедлива следующая система неравенств:

(3.2)

Введем новые переменные:

.

Система неравенств (3.2) теперь примет вид:

(3.3)

Так целью игры для игрока A является максимизация цены игры V, то получаем задачу линейного программирования:

при системе ограничений (3.3).

Решив эту задачу, найдем цену игры V и вероятности p_i в оптимальной смешанной стратегии S_A = (p_i), i = 1,…,m, игрока A:

.

Аналогичные построения проводятся и для игрока B, учитывая, что целью игрока B является минимизация цены игры V.

В итоге получим следующую задачу линейного программирования:

при системе ограничений

.

Решив данную задачу, найдем вероятности q_j в оптимальной смешанной стратегии S_B = (q_j), j = 1, …, n, игрока B.

В [5] доказано, что сформулированные задачи являются двойственными задачами линейного программирования, т.е. минимум линейной формы для одной из них совпадает с максимумом для другой. Для решения данных задач можно использовать, например, симплекс-метод.

3.3.4.Итерационный метод Брауна-Робинсона

Также универсальным, но менее трудоемким по сравнению с методом линейного программирования в плане затрат вычислительных ресурсов является приближенный метод Брауна-Робинсона. Данный итерационный метод предназначен для решения любой игры G(mn), не требуя никаких ограничений на элементы матрицы игры.

Метод базируется на многократном разыгрывании игры и подсчете верхней и нижней оценок цены игры с занесением результатов в таблицу специального вида (табл. 3.11):

Таблица 3.12

k	i	B1	…	Bn	j	A1	…	Am	V		V*

Каждая строка таблицы соответствует однократному розыгрышу игры (партии игры).

Поясним записи в соответствующих позициях:

• k — номер партии (итерации);

• i и j — номера стратегий, выбранных соответственно игроками A и B в данной партии;

• B_1, …, B_n — накопленный за k партий выигрыш игрока A при выборе им стратегии A_i в данной партии и ответе игроком B соответственно стратегиями B_1, …, B_n;

• A_1, …, A_m — накопленный за k партий выигрыш игрока A при выборе игроком B стратегии B_j в данной партии и ответе игроком A соответственно стратегиями A_1, …, A_m;

• V —нижняя оценка цены игры (минимальный накопленный выигрыш, поделенный на k);

• — верхняя оценка цены игры (максимальный накопленный выигрыш, поделенный на k);

• .

В [6] доказано, что при k  : V^* V, , ,

Характеристики

Список файлов книги