Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TIIO_conspect_Lemeshko.docx
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
1 Мб
Скачать
☆

2.8. Вычисление оптимальных стратегий

Теорема о минимаксе гарантирует, что каждая антагонистическая

игра имеет оптимальные стратегии. Она даѐт существование, но не опре-

деляет, как искать эти оптимальные стратегии.

1. Простейшим является тот случай, когда существует седловая точка, т.е.

когда существует элемент aij , являющийся максимальным в своѐм столбце

и минимальным в своей строке. Тогда чистые стратегии i и j (или, что рав-

носильно, смешанные стратегии x и y , для которых xi =1, y j =1, а все ос-

тальные компоненты равны нулю) будут оптимальными стратегиями для

игроков 1 и 2 соответственно.

2. Доминирование. Пусть дана матрица A . Будем говорить, что i-я строка

доминирует k-ю строку, если aij

akj,

j и aij

ak j по крайней мере для

одного j.

Аналогично, будем говорить, что j-й столбец доминирует l-й стол-

бец, если aij

ail ,

i и aij

ail по крайней мере для одного i.

36

Короче говоря, одна чистая стратегия (представленная своей строкой

или столбцом) доминирует другую чистую стратегию, если выбор первой

(доминирующей) стратегии, по крайней мере, не хуже выбора второй (до-

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

Отсюда следует, что игрок всегда может обойтись без доминируе-

мых стратегий и использовать только недоминируемые стратегии.

Теорема. (Без доказательства) Пусть A – матричная игра, и пусть

строки i1 , i2 ,…, ik матрицы доминируются. Тогда игрок 1 имеет такую оп-

тимальную стратегию x , что xi1 = xi2 =…= xik =...=0. Кроме того, любая оп-

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

минируемых строк, будет также оптимальной стратегией для первоначаль-

ной игры.

Аналогичная теорема справедлива и для доминирования столбцов.

Общий результат этих теорем состоит в том, что все доминируемые строки

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

меньшей матрицей.

Пример 2.7. Рассмотрим игру с матрицей

2 0 1 4

1 2 5 3 .

4 1 3 2

Второй столбец доминирует 4-й. Следовательно, игрок 2 никогда не будет

использовать свою 4-ю стратегию. Поэтому на неѐ можно не обращать

внимания и рассматривать матрицу

2 0 1

1 2 5 .

4 1 3

В ней 3-я строка доминирует 1-ю. Удаляя 1-ю строку, получаем

1 2 5

4 1 3

.

В ней 3-й столбец доминируется 2-м. Следовательно, исходная игра сво-

дится к игре с матрицей

1 2

4 1

.

И нужно искать оптимальные стратегии для игры 2 2.

37

3. Игры (2 2). Пусть дана матричная игра 2×2 с платежной матрицей

a11 a12

a21 a22

. Если есть седловая точка, то всѐ определено. Если нет, то оп-

тимальные стратегии x

( x1, x2 ) и y

( y1, y2 ) имеют положительные

компоненты xi

0 , yi

0 .

т.е.

Если значение игры – v , это для оптимальных стратегий xAy T

v ,

a11 x1 y1

a12 x1 y2

a21 x2 y1

a22 x2 y2

v .

Преобразуем

x1(a11 y1

a12 y2 )

x2 (a21 y1

a22 y2 )

v

(*)

Так как y оптимальная стратегия, то должно выполняться:

a11 y1

a21 y1

a12 y2

a22 y2

v ,

v .

Допустим, что одно из выражений меньше v :

a11 y1

a21 y1

a12 y2

a22 y2

v

v .

Так как x1

0 , x1

x2

1, то левая часть (*) будет меньше правой. Отсю-

да следует, что должно быть

a11 y1

a21 y1

a12 y2

a22 y2

v ,

v .

Аналогично можно показать:

a11 x1 a21 x2 v ,

a12 x1 a22 x2 v .

Из этих уравнений, с учѐтом того, что x1

x2

1, y1

y2

1 легко

найти стратегии обоих игроков.

4. Симметричные игры. Квадратичная матрица A называется кососим-

метрической, если aij

a ji , i, j. Матричная игра называется симмет-

ричной , если еѐ матрица кососимметрическая.

Теорема. Значение симметричной игры равно нулю. Кроме того, ес-

ли x есть оптимальная стратегия для игрока 1, то x есть также оптималь-

ная стратегия для игрока 2.

Доказательство: Пусть A

стратегия. Легко видеть, что A

матрица игры и x

AT .

произвольная

Следовательно,

xAx T

xAT xT

(xAx T )T

xAx T .

Поэтому

xAx T

0.

38

Отсюда следует, что для любого x min xAy T

y

0 , так что значение

игры неположительно. В то же время max yAx T

y

0 , так что значение иг-

ры неотрицательно. Следовательно, значение игры равно нулю.

Далее, если x – оптимальная стратегия игрока 1, то

xA 0

(из xA

v ).

Но отсюда x( AT )

0 , так что xAT

0.

Значит, стратегия x оптимальна также и для игрока 2.

5. Решение антагонистических игр в общем случае. На основании тео-

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

m

xi aij

v , j 1,2,..., n; где v – значение игры, является оптимальной

i 1

для 1-го игрока. Т.е. не существует другой стратегии, которая дала бы ему

больший ожидаемый выигрыш, чем v , против каждой стратегии игрока 2.

Таким образом, игру с точки зрения 1-го игрока можно записать как

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

v

m

max ;

i 1

m

xi aij

v , j 1, n;

xi 1; xi

0 ; i 1, m.

i 1

Причѐм v рассматривается как m+1-я переменная, неограниченная по зна-

ку (свободная).

С другой стороны, 2-й игрок стремится минимизировать значение

игры:

v

n

min ;

j 1

n

aij y j

v , i 1, m;

y j

1 ; y j

0 ; j 1, n.

j 1

Причѐм обе эти задачи представляют собой пару двойственных задач ли-

нейного программирования:

39

m

v

max ;

n

v

min ;

aij xi

v

0 , j 1, n;

aij y j

v 0 , i 1, m;

i 1

m

n

j 1

xi

1 ; xi

0 ; i 1, m.

y j

1 ; y j

0 ; j 1, n.

i 1

v – свободная переменная.

j 1

v – свободная переменная.

Таким образом, решив одну из двойственных задач, мы определим

оптимальные стратегии 1-го и 2-го игроков и значение игры.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]