Материал: Теория_игр_УП_ЭК_ЭлРесурс
56
3.3.
Решение
позиционной
игры
с
полной
информацией
Решение
позиционной
игры
с
полной
информацией
легко
решается
в
соответствии
с
теоремой
Куна
,
утверждающей
,
что
данная
игра
разрешима
по
доминированию
,
т
.
е
.
для
каждого
из
игроков
имеются
доминирующие
стратегии
,
которые
и
необходимо
применять
.
Для
того
,
чтобы
это
продемонстрировать
,
рассмотрим
описанную
выше
игру
«
Выборы
с
правом
вето
».
Поскольку
из
всех
вершин
,
предшествующих
конечным
,
ходит
игрок
3,
то
остальные
игроки
,
зная
его
функцию
выигрыша
U
3
,
могут
легко
предвидеть
его
решения
.
Это
позволяет
привести
игру
,
изображенную
на
рис
. 3.1,
к
следующей
схеме
:
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
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
Рис
. 3.3.
Поскольку
в
новом
дереве
игрок
3
уже
по
существу
не
принимает
решения
,
то
финальная
вершина
определяется
ходами
игрока
2.
Игрок
1,
зная
функцию
выигрышей
U
2
,
может
предвидеть
поведение
игрока
2.
В
итоге
получается
игра
с
одним
участником
–
первым
игроком
и
следующим
деревом
игры
:
2
2
2
2
3
3
3
3
3
3
3
1
4
4
4
4
4
4
3
3
3
3
3
3
3
2
2
2
2
2
2
1
1
1
1
1
1
Рис
. 3.4.
Поскольку
для
первого
игрока
желательна
победа
четвертого
претендента
,
то
он
отклонит
третьего
претендента
.
Далее
второй
игрок
вынужден
будет
отклонить
второго
претендента
,
а
третий
игрок
–
первого
.
Выигрыши
игроков
в
данной
игре
равны
7, 4
и
4
соответственно
.
Таким
образом
,
алгоритм
решения
позиционных
игр
с
полной
информацией
,
в
соответствии
с
теоремой
Куна
,
состоит
в
том
,
что
начиная
с
последнего
хода
последовательно
отбрасываются
заведомо
худшие
для
игрока
,
делающего
этот
ход
,
решения
.
После
всех
таких
редукций
получаем
решение
в
чистых
стратегиях
.
57
3.4.
Нормализация
позиционной
игры
Процесс
сведения
позиционной
игры
к
игре
в
нормальной
форме
называют
нормализацией
игры
.
Любая
позиционная
игра
может
быть
сведена
к
игре
в
нормальной
форме
,
в
которой
каждый
из
игроков
делает
только
по
одному
независимому
ходу
.
Для
нормализации
игры
нужно
перечислить
все
возможные
стратегии
игроков
и
для
каждой
совокупности
стратегий
определить
выигрыш
игроков
.
Рассмотрим
процесс
нормализации
позиционной
игры
на
конкретном
примере
.
Пусть
игра
задана
деревом
,
показанном
на
рис
. 3.5.
4
-2
-2
3
2
2
1
Рис
. 3.5.
Первый
игрок
делает
свой
первый
ход
,
выбирая
правую
или
левую
ветвь
.
Затем
ход
делает
второй
игрок
,
у
которого
в
каждой
вершине
также
имеется
два
выбора
,
после
чего
игра
заканчивается
.
В
данной
игре
у
первого
игрока
(
игрока
А
)
имеется
две
чистых
стратегии
:
Ф
1
=/
А
1
,
А
2
/,
где
стратегия
А
1
–
всегда
выбирать
левую
ветвь
;
стратегия
А
2
–
всегда
выбирать
правую
ветвь
.
Второй
игрок
(
игрок
В
)
имеет
больше
стратегий
:
Ф
2
=/
В
1
,
В
2
,
В
3
,
В
4
/,
где
стратегия
В
1
–
всегда
выбирать
левую
ветвь
;
стратегия
В
2
–
всегда
выбирать
правую
ветвь
;
стратегия
В
3
–
выбирать
ветвь
,
которую
выбрал
игрок
А
;
стратегия
В
4
–
выбирать
ветвь
,
противоположную
той
,
которую
выбрал
игрок
А
.
Матрица
игры
в
этом
случае
имеет
вид
:
B
j
A
i
B
1
B
2
B
3
B
4
A
1
4 -2 4 -2
A
2
-2 3 3 -2
Очевидно
,
что
исходная
позиционная
игра
является
игрой
с
полной
информацией
.
Следовательно
,
она
должна
иметь
седловую
точку
,
а
,
следовательно
,
решение
в
чистых
стратегиях
.
Действительно
,
так
как
max min
i
j
ij
a
2
;
min max
j
i
ij
a
2
,
и
,
следовательно
,
.
Поэтому
S
A
=||1,0||
или
S
A
=||0,1||,
а
S
B
=||0,0,0,1||.
Цена
игры
v
=-2.
Допустим
,
что
в
рассматриваемом
примере
второму
игроку
не
сообщается
выбор
,
сделанный
первым
игроком
.
Тогда
в
дереве
игры
на
втором
ходе
появляется
класс
информации
V
1
,
содержащей
две
вершины
58
второго
игрока
(
рис
. 3.6)
4
-2
-2
3
2
2
1
V
1
Рис
. 3.6.
Количество
чистых
стратегий
второго
игрока
по
сравнению
с
первым
случаем
сократится
до
двух
:
Ф
2
=/
В
1
,
В
2
/,
где
В
1
–
всегда
выбирать
левую
ветвь
;
В
2
–
всегда
выбирать
правую
ветвь
.
Процесс
нормализации
приводит
к
следующей
платежной
матрице
:
B
j
A
i
B
1
B
2
A
1
4 -2
A
2
-2 3
В
новой
игре
,
т
.
е
.
седловая
точка
отсутствует
.
Решение
игры
в
смешанных
стратегиях
имеет
вид
:
S
S
v
A
B
5
11
6
11
5
11
6
11
8
11
;
;
;
;
.
Уменьшение
информации
,
имеющейся
у
второго
игрока
на
момент
принятия
решения
,
привело
к
уменьшению
его
выигрыша
с
2
до
11
8
.
Итак
для
нормализации
позиционной
игры
необходимо
:
*
перечислить
все
возможные
стратегии
каждого
из
игроков
(
в
таких
играх
,
как
шахматы
,
это
пока
неразрешимая
задача
);
*
определить
исходы
игры
при
всех
возможных
сочетаниях
стратегий
игроков
(
выборы
стратегий
делаются
игроками
одновременно
и
независимо
).
В
зависимости
от
количества
игроков
,
а
также
значений
их
выигрышей
путем
нормализации
позиционные
игры
можно
свести
к
матричной
или
бескоалиционной
,
в
частности
,
биматричной
игре
,
каждые
из
которых
решаются
по
-
своему
.
ТЕСТЫ
(
В
–
Верно
,
Н
–
Неверно
)
1.
В
позиционных
играх
каждый
из
игроков
может
делать
по
несколько
ходов
,
причем
информация
о
прошедшем
может
меняться
от
хода
к
ходу
.
2.
Позиционные
игры
не
могут
включать
случайные
ходы
.
3.
Дерево
позиционной
игры
имеет
не
более
одного
корня
и
не
менее
одной
вершины
.
4.
Из
корня
дерева
позиционной
игры
к
какой
-
нибудь
его
вершине
могут
быть
несколько
путей
.
59
5.
Если
все
классы
информации
позиционной
игры
содержат
только
по
одной
вершине
,
то
такая
игра
является
игрой
с
неполной
информацией
.
6.
Классы
информации
должны
содержать
вершины
только
одного
игрока
.
7.
Вершины
класса
информации
могут
соответствовать
различным
временным
ходам
.
8.
Из
всех
вершин
,
составляющих
класс
информации
,
может
выходить
только
одинаковое
количество
ветвей
.
9.
Любая
позиционная
игра
может
быть
сведена
к
игре
в
нормальной
форме
.
10.
Игры
с
полной
информацией
имеют
седловую
точку
и
решаются
в
чистых
стратегиях
.
11.
Теорема
Куна
утверждает
,
что
позиционная
игра
с
полной
информацией
разрешима
по
доминированию
.
12.
Для
нормализации
позиционной
игры
необходимо
перечислить
все
возможные
стратегии
каждого
из
игроков
и
определить
все
возможные
исходы
игры
.
(
Ответы
:
1-
В
; 2-
Н
; 3-
В
; 4-
Н
; 5-
Н
; 6-
В
; 7-
Н
; 8-
В
; 9-
В
; 10-
В
; 11-
В
; 12-
В
).
ЗАДАЧИ
І
.
Произвести
нормализацию
позиционных
игр
,
у
которых
дерево
игры
имеет
вид
,
приведенный
ниже
.
У
конечных
вершин
поставлен
выигрыш
первого
игрока
,
а
выигрыш
второго
игрока
противоположен
по
знаку
.
Варианты
:
1.
5
2
-7
1
2
2
1
4
1
2
2.
4
5
5
1
2
2
1
60
3.
3
6
12
8
2
2
1
V
1
4.
3
4
1
2
2
2
1
4
2
2
V
1
2.
Нарисовать
дерево
следующей
позиционной
игры
«
Выбор
с
правом
вето
»,
у
которой
N
игроков
выбирают
одного
кандидата
из
множества
C
c c
c
i
1
2
, ,...,
,
i
N.
Правило
голосования
таково
:
начиная
с
игрока
1,
каждый
игрок
последовательно
налагает
вето
на
выбор
кандидатуры
одного
из
не
отведенных
кандидатов
.
Единственный
оставшийся
кандидат
считается
избранным
.
Заданы
также
функции
выигрыша
u
1
, u
2
, …, u
N
на
множестве
С
,
т
.
е
.
выигрыш
каждого
игрока
в
зависимости
от
того
,
какой
кандидат
победил
.
Найти
решение
,
используя
теорему
Куна
.
Варианты
:
1. N =2;
C
c c c
1
2
3
, ,
u
1
={2,-5,4}; u
2
={-2,5,-4}
2. N =2;
C
c c c c c
1
2
3
4
5
, , , ,
u
1
={2,5,-4,-3,1}; u
2
={-2-3,4,3,-1}
3. N =3;
C
c c c c
1
2
3
4
, , ,
u
1
={1,2,-3,4}; u
2
={3,2,1,-5}; u
3
={-2,-3,-1,8}.
4. N =4;
C
c c c c c
1
2
3
4
5
, , , ,
u
1
={1,2,-2,-3,4}; u
2
={3,5,1,-7,6}; u
3
={2,4,-5,-1,1}; u
4
={2,3,4,1,6}.