Games_theory5
.pdfПример 5.8. Выполнить 12 итераций метода Брауна−Робинсон для решения матричной игры с платежной матрицей
1 |
3 |
2 |
|
|
|
2 |
1 |
3 |
. |
|
|
|||
|
3 |
2 |
1 |
|
|
|
|||
Решение. Запишем изменение эмпирических распределений на каждом шаге алгоритма.
Шаг 1. i =1, |
j =1 p1 |
= (1, 0, 0), q1 = (1, 0, 0). |
1 |
1 |
|
Шаг 2. |
α1 |
= 3, i = 3 |
|
p2 = (1/ 2, 0, 1/ 2) |
|
1 |
|
|
|
|
α1 + β1 |
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
2 |
|
|
|
|
q2 =(1, 0, 0) |
ν |
= |
|
|
|
|
2 |
|
= 2. |
|
|
|
||||||||||||||||
|
β1 =1, j =1 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 3. α2 = 3, |
i3 =3 |
|
|
|
p3 = (1/ 3, 0, 2 / 3) |
|
|
|
|
|
2 |
|
|
|
α2 + β |
2 |
9 |
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
β2 |
=3 / 2, |
j |
=3 |
|
|
|
|
q3 =(2 / 3, 0, 1/ 3) |
|
|
ν |
|
= |
|
|
|
2 |
= |
4 |
= 2, 25. |
|||||||||||||
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 4. α3 = 7 / 3, |
i4 =3 |
|
|
p4 |
=(1/ 4, 0, 3 / 4) |
|
|
|
|
|
3 |
|
|
|
|
α3 + β |
3 |
11 |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
β3 = 4 / 3, |
j |
=3 |
|
|
|
|
q4 |
=(1/ 2, 0, 1/ 2) |
|
|
|
ν |
|
|
= |
|
|
|
2 |
= |
6 |
≈1,833. |
|||||||||||
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 5. |
α4 |
=5 / 2, i = 2 |
|
p5 =(1/ 5, 1/ 5, 3 / 5) |
|
|
|
|
ν |
|
4 |
|
= |
α4 + |
β4 |
=1,875. |
||||||||||||||||||
|
|
|
|
|
|
|
||||||||||||||||||||||||||||
β4 |
|
5 |
|
|
|
|
|
|
|
|
|
|
q5 |
=(1/ 3, 0, 2 / 3) |
|
|
|
|
|
|
2 |
|
||||||||||||
|
=5 / 4, |
j |
=3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 6. |
α5 |
=8 / 3, i = 2 |
|
p6 =(1/ 6, 2 / 6, 1/ 2) |
|
|
|
ν |
5 |
|
= |
α5 + |
β5 |
≈ 2,133. |
||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||
β5 |
|
6 |
|
|
|
|
|
|
|
|
|
|
q6 |
=(1/ 4, 0, 3 / 4) |
|
|
|
|
|
2 |
|
|||||||||||||
|
=8 / 5, |
j |
=3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 7. |
α6 |
=11/ 4, |
i |
|
= 2 |
|
|
|
p7 |
=(1/ 7, 3 / 7, 3 / 7) |
|
|
|
|
|
6 |
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
q7 =(1/ 5, 0, 4 / 5) |
|
|
|
ν |
|
≈ 2, 291. |
|
|
|
|||||||||||
|
β6 |
=11/ 6, |
j |
|
=3 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 8. |
α7 |
=14 / 5, i = 2 |
|
p8 =(1/ 8, 1/ 2, 3 / 8) |
|
|
ν |
7 |
≈ 2, 257. |
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|||||||||||||||||||||||||||||
β7 |
|
8 |
|
|
|
|
|
|
|
|
|
|
q8 |
=(1/ 6, 1/ 6, 2 / 3) |
|
|
|
|
|
|||||||||||||||
|
=12 / 7, |
j |
|
= 2 |
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
На дальнейших шагах получаем следующие значения:
ν8 ≈ 2, 02, ν9 ≈1,98, ν10 ≈1,875, ν11 ≈1,984, ν12 ≈ 2, 208.
64
ν
2,3
2,2
2,1
2,0
1,9
1,8
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Номер итерации |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|||||
|
|
|
|
|
|
|
Рис. 5.3 |
|
|
|
|
|
|
|||
Из рис. 5.3 видно, что процесс не монотонен, поэтому его остановка по критерию |ν N −ν N −1 | ≤ ε не корректна.
Упражнения
1.Первый игрок загадывает любое целое число от 1 до 3. Второй игрок должен отгадать это число. Если второй игрок указывает число правильно, он получает выигрыш, равный значению этого числа. В противном случае этот выигрыш получает первый игрок.
а) Определите число стратегий игроков и составьте платежную матрицу задачи.
б) Определите нижнюю и верхнюю цену игры. Установите, существует ли в данной игре решение в чистых стратегиях.
2.Решить матричные игры в чистых стратегиях для матриц:
|
1 |
2 |
−1 |
3 |
0 |
|
|
2 |
1 |
−1 |
|
|
0 |
1 |
−5 |
|
|||||||
а) |
2 |
2 |
0 |
2 |
1 |
|
; б) |
. |
|||
|
|
|
|
|
|
|
|
3 |
1 |
10 |
|
|
2 |
1 |
1 |
7 |
1 |
|
|||||
|
|
|
5 |
2 |
2 |
|
|||||
|
|
|
|
|
|
|
|
|
|||
65
3.Решить матричную игру с матрицей (aij )m×n = ( f (i) + g( j))m×n .
4.Решить матричные игры в смешанных стратегиях:
2 |
−1 |
1 2 |
3 |
3 |
−1 |
|
1 |
2 |
1 |
−2 |
|||||
; б) |
0 |
1 |
1 |
−2 −2 |
|
; в) |
3 2 |
1 |
−3 |
. |
|||||
а) |
|
||||||||||||||
1 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
3 6 |
2 |
1 |
|
|
1 |
2 |
3 3 |
|
|||||
|
|
|
|
|
|
||||||||||
5. Осуществить 10 итераций метода фиктивного розыгрыша Брауна−Робинсон для решения матричной игры
1 |
−1 |
3 |
|
|
|
2 |
1 |
−3 |
|
|
. |
|||
|
2 |
3 |
1 |
|
|
|
|||
66