МЕТОДЫ РЕШЕНИЯ МАТРИЧНЫХ ИГР
Игры 2×2
Рассмотрим вначале случай, когда в матричной игре оба участника имеют по две стратегии (игры размерности 2×2). Очевидно, такая игра
⎛a a ⎞
задается матрицей вида A= ⎜ 11
12 ⎟.
Пусть (х1, х2)- оптимальная стратегия
⎝a21
a22 ⎠
игрока 1, (у1, у2) - оптимальная стратегии игрока 2. Тогда, исключая тривиальный случай (наличие чистой оптимальной стратегии хотя бы у одного из игроков), имеем:
x1 + x2
=1,
x1 > 0,
x2 > 0;
y1 + y2
=1,
y1 > 0,
y2 > 0.
(5.1)
Из теоремы 4.6 получаем
⎧a11x1 + a21x2
⎨
⎩a12x1 + a22 x2
=υ
=υ.
(5.2)
Приравнивая левые части уравнений (5.2) и подставляя
получаем
x2 =1− x1 ,
a − a
x1 = 22 21,
ΔA
x2 =1− x1,
где
Δ A = (a11 + a22 ) − (a12
+ a21 ).
(5.3)
Аналогично находим
a − a
y1 = 22 12 ,
ΔA
y 2 =1− y1, где
Δ A = (a11 + a22 ) − (a12
+ a21 ).
(5.4)
Цена игры υ находится подстановкой найденных значений х1, х2 в
любое из уравнений системы (5.2).
Игры 2×m
Теперь пусть матрица А матричной игры имеет размерность 2×m.
Рассмотрим графический метод решения такой игры. Базируется он на теореме 4.5 и следствии из нее. Представим матрицу в виде
⎛a1...aj...am⎞
|
|
⎟
...b ⎟
⎝ 1 j m⎠
Каждую смешанную стратегию первого игрока xможно задать таким
образом:
x= (x,1− x),
0≤ x≤1.
Оптимальная стратегия первого игрока
x0 = (x0 ,1− x0 )
определяется из условия
min
(x0aj
+ (1− x0 )bj ) =
max
min
(x a j
+ (1− x)bj).
1 ≤ j ≤ m
0 ≤ x ≤ 1 1 ≤
j ≤ m
Значение х0 удобно определять графически. Для этого введем обозначения
ϕj(x) = ajx+ bj(1− x),
j =1,...,m,
ϕ(x) =
min
ϕ j (x).
Здесь
1≤ j ≤ m
ϕ j ( x),
j=1,..., m -
ϕ(x)
линейные функции,
aj
ϕ( x) -
ϕj(x)
вогнутая функция (ее график,
выделенный на рисунке пунктиром, называется нижней огибающей), х0- точка, в которой достигается
максимум функции
ϕ( x) .
bj
0 x0 1
ϕ(x)
Построив график данных функций (рис 5.1), получим: если х0=0 или х0=1, то для второго игрока оптимальной будет чистая
x стратегия, соответствующая
функции
ϕj (x),
график
ϕj(x)
ϕ(x)
j=1,...,m
которой проходит через точку
(0,ϕ(0) ) или (1,ϕ(1) ) и имеет
соответственно наибольший
отрицательный или
Рис. 5.1
наибольший положительный наклон среди всех прямых,
проходящих через эту точку; если максимум функции
ϕ( x)
достигается во
внутренней точке х0 и существует функция
ϕj (x), график которой проходит
через точку
(x0 , ϕ(x0 ))
параллельно оси абсцисс, то оптимальной для
второго игрока является j0-я чистая стратегия; если максимум функции
ϕ( x)
достигается во внутренней точке х0 и нет прямой, проходящей через точку
(x0 , ϕ(x0 ))
параллельно оси абсцисс, то оптимальная смешанная стратегия
второго игрока имеет вид
y0 = (0,..., y0 ,...,0,...,1 − y0 ,...,0) , график функции
|
проходит через точку
j1
(x0 , ϕ(x0 ))
j 2
и имеет наибольший
положительный наклон среди всех прямых, проходящих через эту точку;
график функции
ϕ (x)
|
проходит через точку
(x0 , ϕ(x0 ))
и имеет
наибольший отрицательный наклон среди всех прямых, проходящих через
эту точку; число
0 ≤ y0 ≤1
выбирается таким образом, чтобы график
| |
y0ϕ
j(x) + (1− y0 )ϕ
(x)
|
был параллелен оси абсцисс. Цена игры
подсчитывается по формуле υ=ϕ(x0 )
или υ= F(x0 , y0 ).
Если игра имеет размерность n×2, то, например, поменяв игроков номерами и, взяв функцию выигрыша с обратным знаком, мы снова получим матричную игру размерности 2×n, и можем применить тот же метод.
Рассмотрим примеры нахождения решения матричной игры в смешанных стратегиях графическим методом. Для получения подходящей размерности матричной игры можно предварительно исключить
доминируемые стратегии.
Пример 5.1. Распределение площади посева.
У фермера имеется поле, которое он может засеять культурами А1, А2, А3 в любой пропорции. Урожайность этих культур зависит от сочетания погодных факторов, главными из которых являются осадки и тепло в летний период. Будем считать, что по признаку "осадки" лето имеет три градации: Н
- нормальное, З - засушливое, Д - дождливое; по признаку "тепло" - две градации: Н - нормальное и Ж - жаркое.
Известна урожайность культур А1, А2, А3 (в центнерах) в зависимости от сочетания типов погодных условий (табл. 5.1), а также рыночная цена этих культур в рублях за центнер (табл. 5.2).
Таблица 5.1
| Культура | Осадки, тепло | |||||
| Н,Н | Н,Ж | З,Н | З,Ж | Д,Н | Д,Ж | |
| А1 | ||||||
| А2 | ||||||
| А3 |
Таблица 5.2
| Культура | Цена |
| А1 | |
| А2 | |
| А3 |
Предполагается, что расходы, связанные с выращиванием культур А1, А2, А3, одинаковы. В какой пропорции надо засеять поле культурами А1, А2, А3, чтобы максимизировать гарантированную прибыль?
Умножая урожайность культур на их цены, получаем прибыль без учета постоянной величины всех расходов (в табл. 5.3 прибыль записана в тысячах рублей).
Таблица 5.3
| Культура | ||||||
| А1 | ||||||
| А2 | ||||||
| А3 |
Таблицу 5.3 можно рассматривать как матрицу, задающую матричную игру фермера (игрок 1) против природы (игрок 2); при этом всевозможные стратегии природы перенумерованы по порядку. Находим решения этой игры графическим методом (построения приведены на рис. 5.2).
Убеждаемся, что в данной игре нет седловой точки. Производим упрощение игры, исключая доминируемые стратегии игроков. В данном случае второй столбец матрицы доминирует первый, а шестой - пятый.
Вычеркиваем столбцы №2 и №6, после чего в новой матрице первая строка доминирует третью. Вычеркиваем третью строку, соответствующую доминируемой стратегии игрока 2, получаем матричную игру размерности
2×4, представленную матрицей
⎛12
⎜
⎝15
9 3
24 30
21⎞
⎟.
9 ⎠
Примем за х вероятность выбора стратегии А1 и за (1-х) - вероятность выбора стратегии А2. В декартовой системе координат (рис 5.2) строим
графики функций
ϕj(x).
ϕ1 (x)=12x+15(1 − x);
ϕ3 (x)= 9x+ 24(1 − x);
ϕ4 (x)= 3x+ 30(1 − x);
ϕ5 (x)= 21x+ 9(1 − x).
По графику установим, что М* - верхняя точка нижней огибающей данного семейства прямых соответствует пересечению графиков функций
ϕ1 (x)
и ϕ5 (x).
Тогда
x0 удовлетворяет следующему уравнению:
12 x+15(1 − x)= 21x+ 9(1 − x).
Следовательно,
x0 = 0.4,а цена игры в
смешанных стратегиях υ=ϕ1( xo) = ϕ5 (x0)=13.8.
Оптимальную стратегию 2-го игрока будем искать в виде
y0 = (y0 ,0,0,0,1− y0 ,0).
График функции
y0ϕ1 (x) + (1− y0 )ϕ5 (x)
должен
быть параллелен оси абсцисс, то есть коэффициенты при x должны быть равны нулю.
y0ϕ1 ( x) + (1 − y0 )ϕ5 ( x) = y0 (15 − 3 x) + (1 − y0 )(12 x+ 9) = v.
− 3 y0
+12 −12 y0
= 0.
Тогда
y = 12 . Перенося эти результаты в первоначальную игру,
0 15
находим окончательное ее решение:
υ=13.8.
x0 =(0.4, 0.6, 0), y0
=(0.8, 0, 0, 0, 0.2, 0),
Можно было бы после построения графика решить задачу другим способом: перейти к игре размерности 2×2, оставляя из чистых стратегий
игрока 2 только первую и пятую. Для матрицы
(5.2) - (5.4) находится решение.
⎛12
A= ⎜
⎝15
21⎞
⎟по формулам
9 ⎠
φj(x)
30 φ4(x) 30
27 27
φ3(x)
24 24
18 φ1(x)
12 φ5(x)
M*
x0
Рис. 5.2
υ
φ(x)
x
Результат интерпретируется следующим образом: оптимальная стратегия фермера состоит в том, чтобы 40% поля засеять культурой А1, 60%
- культурой А2, а культуру А3 не сеять совсем. При этом фермер получит
максимально возможную гарантированную прибыль в 13.8 тыс. руб. Здесь
речь идет о гарантированной прибыли, то есть о той, которая получается при наиболее неблагоприятном сочетании погодных факторов. В случае более
благоприятного сочетания погодных условий прибыль фермера увеличивается, см. рис. 5.2. Отметим также, что в данной задаче компоненты смешанной стратегии игрока 1 (фермера) могут быть интерпретированы не
как вероятности использования чистых стратегий, а как доли, в которых засевается общая площадь поля той или иной культурой. Таким образом, смешанная стратегия игрока здесь носит характер "физической смеси",
принимая вид пропорций сочетания культур А1, А2, А3. В этом случае оптимальная стратегия игрока максимизирует не ожидаемую, а гарантированную прибыль.
Пример 5.2. Полицейские и воры.
В магазине работает охранная служба (в рабочее время это двое полицейских в штатском). Торговый зал магазина делится на две условные
зоны – в зоне А почти всегда посетителей значительно больше, чем в зоне В. Имеется некоторая позиция Т вне торговой площади, в T установлена телекамера. В каждой из двух условных зон может находиться похититель товаров (считаем, что он один, и далее называем его вором). Полицейские же могут находиться в А, в В или в Т. Предполагается, что известны вероятности обнаружения вора в определенной зоне при условии, что полицейский находится в фиксированном месте. Так, вора, находящегося в А, полицейский на том же месте заметит с вероятностью 0.4; из зоны Т он заметит его в зоне А с вероятностью 0.3; и т.д. в соответствии с матрицей (название строки – позиция вора, название столбца – позиция охраны).
Т А В
А ⎛ 0.3
⎜
В ⎝0.5
0.4
0.2
0.1⎞
⎟
0.7 ⎠
|
Пусть вор, например, в зоне А.
Пусть
pA, pA, pA- вероятности обнаружения вора (находящегося в A)
|
|
из T,Aили Bсоответственно. В соответствии с вышеприведенной матрицей
|
|
|
= 0.4; p A
= 0.1.
|
A A A TT AT AB
- вероятности обнаружения вора (находящегося в
А) парой полицейских, находящихся в Т, в А и Т, в В и Т соответственно.
pA = p A +
pA −
pA ⋅ p A
= 0.3 + 0.3 − 0.3⋅ 0.3 = 0.51;
TT T
T T T
pA =
pA +
pA −
pA ⋅ p A
= 0.4 + 0.3 − 0.4 ⋅ 0.3 = 0.58;
AT A T A T
pA = p A +
pA −
pA ⋅ p A
= 0.4 + 0.1− 0.4 ⋅ 0.1= 0.46.
AB A B A B
Подобным образом рассчитываются остальные вероятности.
Получим матрицу (название строки – место вора, столбца - охраны).
ТТ АА ВВ ТА ТВ
А ⎛ 0.51
⎜
В ⎝0.75
0.64
0.36
0.19
0.91
0.58
0.6
0.37
0.85
0.46 ⎞
⎟
0.76 ⎠
Если рассматривать вора и охрану как первого и второго игроков, стратегию каждого игрока – как выбор места (для воровства или для наблюдения соответственно) и взять элементы данной матрицы с отрицательным знаком, то мы получим матричную игру. Выигрыш охраны (или проигрыш вора) – это вероятность обнаружения. Легко установить, что седловой точки в матрице нет. Решение данной матричной игры находим графическим методом, приняв за х вероятность выбора вором зоны А и за (1- х) - вероятность выбора им же зоны В. В декартовой системе координат (рис.
5.3) строим графики следующих функций:
−ϕ1 ( x) = 0.51 x+ 0.75 (1 − x);−ϕ2 ( x) = 0.64 x+ 0.36 (1 − x).
−ϕ3 ( x) = 0.19 x+ 0.91 (1 − x);−ϕ4 ( x) = 0.58 x+ 0.60 (1 − x).
−ϕ5 ( x) = 0.37 x+ 0.85 (1 − x);−ϕ6 ( x) = 0.46 x+ 0.76 (1 − x).
-φ
-φ2(x) и -
-φ1(х)
-φ4(х)
0,5
-φ2(х)
-φ6(х)
-φ5(х)
-φ3(х)
0,1
0 0,1 0,5
x0 1
Рис. 5.3
Здесь для удобства построений, чтобы не переходить к отрицательным числам, рассматриваются выигрыши второго игрока (представителей охраны). Таким образом, сверху на графике черной ломаной (верхней
огибающей) выделена функция
−ϕ( x) =
max
(−ϕj( x)).
Число
x0 ,
1 ≤ j ≤ 6
определяющее оптимальную стратегию первого игрока, находим как точку, в
которой достигается
min
ϕ(x). Эта точка соответствует пересечению
x∈ [0,1]
второй и четвертой прямых, другие прямые через
(x0 ,ϕ(x0 )) не проходят.
Тогда, исходя из того, что функции ϕ2 и ϕ4
должны быть равны, получим:
0.36+0.28x0=0.60-0.02x0.
Тогда x0=0.8, а цена игры
v=ϕ(x0 ) = −0.564. Оптимальную стратегию
2-го игрока будем искать в виде
y0 = (0, y0,0,1 − y0 ,0,0).
График функции
y0ϕ2 (x) + (1− y0 )ϕ4 (x)
должен быть параллелен оси абсцисс, то есть
коэффициенты при x должны быть равны нулю.
y0ϕ2 ( x) + (1 − y0 )ϕ4 ( x) = y0 (−0.36 − 0.28 x) + (1 − y0 )(−0.60 + 0.02 x) = v.
− 0.28 y0
+ 0.02 − 0.02 y0
= 0.
Тогда
y0 =15
. Оптимальная стратегия полицейских имеет вид
(0, 1 ,0,14 ,0,0).
Таким образом, полицейские должны пятнадцатую часть
15 15
своего рабочего времени проводить вместе в A. Оставшееся же время один из должен проводить в A, а другой в Т. Вор должен пятую часть краж совершать в В, а местом других его преступлений будет A. Таковы оптимальные стратегии игроков. Полицейские гарантируют себе вероятность поимки преступника, равную 0.564, а преступник знает, что вероятность его задержания будет не более 0.564.
Игры 3×3
Графический подход, основанный на утверждениях теоремы 4.5,
применим также к играм размерности 3хn. Рассмотрим наиболее простой частный случай - алгоритм решения игр 3х3.
В трехмерном случае смешанные стратегии игроков задаются
следующим образом:
x= ( x1 ,x2 ,x3 ); x1 + x2 + x3 =1;
0≤ xi
≤1.
(5.5)
y= ( y1 ,y2 ,y3 ); y1 + y2 + y3 =1;
Введем следующие обозначения:
0 ≤ yj
≤1.
(5.6)
ϕj( x) = F( x, fj) =
Σaijxi,
i =1
j =1,...,3.
ψi ( y) = F (ei , y
) = Σ
j =1
aijyj,
i=1,...,3.
Составляется система уравнений
⎧ϕ1 =ϕ2
⎪
⎨ϕ1 =ϕ3
⎪
. (5.7)
⎩ϕ2
= ϕ 3
Каждое из уравнений данной системы определяет плоскость в 3-
мерном пространстве. Ищутся точки пересечения этих трех плоскостей между собой в плоскости треугольника решений (этот треугольник (рис. 5.4)
- множество точек, удовлетворяющих (5.5)), точки пересечения каждой из трех плоскостей со сторонами треугольника, а также вершины треугольника.
Все эти точки образуют множество X. Являясь стратегиями, они
удовлетворяют условию
x1 + x2 + x3 =1.
Оптимальная стратегия x0
первого
игрока выбирается именно на этом множестве так, чтобы выполнялось:
min
ϕ j ( x0 ) = max
min
ϕ j( x) = v.
Такая стратегия может быть и не
1≤ j≤ 3
x∈ X1≤
j≤ 3
единственна.
Для поиска оптимальных стратегий второго игрока составляется система уравнений
⎧ψ1 =ψ2
⎪
⎨ψ1
⎪
=ψ3
. (5.8)
⎩ψ2
= ψ 3
Далее процесс решения сходен с
поиском оптимальных стратегий 1-го игрока. Каждое из уравнений данной
системы определяет плоскость в 3- мерном пространстве. Ищутся точки пересечения этих трех плоскостей между собой в плоскости
треугольника решений (множества точек, удовлетворяющих (5.6) и представляющего собой треугольник,
аналогичный тому, что приведен на
рис. 5.4), точки пересечения каждой 1
из трех плоскостей со сторонами x1
треугольника, а также вершины
x3
Рис. 5.4
1 x2
треугольника. Все эти точки образуют множество Y. Являясь стратегиями,
элементы Y удовлетворяют условию
y1 + y2 + y3 =1.
Оптимальная стратегия
y0 2-го игрока выбирается именно на этом множестве так, чтобы
выполнялось:
max
ψi( y0 ) = min
max
ψi ( y) =υ.
1 ≤ i ≤ 3
y ∈Y 1 ≤ i ≤ 3
Такая стратегия может быть и не единственна.
Трехмерный графический метод обыкновенно применяется в том случае, если нет седловых точек в чистых стратегиях.
Пример5.3.
⎛1 1
⎜
|
⎝2 0
2 ⎞
⎟
| |
⎟
⎠
Для решения игры графическим методом найдем функции ϕj.
ϕ1 = x1 + 2x3 ;ϕ2
= x1 + 2x2 ;ϕ3
= 2x1.
⎧x1 + 2 x3 = x1 + 2 x2
Система уравнений (5.7) будет иметь вид ⎪x
+ 2 x
= 2 x .
⎨ 1 2 1
⎪
⎩2 x1 = x1 + 2 x3
Опустим элементарные алгебраические вычисления, производимые во время поиска точек, образующих множество Х. Все эти 7 точек приведены на рис 5.5. Как видно из рисунка, все плоскости пересекаются в одной точке G.
G(0,0,1)
Ее координаты - ⎜ 1 , 1 , 1 ⎟.
⎛ ⎞
⎝2 4 4 ⎠
Составим матрицу значений
G D(0,1/2,1/2)
ϕj(x)для
x∈ X, j=1,2,3.
1 2 3
F(2/3,0,1/3)
⎛ 1 1 2 ⎞
|
B ⎜ 3
3 3 ⎟
A(1,0,0) B(2/3,1/3,0)
|
C(0,1,0)
C ⎜ 0 2 0 ⎟
⎜ ⎟
D⎜ 1 1 0 ⎟
⎜ 2 0 0 ⎟
⎜ ⎟
F⎜4 3 2 3 4 3 ⎟
G⎜ ⎟
⎝ 1 1 1 ⎠
Получаем: у первого игрока есть две оптимальные стратегии - (1,0,0) и
(1/2,1/4,1/4) - те, в которых достигается
max
min
ϕj( x) =1 (в первой и
x∈ X
1 ≤ j≤ 3
седьмой строках наибольшие минимумы, равные 1). Цена игры v=1.
Найдем функции ψi.
ψ1 = y1 + y2
+ 2y3 ;ψ2
= 2y2 ;ψ3
= 2y1..
E(0,0,1) Система уравнений (5.8) будет
⎧y1 + y2 + 2 y3 = 2 y2
иметь вид
⎪2 y
|
|
| |
= 2 y1 .
F(2/3,0,1/3)
D(0,2/3,1/3
⎩2 y1 = y1 + y2 + 2x3
A(1,0,0) B(1/2,1/2,0)
Рис. 5.6
C(0,1,0)
пересекаются в одной и той же точке.
Составим матрицу значений
ψi(y)для
1 2 3
A B C D E
F
y∈ Y,i=1,2,3.
⎛ ⎞
⎜ ⎟
|
⎜ ⎟
⎜ ⎟
⎜4 3 4 3 0 ⎟
⎜ 2 0 0 ⎟
⎜ ⎟
| |
| |
|
Получаем: у второго игрока есть одна оптимальная стратегия -
(1/2,1/2,0) - та, в которой достигается
строке – наименьший максимум=1).
min
y
max
1 ≤ i ≤ n
ψi ( y) =υ=1 (во второй
Метод Брауна-Робинсон
Аналитическое решение матричных игр произвольной размерности
(например, сведением к задаче линейного программирования) весьма затруднительно. Для приближенного решения матричных игр произвольной
размерности рассмотрим итеративный метод Брауна-Робинсон. Пусть дана
матричная игра с матрицей А=(aij), i=1,…,n; j=1,…,m. Рассматривается бесконечный процесс повторения данной игры, при котором каждый из игроков на каждом шаге предполагает, что противник выберет смешанную стратегию, определяемую частотами появлений чистых стратегий на предыдущих шагах, а сам выбирает чистую стратегию, обеспечивающую наилучший результат при данном предположении. Пусть уже сделано k повторений игры, в которых первый игрок выбирал чистые стратегии i1,…, ik, а второй - j1,…, jk. Тогда в соответствии с вышесказанным игрок 1 выберет на (k+1)-м шаге стратегию ik+1 из условия
|
|
|
∑ max ∑
=υ1
(k),
| |
|
ik+ j
1 ≤ i≤ nkν=1 ij
а игрок 2 - стратегию jk+1 из условия
k k
1 ∑ a
k i jk
= min
k ∑ ai
j =υ2
(k ).
ν =1 ν
+ 1 1 ≤
j ≤ m
ν =1 ν
Если же стратегий, удовлетворяющих соответствующему условию,
несколько, игрок выбирает любую из них.
Истинный платеж на (k+1)-м шаге равен
aik+1 jk+1
, а средний платеж -
1 k+1
∑ a
=υ*
(k).
Но эта величина не учитывается в итеративном
k + 1ν=1
iνjν
процессе. Чистые стратегии i1 и j1 выбираются произвольно.
Обозначим через
xk и yk
предполагаемые смешанные стратегии
игроков на (k+1)-м шаге. Имеем цепочку неравенств
υ1(k) =
max
1 ≤ i ≤ n
1 k
|
kν =1 i j
= max
1≤ i ≤ n
F(ei ,yk )≥ min
y
max
1 ≤ i ≤ n
F(ei ,y ) =
= max
min
F(x, f
j )≥
min
F(xk , f
j )=
1 k
|
|
=υ2
(k).
x 1≤
j ≤ m
1≤ j ≤ m
1≤ j ≤ m kν =1 i j
Дж. Робинсон доказала справедливость следующего соотношения:
lim
k → ∞
υ1 (k) =
lim
k → ∞
υ2 (k) =υ.
Оно означает, что воображаемые платежи
υ1 (k)
и υ2 (k)
стремятся к истинной цене игры υ.
Сходимость этого итеративного метода медленная, но значение его велико, так как он прост и в какой-то мере отражает приобретение игроками опыта в результате многих повторений конфликтной ситуации.
Пример 5.4.
Рассмотрим применение метода Брауна-Робинсон (5 итераций) для
⎛12
матрицы ⎜
⎝15
9 3
24 30
21⎞
⎟.
9 ⎠
Такая матричная игра исследовалась графически в примере 5.1.
Предположим, на 1-м шаге оба игрока выбрали стратегии с 1-м
номером.
i1 =1; j1 =1.
Тогда начальные смешанные стратегии игроков таковы:
x1 = (1,0);
y1 = ( 1,0,0,0 ) .
Пусть k =1. На (k+1)-м шаге
k
max
1 ∑ a
= max{12,15} =15 =υ1
(k ) .
|
1-й игрок выберет 2-ю стратегию, i2 = 2.
k
min
1 ∑ a
k i
j = min{12, 9, 3, 21} = 3 =υ2
(k) .
1 ≤ j≤ m
ν=1 ν
2-й игрок выберет 3-ю стратегию,
j2 = 3.
Тогда
x2 = ⎜ 1 , 1 ⎟ ;
y2 = ( 1 ,0, 1 ,0) .
⎛ ⎞
⎝2 2 ⎠ 2 2
Пусть k =2. На (k+1)- м шаге
k
max
1 ∑ a
12 + 3 15 + 30
|
=υ1 (k ) .
|
2 2 2
1-й игрок выберет 1-ю стратегию, i3 = 2.
|
1 k
|
= 12 +15 , 9 + 24 , 3 + 30 , 21 + 9} = 27
=υ2 (k) .
1 ≤ j≤ mkν=1 ν
2 2 2 2 2
2-й игрок выберет 1-ю стратегию, j3 =1.
Тогда
x3 = ⎜1 , 2 ⎟ ;
3 2 1
y = ( ,0, ,0) .
⎛ ⎞
|
Пусть k =3. На (k+1)-м шаге
k
max
1 ∑ a
12 ⋅ 2 + 3 15 ⋅ 2 + 30
max{ =
=υ1 (k ) .
|
3 3 3
1-й игрок выберет 1-ю стратегию, i4 = 2.
|
min
1 ∑ a
= 12 +15⋅ 2 , 9 + 24 ⋅ 2 , 3 + 30 ⋅ 2 , 21+ 9⋅ 2}=
1≤ j
≤ mkν=1
iνj
3 3 3 3
= 39 =υ
3 2
(k ).
2-й игрок выберет 4-ю стратегию, j4 = 4.
Тогда
x4 = ⎜ 1 , 3 ⎟ ;
y4 = ( 2 ,0, 1 , 1 ) .
⎛ ⎞
⎝4 4 ⎠
4 4 4
Пусть k =4. На(k+1)-м шаге
k
max
1 ∑ a
12 ⋅ 2 + 3 + 21 15 ⋅ 2 + 30 + 9 69
|
=υ1 (k ) .
|
4 4 4
1-й игрок выберет 2-ю стратегию, i5 = 2.
1 k
min ∑
12 + 15 ⋅ 3
min{ ,
9 + 24.3 ,
3 + 30 ⋅ 3 ,
21 + 9 ⋅ 3
} =
|
|
iνj
4 4 4 4
= 48 = 12 = υ
4 2
(k ).
2-й игрок выберет 4-ю стратегию, j5 = 4.
Тогда
x5 = ⎜ 3 , 2 ⎟ ;
y5 = ( 2 ,0, 1 , 2 ) .
⎛ ⎞
⎝5 5 ⎠
5 5 5
Цена игры равна 13.8, как уже известно из решения, полученного в
примере 5.1. Значения
υ1 (4) =17.25
и υ2 (4) =12
достаточно сильно
разнятся. Пример показывает, что ожидать от метода Брауна-Робинсон оценок, близких к истинным значениям, можно лишь при большом числе итераций. Для этого требуется автоматизация процесса вычислений.