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

• Название: Учебное пособие по курсам Теория игр и исследование операций, Теория принятия решений
• Анкор: Теоретико-игровые методы принятия решений (Еремеев А. П.).doc
• Дата: 27.03.2018
• Размер: 1.18 Mb.
• Имя файла: Теоретико-игровые методы принятия решений (Еремеев А. П.).doc
• Тип: Учебное пособие; #17282
• Категория: Математика
• страница: 6 из 15

3.3.Методы решения матричных игр
при отсутствии седловой точки

3.3.1.Смешанные стратегии

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

,

где p_iиq_j – вероятности выбора стратегий A_iиB_j игроками A и Bсоответственно. Решением игры в данном случае является пара оптимальных смешанных стратегий (S_A^*,S_B^*), максимизирующих математическое ожидание цены игры (средний выигрыш).

Теорема 3.2 [6]. Любая антагонистическая игра имеет хотя бы одно оптимальное решение, т.е., пару в общем случае смешанных стратегий (S_A^*,S_B^*), дающих игроку А устойчивый выигрыш, равный цене игры V,α ≤ V ≤ β.

Чистую стратегию можно рассматривать как частный случай смешанной стратегии, когда одна вероятность имеет единичное значение, а все остальные – нулевое.

Рассмотрим матричную игру G(mn), не имеющую седловой точки, для которой необходимо найти решение – пару оптимальных смешанных стратегий S_A=(p₁, p₂, …, p_m)и S_B=(q₁,q₂, …, q_n) и соответствующую цену игры V.

Предварительно следует попытаться упростить матрицу игры. Для этого вводятся отношения предпочтения (доминирования) и безразличия (дублирования) на множестве стратегий.

Определение 3.3:

• 
  стратегия A_i предпочтительнее стратегии A_k (доминирует A_k) (обозначается ), если все выигрыши, указанные в i-й строке матрицы игры, не меньше соответствующих выигрышей k-й строки, или формально ;
  
• 
  стратегии A_i и A_k находятся в отношении безразличия (дублирования) (обозначается A_iA_k), если все выигрыши, указанные в i-й строке матрицы игры, совпадают с соответствующими выигрышами k-й строки, или формально ;
  
• 
  стратегия B_j предпочтительнее стратегии B_r (доминирует B_r) (обозначается ), если все выигрыши, указанные в j-м столбце матрицы игры, не меньше соответствующих выигрышей r-го столбца, или формально ;
  
• 
  отношение безразличия для стратегий игрока B вводится аналогично игроку A, т.е. .
  

Можно доказать следующую лемму [5].

Лемма 3.2. Для игры G(mn)число активных стратегий игроков равно min{m,n}. Другими словами, если, например, m>n, то в оптимальной стратегии S_A=(p₁, p₂, …, p_m) игрока A будет не более n отличных от нуля вероятностей p_i.

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

Рассмотрим данный этап на примере матричной игры G(55), представленной табл. 3.7.

Таблица 3.8

Bj Ai	B1	B2	B3	B4	B5
A1	4	7	2	3	4
A2	3	5	6	8	9
A3	4	4	2	2	8
A4	3	6	1	2	4
A5	3	5	6	8	9

Так как справедливы соотношения , , , , , то удалим доминируемые и дублируемые стратегии A₄,A₅,B₂,B₄,B₅.

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

Таблица 3.9

Bj Ai	B1	B3
A1	4	2
A2	3	6

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

После упрощения игры следующим (основным) этапом является поиск оптимального решения в виде смешанных стратегий (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

Bj Ai	B1	B2
A1	a11	a12
A2	a21	a22

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

Bj Ai	B1	B2	B3
A1	a11	a12	a13
A2	a21	a22	a23
A3	a31	a32	a33

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



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



.

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



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


Обозначив

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, , ,

где V – цена игры, N_iи N_j – число применений соответственно стратегий А_iи B_jзаk партий, p_iи q_j– значения вероятностей в оптимальных стратегиях S_A=(p_i),i=1, …, m,S_B=(q_j),j=1, …, n,игроков A и Bсоответственно.

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

Таблица 3.13

Bj Ai	B1	B2	B3
A1	7	2	9
A2	2	9	0
A3	9	0	11

Требуется найти решение – пару оптимальных смешанных стратегий (S_A,S_B), S_A=(p₁, p₂, p₃),S_B=(q₁, q₂, q₃), и цену игры V.

Будем искать пару смешанных стратегий S_A=(p₁, p₂, p₃),p₁ + p₂ + p₃ = 1,S_B=(q₁, q₂, q₃),q₁ + q₂ + q₃ = 1 и цену игры V.

Построим табл. 3.13 для первых десяти итераций.

Таблица 3.14

k	i	B1	B2	B3	j	A1	A2	A3	V	V	V*
1	3	9	0	11	2	2	9	0	0	9	4,5
2	2	11	9	11	2	4	18	0	4,5	9	6,75
3	2	13	18	11	3	13	18	11	3,67	6	4,84
4	2	15	27	11	4	22	18	22	2,75	5,5	4,13
5	1	22	29	20	3	31	18	33	4,0	6,6	5,3
6	3	31	29	31	2	33	27	33	4,84	5,5	5,17
7	1	38	31	40	2	35	36	33	4,43	5,14	4,79
8	2	40	40	40	2	37	45	33	5,0	5,61	5,30
9	2	42	49	40	3	46	45	44	4,45	5,11	4,78
10	1	49	51	49	1	53	47	53	4,90	5,30	5,1

Поясним процесс заполнения табл. 3.13.

Пусть начинает (k=1) игрок A и выбирает на первом шаге стратегию А₁. Его выигрыш в зависимости от выбора игрока B может равняться 9 (при выборе стратегии B₁), 0 (при выборе B₂) или 11 (при выборе B₃). Поскольку теперь выбор за игроком B (а он заинтересован в минимизации выигрыша игрока A), то выделим (жирным шрифтом) минимальный выигрыш 0, соответствующий стратегии B₂. Следовательно игроку B выгоднее всего ответить стратегией B₂, что, в свою очередь, может привести к выигрышу игрока A при его ответе в следующей партии, равному 2 (при выборе стратегии A₁), 9 (A₂) или 0 (A₃). Так как игрок A заинтересован в максимизации выигрыша, то выделим максимальный выигрыш 9 (для A₂). Соответствующие значения V, и V^* равны 0; 9 и 4,5.

Во второй партии (k=2) игроку A,следовательно,выгодно выбратьстратегиюA₂,которая позволит ему накопить выигрыш, равный соответственно 11 (для B₁), 9 (для B₂) или 11 (для B₃) и т.д. Заметим, что для k=4в столбцах А₁и А₃ получаются одинаковые накопленные выигрыши (22), поэтому игрок Aв пятой партии может выбрать как стратегию А₁, так и А₃.

К сожалению (что видно и по табл. 3.12), сходимость данного метода довольно слабая, но существуют методы ее ускорения. Критерием останова можно выбрать достаточную стабильность величины V^* при увеличении числа итераций.

Для рассматриваемого примера в итоге получим:

и , что соответствует точному решению, полученному, например, методом Лагранжа.

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