Материал: Теория_игр_УП_ЭК_ЭлРесурс
51
ЗАДАЧИ
Решить
матричные
игры
,
имеющие
платежные
матрицы
вида
:
1. 8 4 2 2. -1 1 1 3. 1 2 -5 3 2
2 8 4
2 -2 2
-1 4 7 2 -4
1 2 8
3 3 -3
5 -1 1 1 3
4. 0 -13
-1 5. 1 0 -1 6. 3 2 4
13 0 -13
0 2 1
4
3 2
1 13 0
1 -1 3
2 4 3
7. 3 6 0 8.
3 0 7 9. 203 403 103
5 3 2
4 6 0
303
3 103
2 1 6
3 4 3
3 103 303
10. 2
-11 1
11.
7 5 4 12.
16
0 14
15 2
-11
1 3 7
6
6 16
3 15 2
2 7 4
6 12
2
13. 0 1 1
14. -1 1 0 15.
0
2
1
1 0 1
0 -1 1
2
0
2
1 1 0
1 0 -1
1
2
0
18.
1
6
2
5 19.
6
0
1
2 20.
4
3
3
2
2
6
5
1
6
2
0
3
1
0
6
0
4
2
6
2
2
5
1
6
2
0
3
1
0
7
3
6
2
2
21. 0
-13 -3
22. 9
6 12
23.
2
7 3 6
13 0
-13
12
9
6
6
2 7 3
1 13 0
6 12
9
3
6 2 7
24. 12 0 2
4
25. 6 -10
4
26. 104 304 4
0 6 2
0 -4 -4
6
204 -96 4
4 0 6
2 -4
2 -8
-96
4
204
27.
3
1
4
1
6 28.
2
3
1
4
29. -1 -2 -3
6
3
1
4
1
1
2
5
4
-3 -1 -1
1
6
3
1
4
2
3
4
1
-1 -3
1
4
1
6
3
1
4
2
2
2
1 4 1
6 3
30. 1/7 2/7 3/7
3/7 1/7 1/7
1/7 3/7 1/7
52
3.
ПОЗИЦИОННЫЕ
ИГРЫ
3.1.
Общие
сведения
В
общих
играх
число
игроков
может
быть
больше
двух
,
некоторые
ходы
возможно
являются
случайными
,
игроки
могут
иметь
по
несколько
ходов
,
причем
информация
о
прошедшем
может
меняться
от
хода
к
ходу
.
Такие
игры
называются
позиционными
или
играми
в
развернутой
форме
.
Пример
.
Выборы
с
правом
вето
.
Пусть
три
игрока
(N=3)
выбирают
одного
из
четырех
(G=4)
кандидатов
в
президенты
.
Правило
выбора
таково
:
начиная
с
первого
игрока
,
каждый
игрок
налагает
вето
на
выбор
одного
из
неотведенных
кандидатов
.
Единственный
оставшийся
кандидат
считается
избранным
.
Функции
выигрышей
U
i
для
каждого
из
игроков
в
зависимости
от
выбранного
в
президенты
кандидата
имеют
вид
:
.
4
,
5
,
8
,
3
;
4
,
5
,
7
,
6
;
7
,
3
,
4
,
5
3
2
1
U
U
U
В
развернутой
форме
данная
игра
может
быть
представлена
в
виде
следующего
дерева
игры
(
рис
. 3.1),
где
около
ветвей
поставлены
номера
отводимых
кандидатов
,
а
у
конечных
вершин
–
номера
победивших
кандидатов
.
Если
победил
,
например
,
кандидат
под
номером
4,
то
выигрыш
первого
игрока
будет
равен
7,
а
для
второго
и
третьего
игроков
–
4.
Позиционные
игры
должны
включать
следующие
элементы
описания
:
*
последовательность
личных
и
случайных
ходов
игроков
;
*
выборы
,
которые
могут
делать
игроки
при
каждом
личном
ходе
;
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
1
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Рис
. 3.1.
*
исходы
случайных
ходов
и
распределение
вероятностей
этих
исходов
;
*
информацию
,
доступную
игрокам
при
выполнении
личного
или
случайного
хода
;
*
правила
окончания
игры
и
подсчеты
выигрыша
игроков
.
Число
ходов
в
данной
игре
не
фиксируется
.
В
общем
случае
,
оно
зависит
от
последовательности
выборов
,
исходов
.
Однако
,
правила
должны
гарантировать
,
что
игра
в
конце
концов
закончится
.
53
Относительно
ходов
правила
игры
имеют
следующую
структуру
.
Для
первого
хода
правила
указывают
его
вид
.
Если
это
личный
ход
,
то
правила
перечисляют
возможные
варианты
и
указывают
игрока
,
который
делает
выбор
.
Если
это
случайный
ход
,
то
перечисляются
возможные
варианты
и
обуславливаются
вероятности
их
выбора
.
Для
последующих
ходов
1
правила
определяют
в
зависимости
от
выбора
и
исходов
предыдущих
(
-1)
ходов
,
будет
ли
-
й
ход
личным
или
случайным
.
Если
ход
личный
,
то
перечисляются
возможные
варианты
игрока
,
который
будет
делать
выбор
,
и
определяется
информация
о
выборах
и
исходах
при
первых
(
-1)
ходах
,
которой
располагает
игрок
к
моменту
своего
выбора
.
Если
ход
случайный
,
то
перечисляются
возможные
варианты
и
вероятности
их
выбора
.
Правила
,
наконец
,
определяют
в
зависимости
от
выборов
и
исходов
в
последовательности
ходов
,
когда
игра
должна
закончиться
и
выигрыш
каждого
из
игроков
.
3.2.
Задание
позиционной
игры
в
виде
дерева
Позиционные
игры
удобно
задавать
графически
в
виде
дерева
игры
(.3.2.).
Дерево
состоит
из
вершин
,
соединенных
между
собой
ветвями
.
Вершины
дерева
называют
еще
позициями
игры
,
а
его
ветви
–
ходами
игрока
.
2
0
0
1
-11
2
5
4
+10
8
2
3
3
3
-7
2
2
0
0
-11
2
+10
8
2
3
3
-7
2
0
0
+12
2
-11
-9
2
3
3
8
2
0
0
+12
2
-11
-9
2
3
3
8
2
2
5
Г
(
Герб
)
1/2
5
2
5
V
1
0
0
Г
(
Герб
)
1/2
Р
(
Решка
)
1/2
Р
(
Решка
)
1/2
Рис
. 3.2
Основными
свойствами
дерева
игры
являются
:
*
дерево
содержит
одну
единственную
начальную
вершину
(“
корень
”
дерева
),
в
которую
не
входит
ни
одна
ветвь
;
*
дерево
имеет
не
менее
одной
вершины
,
из
которой
не
выходит
ни
одна
ветвь
.
Эти
вершины
называются
конечными
вершинами
;
*
из
корня
дерева
имеется
единственный
путь
к
каждой
из
остальных
вершин
дерева
.
Вершина
соответствует
определенному
состоянию
игры
перед
очередным
ходом
.
Каждую
вершину
занимает
только
один
игрок
,
и
ей
присваивается
номер
,
равный
номеру
игрока
,
который
делает
выбор
.
Вершины
,
соответствующие
случайным
ходам
,
обозначают
номером
0.
Ветви
,
выходящие
из
вершины
,
изображают
выборы
,
которые
могут
быть
сделаны
игроком
при
данном
ходе
.
Вероятности
выполнения
случайного
хода
записывают
у
соответствующих
ветвей
.
Возле
конечных
54
вершин
дерева
указываются
исходы
игры
–
значения
выигрыша
игроков
(
а
в
антагонистических
играх
–
выигрыш
первого
игрока
).
Партия
начинается
с
корня
(
нижней
вершины
).
Каждый
ход
есть
изменение
позиции
,
соответствующее
перемещению
из
одной
вершины
на
какую
-
нибудь
из
примыкающих
верхних
вершин
.
Число
ветвей
у
вершины
равно
числу
вариантов
хода
.
Партия
заканчивается
при
достижении
одной
из
конечных
вершин
.
Величина
называется
длиной
дерева
.
В
зависимости
от
выбора
игроков
возможно
столько
различных
партий
игры
,
сколько
конечных
вершин
у
дерева
.
Очевидно
,
если
в
игре
нет
случайных
ходов
,
и
каждый
из
игроков
выбрал
свою
стратегию
,
то
исход
игры
однозначно
определен
.
Для
игры
со
случайными
ходами
,
результат
партии
становится
случайной
величиной
,
поэтому
необходимо
случайные
выигрыши
заменить
их
математическими
ожиданиями
.
Как
совокупность
всех
решений
,
которые
должен
принять
игрок
,
можно
описать
как
одно
решение
–
выбор
стратегии
,
так
и
совокупность
случайных
ходов
,
может
быть
заменена
одним
случайным
испытанием
Н
.
В
рассматриваемом
примере
(
рис
. 3.2)
случайное
испытание
Н
может
иметь
следующие
исходы
:
Н
=|(
Г
,3),(
Г
,2),(
Р
,3),(
Р
,2)|,
с
вероятностями
;
4
1
;
4
1
;
4
1
;
4
1
P
,
где
Г
–
означает
выпадение
“
герба
”,
Р
– “
решки
”,
а
цифры
2, 3
соответствуют
случайному
выбору
на
четвертом
ходу
.
Игра
,
полученная
путем
усреднения
случайных
исходов
,
не
полностью
эквивалентна
исходной
игре
,
так
как
она
характеризует
не
частный
результат
отдельной
партии
,
а
средние
исходы
большого
числа
партий
.
Информация
,
доступная
игрокам
задается
информационным
разбиением
вершин
на
множества
V
i
,
называемые
классами
информации
или
информационными
множествами
.
Если
достигнута
вершина
v
V
i
,
то
игроку
,
который
должен
ходить
,
указывается
только
класс
информации
,
а
не
точное
положение
вершины
v
.
Таким
образом
,
в
классы
информации
могут
входить
несколько
вершин
,
неразличимых
игроком
,
делающим
выбор
на
данном
ходе
,
т
.
е
.
игрок
не
в
состоянии
различить
,
какой
из
нескольких
вершин
соответствует
состояние
игры
в
данный
момент
времени
.
В
рассматриваемом
примере
класс
информации
V
1
состоит
из
двух
вершин
.
В
том
случае
,
когда
всякий
класс
информации
содержит
только
одну
вершину
,
имеем
игру
с
полной
информацией
(
например
,
игра
в
шахматы
).
В
играх
с
неполной
информацией
содержится
хотя
бы
один
класс
информации
с
числом
вершин
не
менее
двух
.
При
вычерчивании
дерева
игры
классы
информации
обводят
замкнутой
линией
.
Игрок
всегда
знает
,
какому
классу
информации
соответствует
состояние
игры
в
данный
момент
,
но
не
знает
конкретной
вершины
этого
класса
.
55
Классы
информации
(
информационные
множества
)
должны
удовлетворять
следующим
условиям
:
1)
содержать
вершины
только
одного
игрока
;
2)
каждая
вершина
может
принадлежать
только
одному
классу
информации
;
3)
вершины
класса
информации
соответствуют
только
одному
временному
ходу
;
4)
из
всех
вершин
,
составляющих
класс
информации
,
может
выходить
только
одинаковое
количество
ветвей
.
Дерево
,
изображенное
на
рис
. 3.2,
соответствует
следующей
игре
.
Первый
игрок
выбирает
одно
из
двух
направлений
(“
налево
”
или
“
направо
”).
Ход
“
налево
”
оценивается
тремя
баллами
,
а
“
направо
” –
четырьмя
.
Затем
бросается
жребий
(
монета
)
и
,
если
выпадает
герб
,
второму
игроку
сообщается
предыдущий
выбор
первого
игрока
.
Если
выпадает
решка
,
то
второй
игрок
знает
лишь
,
что
он
находится
в
классе
информации
V
1
,
но
не
знает
,
в
какой
из
двух
вершин
этого
класса
он
находится
.
Второй
игрок
выбирает
одно
из
двух
направлений
(“
налево
”
или
“
направо
”).
Ход
“
налево
”
оценивается
пятью
баллами
,
а
“
направо
” –
двумя
.
Четвертый
ход
является
опять
случайным
и
состоит
в
выборе
с
равными
вероятностями
одного
из
направлений
: “
налево
”, “
направо
”,
которые
оцениваются
тремя
и
двумя
баллами
соответственно
.
Поскольку
вероятности
выбора
направления
при
случайном
ходе
одинаковы
(
равны
2
1
),
то
их
можно
на
графическом
изображении
дерева
игры
и
не
указывать
.
Числа
,
выбранные
в
первом
,
третьем
и
четвертом
ходах
,
складываются
,
и
полученная
сумма
уплачивается
вторым
игроком
первому
,
если
она
четная
,
в
противном
случае
первый
игрок
платит
второму
.
Пространства
Ф
1
и
Ф
2
всех
возможных
стратегий
игроков
1
и
2
в
рассматриваемом
примере
следующие
:
Ф
1
=|(3), (4)|;
Ф
2
=|(3,
Г
,5),(3,
Г
,2),(3,
Р
,5),(3,
Р
,2),(4,
Г
,5),(4,
Г
,2),(4,
Р
,5),(4,
Р
,2)|,
где
первое
число
каждой
стратегии
в
пространстве
Ф
2
соответствует
выбору
первого
игрока
,
второе
число
–
выпаданию
герба
или
решки
(“
Г
” –
выпал
“
герб
”; “
Р
” –
выпала
“
решка
”).
Третья
–
выбору
второго
игрока
пятерки
или
двойки
.
Очевидно
,
что
если
в
игре
нет
случайных
ходов
и
каждый
из
игроков
выбрал
свою
стратегию
,
то
исход
игры
однозначно
определен
.
Описание
позиционной
игры
в
виде
дерева
позволяет
глубже
проанализировать
ход
игры
.
Вместе
с
тем
,
оптимальное
поведение
игроков
легче
определить
для
игры
,
заданной
в
нормальной
форме
(
для
двух
игроков
–
в
матричной
форме
),
особенно
в
том
случае
,
если
игра
содержит
информационные
множества
и
случайные
ходы
.