Материал: Теория_игр_УП_ЭК_ЭлРесурс
46
например
,
свойств
1
и
2
из
параграфа
2.6,
позволяет
находить
оптимальные
стратегии
задавая
лишь
относительные
значения
элементов
платежной
матрицы
.
Например
,
если
в
платежной
матрице
имеется
всего
три
различных
значения
элементов
платежной
матрицы
,
то
в
этом
случае
совершенно
не
важно
,
какое
значение
имеют
наименьший
и
наибольший
платежи
.
Единственно
,
что
имеет
значение
–
это
относительное
положение
третьего
платежа
.
Таким
образом
,
теория
игр
может
дать
важные
результаты
даже
в
тех
случаях
,
в
которых
точные
оценки
платежей
затруднены
.
В
частности
,
имеется
слабая
форма
оценки
платежей
,
называемая
упорядочением
.
Она
заключается
в
расположении
платежей
по
порядку
их
относительной
величины
.
Существуют
игровые
ситуации
,
для
которых
не
требуется
ничего
большего
,
чем
определение
порядка
расположения
платежей
по
величине
.
В
других
игровых
ситуациях
знание
порядка
платежей
позволяет
сделать
частичные
выводы
относительно
оптимальных
стратегий
и
цены
игры
.
Пусть
,
например
,
платежи
оцениваются
как
плохие
(
п
);
удовлетворительные
(
у
),
хорошие
(
х
)
или
отличные
(
о
),
а
матрица
игры
имеет
вид
B
j
A
i
B
1
B
2
B
3
B
4
B
5
i
A
1
п
о
х
о
х
п
A
2
у
у
х
о
х
у
*
A
3
п
х
о
о
х
п
A
4
у
о
о
п
о
п
j
у
*
о
о
о
о
В
этой
игре
=
=y
,
т
.
е
.
игра
решается
в
чистых
стратегиях
.
Игрок
А
должен
придерживаться
своей
второй
стратегии
,
а
игрок
В
–
стратегии
В
1
.
Цена
игры
– «
удовлетворительно
».
Пусть
игра
имеет
седловую
точку
в
клетке
,
отмеченной
звездочкой
.
B
1
B
2
B
3
B
4
B
5
B
6
A
1
A
2
A
3
A
4
*
A
5
A
6
A
7
Так
как
седловая
точка
отмечает
наименьшее
число
в
этой
строке
и
наибольшее
число
в
столбце
,
то
все
остальные
числа
в
данной
строке
(
столбце
)
могут
быть
какими
угодно
,
лишь
бы
число
,
отмеченное
звездочкой
,
оставалось
наименьшим
в
строке
(
наибольшим
в
столбце
).
47
Наконец
,
все
остальные
числа
в
матрице
,
которые
не
попали
в
строку
и
столбец
,
соответствующих
оптимальным
стратегиям
,
могут
быть
вообще
какими
угодно
.
Их
значения
не
влияют
ни
на
оптимальный
способ
ведения
игры
,
ни
на
ее
цену
.
Пример
.
Решить
игру
,
платежная
матрица
которой
имеет
вид
B
j
A
i
B
1
B
2
B
3
A
1
п
о
у
A
2
х
у
х
A
3
п
у
о
Как
видно
стратегия
В
1
доминирует
стратегию
В
3
,
далее
стратегия
А
1
будет
доминировать
стратегию
А
3
,
а
,
следовательно
,
исходную
игру
можно
свести
к
игре
2*2:
B
j
A
i
B
1
B
2
i
A
1
п
о
п
A
2
х
у
у
*
j
х
*
о
Таким
образом
,
игрокам
не
следует
использовать
стратегии
А
3
и
В
3
.
Так
как
=
у
не
равняется
=
х
,
то
игра
не
имеет
седловой
точки
и
должна
решаться
в
смешанных
стратегиях
.
Частоты
применения
своих
стратегий
игроком
А
равны
:
y
n
o
x
y
x
o
x
y
n
x
y
p
1
;
y
n
o
x
n
o
p
2
.
Частоты
применения
своих
стратегий
игроком
В
равны
:
y
n
o
x
y
o
o
x
y
n
o
y
q
1
;
y
n
o
x
n
x
q
2
,
таким
образом
,
частота
применения
стратегии
А
1
пропорциональна
разности
между
“
хорошо
”
и
“
удовлетворительно
”,
а
стратегии
А
2
пропорциональна
разности
между
“
отлично
”
и
“
плохо
”.
Ясно
,
что
стратегия
А
1
должна
применяться
реже
,
чем
стратегия
А
2
независимо
от
того
,
какие
упорядоченные
числа
будут
приписаны
этим
понятиям
.
Положение
игрока
В
несколько
более
неопределенно
.
Он
должен
применять
стратегию
В
1
с
частотой
пропорциональной
разности
между
“
отлично
”
и
“
удовлетворительно
”,
а
стратегию
В
2
–
с
частотой
,
пропорциональной
разности
между
“
хорошо
”
и
“
плохо
”.
Здесь
неясно
,
какая
разность
больше
.
Хотя
в
данном
примере
мы
не
получили
строгого
решения
,
но
полученное
решение
дает
ориентацию
,
как
следует
себя
вести
в
исходной
слабо
определенной
ситуации
.
48
2.11.
Способы
реализации
случайного
механизма
выбора
стратегий
Для
реализации
применения
игроком
его
активных
стратегий
с
оптимальными
вероятностями
(
относительными
частотами
),
необходимо
иметь
случайный
механизм
выбора
стратегий
.
Например
,
если
оптимальная
смешанная
стратегия
5
.
0
;
5
.
0
S
(
относительные
частоты
1:1),
то
для
ее
реализации
можно
использовать
подбрасывание
монеты
:
если
выдает
“
герб
”,
то
применяется
первая
стратегия
,
а
если
“
решка
”, –
то
вторая
.
Игральную
кость
можно
использовать
при
относительных
частотах
1:5; 2:4; 1:1; 4:2
;
и
так
далее
до
5:1
.
Секундная
стрелка
часов
может
служить
для
выбора
случайных
чисел
от
0
до
59,
если
только
игрок
не
смотрел
на
часы
недавно
и
не
знает
наперед
,
даже
приблизительно
,
ответ
.
Но
на
практике
могут
потребоваться
любые
сочетания
чисел
в
качестве
относительных
частот
.
Механизмом
,
удовлетворяющим
вышеуказанному
требованию
,
является
датчик
случайных
чисел
R
от
0
до
1
с
равномерной
плотностью
вероятности
.
Так
как
стратегии
А
1
,
А
2
, ...,
А
m
несовместны
(
в
каждый
момент
,
применяется
лишь
одна
из
этих
стратегий
)
и
образуют
полную
группу
событий
1
1
m
i
i
p
,
то
для
реализации
случайного
механизма
выбора
стратегий
поступают
следующим
образом
.
Делят
интервал
(0, 1)
на
m
участков
длиной
p
1
, p
2
, ..., p
m
(
рис
. 2.12).
На
какой
из
участков
попало
число
R –
ту
стратегию
и
следует
в
данной
партии
использовать
.
0
p
2
...
p
m
1
p
1
Рис
. 2.12.
Возникает
вопрос
:
а
как
же
реализуется
сам
датчик
случайных
чисел
R?
Самый
простой
из
датчиков
случайных
чисел
(
ДСЧ
) –
это
вращающийся
барабан
,
в
котором
перемешивается
перенумерованные
шары
.
Пусть
,
например
,
нам
надо
разыграть
случайное
число
R
от
0
до
1
с
точностью
0.001.
Заложим
в
барабан
1000
перенумерованных
шаров
и
после
,
случайным
образом
выбранного
одного
из
шаров
,
разделим
его
номер
на
1000.
Можно
поступить
и
иначе
:
вместо
1000
шаров
заложить
только
10,
с
цифрами
0, 1, 2, .... , 9.
Вынув
случайным
образом
первый
шар
,
получаем
первый
десятичный
знак
дроби
.
Вернув
шар
в
барабан
и
прокрутив
его
,
выберем
случайным
образом
второй
шар
–
его
номер
даст
второй
десятичный
знак
и
т
.
д
.
Можно
доказать
,
что
получаемые
таким
образом
десятичные
дроби
будет
иметь
равномерное
распределение
от
0
до
1.
Достоинством
этого
способа
в
том
,
что
он
может
обеспечить
любую
точность
задания
числа
R.
На
практике
широко
применяются
таблицы
случайных
чисел
.
Ниже
приведен
пример
такой
таблицы
(
рис
. 2.13).
Числа
сгруппированы
лишь
49
для
удобства
пользования
таблицей
.
Можно
начинать
с
любой
точки
таблицы
,
отсчитывать
числа
вверх
или
вниз
,
группировать
числа
.
Как
использовать
таблицу
случайных
чисел
,
чтобы
получить
желаемые
относительные
частоты
?
Возьмем
в
качестве
примера
оптимальную
стратегию
7
2
;
7
5
A
S
.
Далее
выбираем
из
таблицы
любое
однозначное
случайное
число
.
Если
это
число
равно
0, 1, 2, 3
или
4,
то
используем
в
данной
партии
первую
стратегию
.
Если
число
равно
5
и
6,
то
применяем
вторую
стратегию
.
Если
это
число
равно
7, 8
и
9,
то
отбрасываем
его
и
берем
число
под
ним
.
Для
следующей
партии
используется
число
ниже
предыдущего
.
11 16 43 63 18 75 6 13 76 74 40 60 31 61 52
21 21 59 17 91 76 83 15 86 78 40 94 15 35 85
10 43 84 44 82 66 55 83 76 49 73 50 58 34 72
36 79 22 62 36 33 26 66 65 83 39 41 21 60 13
73 94 40 47 73 12 3 25 14 14 57 99 47 67 48
49 56 31 28 72 14 6 39 31 17 61 83 45 91 99
64 20 84 82 37 38 60 52 93 41 91 40 27 72 27
51 48 67 28 75 64 51 61 79 71 58 99 98 38 80
99 75 62 63 60 41 70 17 31 17 40 68 49 99 48
71 32 55 52 17 13 1 57 29 7 75 97 86 42 98
65 28 59 71 98 12 13 85 30 10 34 55 63 98 61
17 26 45 73 27 38 22 42 93 1 65 99 5 70 48
95 63 99 97 54 31 19 99 25 58 16 38 11 50 69
61 55 57 64 4 86 21 1 18 8 52 45 88 88 80
78 13 79 87 68 4 68 98 71 30 33 0 78 56 7
62 49 9 92 15 84 98 72 87 59 38 71 23 15 12
24 21 66 34 44 21 28 30 70 44 58 72 20 36 78
16 97 59 54 28 33 22 65 59 3 26 18 86 94 97
59 13 83 95 42 71 16 85 76 9 12 89 35 40 48
29 47 85 96 52 50 41 43 19 61 33 18 68 13 46
Рис
. 2.13.
Часто
желательно
модифицировать
этот
способ
.
Например
,
в
случае
относительных
частот
8:3
сумма
чисел
равна
8+3=11.
Приходится
применять
двухзначные
числа
от
00
до
99.
Но
чтобы
не
отбрасывать
числа
от
11
до
99,
разделим
99
на
11,
получаем
9 (
в
общем
случае
это
будет
смешанная
дробь
).
Далее
умножаем
8
9=72
и
3
9=27.
Теперь
,
если
выбранное
двухзначное
число
лежит
в
пределах
от
00
до
71,
используем
первую
стратегию
,
а
если
от
72
до
99, –
то
вторую
.
Число
99
будем
отбрасывать
.
Для
получения
R
на
ЭВМ
применяются
специальные
датчики
случайных
чисел
.
Это
могут
быть
как
“
физические
датчики
”,
принцип
действия
которых
основан
на
преобразовании
случайных
шумов
,
так
и
50
вычислительные
алгоритмы
,
по
которым
сама
машина
вычисляет
так
называемые
“
псевдослучайные
”
числа
.
Один
из
самых
простых
алгоритмов
вычисления
псевдослучайных
чисел
состоит
в
следующем
.
Берут
два
произвольных
n-
значных
числа
a
1
и
a
2
и
перемножают
их
,
и
в
полученном
результате
берут
n
средних
знаков
.
Так
получают
число
а
3
.
Затем
перемножают
а
2
и
а
3
и
в
полученном
результате
берут
n
средних
чисел
,
получая
число
а
4
,
и
т
.
д
.
Полученные
таким
образом
числа
рассматриваются
как
последовательность
двоичных
дробей
с
n
знаками
после
запятой
.
Такая
последовательность
дробей
практически
ведет
себя
как
ряд
случайных
чисел
R
от
0
до
1.
В
заключение
изложения
матричных
игр
отметим
,
что
хотя
само
понятие
смешанной
стратегии
требует
многократного
повторения
партий
игры
,
полученные
результаты
справедливы
и
к
играм
,
которые
играются
только
один
раз
,
поскольку
все
изложения
теории
были
выведены
применительно
к
одной
партии
игры
.
Качественно
аргументировать
этот
тезис
можно
следующим
образом
:
очевидно
,
что
если
противник
узнает
,
какую
мы
выбрали
стратегию
,
то
предпримет
ход
,
который
будет
иметь
для
нас
наихудшие
последствия
.
Поэтому
единственным
выходом
является
использование
для
выбора
стратегии
случайного
механизма
(
жребия
),
результат
которого
противник
не
может
предвидеть
(
хотя
,
конечно
,
ему
может
и
повезти
).
Теория
игр
указывает
характеристики
(
частоты
применения
стратегий
),
которыми
должен
обладать
используемый
случайный
механизм
.
ТЕСТЫ
(
В
–
Верно
,
Н
–
Неверно
)
1.
Каждая
матричная
игра
может
быть
представлена
парой
прямой
и
двойственной
задач
линейного
программирования
.
2.
Преимуществом
приближенного
метода
Брауна
-
Робинсона
является
то
,
что
объем
вычислений
с
увеличением
размерности
игры
m*n
растет
существенно
медленнее
,
чем
в
методах
линейного
программирования
.
3.
Теория
игр
не
может
дать
результатов
в
тех
случаях
,
когда
элементы
платежной
матрицы
заданы
неточно
(
например
,
когда
они
только
упорядочены
).
4.
Случайные
числа
выдаваемые
датчиком
случайных
чисел
,
используемые
для
реализации
оптимальных
стратегий
,
должны
быть
распределены
по
равномерному
закону
.
5.
Теория
игр
применима
и
для
игр
,
которые
играются
только
один
раз
.
(
Ответы
:
1 -
В
; 2 -
В
; 3 -
Н
; 4 -
В
, 5 -
В
).